Методические указания к выполнению расчетно-графической работы №2

Код Хэмминга позволяет обеспечить самоконтроль и самокоррекцию кода путем кодирования какого-либо информационного сообщения определённым образом и после передачи осуществить определение единичной ошибки в этом сообщении, а также восстановить это сообщение. Для исправления одиночной ошибки бинарного кода, который состоит из n_и символов, несущих информацию, и n_к контрольных (избыточных) символов, расчет количества символов в коде производится по формуле:

 

                                            n = n_и+ n_к .                                        (2.1)

 

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

 

                                            2ⁿ_к ≥ n + 1.                                    (2.2)

 

Тогда, согласно (2.2):

                                  2ⁿ = 2ⁿ_к⁺ⁿ_и = 2ⁿ_к ⋅ 2ⁿ_и.                           (2.3)

 

Используя (2.2), запишем:

 

                                 2ⁿ ≥ (n + 1) ⋅ 2ⁿ_и,                                                 (2.4)

 

где 2ⁿ – полное число комбинаций кода.

Отсюда число информационных символов кода, обнаруживающего и корректирующего одиночную ошибку:

 

                                 2nи ≤ 2n /(n + 1).                                                 (2.5)

 

Для вычисления основных параметров кода Хэмминга задается количество либо информационных символов, либо информационных комбинаций N = 2ⁿ_и.

Номера контрольных символов удобно выбирать по закону 2ⁱ, где i = 0, 1, 2, 3,... – натуральный ряд чисел. Номера контрольных символов в этом случае равны 1, 2, 4, 8, 16, 32... Затем определяют значения контрольных коэффициентов (0 или 1), руководствуясь следующим правилом: сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна – значение контрольного коэффициента нуль, в противном случае – единица.

Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты. Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.

2.2.1 Подготовка сообщения.

Пусть необходимо закодировать и передать без ошибок сообщение «habr». Для кодирования данного сообщения при помощи Кода Хэмминга необходимо представить его в бинарном виде. Для этого используем таблицу ASCII.

На данном этапе необходимо определиться с длиной информационного слова, то есть длиной строки из нулей и единиц. Пусть длина нашего слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит (таблица 2.4), которые будут потом кодироваться отдельно друг от друга. Так как один символ занимает в памяти 8 бит (таблица 2.2), то в одно кодируемое слово помещается ровно два ASCII символа (таблица 2.3).

 

Таблица 2.2 – Бинарные строки исходного сообщения

Символ	Код ASCII	2-ый код
h	68	01000100
a	61	00111101
b	62	00111110
r	72	01001000

 

Длину сообщения можно брать равной 8, 16, 32 бит.

Таблица 2.3 – Таблица символов ASCII

10-й код	2-ый код	ASCII	10-й код	2-ый код	ASCII	10-й код	2-ый код	ASCII
0	00000000	NUL	10	00001010	LF**	20	00010100	DC4
1	00000001	SOH	11	00001011	VT	21	00010101	NAK
2	00000010	STX	12	00001100	FF	22	00010110	SYN
3	00000011	ETX	13	00001101	CR**	23	00010111	ETB
4	00000100	EOT	14	00001110	SO	24	00011000	CAN
5	00000101	ENQ	15	00001111	SI	25	00011001	EM
6	00000110	ACK	16	00010000	DLE	26	00011010	SUB
7	00000111	BEL	17	00010001	DC1	27	00011011	ESC
8	00001000	BS**	18	00010010	DC2	28	00011100	FS
9	00001001	TAB**	19	00010011	DC3	29	00011101	GS

Продолжение таблицы 2.3

10-й код	2-ый код	ASCII	10-й код	2-ый код	ASCII	10-й код	2-ый код	ASCII
30	00011110	RS	64	01000000	@	97	01100001	a
31	00011111	US	65	01000001	A	98	01100010	b
32	00100000	space	66	01000010	B	99	01100011	c
33	00100001	!	67	01000011	C	100	01100100	d
34	00100010	"	68	01000100	D	101	01100101	e
35	00100011	#	69	01000101	E	102	01100110	f
37	00100101	%	70	01000110	F	103	01100111	g
38	00100110	&	71	01000111	G	104	01101000	h
39	00100111	'	72	01001000	H	105	01101001	i
40	00101000	(	73	01001001	I	106	01101010	j
41	00101001	)	74	01001010	J	107	01101011	k
42	00101010	*	75	01001011	K	108	01101100	l
43	00101011	+	76	01001100	L	109	01101101	m
44	00101100	,	77	01001101	M	110	01101110	n
45	00101101	-	78	01001110	N	111	01101111	o
46	00101110	.	79	01001111	O	112	01110000	p
47	00101111	/	80	01010000	P	113	01110001	q
48	00110000	0	81	01010001	Q	114	01110010	r
49	00110001	1	82	01010010	R	115	01110011	s
50	00110010	2	83	01010011	S	116	01110100	t
51	00110011	3	84	01010100	T	117	01110101	u
52	00110100	4	85	01010101	U	118	01110110	v
53	00110101	5	86	01010110	V	119	01110111	w
54	00110110	6	87	01010111	W	120	01111000	x
55	00110111	7	88	01011000	X	121	01111001	y
56	00111000	8	89	01011001	Y	122	01111010	z
57	00111001	9	90	01011010	Z	123	01111011	{
58	00111010	:	91	01011011	[	124	01111100	|
59	00111011	;	92	01011100	\	125	01111101	}
60	00111100	<	93	01011101	]	126	01111110	~
61	00111101	=	94	01011110	^	127	01111111	Del
62	00111110	>	95	01011111	_
63	00111111	?	96	01100000	‘

 

Используя таблицу 2.3, закодируем исходное сообщение с помощью кода ASCII и получим две информационные последовательности, состояцих из 16 бит каждая (таблица 2.4).

 

Таблица 2.4 – Два информационных слова исходного сообщения

Информационное слово «ha»		Информационное слово «br»
h	a	b	r
01000100	00111101	00111110	01001000

 

2.2.2 Кодирование сообщения.

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

Для кодирования каждого информационного слова необходимо добавить контрольные биты, которые являются позициями в строго определенных местах последовательности, т.е номера позиций, равных степени двойки. Для полуслова в 8 бит позициями контрольных бит будут служить 1,2,4,8 и контрольных бит будет 4.

Для информационного слова в 16 бит позициями контрольных бит будут служить 1,2,4,8,16 и контрольных бит будет 5.

Для двойного слова в 32 бита позициями контрольных бит будут служить 1,2,4,8,16,32 и контрольных бит будет 6.

В примере используется деление на слова по 16 бит, они выделены красным в таблице 2.5. Длина всего сообщения увеличилась на 5 бит. До вычисления контрольных бит им присваивается значение «0».

 

Таблица 2.5 – Добавление контрольных бит

Информационное слово «ha»		Информационное слово «br»
h	a	b	r
00 0 0 100 0 0100 001 0 11101		00 0 0 011 0 1110  010 0 01000

 

2.2.3 Вычисление контрольных бит.

Значение каждого контрольного бита зависит от значений информационных бит, которые они контролируют: контрольный бит с номером «N» контролирует все последующие «N» биты через каждые «N» бит, начиная с позиции «N». Составим таблицу 2.6 контрольных бит, в которой значением «Х» будут обозначены позиции контролируемых битов.

 

Таблица 2.6 – Таблица контролируемых битов

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	Кол-во ед.
0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	1	1	1	0	1
х		х		х		х		х		х		х		х		х		х		х	5
	х	х			х	х			х	х			х	х			х	х			4
			х	х	х	х					х	х	х	х					х	х	3
							х	х	х	х	х	х	х	х							2
															х	х	х	х	х	х	4

 

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

Если это число четное, то ставим «0», если нечетное - «1».

Согласно таблице 2.6, составим последовательность контролируемых бит (таблица 2.7).

 

Таблица 2.7 – Вычисление контрольных бит

Информационное слово «ha»		Информационное слово «br»
h	a	b	r
10 0 1 100 0 0100 001 0 11101		1 0 0 1 011 0 1110 010 0 01000

 

2.2.4 Декодирование сообщения и исправление ошибок.

Пусть первая часть сообщения пришла с ошибкой в 11 бите (таблица 2.8).

Таблица 2.8 – Ошибка в сообщении

Информационное слово «ha»
h	a
10 0 1 100 0 0100 001 0 11101
10 0 1 100 0 01 1 0 001 0 11101

 

Для нахождения и исправления ошибки необходимо заново рассчитать контрольные биты и сравнить их с вычисленными ранее битами. Для этого составим таблицу 2.9 по закодированной последовательности с ошибкой (таблица 2.8).

 

Таблица 2.9 – Таблица контролируемых битов

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	Кол-во ед.
1	0	0	1	1	0	0	0	0	1	1	0	0	0	1	0	1	1	1	0	1
х		х		х		х		х		х		х		х		х		х		х	7
	х	х			х	х			х	х			х	х			х	х			5
			х	х	х	х					х	х	х	х					х	х	4
							х	х	х	х	х	х	х	х							3
															х	х	х	х	х	х	4

 

Получили последовательность контрольных бит уже декодированной последовательности с ошибкой (таблица 2.10).

 

Таблица 2.10 – Последовательность при декодировании сообщения

Информационное слово «ha»
h	a
11 0 0 100 1 01 1 0 001 0 11101

Проверяем соответствие контролируемых бит в таблице 2.11 с таблицей 2.6.

 

Таблица 2.11 – Таблица контролируемых битов после дешифровки и проверки битов

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	поз	ед
1	1	0	0	1	0	0	1	0	1	1	0	0	0	1	0	1	1	1	0	1
х		х		х		х		х		х		х		х		х		х		х	1	7
	х	х			х	х			х	х			х	х			х	х			2	6
			х	х	х	х					х	х	х	х					х	х	4	3
							х	х	х	х	х	х	х	х							8	4
															х	х	х	х	х	х	16	4

 

Исходя из сравнения таблиц 2.11 и 2.6 видно, что контролируемые биты под номерами 1,2,8 не совпадают. Сложив номера позиций неправильных контрольных бит 1+2+8 = 11, получим позицию ошибочного бита.

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

 

2.3 Контрольные вопросы

1 Объяснить методику построения кода Хемминга.

2 Что такое кодирование?

3 Что такое контрольный бит и как его определить?

4 Что такое помехоустойчивые коды? Для чего вводится избыточность?

5 Что такое блочные коды?

6 Как построить кодовые слова в коде Хэмминга?

7 Как определить общее число элементов кодовых комбинаций кодов Хэмминга для двоичных последовательностей?

8 Как определить количество контрольных бит в коде Хемминга?

9 Как исправить ошибку в коде Хемминга?

10 Сколько ошибок может исправлять код Хемминга?