Анализ эффективности современных помехоустойчивых кодов. Код Голея

Сегодня в мире постоянно растут объемы информации во всех отраслях деятельности. Использование кода Голея в системах телеметрии обеспечивает получение, преобразование, передачу данных по каналу связи, прием, обработку и регистрацию измерительной информации и информации о событиях с целью дистанционного контроля состояния и функционирования контролируемых объектов. Тем не менее, не всегда есть возможность связать диспетчерский центр (ДЦ) с объектом контроля кабельным каналом, поскольку, как правило это требует значительных финансовых затрат. В этой связи, актуальной задачей является организация надежного радиоканала передачи данных. В настоящее время задача обеспечения достоверности передачи информации все чаще решается применением помехоустойчивого кодирования, которое представляет собой класс преобразований сигнала, выполняющихся для повышения качества связи. Работы таких ученых как Витерби А.Д., Берлекэмпа Э.Р., Хеминг Р.У., Боуз Р.Ч., Рэй Чоудхури Д.К., Хоквингем А.М., Голей М.Д., Род И.С., Соломон М., Нордстрем К.А., Робинсон Д.Н., Зубарев Ю.Б., Золотарев В.В., Овечкин Г.В. и многих других сформировали и развили теорию помехоустойчивого кодирования.. Однако проблема выбора вида кодирования для конкретного канала передачи информации пока не решена.
Исследование и разработку адаптивного каскадного кодера / декодера с исправлением ошибок для повышения достоверности передачи сообщений нерегулярной длины по цифровым радиоканалам связи систем телеметрии целесообразно производить в рамках повышенного интереса к применению кода Голея, совершенного кода, помогающего надежно кодировать и декодировать данные.
2. Код Голея: принципы кодирования и декодирования
Для повышения качества радиосвязи используется помехозащищенное кодирование, т.е. перед передачей в канал радиосвязи, информация кодируется, а на приемной стороне декодируется. Код Голея используется в таких радиостанциях, которые работают на низких радиочастотах и передают информацию друг другу за несколько тысяч километров. Помехой для таких радиостанций может служить обычная молния.
В основе кода лежит образующий полином 11-й степени. Длина кодовой комбинации 23 символа: информационной части 12 символов и проверочной части 11символов. Такой код без труда обнаруживает и исправляет до трех ошибок включительно.
Чтобы лучше разобраться в принципе работы кода Голея, рассмотрим пример кодирования и декодирования при помощи образующего полинома не 11-й степени, а 3-й:
P (x) = x3 + x + 1, что соответствует вектору коэффициентов {1011}.
К примеру, и нформационная последовательность имеет вид 1100, тогда полином Q(x) имеет вид Q (x) = X3+X2. Умножим Q (x) на X3(т.к степень образующего полинома 3-я) и в результате получим Q (x) * X3 = X6 + X5.
Вектор коэффициентов этого полинома имеет вид {1100000}. Разделим
произведение Q (x) * X3 на образующий полином {1011}. Деление полиномов происходит по mod(2). В результате деления имеем остаток 010.
Формируем разрешенную кодовую комбинацию из 7 символов и имеем 4 информационных, и 3 проверочных. Передаем в канал связи.
Декодирование можно производить двумя методами.
No1. По таблице соответствий, для этого строим проверочную матрицу путем сдвига вектора коэффициентов 001 и сложением с образующим полиномом 1011. В правом углу пример принятой кодовой комбинации с ошибкой. С помощью проверочной матрицы, мы можем эту ошибку
обнаружить и исправить.
Метод No2. «Метод ловли ошибки». Этот метод не требует построения проверочной матрицы, а всё гораздо проще. Введем новое понятие:
Вес полинома – количество единичных бит. 1) Делим кодовое слово на
P(x) = X3+X+1
Если вес остатка равен нулю – ошибки не произошло;
Если вес равен 1 – значит ошибка произошла в проверочных 3 битах кодового слова.
2) Делаем циклический сдвиг кодового слова в сторону младших разрядов и начинаем с первого шага. Когда на очередном этапе ошибка будет найдена, необходимо кодовое слово сдвинуть в обратную сторону, на соответствующее количество бит.
Алгоритм «методом ловли ошибок» является на порядок эффективней по скорости выполнения, а достоверность остаётся на прежнем уровне.
В дальнейшем при разработке программы - декодирование бинарной последовательности закодированной кодом Голея целесообразно использовать рассмотренный алгоритм.
Код Голея - совершенный двоичный код (23, 12, 7) с t = 3

. Поскольку он относится к линейным и двоичным, процедура кодирования и декодирования аналогична коду Хэмминга. Образующий полином g(p) = p11 + p10 + p6 + p5 + p4 + p2 +1.
Считается, что для кодирования и декодирования удобнее пользоваться матрицами, а вектор ошибки определять по синдрому с помощью заранее заготовленной таблицы [1 – 3, 9 – 11]. Если к коду Голея добавить проверку на четность то получится расширенный код Голея. Он является самодуальным, т.е., для него проверочная и порождающая матрицы равны.
3. Код Голея: достоинства и недостатки
Основными преимуществами кода Голея являются следующие:
-min значности и простота построения;
-наличие резерва;
-разрабатывается на длительный период времени;
- в каждой отдельной номенклатуре имеет одинаковую значность;
- дублирует уже сложившиеся обозначения;
- учитывает специфику программных и технических средств;
- помехозащищенность.
Код Голея, очевидно, не способен кодировать большой объем данных в одном кодовом слове. Двенадцать битов - это максимально допустимое значение для 23- или 24-битного кодового слова. Так в чем его польза? Одно из преимуществ исправления ошибок - устранение повторных попыток обмена данными, которые могут затормозить шумный канал. В некоторых случаях издержки, связанные с запросом повторной отправки, намного превышают длину пакета данных. Например, чтобы отправить пакет данных в полудуплексной или симплексной радиосистеме, микропроцессор должен включить передатчик и подождать, пока он достигнет полной мощности, обычно до 100 мс. Исходящая станция должна подвергаться той же задержке перед передачей при повторной отправке своих данных. Даже если все пойдет хорошо, в запросе на повторную отправку будет затрачено 200 мс времени. При скорости 1200 бит в секунду 200 мс представляют 240 бит данных, что является разумной длиной сообщения в некоторых системах. И если радиоканал занят другим трафиком, задержки могут быть больше. Код Голея может уменьшить количество событий повторной передачи, позволяя принимающей стороне исправить некоторые ошибки в принятых данных, уменьшая вероятность того, что канал будет перегружен.
В других ситуациях может быть невозможен повторный запрос, скажем, с односторонним радиочастотным, инфракрасным или ультразвуковым каналом передачи данных. Код Голея позволяет таким системам увеличивать вероятность одностороннего безошибочного приема. Некоторые каналы связи более подвержены ошибкам пакета, чем другие, где много последовательных битов данных повреждены. Код Голея не способен исправлять пакеты ошибок длиной более трех бит в одном кодовом слове. Однако, будучи дополнен техникой, называемой чередованием битов, небольшой модульный формат кода Голея позволяет исправлять большие пакетные ошибки, как мы увидим позже. Немодифицированный код Голея действительно заметен в приложениях, склонных к случайным битовым ошибкам, и он допускает повторные (3-битные ошибки) / (24 бита на кодовое слово) = 12,5% ошибок по битам без повторных передач данных. Конечно, недостатком расширенного кода Голея является то, что вы должны передавать столько битов проверки, сколько битов данных. Почему бы просто не отправить данные дважды, без проверочных битов? Ответ в том, что в такой системе исправление ошибок невозможно. Как бы вы узнали, какие из двух разных сообщений, если не оба, были повреждены? Код Голея позволяет исправлять ошибки в обмен на цену удвоения данных.
4. Реализация - исправление ошибок Исправление ошибок при помощи кода Голея не так тривиально. Он опирается на циклические свойства кодовых слов в схеме, называемой систематическим поисковым декодированием. Существуют и другие методы исправления ошибок кодом Голея, перечисленные в ссылках, но этот метод легко реализовать в программном обеспечении. Это «декодер ближайшего соседа», поскольку он определяет, какое кодовое слово является наиболее близким с точки зрения расстояния. Вот эскиз алгоритма систематического поиска.1