Анализ алгоритмов декодирования стандарта радиосвязи mil-std-188-141b

четности/нечетности колебания и электрической толщины образца. При толщине, кратной целому числу полуволн, и узлах электрического поля на поверхностях диэлектрического образца относительный запас электрической энергии в образце К1Е =

принимает минимальное значение, что соответствует максимуму резонансной частоты при симметричном положении образца. Здесь - электрическая энергия в образце, ^^ - полная энергия резонатора. При пучностях электрического поля на поверхностях образца Ке принимает максимальное значение, что

соответствует минимуму резонансной частоты при симметричном положении образца. Системы (1), (2) позволяют проводить измерения параметров смещенного образца, при этом неизвестными величинами являются диэлектрическая проницаемость а и смещение образца А или стенок 5. Для их нахожде-

ния необходимо не мене двух уравнений, т.е. измерений на двух и более резонансных частотах.

Заключение. Представление резонатора со сферическими зеркалами и смещенным от плоскости симметрии образцом как двух полусферических резонаторов различной длины с плоской «электрической» или «магнитной» стенками и одинаковой резонансной частотой позволяет рассчитать смещение резонансных частот при смещении образца от плоскости симметрии. Вид экстремума в зависимости резонансной частоты от смещения образца относительно центра резонатора в общем случае зависит от четности/нечетности колебания и электрической толщины образца. Направление изменения резонансной частоты колебания при смещении диэлектрического образца от центра противоположно направлению изменения относительной доли электрической энергии в образце.

Статья поступила 11.11.2014 г.

Библиографический список

1. Yu P.K., Cullen A.L. Measurement of permittivity by means of an open resonator. 1. Theoretical // Proc. Roy. Soc. Lond.: 1982. V. A. P. 49-71.

2. Toraldo Di Francia G., Checcacci P.F., Scheggi A.M. Research on open resonators. Part I: Theory of Flat roof Resonators. Part II: experimental Tests of Microwave Models of Optical Resonators // Defense technical Information Center, Florence Univ., Italy. 1965.

3. Jones R.G. «Precise dielectric measurements at 35 GHz using an open microwave resonator» // Proc. Inst. Elec. Eng. 1976. Vol. 123. P. 285-290.

4. Егоров В.Н. Резонансные методы исследования диэлектриков на СВЧ // ПТЭ. 2007. № 2. С. 5-38.

5. Нонг Куок Куанг. Измерение свойств диэлектриков в открытом резонаторе на частотах от 95 до 176 ГГц // Вестник ИрГТУ. 2013. № 3. С. 95-99.

УДК 621.39

АНАЛИЗ АЛГОРИТМОВ ДЕКОДИРОВАНИЯ СТАНДАРТА РАДИОСВЯЗИ MIL-STD-188-141B

ij о

© О.В. Кузьмин1, А.А. Тимошенко2

Иркутский государственный университет, 664003, Россия, г. Иркутск, б. Гагарина, 20.

Рассмотрена система автоматической установки связи «ALE» (Automatic Link Establishment), которая лежит в основе стандарта радиосвязи MIL-STD-188-141B. Основное назначение системы - организация сетей передачи данных в КВ-диапазоне, основанной на использовании низкоскоростных цифровых модемов. Описан протокол организации системы связи и передачи данных. Проанализированы временные параметры работы алгоритмов декодирования помехоустойчивого кода Голея. Авторами предложен более эффективный по характеристикам алгоритм, устраняющий временные задержки и позволяющий работать в режиме реального времени. Ключевые слова: стандарт радиосвязи; протокол организации системы связи; коротковолновый диапазон; алгоритм декодирования; помехоустойчивый код Голея.

ANALYSIS OF DECODING ALGORITHMS OF MIL-STD-188-141B RADIO COMMUNICATION STANDARD O.V. Kuzmin, A.A. Timoshenko

Irkutsk State University,

20 Gagarin Blvd., Irkutsk, 664003, Russia.

The paper deals with the system of automatic communication installation of «ALE» (Automatic Link Establishment), which is the cornerstone of MIL-STD-188-141B radio communication standard. The system is mainly designed for the organization of networks of data transmission in HF band based on the use of low-speed digital modems. The protocol of communication system organization and data transmission is described. Temporary operation parameters of noise-

1 Кузьмин Олег Викторович, доктор физико-математических наук, профессор, зав. кафедрой теории вероятностей и дискретной математики, тел.: (3952) 242214, e-mail: quzminov@mail.ru

Kuzmin Oleg, Doctor of Physical and Mathematical sciences, Professor, Head of the Department of Probability Theory and Discrete Mathematics, tel.: (3952) 242214, e-mail: quzminov@mail.ru

2Тимошенко Антон Александрович, магистрант, тел.: (3952) 650946, e-mail: irkrodogosh@yandex.ru Timoshenko Anton, Master's Degree Student, tel.: (3952) 650946, e-mail: irk-isu@yandex.ru

immune Golay code decoding algorithms are analyzed. The authors introduce a more efficient algorithm that eliminates time delays and enables real time operation.

Keywords: standard of radio communication; protocol of communication system organization; short-wave band; algorithm of decoding; noise-immune Golay code.

В настоящее время, в связи с многократно возросшими объемами передаваемой и сохраняемой информации, ужесточились требования к ее достоверности. Одним из самых перспективных методов решения этой проблемы является помехоустойчивое кодирование на основе корректирующих кодов. Сегодня коды, исправляющие ошибки, нашли применение во многих системах передачи и хранения информации. Самые известные из них - сотовая, спутниковая, радиосвязь в коротковолновом диапазоне и др. В системах с помехозащищенной обработкой информации используются наиболее простые и эффективные циклические корректирующие коды, которые, наряду с простотой кодирования и декодирования, отличаются достаточно большой корректирующей способностью [1-4].

Система автоматической установки связи «ALE» (Automatic Link Establishment), которая лежит в основе стандарта MIL-STD-188-141B, разработана для использования в полосе стандартной аппаратуры. Она

позволяет обеспечить устойчивую связь в условиях сложной помехоустойчивой обстановки, а также подключать созданные на ее основе локальные радиосети к сетям общего пользования.

Протокол организации связи и передачи данных. Для установки связи используется 8-позиционная радиопередача с частотно временным распределением сигнала (табл. 1). Одновременно передается одна частота, каждая соответствует коду из трех бит. Скорость передачи 375 бит/сек.

По протоколу организации, в системе связи «ALE», передаваемое слово содержит 24 информационных бита, старший бит слева. Структура слова содержит 4 части: 3-битовую преамбулу и три 7-битных символа (табл. 2).

Первые 3 бита из 24 определяют значения преамбулы P1—P3 (табл. 3). Преамбула используется для идентификации одного из восьми возможных форматов слова.

Частотно временное распределение сигнала

Таблица 1

Частота

2500 Гц

2250 Гц

2000 Гц

1750 Гц

1500 Гц

1250 Гц

1000 Гц

750 Гц

Биты данных

1 0 0

1 0 1

1 1 1

1 1 0

0 1 0

0 1 1

0 0 1

0 0 0

Период излучения частоты

8

8

8

8

8

8

8

8

Таблица 2

Структура слова_

Стандартное слово «ALE» 24 бита

Преамбула Символ 1 Символ 2 Символ 3

3 бита 7 бит 7 бит 7 бит

P1 P2 РЗ C1 C1 C1 C1 C1 C1 C1 C2 C2 C2 C2 C2 C2 C2 C3 C3 C3 C3 C3 C3 C3

12 Бит 12 Бит

Применяется кодер Голея Применяется кодер Голея

Таблица 3

Типы слов и соответствующие им значения преамбул_

Тип слова Комбинация бит Функция Значение

THRU 0 0 1 Множественная и косвенная адресация Адресат в групповом вызове.

To 0 1 0 Непосредственная адресация Адресат для индивидуальных и сетевых вызовов.

COMMAND 1 1 0 Служебное слово Для организации контроля, отслеживания статуса и выполнения специальных функций.

FROM 1 0 0 Идентификация Идентифицирует текущий передатчик без прерывания сеанса.

THIS IS 1 0 1 Прерывание, идентификация и возобновление Прерывает сеанс, идентифицирует текущий передатчик и возобновляет работу.

THIS WAS 0 1 1 Прерывание, идентификация и завершение Прерывает сеанс, идентифицирует текущий передатчик и завершает работу.

DATA 0 0 0 Данные Данные, определяемые предыдущим словом.

REPEAT 1 1 1 Дубликат и информация Означает продолжение действия предыдущей преамбулы с новым полем данных или другой информацией.

Помехоустойчивое кодирование. Перед передачей в канал радиосвязи слово делится на две 12-битные части, к которым применяется помехоустойчивый код Голея [1]. Он определяет, как этим 12 битам сопоставить кодовое слово в 23 бита. Такое преобразование вносит избыточность в информацию, но зато позволяет восстановить исходное информационное слово, даже если в кодовое слово внести 3 ошибки. Предположим, имеется 12 бит полезной информации. Кодируем их кодом Голея и передаем в канал 23 бита. В канале возникли ошибки, и несколько (1, 2 или 3) бит передались неправильно. В итоге на приемной стороне имеем 23 бита с ошибками. Но, поскольку известно, что они закодированы кодом Голея, то можно точно восстановить 12 бит полезной информации, даже если 3 любых бита из 23 ошибочные. На рис. 1 представлена иллюстрация сказанного.

Метод кодирования. Данный метод основан на использовании производящей матрицы С(х). Матрицу С(х) можно представить двумя подматрицами: информационной - Е(х) и проверочной - С(х). Информационная подматрица имеет k столбцов (т.е. матрица размером кхк), а проверочная - п столбцов. Установлено, что в качестве информационной под матрицы удобно брать единичную матрицу. Количество информационных разрядов к кода Голея равно 12, следовательно, размерность информационной подматрицы

E(x) = 2х12. Она имеет вид:

000000000001 000000000010 000000000100 000000001000 000000010000 000000100000 000001000000 000010000000 000100000000 001000000000 010000000000 100000000000

Для построения проверочной подматрицы С(х) выбираем комбинацию из 23 бит, содержащую только одну единицу - 00000000000100000000000, и делим ее на образующий полином кода Голея: д(х) = х11 + х10 + х6 + х5 + х4 + х2 + 1 (101011100011); получаем остаток R(x), который в результате и есть строка проверочной подматрицы:

Канал передачи

Полезная 12 бит w Кодер 23 бита г

информация w Голея 1

Декодер 12 бит w

Голея w

Полезная информация

ошибки

Рис. 1. Организация передачи данных

Аналогичным образом, сдвигая каждый раз единицу в следующий разряд информационной комбинации, получаем последующие строки проверочной подматрицы С(х). Таким образом, проверочная подматрица имеет вид:

01011100011 10111000110 00101101111 01011011110 10110111100 00110011011 01100110110 11001101100 11000111011 1 1010010101 11111001001 10101110001

с,

Полученная подматрица С11, 12 приписывается справа к единичной подматрице Е12, 12, в результате чего получается производящая матрица:

01011100011000000000001 10111000110000000000010 00101101111000000000100 01011011110000000001000 10110111100000000010000 00110011011000000100000 01100110110000001000000 11001101100000010000000 11000111011000100000000 11010010101001000000000 11111001001010000000000 10101110001100000000000

В коде Голея процесс кодирования сводится к умножению информационных посылок, представленных в виде векторов A12(x), на соответствующую производящую матрицу:

B23(X) = ^2(^23, 12.

Алгоритмы декодирования

Алгоритм 1

Шаг 1. Строим проверочную матрицу H(x). На рис. 2 показано образование этой матрицы, которая производится путем замены строк производящей матрицы на столбцы.

В результате проверочная матрица имеет вид:

Рис. 2. Процесс образования проверочной матрицы Нп,г

'23,11

01001001111110000000000 10010011111001000000000 01101110001100100000000 11011100011000010000000 11110001001100001000000 Н,,„ = 10101011100100000100000 00011110110100000010000 00111101101000000001000 01111011010000000000100 11110110100000000000010 10100100111100000000001

Шаг 2. На стороне получателя сообщений, принятую возможно искаженную в канале, кодовую комбинацию B'23(x) умножаем, по модулю два, на проверочную матрицу Н(х).

Шаг 3. При умножении B'23(x) на Н2311 у нас остаЕтся 11-битный остаток Щх). Если в остатке все биты нулевые, то комбинация передана без ошибок. Если есть единичные биты, то ищем подобную комбинацию единичных бит в строках проверочной матрицы. Номер строки указывает на номер искаженного бита в принятой кодовой комбинации.

Шаг 4. В принятой кодовой комбинации исправляем искаженный бит.

Шаг 5. Завершение алгоритма.

Метод ловли ошибок. Прямой алгоритм декодирования по таблице соответствий, который лежит в основе рассмотренного выше стандарта радиосвязи М!1_-8ТО-188-141В, - очень ресурсоемкий процесс и занимает много времени, поэтому рассмотрим алгоритм декодирования «методом ловли ошибок». Введем еще некоторые понятия [2]. Синдром - остаток от деления кодового слова на д(х). Вес полинома - количество единичных бит. На рис. 3 представлена структура кодового слова, используемая в алгоритме 2 [3].

Алгоритм 2

Шаг 1. Делим кодовое слово на д(х), т.е. находим синдром («нормальный»). Если вес синдрома равен нулю (т.е. д(х) делит кодовое слово без остатка), это означает, что в кодовом слове нет ошибок. Если вес синдрома 1, 2 или 3, все (1, 2 или 3) ошибки содержатся в младших 11 битах кодового слова. Причем, единичные биты в синдроме соответствуют ошибочным битам в кодовом слове. При весе больше 3 переходим к шагу 2.

Шаг 2. Если в 18 бите ошибка, а остальные (0, 1 или 2) ошибки в младших 11 битах, то находим модифицированный синдром. Для этого складываем «нор-

мальный» синдром с остатком от деления х на д(х). Остаток заранее посчитан - это 11011001100 (старшие биты слева). Операция сложения эквивалентна побитовой операции хог (исключающей или). Если вес модифицированного синдрома равен 0, 1 или 2, - в 18 бите ошибка, а все остальные ошибки в младших 11 битах. Причем, единичные биты в модифицированном синдроме соответствуют ошибочным битам в кодовом слове. Если вес больше 3, то переходим к шагу 3.

Шаг 3. Если в 17 бите ошибка, а остальные (0, 1 или 2) ошибки в младших 11 битах, то находим модифицированный синдром. Складываем «нормальный» синдром с остатком от деления х16 на д(х). Остаток от деления - 01101100110 (старшие биты слева). Если вес модифицированного синдрома равен 0, 1 или 2, -в 17 бите ошибка, а все остальные ошибки в младших 11 битах. Если вес больше 3, переходим к шагу 4.

Шаг 4. Делаем циклический сдвиг кодового слова в сторону младших разрядов и начинаем с 1 шага.

Шаг 5. Если на очередном этапе ошибки найдены, исправляем искаженные биты, кодовое слово циклически сдвигаем в обратную сторону на соответствующее количество бит.

Шаг 6. Завершение алгоритма. Пример декодирования

Пусть 10010011100111110001101 - кодовое слово с ошибкой (23 бита);

д(х) = х11+х10+х6+х5+х4 +х2 +1 (110001110101) -образующий полином. Шаг 1.

Найдем синдром: Делим 10010011100111110001101 на 110001110101 10010011100111110001101 частное (столбец ниже) +110001110101 =0101010011001 000000000001 +110001110101 =0110111011001 +110001110101 =0001101011001 0011010110011 0110101100110 +110001110101 =0001000100110 0010001001100 0100010011001 +110001110101 =0100111011001 +110001110101 =0101101011000 +110001110101 =0111001011011 +110001110101 =001000101110 111001001111

000000000011

000000000111 000000001110 000000011100

000000111001 000001110010 000011100100

000111001001

001110010011

011100100111

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

5 бит 18 и 17 w .биты w J 5 бит > < 11 бит —

Номер бита

Рис. 3. Структура кодового слова

01000101110 - синдром - остаток от деления. Шаг 2.

01000101110 - синдром + 11011001100 - остаток от деления хЛ17 на д(х) = 10011100010 - синдром-17. Шаг 3. 01000101110 - синдром + 01101100110 - остаток от деления хЛ16 на д(х) = 00101001000 - синдром-16, итого:

синдром вес 001000101110 5 синдром 000101001000 3 синдром-16 010011100010 5 синдром-17. Шаг 4.

Ошибки не найдены, выполняем сдвиг. 10010011100111110001101 - старое кодовое слово, 11001001110011111000110 - новое кодовое слово, полученное циклическим сдвигом. Шаг 1.

01000101110 - старый синдром, 00100010111 - новый синдром. Шаг 2. 00100010111 - синдром + 01101100110 - остаток от деления хЛ16 на д(х) = 01001110001 - синдром-16. Шаг 3. 00100010111 - синдром + 11011001100 - остаток от деления хЛ17 на д(х) = 11111011011 - синдром-17, итого:

синдром вес 000100010111 5 синдром 001001110001 5 синдром-16 011111011011 9 синдром-17. Шаг 4.

Ошибки не найдены, выполняем следующий сдвиг, и так далее, пока вес синдрома не будет менее 3.

На 6-циклическом сдвиге получаем: вес синдрома-16 меньше либо равен 2, следовательно, в 17 разряде (хЛ16) ошибка, а остальные ошибки в младших 11 разрядах.

Шаг 5.

Исправляем ошибки: 01101100100111001111100 - кодовое слово + 10000000100 синдром-16

+ 00000010000000000000000 - ошибка в 17 разряде = 01101110100101001111000 - кодовое слово без ошибок.

Для получения исходного кодового слова выполняем обратный циклический сдвиг.

Шаг 6.

11010010100111100001101 - результат декодирования - кодовое слово без ошибок.

Время выполнения алгоритмов. Для тестирования и определения времени выполнения рассмотренных алгоритмов декодирования была написана специальная программа. Она определяет системное время вначале, а затем и после выполнения кода. По результатам определения времени вычисляется время выполнения алгоритма. Для более точной оценки быстродействия код выполняется несколько сотен раз, затем определяется среднее значение. Проанализировав результаты программы, мы пришли к выводу, что алгоритм 2 является на порядок эффективней по скорости выполнения алгоритма 1, а достоверность остается на прежнем уровне. Таким образом, предложенный алгоритм справляется с поставленной задачей: обработкой полученной информации в режиме реального времени.

Статья поступила 30.01.2015 г.

Библиографический список

1. Никитин Г.И. Помехоустойчивые циклические коды: учеб. пособие. СПб.: ГУАП, 2003. 15 с.

2. Кузьмин О.В., Дружинин В.И. Коды Боуза-Чоудхури-Хоквингема в системах обнаружения и исправления ошибок при передаче данных // Современные технологии. Системный анализ. Моделирование. 2013. № 3 (39). С. 23-29.

3. Джураев Р.Х., Джаббаров Ш.Ю., Умирзаков Б.М., Хамраев

3.А. Помехоустойчивые коды в телекоммуникационных системах: учеб. пособие. Ташкент: Изд-во ТУИТ, 2008. 44 с.

4. Johnson E., Kenney T., Chamberlain M. and others. U.S. MIL-STD-188-141B Appendix C-A: Unified 3rd Generation HF Messaging Protocol: Harris Corporation, RF Communications Division, 1998. 78 p.