Циклические коды

Коды Хемминга

В отличие от канонического систематического кода, в коде Хемминга информационные и проверочные биты не разнесены в отдельные подматрицы, а чередуются. Если биты кодовой комбинации пронумеровать, начиная с 1, слева направо, то контрольными (проверочными) оказываются биты с номерами 1, 2, 4, 8 и т.д. – все остальные являются информационными. Цель этих перестановок – сделать так, чтобы синдром ошибки непосредственно указывал на локализацию ошибок, миную промежуточную таблицу соответствия синдромов и ошибок. Код Хемминга начинают строить с проверочной матрицы H, так как ее вид очевиден: столбцы проверочной матрицы представляют собой набор синдромов, соответствующих двоичному представлению номера столбца. Затем строят порождающую матрицу G, исходя из того, что матрицы H и G ортогональны, т.е. скалярное произведение каждой строки матрицы G на каждую строку матрицы H равно нулю, то есть

H´ G^T = 0 и G´ H^T = 0.

Построим код Хемминга для (7,4)-кода. Чтобы синдром ошибки указывал на место ошибки, проверочная матрица должна иметь вид:

В ней на 1-м, 2-м и 4-м местах стоят столбцы единичной матрицы, а на остальных – столбцы, соответствующие информационным разрядам кода. Выделим подматрицу, соответствующую информационным разрядам:

Повернем матрицу по часовой стрелке и получим проверочную подматрицу порождающей матрицы

Поставим столбцы матрицы P на 1, 2 и 4-е место, а остальные столбцы будут столбцами единичной матрицы. Получим порождающую матрицу кода Хемминга:

.

Закодируем по Хеммингу входную комбинацию m = [0 0 1 1].

Проверим кодовое слово, вычислив синдром:

.

Синдром нулевой, следовательно, получена разрешенная кодовая комбинация. Предположим, что произошла ошибка в третьем разряде и принята кодовая комбинация û=[1 0 1 0 0 1 1]. Вычислим синдром:

.

Синдром представляет собой двоичное число 3, что локализует ошибку в третьем разряде.

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

Решение:

Порождающая матрица (8, 3)-кода уже была получена:

Представим ее в каноническом виде, переставив столбцы:

Выделим проверочную подматрицу:

и транспонируем ее:

Составим проверочную матрицу (8,3)-кода:

. Код построен.

Название кодов произошло от их свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов комбинации, принадлежащей этому же коду. Это значит, что если, например, комбинация a₀ a₁ a₂ … a_n-1 является разрешенной, то комбинация a_n-1a₀ a₁ a₂ … a_n-2 также является разрешенной. Циклические коды обычно имеют полиномиальное представление, означающее, что бинарные элементы кодового слова a₀ a₁ a₂ … a_n-1 интерпретируются как коэффициенты полинома от некоторой фиктивной переменной х: f(x)=a_n-1x^n-1 + a_n-2x^n-2 +…+ a₂x²+a₁x + a₀

Например, кодовое слово 11010 представляется в виде полинома x⁴+x³+x.

Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью полинома. Таким образом, в полиноме степени n-1 старший коэффициент a_n-1 равен 1.

Действия над кодовыми комбинациями сводятся к действиям над полиномами. Причем операция сложения производится по модулю 2. Множество таких полиномов и действий над ними образуют т.н. поле Галуа порядка 2 (обозначается GF(2)).

Циклический сдвиг коэффициентов полинома получается умножением полинома на x с одновременным сложением с двучленом xⁿ+1. Действительно, пусть

f(x)=1•x^n-1+a_n-2x^n-2 +…+a₂x²+a₁x+a₀.

Тогда f(x)•x + (xⁿ+1) = xⁿ+a_n-2x^n-1+ … +a₂x³+a₁x²+a₀x + xⁿ+1 =

= a_n-2x^n-1+ … +a₂x³+a₁x²+a₀x +1

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

u₁(x) = g(x)

u₂(x) = g(x)∙x + (xⁿ+1)

u₃(x) = u₂(x)∙x + (xⁿ+1) = g(x)∙x² + (xⁿ+1)(x+1)

…

u_n(x) = g(x)∙x^n-1 + (xⁿ+1)(x^n-2+x^n-3+…+1)

При таком способе построения полином g(x) называется порождающим. Если потребовать, чтобы порождающий полином g(x) был делителем двучлена (xⁿ+1), то все разрешенные комбинации приобретают свойство делимости на g(x). Из этого следует, что можно легко проверить, является ли комбинация разрешенной. Достаточно проверить ее делимость на полином g(x).

Основные свойства циклических кодов:

1. В циклическом (n,k)- коде каждый кодовый полином должен иметь степень не более n-1.

2. Существует полином g(x) степени (n-k) вида

g(x)=x^n-k+g_n-k-1x^n-k-1+…+g₂x²+g₁x+1,

называемый порождающим полиномом кода.

3. Каждый кодовый полином u(x) является кратным g(x), то есть u(x) = m(x)•g(x).

Дата добавления: 2014-10-22