КОДИРОВАНИЕ

ДВОИЧНЫЕ ЦИКЛИЧЕСКИЕ КОДЫ

Наиболее изученными среди всех кодов являются циклические коды, так как они легко кодируются и содержат важнейшее семейство кодов Боуза-Чоудхури-Хоквингема (БЧХ). Кроме того, они используются для построения многих других кодов, таких как, кодов Керока, Препараты и Юстенсена.

Код С называется циклическим, если он линеен и любой циклический сдвиг разрешённой кодовой комбинации (кодовое слово) также является разрешённой кодовой комбинацией, т.е. если (с₀,с₁,…,с_n-1) принадлежит C, то и (с_n-1,с₀,с₁,…,с_n-2) принадлежит С.

Порождающим многочленом g(x) циклического кода С длины n, является многочлен с максимальной степенью n – m, являющийся множителем двучлена xⁿ + 1, где n – количество разрядов кодового слова, m – количество информационных разрядов (содержат данные).

Благодаря главной конструктивной особенности циклического кода возможен простой не ресурсоёмкий способ декодирования и обнаружения/исправления ошибок.

Основными операциями помехоустойчивого кода являются кодирование и декодирование.

Кодирование помехоустойчивым кодом – это процесс преобразования информационных разрядов в кодовое слово, путём ввода избыточности.

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

 

В зависимости от представления информационных символов в кодовом слове существует два метода кодирования: явный и неявный.

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

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

Известно два основных способа кодирования циклическим помехоустойчивым кодом:

1. табличный метод;

2. с помощью деления.

 

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

Рис. 1. Табличное кодирование

D – информационный блок разрядности m; cW – кодовое слово разрядности n.

 

Во втором способе кодирования данные D, подлежащие кодированию, сдвигаются на n–m разрядов влево, затем производятся вычисление остатка от деления на образующий полином и подстановка остатка в младшие разряды кодового слова cW (рис. 2).

 

Рис. 2. Кодирование циклическим кодом