Методическое пособие Теория информации-2

Вероятность 8 = 0.09. Данная вероятность впервые участвует в четвертом суммировании, причём из пары вероятностей это наименьшее значение, следовательно, коду присваивается 0. Суммарная вероятность данной пары равняется 0.20 и участвует в суммировании через один столбец, причём из пары она наибольшая. В связи с этим присваиваем коду единицу, получая 10.

Суммарная вероятность данной пары равняется 0.37 и участвует в последнем суммировании через один столбец, причём из пары она наименьшая. В связи с

этим присваиваем коду ноль, получая итоговый код 010.

Вероятность = 0.35. Данная вероятность впервые участвует в

предпоследнем суммировании, причём из пары она имеет наибольшее значение, следовательно, коду присваивается 1. Суммарная вероятность данной пары равняется 0.63. Это наибольшее значение в последнем суммировании,

следовательно, коду присваивается ещё одна единица – 11.

Энтропия найденного кода:		= 2.75 символ. .
						дв ед
Средняя длина кодового слова = 2.82. При этом среднее число нулей:
				=*
# 0 =				μ	= 1.19,
а вероятность их появления:	0	= # 0			= 0.423.
Аналогично среднее	число		единиц равно 1.63, а вероятность их

появления – 0.578. Таким образом, полученный код близок к оптимальному.

. Рассмотрим процедуру эффективного кодирования двух

Пример > = 0.9 > = 0.1

сообщений и с вероятностями и по методу Хаффмана: отдельных сообщений; сообщений, составленных по два в группе;

сообщений, составленных по три в группе. Сравним коды по средней длине кодового слова , по скорости передачи ?@ и по избыточности ?, если длительности кодовых символов одинаковы и равны τ = 10BC D.

141

Энтропия источника сообщений будет равна			,
	= −0.9 log 0.9 − 0.1 log 0.1 = 0.469 собщение. .
		дв ед

а средняя длина кодового символа при условии, что сообщению
присваивается 1, а сообщению			> – ноль:
		= 0.9 ∙ 1 + +0.1 ∙ 1 = 1
Скорость передачи будет равна:							дв.сед.
			0.469
?@ =		H̅	= 10BC	= 469000						,
что составляет 46.9 % от пропускной способности канала										. Избыточность
кода будет равна избыточности источника сообщений:										J = K
? =	%L		−	=	1 − 0.469			= 0.531.
		%L				1
Для повышения	эффективности			кода		перейдём к				кодированию групп

сообщений. В табл. 6.4 представлено кодирование пар сообщений методом Хаффмана.

Таблица 6.4

Кодирование групп сообщений (по два в группе)

Сообщение			Объединение сообщений				Код	Длина кодового
/	/							слова	-
		0.81		0.81		0.81	1	1
		0.09		0.10		0.19	00	2
/	0	0.09		0.09			011	3
0	0	0.01					010	3
0	/

Средняя длина кодового слова, приходящаяся на одно сообщение:
1			+ 3 ∙ 0.09 + 3 ∙ 0.01 = 0.645
= 2 1 ∙ 0.81 + 2 ∙ 0.09
Скорость передачи:
?@ =	=	0.469 BC = 727000		дв.сед.	,
H̅		0,645	∙ 10
			142

что составляет 72.7 % от максимально возможной скорости передачи.

Вероятности появления кодовых символов 0 и 1:

0 = 2 ∙ 0.09 + 0.09 + 2 ∙ 0.01 = 0.23 2 ∙ 0.645

1 = 1 ∙ 0.81 + 2 ∙ 0.09 + 0.01 = 0.77 2 ∙ 0.645

Энтропия кода:

= −0.23 ∙ log 0.23 − 0.77 ∙ log 0.77 = 0.778

Избыточность кода:

? = 1 − = 0.222

Перейдем к кодированию групп сообщений, содержащих по три сообщения в группе (см. табл. 6.5).

Таблица 6.5

Кодирование групп сообщений (по три в группе)

												Длина
Сообщение				Объединение сообщений							Код	кодового
/	/	/										слова	-
			0.729	0.729	0.729	0.729	0.729		0.729	0.729	1	1
			0.081	0.081	0.081	0.081	0.109		0.162	0.271	011	3
/	/	0	0.081	0.081	0.081	0.081	0.081		0.109		010	3
/	0	/	0.081	0.081	0.081	0.081	0.081				001	3
0	/	/	0.009	0.010	0.018	0.028					00011	5
/	0	0	0.009	0.009	0.010						00010	5
0	/	0	0.009	0.009							00001	5
0	0	/	0.001								00000	5
0	0	0

Средняя длина кодового слова, приходящаяся на одно сообщение:

= 0.533

	Скорость передачи:			дв.сед.
	?@ =		= 880000		,
		H̅
			143

что составляет 88.0 % от максимально возможной скорости передачи.

Вероятности появления кодовых символов 0 и 1:

0 = 2 ∙ 0.09 + 0.09 + 2 ∙ 0.01 = 0.32 2 ∙ 0.645

1 = 1 ∙ 0.81 + 2 ∙ 0.09 + 0.01 = 0.68 2 ∙ 0.645

Энтропия кода:

= 0.904

Избыточность кода:

? = 1 − = 0.096

Отметим, что если кодировать группы по 4 и более сообщений, то мы ещё более приблизимся к предельным значениям вычисляемых величин. Следует подчеркнуть, что увеличение эффективности кодирования при укрупнении блоков не связано с учётом всё более далёких систематических связей, так как нами рассматривались алфавиты с некоррелированными знаками. Повышение эффективности определяется лишь тем, что набор вероятностей, получающихся при укрупнении блоков, можно делить на более близкие по суммарным

вероятностям подгруппы.

Коды, получаемые в результате применения методики Шеннона-Фано

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

известна вероятность их появления .

Рассмотрим метод эффективного кодирования при неизвестной

статистике сообщений.

6.1.4. Префиксное кодирование при неизвестной статистике сообщений
		и >
144		и M = 1 − , соответственно,

однако величина заранее неизвестна. Множество всех блоков длины N в

алфавите разбивают на группы, которые имеют одинаковые вероятности при любом . Таких групп будет N + 1.

В нулевой группе отсутствует символ >, она состоит из единственного блока … длиной N, вероятность появления которого .

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

Эта группа состоит из J = N блоков, вероятность каждого из которых равна

B ∙ M.

Группы с номером P состоят из всех блоков длиной N, содержащих P

букв >. Эта группа содержит N блоков, вероятность каждого из которых

BQ ∙ MQ. Универсальный код для каждой группы состоит из двух частей:

префикса и суффикса.

Префикс содержит log N + 1 1 двоичных знаков и указывает, к какой

группе сообщений принадлежит кодируемый блок и кодируется с
использованием равномерных кодов; суффикс содержит							log JQ двоичных
символов и указывает номер блока в группе. Пусть в блоке длиной N символ
встречается	на	местах	R , R>, … , RS, тогда суффиксом для такой
последовательности		будет	являться число		T , выраженное в двоичной
системе исчисления и вычисляемое по формуле:
где JQ –		UB		VB	XB		(6.2)
	биноминальные		коэффициенты,		которые представлены в виде
треугольника Паскаля в табл. 6.6.
Построенный таким образом код будет однозначно дешифрируемым. На
приёмном конце первоначально				по log N + 1		элементам	кода определяют

(префикс), к какой группе принадлежит переданное сообщение, а затем по следующим log JQ элементам (суффикс) определяют, какое именно сообщение передавалось.

1 Производят округление получившегося значения в большую сторону.

145

								Таблица 6.6
Биноминальные коэффициенты (треугольник Паскаля)
0	1Y	0Y	0Y	0Y	0Y	0Y	0Y	0Y
1	1	1	0	0	0	0	0	0
2	1	2	1	0	0	0	0	0
3	1	3	3	1	0	0	0	0
4	1	4	6	4	1	0	0	0
5	1	5	10	10	5	1	0	0
6	1	6	15	20	15	6	1	0
7	1	7	21	35	35	21	7	1

	Пример. Построим префиксный код при неизвестной статистике
сообщений для алфавита, состоящего из двух символов					и > появляющихся
независимо с вероятностями			и M. Примем, что длина кодирующей
последовательности составляет 4 символа N = 4 . Тогда длина префикса будет
равна	log> N + 1 = log> 5 = 2.32 ≈ 3			(округляем в	большую сторону).

Кодирование префикса проводим в соответствии с трёхразрядным равномерным кодом по основанию 2, приведенным в табл. 6.1. Определим следующие величины: количество символов в каждой из групп последовательностей ] ; длину суффиксов для каждой из групп последовательностей; местоположение символов в каждой из последовательностей и вычислим длину префикса T для кодируемых последовательностей через биноминальные коэффициенты в соответствии с

(6.2). Сведём все расчёты в табл. 6.7.

Алгоритм перевода чисел из десятичной системы в двоичную может быть сформулирован следующим образом:

∙десятичное число делят на 2; частное запоминают для следующего шага, а остаток записывают как младший бит двоичного числа;

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

146

∙ если частное равно 0, а остаток равен 1, то расчёт останавливается.

Таблица 6.7

Построение префиксного кода при неизвестной статистике сообщений

	Кодируемые				Номер	Вероят-								Длина					Код
	последова												4	_`a	Y	нет	0	0	0
					1
													^	суффикса		b
	тельности-				группы	ность								С^			Префикс			Суффикс
														8		0	0	0	1	0	0
				>	2			c	∙ M				3	log J8	= 2	1	0	0	1	0	1
		>														3	0	0	1	1	1
	>													c		2	0	0	1	1	0
	>															0	0	1	0	0	0	0
	> >															1	0	1	0	0	0	1
	> >				3		>		∙ M		>		2	log J8	= 3	2	0	1	0	0	1	0
		>	>													4	0	1	0	1	0	0
	> >													>		3	0	1	0	0	1	1
	> >															5	0	1	0	1	0	1
	>	>														3	0	1	1	1	1
	>	>	>		4	∙ M				c			1	log J8	= 2	2	0	1	1	1	0
	>		>	>												0	0	1	1	0	0
	> > >															1	0	1	1	0	1
	>	>	>	>	5								0	8		нет	1	0	0
		>	>	>
T		Отметим особенность построения суффикса путём перевода значения
		в	двоичную систему									исчисления			по	вышеописанному				алгоритму:

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

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

заполняя недостающие поля, располагая полученный код справа и смещаясь справа налево. В табл. 6.7 полученный код суффиксов выделен жирным начертанием, а дополнительно введённые нули такого выделения не имеют. В

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

Пример. Рассмотрим декодирование последовательности. Пусть

147

поступила последовательность 010011 и пусть известна длина префикса, равная трём. Тогда, по префиксу 010 можем определить, что кодирующая последовательность принадлежит к 3 группе, содержащей два символа .

Определим их положение. Зная суффикс 011, определим величину T = 3.

Для J?> определим номер строки во втором столбце, значение биноминального коэффициента в которой не превышает 3. Этому условию отвечает коэффициент Jc> = 3, т.е. R − 1 = 3 R = 4. Определим позицию оставшегося символа . Значение биноминального коэффициента в первом столбце в этом случае не должно превышать 3 − 3 = 0. Этому условию удовлетворяет коэффициент J* = 0, т.е. R − 1 = 0 R = 1. Следовательно, декодируемая последовательность – это > > .

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

6.1.5. Недостатки неравномерного кодирования

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

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

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

148

велико, особенно при появлении блока, вероятность которого мала. Это следует учитывать при выборе длины кодируемого блока.

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

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

6.2. Помехозащитное кодирование

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном и сформулированных им в виде следующих теорем:

1. При любой производительности источника сообщений, меньшей, чем пропускная способность канала связи, существует такой способ кодирования,

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

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

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

149

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

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

посредством которого только обнаруживаются ошибки, носит название обнаруживающего кода. Исправление ошибки при таком кодировании обычно производится путём повторения искажённых сообщений. Запрос о повторении передаётся по каналу обратной связи. Код, исправляющий обнаруженные ошибки, называется исправляющим кодом. В этом случае фиксируется не только сам факт наличия ошибок, но и устанавливается, какие кодовые символы приняты ошибочно, что позволяет их исправить без повторной передачи. Известны такие коды, в которых исправляется только часть обнаруженных ошибок, а остальные ошибочные комбинации передаются повторно.

6.2.1. Коды с обнаружением ошибок

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

Проверки на чётность

Простейший способ кодирования двоичного сообщения для обнаружения ошибок состоит в подсчете числа 1 в сообщении и добавлении ещё одного двоичного символа таким образом, чтобы во всём сообщении содержалось чётное число 1.

В таком коде к N − 1 символам сообщения добавляется -ая позиция для проверки на четность. На приёмном конце производится подсчет числа 1, и

нечётное число 1 во всех N позициях говорит по крайне мере об одной ошибки.

Такой код не позволяет обнаруживать двойные ошибки.

150