16. Идея построения циклических кодов

Пусть слово длины n над алфавитом из элементовконечного поля иполином, соответствующий этому слову, от формальной переменной x. Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации пары слови, равен линейной комбинации полиномов этих слов

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем

Алгебраическое описание

Если кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова, то соответствующий ему полиномc₁(x) получается из предыдущего умножением на x:

, пользуясь тем, что ,

Сдвиг вправо и влево соответственно на j разрядов:

Если m(x) — произвольный полином над полем GF(q) и c(x) — кодовое слово циклического (n,k) кода, то m(x)c(x) mod(xⁿ − 1) тоже кодовое слово этого кода.

17. Порождающий полином циклического кода

Определение Порождающим полиномом циклического (n,k) кода C называется такой ненулевой полином изC, степень которого наименьшая и коэффициент при старшей степени g_r = 1.

Теорема 1 Если C — циклический (n,k) код и g(x) — его порождающий полином, тогда степень g(x) равна r = n − k и каждое кодовое слово может быть единственным образом представлено в виде

c(x) = m(x)g(x),

где степень m(x) меньше или равна k − 1.

Теорема 2 g(x) — порождающий полином циклического (n,k) кода является делителем двучлена xⁿ − 1

Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель xⁿ − 1. Степень выбранного полинома будет определять количество проверочных символов r, число информационных символов k = n − r.

18. Алгоритм получения разрешенных комбинаций циклического кода из простого линейного кода

Пусть задан полином P(x) = a_r−1 x^r + a_r−2 x^r−1 + … + 1, определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена A_k−1(x).

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

1. Умножаем многочлен исходной кодовой комбинации на x^r:

A_k−1(x) · x^r

2. Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином:

A_k−1(x) · x^r ⁄ P_r(x) ⇒ R(x)

3. Окончательно разрешенная кодовая комбинация циклического кода определится так:

A_n−1(x) = A_k−1(x) · x^r + R(x)

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Пример. Пусть требуется закодировать комбинацию вида 1101, что соответствует A(х) = х³ + х² + 1.

Определяем число контрольных символов r = 3. Из таблицы возьмем многочлен P(х) = х³ + х + 1, т. е. 1011.

Умножим A(х) на х^r:

A(x) · x^r = (x³ + x² + 1) · x³ = x⁶ + x⁵ + x³ ⇒ 11010000

Разделим полученное произведение на образующий полином g(х):

A(x) · x^r ⁄ P(x) = (x⁶ + x⁵ + x³) ⁄ (х³ + х + 1) = х³ + х² + х + 1 + 1 ⁄ (х³ + х + 1) ⇒ 1111 + 001 ⁄ 1011

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х) · х^r. В результате получим закодированное сообщение:

F(x) = (x³ + x² + 1) · (x³ + x + 1) = (x³ + x² + 1) · x³ + 1 ⇒ 1101001

В полученной кодовой комбинации циклического кода информационные символы A(х) = 1101, а контрольные R(х) = 001. Закодированное сообщение делится на образующий полином без остатка.