Циклический несистематический (7, 4) код Хемминга

Рассмотрим частный вид линейных кодов — циклический код.

Линейный код называют циклическим, если для любого кодового слова [x_n, x_0, x₁… x_n-1] циклическая перестановка символов [x₀ x₁… x_n-1 x_n] также дает кодовое слово.

Циклический несистематический (7,4) код Хемминга — двоичный циклический код, позволяющий исправлять одну ошибку и находить две.

Процедура построения таких кодов гораздо более управляемая. Однако, нам потребуется перейти от векторного описания кодов к полиномиальному. Последовательность символов основного алфавита (биты в простейшем случае), составляющие сообщения и кодовые слова мы будем интерпретировать как коэффициенты полиномов. Например, считая, что коэффициенты записаны в порядке возрастания степени, сообщение [1010] запишем в виде многочлена 1 + x². Кодирование сообщения в более «длинное» кодовое слово будет проводится умножением этого многочлена на другой, что дает в результате многочлен более высокой степени.

Введем необходимые операции в кольце Z2.

Деление. Деление в Z2 происходит, как и в обычной арифметике. Для примера рассмотрим:

(1 + x + x² + x⁵) / (1 + x²).

x⁵ + x² + x + 1.

x⁵ + x³ | x² + 1 / x³ + x² + x + 1.

x³ + x / x² + 1.

x² + 1 / 0.

Также необходимо отметить, что в кольце Z2 x + x = 0.

Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n — 1 на многочлен «x» и нахождения остатка от деления на 1 + xⁿ.

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

Умножение. Умножение в Z₂ происходит, как и в обычной арифметике. Для примера рассмотрим:

(1 + x + x³) * (x² + x³) = x² + x⁴ + x⁵ + x⁶

Лемма 1. Многочлен g (x) является порождающим многочленом линейного циклического кода длины n тогда и только тогда, когда g (x) делит 1 + xⁿ.

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

k = n — deg (g (x)),.

где deg (g (x)) обозначает степень g (x).

В качестве делителя 1 + x⁷ выберем порождающий полином третьей степени: код хемминг программный логика.

g (x) = 1 + x + x³,.

тогда полученный код будет иметь длину n = 7, число проверочных символов (степень порождающего полинома) r = 3, число информационных символов k = 4, минимальное расстояние d = 3.