Васюков В_Н_ Теория электрической связи_

8.3. Пропускная способность дискретного канала

233

Приведем выражение (8.6) к более удобному виду, для чего подставим в него формулы для вычисления безусловной и совместной энтропии.

L M

L M

I(

) p(

i ,

j )log p(

i ) p(

i ,

j )log p( j )

i 1 j 1

i 1 j 1

L

M

L

M

p( i ,

j )

p(

i ,

j )log p(

i ,

j ) p(

i ,

j )log

. (8.7)

p( i ) p(

j )

i 1 j 1

i 1 j 1

8.3.ПРОПУСКНАЯ СПОСОБНОСТЬ ДИСКРЕТНОГО КАНАЛА

Если источник вырабатывает символы со скоростью vп 1/Tп , где Tп – время передачи одного символа, то производительность источника определяется как H ' Hvп H /Tп и имеет размерность

бит/с. Поскольку количество информации на один символ составляет при передаче по каналу величину I( ) , определяемую вы-

ражением (8.7), скорость передачи информации по каналу

I '(	)	I(	)	бит/с.
			Tп

Рассмотрим выражение (8.5), которое характеризует количество информации на символ, передаваемое по дискретному каналу связи, на входе которого действует источник с алфавитом , а на

выходе образуются символы из алфавита		. Заметим, что энтро-
пия H( ) определяется только источником входных символов, в
то время как H ( ) , H ( ) и H (	)	зависят также от свойств

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

лов). Максимальная скорость передачи информации, которая может быть достигнута для данного канала, называется его пропу-

скной способностью

C max I '(		)	1	max I(	) бит/с.
P( A)			Tп P( A)

234	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

Заметим, что нахождение пропускной способности реального канала связи представляет собой сложную задачу. В простейшем случае бинарного канала без помех (см. пример 8.2) пропускная

способность численно равна скорости модуляции vп 1/Tп .

Очевидно, скорость передачи информации по определению не может быть больше пропускной способности канала. Можно рассматривать также пропускную способность канала на символ [10]

Cсимв max I(	) .
P( )

Пример 8.3. Найдем пропускную способность стационарного симметричного канала без памяти. Как было указано в разд. 7, для такого канала входной и выходной алфавиты совпадают

k

k , k 1, K , а вероятность ошибки одинакова для всех симво-

лов и при этом выполняется условие

p

k

p

(K 1),

если

l k,

l

ош

1 pош ,

если

l k,

Найдем согласно (8.4) условную энтропию

|

K

K

H (

) p( i ,

j )log p(

j | i )

i 1 j 1

K

K

p(

i ) p(

j |

i )log p(

j |

i )

i 1

j 1

K

K

p

p

p(

i

)

ош

log

ош

(1

p

)log(1 p

)

i 1

j 1 K

1

K 1

ош

ош

j i

(1 p

)log(1 p

) p log

pош

.

(8.8)

ош

ош

ош

K 1

В последнем преобразовании учтено, что выражение в квадратных скобках не зависит от i , поэтому сумма вероятностей p( i ) ,

равная 1, как сомножитель исчезает, а суммирование в квадратных скобках по j i эквивалентно умножению на (K 1) . Очевидно,

выражение (8.8) не зависит от распределения вероятностей передаваемых символов, поэтому выражение (8.5)

I( , ) H ( ) H ( | )

8.4. Кодирование источника

235

достигает максимума, когда максимальна энтропия H ( ) , что оз-

начает равновероятность символов выходного алфавита, а это, в свою очередь, имеет место, когда равновероятны символы входного алфавита (что очевидно в силу симметрии канала). Таким образом, пропускная способность стационарного симметричного канала без памяти (на символ) равна

Cсимв log K (1 pош )log(1 pош ) pош log Kpош1 . ◄

8.4. КОДИРОВАНИЕ ИСТОЧНИКА

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

Hmax H .

Hmax

Для независимых источников (источников без памяти) избыточность равна нулю (а энтропия максимальна) при равновероятности символов. Для источников с памятью избыточность тем больше, чем выше степень статистической зависимости символов в сообщении, при этом неопределенность относительно очередного символа в сообщении уменьшается, соответственно уменьшается и количество информации, переносимое этим символом. Например, в естественном английском языке после буквы q всегда следует буква u, поэтому при передаче такого текста буква u, следующая за буквой q, информации не несет. (В реальном английском тексте могут встречаться аббревиатуры, например, «QWERTY», а также иноязычные, например французские слова, для которых указанная закономерность не выполняется.)

Объем алфавита источника и количество различных символов, передаваемых по каналу (канальных символов), могут не совпа-

дать. В таких случаях один символ источника представляется (ко-

дируется) последовательностью из нескольких кодовых символов (кодовым словом, или кодовой комбинацией). Если для всех сим-

волов источника длина кодовых слов одинакова, код называют

равномерным, в противном случае – неравномерным. Примером равномерного кода является код Бодó, смысл которого состоит в представлении каждой из букв алфавита двоичным числом фиксированной разрядности (например, для алфавита из 32 символов,

236 8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

включающего 26 латинских букв и знаки препинания, достаточно

пятиразрядного кода Бодо). При передаче сообщений неравномерным кодом говорят о средней длине кодового слова (усреднение

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

Шеннону принадлежит следующая теорема (доказательство см., например, в [10]), называемая основной теоремой о кодирова-

нии в отсутствие шумов.

ТЕОРЕМА. Среднюю длину кодовых слов для передачи символов источника при помощи кода с основанием m можно как

угодно приблизить к величине H( ) / log m .

Смысл теоремы состоит в том, что она определяет нижнюю границу длины кодовых слов и устанавливает принципиальную возможность достичь этой границы, однако она не указывает спо-

собов достижения.

Пример 8.4. Если источник имеет объем алфавита 32, то при равновероятных символах его энтропия равна 5 битам. Тогда для двоичного кода наименьшая средняя длина составляет 5, следовательно, пятизначный код Бодо является оптимальным кодом. Однако при неравных вероятностях символов энтропия источника меньше чем 5 бит (избыточность источника отлична от нуля), сле-

довательно, можно найти код со средней длиной кодового слова меньше пяти и таким образом повысить скорость передачи ин-

формации. Текст на русском языке, например, имеет энтропию около 2,5 бит, поэтому путем соответствующего кодирования можно увеличить скорость передачи информации вдвое против пятиразрядного равномерного кода Бодо (чтобы использовать код Бодо для передачи русского текста, можно отождествить буквы «е» и «ѐ», а также «ь» и «ъ»). ◄

Практическое значение теоремы Шеннона заключается в возможности повышать эффективность систем передачи информации (систем связи) путем применения экономного кодирования (коди-

рования источника).

Очевидно, что экономный код должен быть в общем случае не-

равномерным. Общее правило кодирования источника (без памяти)

состоит в том, что более вероятным символам источника ставятся в соответствие менее длинные кодовые слова (последователь-

ности канальных символов).

Пример 8.5. Известный код Морзе служит примером неравномерного кода. Кодовые слова состоят из трех различных символов:

точки (передается короткой посылкой), тире ― (передается относительно длинной посылкой) и пробела (паузы). Наиболее частой

8.4. Кодирование источника

237

букве в русском тексте – букве «е» – соответствует самое короткое кодовое слово, состоящее из одной точки, относительно редкая буква «ш» передается кодовым словом из четырех тире, разделенных пробелами, и т.д. ◄

Кодирование источника по методу Шеннона – Фано

Принцип построения кода Шеннона – Фано состоит в упорядочении всех символов алфавита (назовем их для краткости «буквами») по убыванию вероятностей. Затем все буквы делятся на две (неравные в общем случае) группы так, что сумма вероятностей букв для обеих групп одинакова или примерно одинакова, и в качестве первого символа кодового слова каждой букве первой группы присваивается кодовый символ 0, а каждой букве второй группы – символ 1 (или наоборот). Далее первая и вторая группы делятся на подгруппы в соответствии с принципом равной вероятности, и эта процедура продолжается до тех пор, пока алфавит источника не будет исчерпан. Пример построения кода Шеннона – Фано приведен в табл. 8.1.

		Построение кода Шеннона – Фано								Т а б л и ц а 8.1
Символ и его			Комбинация кодовых символов								Длина
вероятность											комбинации
i	p( i )	1-й		2-й	3-й	4-й	5-й		6-й		i
1	1/4	0		0							2
2	1/4	0		1							2
3	1/4	1		0							2
4	1/8	1		1	0						3
5	1/16	1		1	1	0					4
6	1/32	1		1	1	1	0				5
7	1/64	1		1	1	1	1		0		6
8	1/64	1		1	1	1	1		1		6

На первом шаге процедуры все символы алфавита источника делятся на две группы, причем в первую группу входят символы

1 и 2 , которым соответствует суммарная вероятность 1/2, а во

вторую – все остальные символы. Символам 1 и 2 приписывается в качестве первого кодового символа символ 0, а всем осталь-

238	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

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

впервой группе содержатся всего два символа, которые получают

вкачестве второго кодового символа 0 и 1 соответственно. Таким

образом, символу источника 1 ставится в соответствие кодовое

слово 00, а символу 2 – слово 01. Вторая	группа символов источ-
ника, включающая символы 3 , 4 , 5 и	6 , делится на две час-
ти в соответствии с их вероятностями, при этом символ 3 , кото-

рому соответствует вероятность 1/4, получает в качестве второго символа кодового слова символ 0, а остальные символы источника – символ 1. Далее процесс продолжается до тех пор, пока не останется группа из двух символов – в данном примере это симво-

лы 7 и	8 , – которым присваиваются	кодовые символы 0 и	1.
Необходимо обратить внимание на		следующее свойство	полу-

ченного кода: ни одна кодовая комбинация не является началом ка- кой-либо другой кодовой комбинации (так называемое префиксное правило). Такие коды называются неперекрываемыми (неприводи-

мыми). Декодирование неприводимого кода может быть осуществлено на основе дерева декодирования105 (рис. 8.1), отвечающего некоторому конечному автомату, который переходит из начально-

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

Перед декодированием конечный автомат устанавливается в

начальное состояние НС,		а дальнейшие переходы зависят только
	1	1	1	1		1
						8
1	0	0	0	0		0
НС	3		4	5	6	7
	0

1

2

0

1

Рис. 8.1. Дерево декодирования для кода Шеннона– Фано

(табл. 8.1)

105 Деревом называется граф, не содержащий циклов (замкнутых путей).

8.4. Кодирование источника

239

от поступающих символов кода, при этом все концевые состояния («листья» дерева) соответствуют декодированным символам алфавита источника; по достижении листа автомат переходит вновь в начальное состояние. Поскольку с поступлением последнего кодового символа декодирование кодового слова всегда заканчивается, префиксные коды называют также мгновенными [16]. Существуют однозначно декодируемые коды, не обладающие префиксным свойством и не являющиеся мгновенными, однако их декодирование требует больших объемов памяти декодера и приводит к большим задержкам результата.

Средняя длина кодовой комбинации для построенного кода

8

p( i ) i

i 1

0,75 2 0,125 3 0,0625 4 0,03125 5 0,03125 6 2,469.

Согласно теореме Шеннона при оптимальном кодировании можно достичь средней длины

	8
min H (	) / log 2 p(	i )log p(	i ) 2.469 .
	i 1

Таким образом, построенный код является оптимальным. Так получилось вследствие того, что на каждом шаге процедуры построения кода удавалось разделить символы на группы с равными вероятностями. Заметим, что восемь различных символов источника можно представить восемью комбинациями равномерного двоичного кода (Бодо), при этом длина каждой кодовой комбинации равняется, очевидно, трем. Уменьшение средней длины кодовой комбинации (и, следовательно, увеличение скорости передачи информации) составляет в данном примере около 22 %. Если при делении символов на группы их суммарные вероятности оказываются неравными, выигрыш может быть не столь значительным.

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

p(1) 0,25 0,25 2 0,125 3 0,0625 4 0,03125 (5 6) 0,015625 0,5 . 2,469

240	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

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

Кодирование источника по методу Хаффмена.

Другим широко известным методом кодирования источника является метод Хаффмена106. Процедура кодирования состоит из следующих шагов.

1.Все символы алфавита записываются в порядке убывания вероятностей.

2.Два нижних символа соединяются скобкой, из них верхнему приписывается символ 0, нижнему 1 (или наоборот).

3.Вычисляется сумма вероятностей, соответствующих этим символам алфавита.

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

5.Повторяются шаги 2, 3 и 4 до тех пор, пока не останется ни одного символа алфавита, не охваченного скобкой.

Скобки в совокупности образуют дерево. Код Хаффмена для некоторого символа алфавита находится путем последовательной записи нулей и единиц, встречающихся на пути от корня дерева (корню соответствует суммарная вероятность 1) до листа, соответ-

ствующего данному символу. Полученное дерево, очевидно, является деревом декодирования.

Для примера, показанного на рис. 8.2, получаются следующие

кодовые		комбинации:			1	11;	2	01;	3	101:	4 100;
5	001;	6	0000;	7	00011;		8	00010.		длина	кодового
	Энтропия		алфавита		H (	) 2,628		. Средняя
слова		n
		pi i 0,3 2 + 0,2 2 + 0,15 3 + 0,15 3 + 0,1 3 +
		i 1
			+ 0,04		4 + 0,03 5 + 0,03 5 = 2,66.

106Доказана оптимальность кода Хаффмена в смысле наименьшей средней длины кодовых слов [16].

8.4. Кодирование источника

241

Следовательно, код не оптимален, но очевидно, что он довольно близок к оптимальному. Для сравнения: равномерный код для этого случая имеет среднюю длину кодового слова 3 (совпадающую для равномерного кода с длиной каждого кодового слова).

1:											1
0,3
2:																		1
0,2														1
3:						1													НС
0,15
										0
4:																		0
0,15					0
5:												1
0,1
6:													0
0,04								0
7:												0
0,03				1
8:							1
0,03		0

Рис. 8.2. Дерево декодирования для кода Хаффмена

Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесенное к средней длине кодового слова

p(1) 2 0,3 0,2 2 0,15 0,15 0,1 2 0,03 0,03 0,541. 2,66

Неоптимальность кода проявляется в неравенстве вероятностей кодовых символов (0,541 для 1 и 0,459 для 0). Избыточность кода, как легко видеть, равна 0.005.

242	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

ЗАМЕЧАНИЯ

1. Из рассмотренных примеров не должно составиться ложное впечатление, будто код Шеннона – Фано оптимален, а код Хаффмена – нет. Оптимальность кода Шеннона – Фано в рассмотренном примере объясняется специально подобранными вероятностями символов, так, что на каждом шаге вероятности делятся ровно пополам.

2. В приведенных примерах предполагалось, что символы в сообщении являются независимыми (т. е. вероятность появления в сообщении любых двух символов рядом равна произведению вероятностей появления каждого из символов в отдельности). В реальных сообщениях на естественных языках символы не являются независимыми; в таких случаях следует кодировать не отдельные символы (буквы), а группы букв или слова. Это уменьшает зависимость и повышает эффективность кода.

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

Пример 8.6. Рассмотрим источник, вырабатывающий два независимых символа с вероятностями 0,1 и 0,9. В этом тривиальном случае методы кодирования Хаффмена и Шеннона – Фано приводят к одинаковому коду: символы алфавита кодируются символами

0 и 1. Пусть для определенности 1 0 ; 2 1. Энтропия источника равна H( ) =0,469; средняя длина кодового слова равна 1, избыточность источника и избыточность кода одинаковы и равны

Hmax ( ) H (	)	1 0,469
Hmax ( )		1	0,531.

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

Согласно построенному дереву код Хаффмена для указанных групп содержит следующие кодовые комбинации:

1

1

1;

1

2

00;

2

1

011;

2

2

010.