Код Хэмминга

Код Хэмминга предназначен для исправления одиночных ошибок и имеет кодовое расстояние d_min=3. Значения n и k кодов Хэмминга связаны соотношением 2^n-k-1=n . Строки проверочной матрицы Н представляют собой различные ненулевые последовательности длины (n-k). Изначально правила формирования проверочных элементов выбирались (50-е годы) так, чтобы результат контрольных сумм при приеме указывал порядковый номер искаженного элемента.

Пусть a_i – информационные символы, b_i – проверочные символы. Если проверочные символы разместить в кодовой комбинации на позициях, номера которых являются степенью двойки (1, 2, 4, 8 и т.д.), то получаемый синдром в двоичном виде указывает на номер искаженного элемента. Рассмотрим это на примере кода (7,4). Пусть на вход кодера поступает информационная последовательность U=u₄u₃u₂u₁. В кодовой комбинации кода Хемминга информационные биты размещаются в разрядах 3,5,6 и 7. В разрядах 1,2 и 4 размещаются проверочные биты. Перепишем информационную последовательность в следующем виде U=a₇a₆a₅a₃.

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

a₇ a₆ a₅ b₄ a₃ b₂ b₁

Решим эту систему уравнений относительноb₁, b₂ и b₄.

Тогда элементы синдрома S=s₂ s₁ s₀ равны

Например, если ошибка произошла в символе a₃ , синдром будет иметь следующий вид S=(011), что означает десятичное число 3.

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

Циклическим кодом называется такой линейный код, у которого при любом циклическом сдвиге разрешенного кодового слова получается другое разрешенное кодовое слово.

Циклический код обладает всеми свойствами линейных кодов.

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

Представление кодовых слов степенными полиномами.

Кодовые слова циклического кода ставят в соответствие степенным полиномам по следующему правилу:

двоичной последовательности V длиной n

соответствует полином (n-1)-й степени ,

здесь х – формальная переменная.

Циклический сдвиг кодового слова на i разрядов влево соответствует умножению полинома V(x) на xⁱ по модулю (xⁿ+1).

A=BmodC (А равно остатку от деления В на С)

Пример.

Пусть n=7. Задано кодовое слово 1001101  x⁶+x³+x²+1. Сдвиг кодового слова на 1 разряд влево дает другое кодовое слово 0011011  х⁴+х³+х+1.

V(x)*xⁱ mod (xⁿ+1)=(x⁶+x³+x²+1)*x mod (x⁷+1)=(x⁷+x⁴+x³+x) mod (x⁷+1)= =x⁴+x³+x+1

Циклический сдвиг кодового слова на i разрядов вправо соответствует умножению полинома V(x) на x^-i или х^n-i по модулю (xⁿ+1).

V(x)*x^-i mod (xⁿ+1)= V(x)*x^n-i mod (xⁿ+1)

При выполнении математических преобразований над полиномами сложение и вычитание коэффициентов при одинаковых степенях переменной х заменяется суммированием по модулю 2. Следует помнить, что x^-i ≡ х^n-i.

Образующий (порождающий, производящий) полином циклического кода

Множество кодовых слов циклического кода можно указать, задав любое ненулевое кодовое слово. НО, обычно для задания циклического кода указывают образующий полином g(x) , который полностью определяет код. Степень образующего полинома равна (n-k) , а свободный член V₀ всегда равен 1.

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

Выбор g(x) для построения циклического кода длины n.

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

Пример.

Требуется определить, какие циклические коды можно построить при длине кодового слова n=7.

Полином x⁷+1 можно разложить на три неприводимых сомножителя:

x⁷+1=(x+1)(x³+x²+1)(x³+x+1)

Можно построить следующие ЦК:

1. (7,6) с g(x)=x+1

2. (7,1) с g(x)= (x³+x²+1)(x³+x+1)=x⁶+x⁴+x³+x⁵+x³+x²+x³+x+1=

=x⁶+x⁵+x⁴+x³+x²+x+1

3. (7,4) c g(x)= x³+x²+1

4. (7,4) c g(x)= x³+x+1

5. (7,3) c g(x)= (x+1)(x³+x²+1)=x⁴+x³+x+x³+x²+1=x⁴+x²+x+1

6. (7,3) c g(x)= (x+1)(x³+x+1)=x⁴+x²+x+x³+x+1=x⁴+ x³+x²+1

Образующий полином используют для определения образующей матрицы циклического кода:

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

2. Вторая строка – x*g(x) (циклический сдвиг первой строки на одну позицию влево).

3. Третья строка – x²*g(x) (циклический сдвиг первой строки на две позиции влево).

……………………………………………………………………………………..

7. К-я строка – x^k-1*g(x) (циклический сдвиг первой строки на (k-1) позицию влево).

Пример.

Задан код (7,4) с образующим полиномомg(x)=x³+x+1. Требуется записать его образующую матрицу.

Полученную матрицу можно преобразовать к каноническому виду путем суммирования строк (по модулю 2) и перестановки строк местами.

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

Процедура кодирования записывается следующим образом:

V(x)=U(x)*x^n-kR(x)

R(x)= U(x)*x^n-k mod g(x)

В этом случае старшие k разрядов кодового слова являются информационными. Младшие разряды r=n-k – являются проверочными.

Пример

Закодировать информационную последовательностьU=0110 циклическим кодом (7,4) с образующим полиномом g(x)= x³+x+1.

U(x)= x²+x, r=n-k=3, U(x)*x³= x⁵+x⁴

R(x)=( x⁵+x⁴) mod (x³+x+1)=1

V=0110001  V(x)= x⁵+x⁴+1

Сложение коэффициентов при одинаковых степенях осуществляется по модулю 2.

Деление можно выполнять в двоичном виде.

U(x)*x³= x⁵+x⁴  0110000

g(x)  1011

R=001V=0110001

Число проверочных символов в кодовой комбинации всегда равно степени образующего полинома.

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

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

Декодирование с обнаружением ошибок

Если принятая комбинация Y(x) делится без остатка на g(x), то считается, что ошибок нет или произошла не обнаруживаемая кодом ошибка.

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

S(x)=Y(x) mod g(x)=[V(x)+e(x)] mod g(x)=e(x) mod g(x), где e(x) – полином ошибки.

Декодирование с исправлением ошибок

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

Ошибке вида e₀ =1 соответствует синдром S₀ =1. Назовем их типовыми, так как это соответствие сохраняется для любого циклического кода.

S₀(x)=e₀(x) mod g(x)

Если вектор ошибки e' получается из e₀ путем i циклических сдвигов влево, то есть

e'(x)=e₀ (x)*xⁱ mod (xⁿ+1),

то синдром ошибки e' S’ можно определить через типовой синдром S₀ по формуле

S'(x)=S₀(x)*xⁱ mod g(x),

Тогда S₀(x)= S'(x)* x^-i mod g(x), то есть типовой синдром образуется в схеме, осуществляющей деление на образующий полином g(x), при циклическом сдвиге S’(x) вправо через i тактов работы после получения S’(x).

Пример

Пусть для передачи сообщений используется циклический код (7,4) с образующим полиномом g(x)= x³+x²+1. Для передачи используется ДСК без памяти. Декодер работает в режиме исправления одиночных ошибок.

При использовании ДСК без памяти таблица декодирования имеет вид

Вектор ошибки ei	Синдром Si
0000001	001
0000010 …………..	010 …….
1000000	110

В качестве типового вектора ошибки и типового синдрома выбираем e₀=0000001 и S₀=001.

Предположим, при декодировании получен синдром S'=100=х². Требуется найти имеющий место вектор ошибки и исправить кодовое слово.

S₀(x)=S'(x)*x^-i mod g(x), проверяем выполнение равенства, задаваясь различными значениями i.

Если i=1, S₁= x²* x^-1 mod (x³+x²+1) = x, не совпадает с типовым синдромом S₀.

Если i=2, S₂=x²*x^-2 mod (x³+x²+1) = 1, совпадает с типовым синдромом S₀.

Искомый вектор ошибки получается циклической перестановкой типового вектора e₀ =0000001 на i=2 разряда влево.

e'=0000100

Решим задачу для случая, если в качестве типового вектора ошибки выбран e₀=1000000 и соответствующий ему типовой синдром S₀=110:

Если i=1, S₁= x²* x^-1 mod (x³+x²+1) = x, не совпадает с типовым синдромом S₀.

Если i=2, S₂=x²*x^-2 mod (x³+x²+1) = 1, не совпадает с типовым синдромом S₀.

Если i=3, S₃=x²* x^-3 mod(x³+x²+1)=x^7-1mod(x³+x²+1)=x⁶mod (x³+x²+1)=x²+x, совпадает с типовым синдромом S₀.

Искомый вектор ошибки получается циклической перестановкой типового вектора e₀ =1000000 на i=3 разряда влево.

e'=0000100