Циклические коды

Циклические коды

Циклический код имеет образующую матрицу G, все строки которой  получены  циклическим сдвигом одной строки – слова, соответствующего образующему  многочлену. Дан пример образующей матрицы с многочленом    g(x)=x³+x¹+x⁰ .

Циклический сдвиг  n - разрядного слова на один разряд  означает умножение многочлена А(х), соответствующего этому слову,  на «х» с операцией «приведения» по модулю хⁿ+1, если 1 выходит при сдвиге за разрядную сетку:     

A(x)x - xⁿ +1 = A(x)x +xⁿ+1

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

Следовательно, если многочлен (xⁿ+1)  делится на  g(x), то и любое разрешенное слово делится на образующий многочлен.

Формирование и проверка слова циклического кода

1.  Информационное к - разрядное слово U(x) умножаем на  x^n-k, т.е. приписываем  к слову (n-k) нулей со стороны младшего разряда.

Рекомендуемые материалы

2. Слово  U(x)x^n-k делим на порождающий многочлен  g(x), в результате получаем многочлен Q(x) и остаток  r(x).Следовательно, U(x) x^n-k  = g(x)Q(x) + r(x), или

U(x) x^n-k  + r(x) =g(x)Q(x).     (1)

3.  Формируем слово циклического кода V(x), приписывая остаток r(x) к слову U(x) со стороны младших разрядов. Из (1) следует, что многочлен кода V(x)   делится на  g(x)   без остатка.

4.  Для обнаружения ошибки в принятом слове его делят на порождающий многочлен.

Ненулевой остаток при делении слова V(x) на многочлен   g(x) – признак ошибки. Нулевой остаток не гарантирует отсутствия ошибки, т.к. любой помехоустойчивый код выявляет только ошибки определенного типа. 

Большинство применяемых на практике блоковых кодов – циклические. Разные классы циклических кодов разработаны для обнаружения и исправления ошибок определенного типа. Корректирующая способность кода зависит от образующего многочлена.

Коды Хемминга исправляют одиночную ошибку.

Коды Боуза-Чоудхури-Хоквингема (БЧХ) исправляют множественные ошибки. Их параметры n, k, s (s - кратность исправляемой ошибки) выбираются в широком диапазоне. Например, (255, 187, 9), (127, 8, 31), (63, 39, 4).

Коды Голея исправляют ошибки кратности выше 1.

Коды Рида-Соломона (не двоичные) способны исправлять несколько  пакетов ошибок.

Коды Бартона, Файра предназначены для исправления одиночного пакета ошибок определенной длины.

Кодирование и декодирование циклических кодов

Рекомендуем посмотреть лекцию "10 Подсудность гражданских дел".

Формирование и обработка циклических кодов сводится к делению многочленов, выполняемому с использованием сдвиговых регистров с обратными связями. При делении делитель – порождающий многочлен вычитается сначала из делимого, затем из остатков. Процесс деления, при формировании слова циклического кода  (7, 3) с порождающим многочленом  g(x)=x³+x²+1 = 1101 поясняет рисунок.

     К исходному слову  U(x) = x³+1 = 1001 приписывается три нуля со стороны младших разрядов. Полученное слово x⁶+x³ = 1001000 делится на порождающий многочлен. Делимое за 3 такта вводится в сдвиговый регистр, после чего начинается процесс деления: на каждый такт, когда появляется 1 на выходе регистра, к содержимому регистра прибавляется делитель (то же самое, что и вычитается) и результат, полученный в регистре, сдвигается. Если на выходе регистра появляется 0, выполняется только сдвиг слова в регистре.

Деление столбиком показывает, что старшие разряды делимого и делителя не влияют на остаток, т.к. содержат 1 и сумма этих разрядов всегда равна 0. Поэтому сумматор для сложения старших разрядов не требуется,  старший разряд х³ делителя - порождающего многочлена g(x) в вычислениях не участвует, а триггер для хранения разряда х⁶ делимого не предусматривается. Остатки, получаемые в процессе деления, выделены на рисунке жирным шрифтом.

Сдвиговые регистры с обратной связью используются как при формировании, так и при проверке циклического кода на отсутствие ошибок. Задача исправления ошибки, в случае ее обнаружения, сводится к определению вектора ошибки по синдрому (остатку от деления). В кодах Хемминга с исправлением одиночной ошибки эта задача решается просто. С увеличением кратности исправляемой ошибки декодирование сильно усложняется.