Кодирование по коду Хэмминга

Nп/п	Исходные информационные комбинации	Закодированные комбинации по Хэммингу
	u3 u5 u6 u7 u9 u10	e1 e2 e3 e4 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10
	0 0 0 0 0 1	0 1 0 0 0 0 0 1 0 1
	0 0 0 0 1 0	1 0 0 0 0 0 0 1 1 0
	0 0 0 0 1 1	1 1 0 0 0 0 0 0 1 1
	0 0 0 1 0 0	1 1 0 1 0 0 1 0 0 0
	0 0 0 1 0 1	1 0 0 1 0 0 1 1 0 1
	0 0 0 1 1 0	0 1 0 1 0 0 1 1 1 0
	0 0 0 1 1 1	0 0 0 1 0 0 1 0 1 1
	0 0 1 0 0 0	0 1 0 1 0 1 0 0 0 0
	0 0 1 0 0 1	0 0 0 1 0 1 0 1 0 1
.........	...................................	.............................................
	1 1 1 0 1 0	1 0 1 0 1 1 0 1 1 0
	1 1 1 0 1 1	1 1 1 0 1 1 0 0 1 1
	1 1 1 1 0 0	1 1 1 1 1 1 1 0 0 0

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

1. Определение элементов синдрома e , e , e , e

e = u₁Å u₃Å u₅Å u₇Å u₉

(28)

e = u₂Å u₃Å u₆Å u₇Å u₁₀

e = u₄Å u₅Å u₆Å u₇

e = u₈Å u₉Å u₁₀

2. Восстановление искаженной принятой кодовой комбинации кода Хэмминга. Пример: передается разрешенная комбинация кода Хэмминга 1001001101 в исходной информационной двоичной комбинации произошло искажение в третьем (слева направо) разряде искажение и на приемник поступил код 10 1 1001101. Каждый разряд слева направо обозначается буквами u₁u₂u₃u₄u₅u₆u₇u₈u₉u₁₀. Декодирование осуществляется по системе уравнений (28):

e = 1 Å 1 Å 0 Å 1 Å 0 =1

e = 0 Å 1 Å 0 Å 1 Å 1 =1

e = 1 Å 0 Å 0 Å 1 =0

e = 1 Å 0 Å 1 =0

Синдром в этом случае равен 0011, что при переводе в десятичное число означает цифру 3, т.е. 0011 ® 3, это указывает на искажение третьего элемента в принятой кодовой комбинации, который и подлежит исправлению с 1 на 0, что в свою очередь и приводит к восстановлению искаженной кодовой комбинации.

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

Название циклических кодов определилось с учетом того, что множество разрешенных комбинаций образуется в результате циклического сдвига. Отображение циклических кодов и выполнение отдельных операций над ними производят на основе степенных многочленов (полиномов) вида:

F(x) = a_n-1x^n-1 + a_n-2x^n-2 +... + a₁x + a₀ (29)

где: x - основание системы счисления;

a₀, a₁,..., a_n-1 - коэффициенты системы счисления в двоичной системе (0, 1).

Например, комбинация 100100110 отображается на многочлене (29) в виде:

100100110 ® 1x⁸ + 0x⁷ + 0x⁶ + 1x⁵ + 0x⁴ + 0x³ + 1x² + 1x +0 =

= x⁸ + x⁵ + x² + x.

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

1. Сложение (x⁵ + x⁴ + x² + 1) + (x⁴ + x³ + x² + x + 1)

x⁵ + x⁴ + 0 + x² + 0 + 1

Å

0 + x⁴ + x³ + x² + x + 0

x⁵ + 0 + x³ + 0 + x + 1 = x⁵ + x³ + x + 1

2. Умножение (x⁴ + x² + x + 1) (x² + 1)

x⁴ + 0 + x² + x + 1

´

x²+ 1

x⁴ + 0 + x² + x + 1

x⁶+0+x⁴ + x³+ x²

x⁶+0+0 + x³ +0 + x + 1 = x⁶ + x³ + x + 1.

3. Деление (x⁵+x³+x²+1):(x+1)

x⁵+0+x³+x²+0+1 ëx+1

x⁵+x⁴ ëx⁴+x³+x+1

x⁴+x³+x²+0+1

x⁴+x³

x²+0+1

x²+x

x+1

x+1

0.

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

Циклическим кодом (n, k) называется систематический код, каждая комбинация которого делится без остатка на образующий многочлен P(x) степени r=n-k. Причем каждая кодовая комбинация циклического кода представляется в виде многочлена степени £ n-1.

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

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

1. Выбирается число информационных элементов циклического кода F(x).

2. Выбирается образующий многочлен P(x).

3. Каждая кодовая комбинация простого двоичного множества умножается на x^r (Q(x)·x^r).

4. Полученное произведение делится на образующий многочлен P(x), , находится частное G(x) и остаток R(x).

5. Определяется кодовый многочлен F(x) циклического кода

F(x) = Q(x)·x^r + R(x) (30).

Например: построить кодовую комбинацию циклического кода F(x) с числом информационных элементов k=6. В качестве образующего многочлена определен многочлен вида P(x)=x³+x+1. В этом случае число проверочных элементов r=3 (определяется по степени образующего многочлена).

1. Общее число элементов кодовой комбинации циклического кода равно n=k+r=6+3=9.

2. Образующий многочлен P(x)=x³+x+1.

3. Выбирается комбинация простого двоичного числа исходного множества (любая) Q(x)=010111®x⁴+x²+x+1 и определяется произведение Q(x)·x^r=(x⁴+x²+x+1)·x³=x⁷+x⁵+x⁴+x³.

4. Определение частного G(x) и остатка R(x)

G(x) + R(x) =

x⁷+x⁵+x⁴+x³ ë x³+x+1

x⁷+x⁵+x⁴ x⁴+1

0 + 0 +0 + x³

x³+x+1

x+1

Следовательно, G(x)=x⁴+1; R(x)=x+1.

В соответствии с формулой (30) определяется кодовый многочлен F(x) и кодовая комбинация циклического кода (9,6) в двоичной форме:

F(x)=Q(x)·x^r+R(x)=(x⁷+x⁵+x⁴+x³)+(x+1)

F(0,1)=010111 011

где: 010111 - информационные элементы циклического кода k;

011 - проверочные элементы циклического кода r.

В таблице 4.9 приведен пример множества кодовых комбинаций циклического кода F(x)_9,6 при образующем многочлене P(x)=x³+x+1.

Образующий многочлен P(x)=x³+x+1; F(x)=Q(x)·x^r+R(x)

Таблица 4.9