Алгоритм кодирования кодом Хэмминга

Пусть задано информационное слово С b 0 b 1 b 2 b 3 1010, которое нужно

закодировать кодом Хэмминга (7,4). Код Хэмминга (7,4) задан порождающей матрицей вида (3).

Комбинация на выходе кодера получается из соотношения:

1000 _ 011

С С G

b b b b

0100 _101

b b b b _ a a a.

0010 _110

0001_111

Проверочные символы для кода Хэмминга (7,4) формируются в соответствии с приведенными выражениями:

a 0	b 1	b 2	b 3	0 1 0 1,
a 1	b 0	b 2	b 3		1 0 0,
a 2	b 0	b 1	b 3		0 0 1.

При записи кодовой комбинации на выходе кодера первые k символов кода

называются информационными, остальные r	n k – проверочными.
На выходе кодера получим кодовую комбинацию:
С b 0 b 1 b 2 b 3 _ a 0 a 1 a 2	1010 _101.

 

Структурная схема кодера для кода Хэмминга (7,4)

bo

bo

приведена на рис. 2.

b1

b1

Задача

декодирования

состоит

в

том,

чтобы

принятому

кодовому

слову поставить

в

соответствие

b2

b2

кодовое слово из числа разрешѐнных. Используя принцип

b3

b3

максимального правдоподобия, в соответствие

ставится

такое разрешѐнное слово, которое минимально отличается

от принятого.

M2

Алгоритмы

декодирования

можно

задавать

ao

№1

таблично. Однако гораздо удобнее знание математической

M2

структуры

кода,

что

может

облегчить

реализацию

№2

a1

операций кодирования и декодирования.

M2

№3

a2

Необходимо

отметить,

что

операция

Рис. 2. Схема кодера

декодирования,

не

есть операция,

обратная операции

кодирования. Это операция оценки принятого сообщения и

Хэмминга (7,4)

принятия наиболее достоверного решения относительно

того, какое из возможных сообщений было передано.

Различают синдромное и мажоритарное декодирование.

Синдромом называется

кодовая

комбинация

размерностью

r

n

k,

равная

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

т.е. S 000. Если жекакой-либосимвол будет принят с искажением, то синдром совпадает со столбцом проверочной матрицы и укажет на номер разряда (символа в кодовом слове), который принят с ошибкой.

Для исправления ошибки нужно к символу разряда в котором произошла ошибка прибавить единицу по модулю два.

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

При декодировании кодом Хэмминга используется синдромное декодирование.

Для порождающей матрицы вида (3),	проверочная матрица имеет канонический
вид:
		0111_100
	H	1011_ 010		.	(4)
	1101_ 001
		h k r __ Ir	r
Проверочная матрица H состоит из2-хподматриц:
h k	r – транспонированной матрицы, определяемой из порождающей матрицы;
I r r	– единичной матрицы размерностью r	r.

Свойство проверочной матрицы: произведение закодированного слова (разрешенной кодовой комбинации) на транспонированную проверочную матрицу равно нуль-вектору:

b 0, b 1, b 2,..., bk 1, a 0, a 1,..., ar 1 H T 0,0,...,0 r 1.

Проверочная и порождающая матрицы связаны выражением:

G	H T	k	0.
k n	n

В обобщенном виде, алгоритм исправления ошибок включает в себя три этапа: вычисление синдрома; синтез вектора ошибок; исправление ошибки.

Рассмотрим этапы более подробно.

 

Вычисление синдрома.

Для кода Хэмминга (7,4) синдромом будет 3-хразрядная кодовая комбинация:

S С H T b b b b _ a a a

S

S S

,

где С b 0 b 1 b 2 b 3 _ a 0 a 1 a 2 – принятое сообщение;

H T – транспонированная проверочная матрица.

Согласно правилу умножения вектора на матрицу элементы синдрома будут определяться выражениями:

S 0 b 1 b 2 b 3 a 0, S 1 b 0 b 2 b 3 a 1, S 2 b 0 b 1 b 3 a 2.

Если кодовое слово будет принято без искажений, то синдром будет равен нулю,

т.е. S 000.

Если же какой-либосимвол будет принят с искажением, то синдром укажет на номер элемента в кодовом слове, который принят ошибочно.

Вектор ошибок это кодовая комбинация, которая ставится в соответствие синдрому и содержит единицу в том разряде, где произошла ошибка, и нули во всех остальных разрядах. Составим таблицу соответствия синдрома и вектора ошибок:

Таблица 1

Таблица соответствия вектора ошибки синдрому сообщения

Синдром

Вектор ошибок

35.

S 0	S 1	S 2	e 0	e 1	e 2	e 3

На основании данной таблицы получим элементы вектора ошибок: e 0 S 0 S 1 S 2, e 1 S 0 S 1 S 2, e 2 S 0 S 1 S 2, e 3 S 0 S 1 S 2.

Например, с ошибкой был принят символ b 2, в этом случае синдром будет равен

S 110, а это третий столбец в проверочной матрице, которому соответствует вектор ошибок e 0010.

Исправить ошибку довольно легко, для этого нужно произвести поразрядное сложение по модулю два принятого кодового слова и синтезированного вектора ошибок.

Пример.

36. Пусть принята кодовая комбинация C 1010 _101 без ошибки. Произведем вычисление синдрома:

S 0	b 1	b 2	b 3	a 0	0 1 0		0,
S 1	b 0	b 2	b 3	a 1	1 1 0 0 0,
S 2	b 0	b 1	b 3	a 2	1 0 0		0.
Т.к. полученный синдром является нулевым, то ошибки нет и можно сразу записать
итоговую кодовую комбинацию: C	1010.

37. 6

38.

Пример.

40. Введем в принятую кодовую комбинацию, ошибку во втором разряде, т.е.

41. C 1110 _101.

42. Произведем вычисление синдрома:

S 0	b 1	b 2	b 3	a 0					1,
S 1	b 0	b 2	b 3	a 1	1 1 0 0 0,
S 2	b 0	b 1	b 3	a 2					1.
Полученному синдрому	S	101,	соответствует	второй столбец проверочной

43. матрицы, в таблице соответствия (табл. 2.1) это третья строка следовательно вектор ошибок примет вид e 0100.

44. Запишем процесс исправления ошибки:

45. С 1110 – информационные символы принятой кодовой комбинации,

e 0100 – вектор ошибок,

С 1010 – исправленная информационная кодовая комбинация.

Схема декодера для выбранного кода Хэмминга (рис. 3) строится по известной проверочной матрице H с использованием метода синдромного декодирования.

В состав структурной схемы декодера кода Хэмминга (7,4) входят: блок вычисления синдрома; формирователь вектора ошибок;

выходные сумматоры по модулю два, в которых происходит процесс исправления ошибок.

bo		M2				bo
	№4
b1			M2			b1
		№5
b2				M2		b2
			№6
b3					M2	b3
				№7
		e0	e1	e2	e3
		&	&	&	&
ao	M2	S0				S0
№1
a1	M2	S1				S1
№2
a2	M2	S2				S2
№3

Блок вычисления синдрома