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

Доказательство.

Перепишем условия (9) следующим образом:

1	3		5	7			t	0,	t	w0 ;
2	3		6	7			t	0,	t	w1;
4	5		6	7			t	0,	t	w2 ;	(10)
	2	k 1		t				0, t wk	1.
1 . Так как разряды			1,	2 , 4 ,	,	2	k 1	попадают только в одно из
множеств w0 , w1,	, wk 1 ,		то они однозначным образом находятся из
уравнений (10).
			1	3	5			7
			2	3	6			7			(11)
			4	5	6			7

Разряды – степени числа 2 называются контрольными, их k , остальные l k разряды называются информационными. Информационные разряды заполняются произвольным образом, формируя множество кодовых слов, их будет 2l k , контрольные разряды вычисляются по информационным в соответствии с уравнениями (11).

2 . Найдем число контрольных разрядов, если длина кодового

слова равна l .
l 2k	1 или 2k	l 1, где k минимальное натуральное число,

удовлетворяющее этому неравенству. Это условие можно записать следующим образом:

	k		min		r : 2r	l	1 min	r : r log	2	(l 1) ,
			N				N
что, по определению, означает
						k	log2 (l	1) .
3 . Докажем, что код Хэмминга исправляет одну ошибку типа
замещения.
Пусть	1	2		l	посланное кодовое слово, принадлежащее коду
Хэмминга,	1	2	l		это же слово, полученное при передаче, и пусть

ошибка произошла в q -том разряде:

23

						l .
1 2	q	l	1 2	q

Исправить ошибку означает установить номер разряда с ошибкой, то есть найти, чему равно q .

По полученному слову

1

2

l

найдем числа c0 ,c1,

,ck

1 :

c0

t ,

c1

t ,

ck 1

t ,

t w0

t

w0

t wk 1

где

– сумма по модулю 2.

Утверждается, что число ck

1ck

2

c0

– двоичный код числа q .

Действительно, пусть q

qk 1qk

2

q0

2 , покажем, что q j

cj .

Пусть q j

0,

тогда число q , то есть номер разряда с ошибкой,

не входит в множество wj и

cj

t

t

0 .

t wj

t

wj

Пусть q j

1, тогда число q (номер разряда с ошибкой) входит в

множество wj и

cj

t

t

1

1.

t wj

t

wj

Таким образом,

q j

cj

и номер разряда с ошибкой q ck 1ck 2

c0 2 .

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

a1, a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10 .

Решение. Найдем число информационных разрядов для

кодирования 10 букв. Их, очевидно, должно быть 4: 24

16 , но трех

информационных недостаточно,

так как

23

8.

Информационными

разрядами

будут

3 ,

5 ,

6 , 7 ,

контрольными

разрядами

будут

1,

2 , 4 ,

что

согласовывается

с

формулой

log2 8

3.

Длина

кодового слова равна 7, все числа от 1 до 7 кодируются трехразрядными двоичными кодами t2t1t0 . Дальше осталось

произвольным образом заполнить информационные разряды и найти по формулам (11) контрольные

24

							Таблица 2
	1	2	3	4	5	6		7
a1	1	0	1	1	0	1		0
a2	0	1	1	1	1	0		0
a3	1	1	0	0	1	1		0
a4	1	0	0	0	0	1		1
a5	0	0	1	0	1	1		0
a6	1	0	1	0	1	0		1
a7	0	0	1	1	0	0		1
a8	0	0	0	1	1	1		1
a9	0	1	0	0	1	0		1
a10	1	1	1	0	0	0		0

Буква a5 произошла

1 2 3 4 5

закодировалась словом 0010110, пусть при передаче

		ошибка	в	пятом	разряде,	то	есть
6	7	0010010 .	Найдем номер		разряда	с ошибкой по

полученному слову.

c0	1	3	5	7	1
c1	2	3	6	7	0
c2	4	5	6	7	1
Номер разряда с ошибкой равняется			c2c1c0 2		101 2 5.
Часто даются кодовые		слова	некоторого равномерного кода,

состоящие только из информационных разрядов, которые надо закодировать кодом Хэмминга.

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

1	2	3	4	5	6	7	8	9	10	11	12 .
		1		1	0	1		1	1	0	0
Контрольными разрядами оказались							1,	2 ,	4 , 8 .	Числа от 1 до 12

кодируются четырехзначными двоичными кодами и образуют 4 подмножества: w0 , w1, w2 , w3 .

25

w0		1,3,5,7,9,11 ,				w1		2,3,6,7,10,11 ,
w2			4,5,6,7,12 ,			w3		8,9,10,11,12
1		3	5	7	9	4	1	1	1	1	0	0
2		3	6	7	10	11	1	0	1	1		0	1
4		5	6	7	12	1	0	1	0	0
8		9	10	11	12	1	1	0	0	0.
Заполнив контрольные разряды, получим кодовое слово в коде
Хэмминга:
1	2	3	4	5	6	7	8	9		10		11	12 .
0	1	1	0	1	0	1	0	1		1		0	0
Пример	11.		Пусть		10101000110011					–		кодовое слово,

закодированное кодом Хэмминга, полученное в процессе передачи. Найдем номер разряда с ошибкой, если ошибки нет, то метод Хэмминга даст в качестве такого номера 0.

	Решение. Длина слова равна 14, все числа от 1 до 14
кодируются четырехразрядными двоичными кодами t3t2t1t0																		и
образуют 4 подмножества:
		w0		1,3,5,7,9,11,13 ,						w1	2,3,6,7,10,11,14			,
		w2		4,5,6,7,12,13,14				,		w3	8,9,10,11,12,13,14
1	2		3	4	5	6	7	8	9	10	11	12	13	14	,
1	0	1		0	1	0	0	0	1	1	0	0	1	1
	c0			t	1 1 1 0 1 0 1 1
		t	w0
	c1			t	0 1 0 0 1 0 1 1
		t	w1
	c2			t	0 1 0 0 0 1 1 1
		t	w2
	c3			t	0 1 1 0 0 1 1 0 .
		t	w3
Номер разряда с ошибкой q								0111 2		7 , следовательно,								1,
														7	7
было послано слово
1	2		3	4	5	6	7	8	9	10	11	12	13	14	,
1	0	1		0	1	0	0	0	1	1	0	0	1	1

26

уберем из него все контрольные разряды, найдем кодовое слово,

состоящее только из информационных разрядов:

1101110011.

5. Задачи и упражнения

1.Выяснить, обладает ли код K , заданный набором кодовых слов, взаимно однозначным.

1.1.K a, ab, cab, baac ;

1.2.K a, b, aab ;

1.3.K cab, abc, bcc, abca, abcb ;

1.4.K a, ba, bb, bbba ;

1.5.K ab, bb, ba, aab ;

1.6.K ac, c, bb, abc, bac, abb, abcb ;

1.7.K a, ba, cab, acb ;

1.8.K a, ba, bba, ..., (b)n a, ... ;

1.9.K a, ba, ..., b(a)n , ... .

Приведем решения некоторых задач.

Решение задачи 1.1.

Код K не является префиксным, так как кодовое слово ab начинается с кодового слова a . Код K также не является суффиксным, так как кодовое слово cab заканчивается кодовым словом ab .

Граф G , соответствующий коду K , показан на рис. 12. Существует контур, проходящий через вершину . Выписывая слова, приписанные вершинам и дугам контура, получаем слово, декодируемое неоднозначно: a baac ab ab a a cab.

Рис. 12

27

Решение задачи 1.2.
Код K не является префиксным,	потому что кодовое слово a
является началом кодового слова aab ,	а кодовое слово b его концом,
поэтому этот код не является суффиксным.
Граф G показан на рис. 13. Граф содержит петлю		. Код не

является однозначно декодируемым: слово aab допускает двоякую расшифровку: a a b aab

Рис. 13
Решение задачи 1.3.
Код суффиксный, нет дуги входящей в вершину	,
следовательно, однозначно декодируемый. Граф G показан	на
рис. 14.

Рис.14

2. Выяснить, является ли код K с кодирующим алфавитом 0,1, 2 однозначно декодируемым:

2.1.K 01, 201, 112, 122, 0112 ;

2.2.K 001, 021, 102, 201, 001121, 01012101 ;

2.3.K 0, 01, 0010001001 ;

2.4.K 20, 01202, 22, 2001, 2012010, 10201121, 1112 ;

2.5.K 01, 011, 100, 2100, 101210, 001210 ;

2.6.K 01, 011, 100, 2100, 10110, 00112 ;

2.7.K 01, 12, 021, 0102, 10112 ;

2.8.K 01, 12, 111, 0102, 10112, 01112 ;

28

2.9.K 01, 12, 012, 0102, 020112 ;

2.10.K 01, 10, 210, 121, 0210, 0112 ;

2.11.K 01, 10, 210, 201, 0210, 011022, 2221 ;

2.12.K 01, 10, 210, 201, 0210, 011022, 221 ;

2.13.K 01, 10, 210, 201, 0210, 011022 ;

2.14.K 01, 12, 011, 01210, 20120, 2011220 ;

2.15.K 01, 12, 011, 01210, 201120, 2011220 ;

2.16.K 000, 0100, 10, 1001, 0010010 ;

2.17.K 01, 12, 01121, 21201 .

3. Выяснить, является ли слово P в алфавите 0,1, 2 кодом сообщения в кодировании, задаваемом схемой:

1 10

2 12 : 3 012

4 101

5 2100

Если да, то выяснить, является ли слово P кодом ровно одного сообщения.

3.1.P 10120121012100;

3.2.P 0121001210201;

3.3.P 1010122100;

3.4.P 101212101012 ;

3.5.P 1012101201210012;

3.6.P 120120121001210;

3.7.P 12101210012;

3.8.P 1010012100101.

4. Выбрать максимальное по числу элементов подмножество M множества M с условием, что двоичные разложения наименьшей длины чисел из M представляют собой префиксный код:

4.1.M 1,5,6,7,12,13,17 ;

4.2.M 1,3,6,8,10,13,19,33,37 ;

29

4.3.M 2,6,7,9,12,15,18,35,36,37 ;

4.4.M 1, 2,5,8,9,10,13,15 ;

4.5.M 2,3,7,8,11,12,13,14 ;

4.6.M 3,5,6,9,10,13,17 ;

4.7.M 1, 2,5,8,9,12,13,14 ;

4.8.M 5,6,7,8,9,10,11,12,13 ;

4.9.M 4,6,7,10,13,15, 20, 23, 25 ;

4.10.M 5,7,9,10,12,14,17, 23, 24 .

Приведем решение задачи 4.1.

Рассмотрим двоичные представления чисел из множества M : 1,101,110,111,1100 1101,10001 . Надо выбрать максимальное

подмножество, чтобы эти двоичные представления образовали префиксный код. Если 1 войдет в M , то все остальные двоичные представления чисел не войдут. Если же 110 взять в качестве

кодового	слова,	то M	101,110,111,10001 . Возьмем в качестве
кодового	слова	101,	тогда M	101,111,1100,1101,10001 . Это

подмножество M и будет максимальным.

5. Для кода K найти слово минимальной длины, декодируемое неоднозначно:

5.1.K 10, 01, 12, 012, 2100, 12011, 12010 ;

5.2.K 0, 101010, 01010101 ;

5.3.K 0, 10 k 1 , 01 k

5.4. K	010,101, 01010,	01 k ,	k	3s	1;
5.5. K	0, 10 k , 01 m ;
5.6. K	001, 011,100,110, 1100 k ,			k	3s ;
5.7. K	0,10,11, 101 k	;
5.8. K	01,10,11, 110 k	, k	2s ;

30

5.9. K	0 k , 0 m ;
5.10. K	01 k 0, 0 10 k	1 ,1 01 m ;
5.11. K	0, 0 k 1,1 0 m	;

5.12.K 01 k , 10 m , 01 s 0 ;

5.13.K 01 k , 01 k 1 0, 10 k 11, 10 k 1 ;

5.14.K 0, 0 k 1 0 m , 1 0 m 2 1 ;

5.15.K 01 k , 10 k 1 , 01 k 0 ;

5.16. K 01 k , 01 k 1 0, 10 k 2 .

6. Построить двоичный префиксный код K с заданной последовательностью L длин кодовых слов:

6.1.L 1, 2, 3, 3 ;

6.2.L 1, 2, 4, 4, 4, 4 ;

6.3.L 2, 2, 3, 3, 4, 4, 4, 4 ;

6.4.L 2, 2, 2, 4, 4, 4 ;

6.5.L 2, 2, 3, 4, 4 ;

6.6.L 2, 3, 3, 3, 4, 4 .

7. С помощью неравенства Макмиллана выяснить, может ли набор чисел L быть набором длин кодовых слов однозначно декодируемого кода в q – значном алфавите:

7.1. L	1, 2, 2, 3	, q	2 ;
7.2. L	1, 2, 2, 3	, q	3;
7.3. L	2, 2, 2, 4, 4, 4 , q 2;
7.4. L	1, 2, 2, 2, 3, 3, 3, 3 , q			3 ;
7.5. L	1, 1, 2, 2, 3, 3, 3 , q			3 ;
7.6. L	1, 1, 1, 2, 2, 2, 2, 3 , q			4 .

31

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

8.1.L 1, 2, 3, 4, 5, 5 ;

8.2.L 2, 2, 2, 3, 3 ;

8.3.L 2, 2, 3, 3, 4, 4 ;

8.4.L 1, 2, 4, 4, 4, 4 ;

8.5.L 2, 2, 2, 3, 4, 4

Рассмотрим решение задачи 8.5.

Построим кодовое дерево для кода K , на каждом шаге деля вероятности пополам (рис. 15).

			Рис. 15
	Из рисунка ясно, что P	1	;	1	;	1	;	1	;		1	;		1	.
		4		4		4		8		16			16

9. Выяснить, существует ли двоичный код с минимальной избыточностью, обладающий заданной последовательностью L длин кодовых слов:

9.1.L 2, 3, 3, 3 ;

9.2.L 3, 3, 3, 3 ;

9.3.L 1, 3, 3, 3, 3 ;

9.4.L 1, 2, 3, 4 ;

32