Методы задания циклических кодов

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

Алгебраическая структура ЦК впервые была исследована Боузом, Чоудхури и Хоквингемом, поэтому они известны как БЧХ-коды.

Эти коды характеризуются следующими свойствами:

длина кодовой комбинации (КК)

, (7.1)

число проверочных элементов

,

циклический код (ЦК) обнаруживает все пачки ошибок длины ,

циклический сдвиг разрешенной кодовой комбинации кода приводит к образованию разрешенной КК этого же кода,

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

.

ЦК образуют путем умножения каждой КК k-элементного безызбыточного кода, выраженной в виде многочлена G(x), на образующий полином Р(х) степени (n-k). Умножение производится по обычным правилам алгебры с приведением подобных членов по модулю два.

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

Однако данный метод приводит к построению несистематического ЦК. Более широкое применение нашел другой метод. Каждая КК первичного кода умножается на одночлен X^n-k,что равносильно приписыванию справа от КК r нулей. Произведение G(x)×X^n-k делится на образующий полином Р(х) степени n‑k

где Q(x)- частное от деления такой же степени, как и G(x), R(x)- остаток, Q(x)- является КК этого же простого k-элементного кода.

Умножая обе части равенства на Р(х) и сделав перенос, получим

.

Таким образом, КК ЦК может быть получена двумя эквивалентными методами:

путем умножения кодовой комбинации G(x) простого к-элементного кода на образующий полином Р(х);

путем умножения КК G(x) простого k-элементного кода на одночлен х^n-k и добавления к этому произведению остатка R(х), полученного в результате деления произведения на образующий полином Р(х).

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

Наименьшей избыточностью обладают циклические (k+1,k) коды, называемые кодами с постоянной четностью единиц. Построение этих кодов осуществляется с помощью образующего полинома Р(х)=х+1.

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

Сущность метода состоит в том, что в конце исходной комбинации G(x) формируется дополнительный контрольный разряд, в который записывается 1, если число единиц четное. Обнаружение нечетного числа единиц полученной КК свидетельствует о наличии ошибок.

Нетрудно заметить, что коды с проверкой на четность обнаруживают любые ошибки нечетной кратности, т.е. m=1,2,3...