Циклические коды. 
Общая теория связи

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

Многие важнейшие помехоустойчивые коды систем связи, ;

в частности циклические, основаны на структурах конечных Арифметика полей Галуа. Полем называется множество элементов, которые конечного поля можно «складывать», «вычитать», «умножать» и «делить». На- _^алУ^а

звания операций взяты в кавычки, потому что они не всегда являются общепринятыми арифметическими операциями. В поле всегда имеется нулевой элемент (0), или нуль, и единичный элемент (1), или единица. Если число q элементов поля ограничено, то поле называется конечным полем, или конечным полем Галуа, и обозначается GF (q)_y где q — порядок поля. Наименьшим полем Галуа является двухэлементное иоле GF (2), состоящее всего из двух элементов 1 и 0. Для того чтобы.

¹ Эварист Галуа (Evariste Galois, 1811 — 1832) — французский математик, заложил основы современной алгебры.

выполнение операций над элементами GF (2) не приводило к выходу за пределы этого поля, они осуществляются по модулю 2 (вообще это определяется порядком поля для простых полей Галуа).

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

Для операций сложения и умножения выполняются обычные математические правила ассоциативности — а + (Ь + с) = (а + Ь) + с, коммутативности — а + b = b + а и а • b = b • а и дистрибутивности — а • (Ь + с) = а • b + а • с.

Для каждого элемента поля а должны существовать обратный элемент по сложению (-а) и, если а не равно нулю, обратный элемент по умножению (й ').

Поле должно содержать аддитивную единицу — элемент 0, такой, что а + 0 = а для любого элемента поля а.

Поле должно содержать мультипликативную единицу — элемент 1, такой, что аЛ = а для любого элемента поля а.

Например, существуют поля вещественных чисел, рациональных чисел, комплексных чисел. Эти поля содержат бесконечное число элементов.

Фактически все наборы, образованные циклической перестановкой кодовой комбинации, также являются кодовыми комбинациями. Так, например, циклические перестановки комбинации 1 000 101 будут также кодовыми комбинациями 1 011, 10 110, 101 100 и т. д. Это свойство позволяет в значительной степени упростить кодирующее и декодирующее устройства, особенно при обнаружении ошибок и исправлении одиночной ошибки. Внимание к циклическим кодам обусловлено тем, что присущие им высокие корректирующие свойства реализуют на основе сравнительно простых алгебраических методов. В то же время для декодирования произвольного линейного блокового кода чаще применяют табличные методы, требующие большой объем памяти декодера.

Циклическим кодом называется линейный блоковый (п, k) —код, который характеризуется свойством цикличности, т. е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду, и у которого множество кодовых слов представляется совокупностью многочленов степени (п — 1) и менее, делящихся на порождающий многочлен g (x) степени r=n-k_y являющийся сомножителем двучлена х^п+

В циклическом коде кодовые слова представляют многочленами (полиномами)

где п — длина кода; A_i — коэффициенты поля Галуа (значений кодовой комбинации).

Например, для кодовой комбинации 101 101 полиномиальная запись имеет вид.

Примерами циклических кодов являются коды с четной проверкой, коды с повторениями, коды Хемминга, PC-коды и турбокоды.

Код Хемминга. Возможности исправления ошибок в коде Хемминга связаны с минимальным кодовым расстоянием d₀. Исправляются все ошибки кратности q = cnt(d₀ — l)/2 (здесь cnt означает «целая часть») и обнаруживаются ошибки кратности d₀- 1. Так, при контроле на нечетность d_Q= 2 и обнаруживаются одиночные ошибки. В коде Хемминга d₀= 3. Дополнительно к информационным разрядам вводится L = log₂Q избыточных контролирующих разрядов, где Q — число информационных разрядов. Параметр L округляется до ближайшего большего целого значения. L-разрядный контролирующий код есть инвертированный результат поразрядного сложения (сложения по модулю 2) номеров тех информационных разрядов, значения которых равны единице.

Пример 7.7.

Пусть имеем основной код 100 110, т. е. Q = 6. Определим дополнительный код.

Решение

Находим, что L = 3 и дополнительный код равен.

где П — символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь с основным кодом будет передан и дополнительный. В приемнике вновь рассчитывают дополнительный код и сравнивают с переданным. Фиксируется код сравнения, и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100 010, го рассчитанный дополнительный код равен инверсии от 010Ш10 = 100, т. е. 011, что означает ошибку в 3-м разряде.

Обобщением кодов Хемминга являются циклические коды БЧХ, которые позволяют корректировать многократные ошибки в принятой кодовой комбинации.

Коды Рида — Соломона базируются на полях Галуа, или конечных нолях. Арифметические действия сложение, вычитание, умножение, деление и г. д. над элементами конечного ноля дают результат, который также является элементом этого ноля. Кодировщик или декодер Рида — Соломона должен обязательно выполнять эти операции. Все операции для реализации кода требуют специального оборудования или специализированного программного обеспечения.

Турбокоды. Избыточные коды могут применяться как самостоятельно, так и в виде некоторого объединения нескольких кодов, когда наборы символов одного избыточного кода рассматриваются как элементарные информационные символы другого избыточного кода. Такое объединение стали называть каскадным кодом. Огромным достоинством каскадных кодов является то, что их применение позволяет упростить кодер и особенно декодер по сравнению с аналогичными устройствами некаскадных кодов той же длины и избыточности. Каскадное кодирование привело к созданию турбокодов. Турбокодом называют параллельную структуру сигнала, состоящую из двух или большего числа систематических кодов. Основной принцип их построения — использование нескольких параллельно работающих компонентных кодеров. В качестве компонентных можно использовать как блочные, так и сверточные коды, коды Хемминга, PC-код, БЧХ и др. Использование перфорации (выкалывания) позволяет увеличить относительную скорость турбокода, адаптировав его исправляющую способность к статистическим характеристикам канала связи. Принцип формирования турбокода состоит в следующем: входной сигнал х, состоящий из К бит, подается параллельно на N перемежителей. Каждый из последних представляет собой устройство, осуществляющее перестановку элементов в блоке из К бит в псевдослучайном порядке. Выходной сигнал с перемежителей — символы с измененным порядком следования — поступает на соответствующие элементарные кодеры. Двоичные последовательности х_р i = 1,2,…, JV, на выходе кодера представляют собой проверочные символы, которые вместе с информационными битами составляют единое кодовое слово. Применение перемежителя позволяет предотвратить появление последовательностей коррелированных ошибок при декодировании турбокодов, что немаловажно при использовании традиционного в обработке рекурентного способа декодирования. В зависимости от выбора компонентного кода турбокоды делятся на сверточные турбокоды и блоковые коды-произведения.