6.7. Кодирующие и декодирующие устройства циклических кодов

6.7.1 Процедура кодирования и декодирования для циклических кодов

Преобразование комбинации первичного k– разрядного кода в комбинацию циклического (n,k) – кода может быть осуществлено либо при помощи порождающего многочленаg(x), либо при помощи проверочного многочленаh(x).

а) Процедура кодирования для циклического кода по g(x).

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

,

где степень r(x)меньшеn-k.

Образуем новый многочлен , у которого коэффициенты при степеняхх, меньшихn-k, есть соответствующие коэффициентыr(x), а коэффициенты при остальных степенях есть соответствующие коэффициенты.

Для полученного многочлена справедливо

и так как его степень не превышает n-1, то по определению 2 циклического кода полученный подобным образом векторпринадлежит циклическому (n,k) – коду.

В векторе коэффициентами при степеняхх, равныхn-kи старше, являются информационные элементы кодовой комбинации, а коэффициентами при младших степенях – проверочные (см. рис. 6.0).

Таким образом, для формирования кодовой комбинации циклического (n,k) – кода по данному способу требуется иметь устройство для умножения комбинации первичного кода, представляемой многочленомстепени не старшейk-1, на, деления, полученного в результате умножения многочленастепени не старшейn-1 на порождающий многочлен циклического кодаg(x)степениn-kи вычисления остатка от этого делениястепениn-k-1 и менее.

В комбинации циклического (n,k) – кода коэффициенты многочлена(n,k) – кода являются информационными разрядами, а коэффициенты многочлена- избыточными.

б) Процедура кодирования для циклического кода по h(x).

Для проверочного многочлена h(x)степениkциклического (n,k) – кода справедливоили.

Так как по определению 2 любая кодовая комбинация кратна g(x), то для произвольной комбинацииf(x)выполняется.

Если принять , то, учитывая, что степень h(x)равнаk, а степеньf(x)равнаn-1, для коэффициентаС_сможно составить соотношение:

.

Учитывая, что находим

Положим с = n-1, тогда

При с = n-2 имеем:

При c =k

Итак, если известны коэффициенты , т.е. информационные элементы кодовой комбинации циклического (n,k) – кода, то при помощи систем рекуррентных соотношений, полученных выше, можно найти значение избыточных элементовТаким образом, для кодирования по проверочному многочлену необходимо иметь устройство для решения рекуррентных соотношений типа

в) Процедура декодирования для циклических кодов

В основе процедуры декодирования лежит процесс выявления принадлежности принятой комбинации к множеству разрешенных кодовых комбинаций. Эта задача решается, как было показано выше, вычислением синдрома для принятой комбинации . Техническая реализация этой операции может осуществляться по методике, изложенной при рассмотрении кодов Хэмминга. Однако для циклических кодов можно получить более рациональное вычисление синдрома, если использовать признак делимости каждой кодовой комбинации этих кодов на порождающий многочленg(x). В данном случае принятая комбинацияf(x)делится на порождающий многочленg(x):

.

Если остаток от деления r(x)=0, то считают, что комбинацияf(x)и была передана.

В этом случае kкоэффициентов отдаются потребителю в качестве переданного сообщения.

Если же остаток от деления , то принятая комбинацияf(x)признается запрещенной и в зависимости от логики работы УЗО потребителю выдается сигнал наличия ошибки в принятой информации или организуется исправление ошибок. При исправлении по виду остаткаr(x)отыскивается смежный класс, которому принадлежит принятая комбинация и определяется наиболее вероятный образец ошибки. Элементы, в которых предполагаются ошибки, инвертируются, и информационные разряды комбинации отдаются потребителям. Покажем, что остаток от деленияr(x)тождественен синдрому в общепринятом определении. Как было показано в разделе 6.3 (пример 6.6) столбцами проверочной матрицы являются остатки от деленияна порождающий многочленg(x).

Действительно, деление обладает свойством суперпозиции, т.е. остаток от деления некоторого многочлена f(x)степениn-1 на порождающий многочлен кода равен сумме остатков от деления степенейxⁱс ненулевыми коэффициентами из этого многочлена (другими словами степенейxⁱ, соответствующих единицам в принятой кодовой комбинации). Произведениесводится к суммированию столбцов матрицыН, соответствующих единицам принятой комбинации. Учитывая, что столбцы матрицыН– это остатки от деленияxⁱ(где), на порождающий многочленg(x) находим, что.

Пример 6.13.Определить принадлежность комбинациициклическому (7,4) – коду с

Вычисляем синдром

1 0 0.

. S=100.

Найдем остаток от деления многочленана

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

Итак, мы установили существование двух способов вычисления синдрома для кодовых комбинаций. При этом второй способ отражает специфику представления кодовой комбинации в виде многочлена. Возможен ещё и третий способ вычисления синдрома, также вытекающий из представления кодовых комбинаций многочленами. Каждая кодовая комбинация циклического (n,k)кода кратна порождающему многочленуg(x)степениn-k. Это в свою очередь означает, что любая кодовая комбинация имеет среди своих корнейn-kкорней порождающего многочлена. Значит принадлежность принятой комбинацииf(x)к используемому коду можно определить подстановкой вместо формальной переменнойxв принятой комбинации корней порождающего многочленаg(x).

Пусть – αⁱ– корень порождающего многочлена(n,k)–кода, аf(x)– кодовая комбинация этого кода, тогда должно быть справедливо:f(x=αⁱ)=0 для всех значенийi, определяющих корниg(x).

Выше отмечалось, что синдром должен определять вид ошибок, появившихся в кодовой комбинации при передаче её по каналу с помехами.

Пусть передана комбинация f(x), а принята комбинацияf'(x)=f(x)+e(x), гдеe(x)– многочлен ошибок. Тогдаf'(x=αⁱ)=f(x=αⁱ)+e(x=αⁱ)=e(x=αⁱ)=S_i

2.Если e(x)по виду совпадает с одной из кодовых комбинаций, тоS_i=e(x=αⁱ)=0,

т.е. имеет место нулевой синдром, который приведёт к необнаруженной ошибке. Если же e(x)отличается от кодовой комбинации, то синдром будет ненулевым:S_i=e(x=αⁱ)≠0 и ошибка будет выявлена.

Пример 6.13. (продолжение)

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

Из приложения находим, что многочлен g(x)=1+x+x³имеет следующие корни α¹, α²,α⁴, являющиеся элементамиGF(2³). Рассмотрим результаты подстановкиf(x=αⁱ), для случаяi=1.

Для этого обратимся к процедуре к процедуре умножения:

(1111001)×H^T.

Обратим внимание, что матрица H^T(7,4)- кода в точности соответствует представлению элементовGF(2³)в виде ненулевых векторов в таблице задачи 6 раздела 5.8. Это не случайное совпадение. Обе эти совокупности двоичных последовательностей длины 3 получены как классы вычетов многочленов по модулю одного и того же многочлена 3-ей степени и отображают одну и ту же циклическую группу.

При этом процедура замены в проверяемом многочлене xⁱна αⁱи последующего суммирования результатов замены полностью эквивалентна сложению строк матрицыH^Tсоответствующим «1» в двоичном представлении многочлена.

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

В случае исправления ошибок необходима еще и схема сопоставления синдрома образцу ошибки. В простейшем случае при исправлении однократных ошибок в основе этой схемы лежит генератор элементов поля GF(2^m).