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

Наиболее распространенным подклассом линейных кодов являются циклические коды. Это обусловлено относительно простым построением кодера и декодера, обнаруживающего ошибки, при достаточно высоких корректирующих способностях кода. Эти коды позволяют преодолеть некоторые трудности, связанные с технической реализацией, свойственные линейным кодам. В информационной системе циклические коды предпочтительны для передачи сообщений небольшой длины, например, команд управления объектами.

Алгебраическая структура циклических кодов впервые была исследована Боузом, Чоудхури и Хоквингемом, поэтому они известны как БЧХ-коды. Эти коды характеризуются следующими свойствами [7, 110]: длиной кодовых последовательностей

 (6)

где т = 1,2,3,…;

числом проверочных элементов, не превышающим величины , т.е.

 (7)

способностью обнаруживать все пакеты ошибок длины

 (8)

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

Возможно задание циклических БЧХ-кодов при помощи порождающих или проверочных матриц аналогично общим правилам, построения линейных кодов. Однако воспользуемся более простыми инженерными методиками, базирующимися на алгебраических понятиях. В этом случае более удобной является запись кодовых комбинаций в виде полинома переменной х:

Коэффициенты a_i представляют собой цифры данной системы счисления. В двоичной системе счисления коэффициенты могут принимать одно из двух значений 0 или 1. Так, двоичное четырехразрядное число 1001 может быть записано в виде полинома

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

Циклические коды образуются умножением каждой комбинации – элементного безызбыточного кода, выраженной в виде многочлена G (х), на образующий полином Р (х) степени (п – k). При этом умножение производится по обычным правилам с приведением подобных членов по модулю два [6, 98]. Следовательно, в случае отсутствия ошибок любая разрешенная кодовая комбинация циклического кода должна разделиться на образующий полином Р (х) без остатка. Появление остатка от деления указывает на наличие ошибок в кодовой комбинации. При этом гарантийно обнаруживаются ошибки, определяемые выражениями (7) и (8).

Кроме того, обнаруживается большая часты  ошибок более высокой кратности.

Широкое применение нашел другой метод, который в отношении степени избыточности и помехоустойчивости приводит к построению эквивалентного циклического кода. В соответствии с этим методом каждая кодовая комбинация первичного кода G (х) умножается на одночлен X ^{n - k}. Это эквивалентно приписыванию справа к комбинации G (х), записанной в двоичной форме, (п – k) нулей. Произведение G(х) x ^{n - k} делится на образующий полином Р (х) степени (п – k):

 (9)

где Q (х) – частное от деления такой же степени, как и G (х); R (х) – остаток.

Так как частное Q (х) имеет такую же степень, как ^и кодовая комбинация G (х), то, следовательно, Q (х) является кодовой комбинацией этого же простого k-элементного кода.

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

 (10)

Здесь знак минус заменен знаком плюс, так как сложение и вычитание по модулю два – операции эквивалентные.

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