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

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

Двоичные комбинации формально можно записать полиномом фиктивной переменной х Например, комбинации 1110001 соответствует полином x6-f- х5+ хА-\- 1. Над этими многочленами можно выполнять все операции согласно законам алгебры, за исключением вычитания и сложения, которое осуществляется по модулю 2. Отличительной способностью разрешенных комбинаций данного циклического кода является то, что все они делятся без остатка на производящий полином.
Рассмотрим образование разрешенных комбинаций заданного циклического кода (я, k) с производящим полиномом q(x). Например задан код (7,4) с q(x)= хг-\- х2-\- 1, тогда комбинация, которую необходимо закодировать в данном коде,
1011 -*х3 + х + 1 = G(x)
Кодирование заключается в циклическом сдвиге G(x) на г разрядов, что соответствует умножению этого полинома на хг. В данном случае г= 3, поэтому
G(x)x’ = (У + х + 1)*’ = Xs + х-4 + х3 Полученный полином делим на производящий полином
{хе+ х< + х<)/(х3 + х>+ 1) = = х3+ х2+ R (x)/q (х),
где R (х) — х’ 4- 1 — остаток от деления

Этот остаток прибавляем к полиному G (х) хг и окончательно получаем нужную нам разрешенную комбинацию
хь + х* + х3 + х1 -f- 1 — 1011 101,
где х6 + х4 + х3 = G (х)хг, 1011 = к, 101 = г
В полученной комбинации четыре информационных и три проверочных элемента. Она без остатка делится на q(x)= х3-\- х2 -f-1.

Искажение комбинации можно представить как результат сложения неискаженной комбинации’ и комбинации ошибки, которая также может быть записана полиномом. Ошибка не будет обнаружена, если полином ошибки без остатка делится на q(x). Это возможно только в том случае, если степень полинома ошибки выше степени q(x). Следовательно, циклический код надежно обнаруживает пакеты (группы) ошибок длиной, равной или меньшей степени q(x), т. е. числа проверочных разрядов г.

Статьи на близкие темы: