4. Теорема о минимальной средней длине кодового слова.

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

Теорема 4.

Формулировка. Для данного дискретного источника без памяти (с независимыми буквами) и энтропией H и объемом вторичного алфавита m при кодировании блоками по L букв существует префиксный код со средней длиной кодового слова, отвечающей неравенству:

.

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

Последовательность из L букв можно рассматривать как новую супербукву. Тогда можно использовать теорему 3, согласно которой минимальная средняя длина кодового слова для такого сообщения ограничивается неравенством:

.

Так как отдельные буквы предполагаются независимыми, то энтропия последовательности L букв . Кроме того, средняя длина кода для последовательности L букв , тогда

.

После деления всех частей неравенства на L получаем окончательный результат: .

Из теоремы 4 следует, что если кодировать блоками, то, увеличивая размер блоков L, можно сколь угодно приблизиться к нижней границе средней длины кодового слова, т.е. .

5. Назначение и порядок построения оптимальных кодов Шеннона-Фэно и Хаффмена. Коды Хаффмена

На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году Хаффменом:

1. буквы первичного алфавита выписываются в основной столбец в порядке убывания вероятностей;

2. две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;

3. вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются;

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

М

Таблица 3.2.

етодика поясняется примером, представленным табл. 3.2.

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

Д

Рис. 3.3. Кодовое дерево.

ля наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей − 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждой буквы. Кодовое дерево для алфавита букв, рассматриваемого в таблице, изображено на рис. 3.3.

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

Таблица 3.3

Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8
01	00	111	110	100	1011	10101	10100

Коды Шеннона−Фэно:

Ранее, независимо друг от друга Шенноном и Фэно была предложена другая процедура построения эффективного кода. Получаемый при ее помощи код называют кодом Шеннона−Фэно.

Код Шеннона−Фэно строится следующим образом:

1. буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

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

3. всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним 0;

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

5. процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

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

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию: и среднее число символов на букву где n(Zi) —число символов в кодовой комбинации¹, соответствующей букве Zi. Характеристики такого ансамбля и коды букв представлены в таблице 3.4.

Таблица 3.4.

Буквы	Вероятности	Ступени разбиения							Кодовые комбинации
		1	2	3	4	5	6	7
Z1	1/2	1							1
Z2	1/4	0	1						01
Z3	1/8	0	0	1					001
Z4	1/16	0	0	0	1				0001
Z5	1/32	0	0	0	0	1			00001
Z6	1/64	0	0	0	0	0	1		000001
Z7	1/128	0	0	0	0	0	0	1	0000001
Z8	1/128	0	0	0	0	0	0	0	0000000

В более общем случае для алфавита из восьми букв среднее число символов на букву будет меньше трех, но больше энтропии алфавита H(Z). Для ансамбля букв, приведенного в таблице 3.5, энтропия равна 2,76, а среднее число символов на букву 2,84.

Таблица 3.5

Буквы	Вероят-ности	Ступени разбиения								Кодовые комбинации
		1	2	3	4	5	6	7
Z1	0,22	1	1						11
Z2	0,20	1	0	1					101
Z3	0,16	1	0	0					100
Z4	0,16	0	1						01
Z5	0,10	0	0	1					001
Z6	0,10	0	0	0	1				0001
Z7	0,04	0	0	0	0	1			00001
Z8	0,02	0	0	0	0	0			00000

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

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв Z₁ и Z₂, с вероятностями появления соответственно p(Z_i)==0,9 и р(Z₂) =0,1.

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

Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна 0,47.

При кодировании блоков, содержащих по две буквы, получим коды, показанные в табл. 3.6.

Таблица 3.6

Буквы	Вероятности	Ступени разбиения							кодовые комбинации
		1	2	3	4	5	6	7
Z1 Z1	0,81	1								1
Z2 Z1	0,09	0	1							01
Z3 Z1	0,09	0	0	1						001
Z4 Z1	0,01	0	0	0						000

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

Среднее число символов на блок получается равным 1,29; а на букву − 0,645.

Кодирование блоков, содержащих по три буквы, дает еще больший эффект. Соответствующий ансамбль и коды приведены в табл. 3.7.

Таблица 3.7.

Буквы	Вероят ности	Ступени разбиения							кодовые комбинации
		1	2	3	4	5	6	7
Z1 Z1 Z1	0,729	1							1
Z2 Z1 Z1	0,081	0	1	1					01
Z1 Z2 Z1	0,081	0	1	0					010
Z2 Z2 Z1	0,081	0	0	1					001
Z1 Z1 Z2	0,009	0	0	0	1	1			00011
Z2 Z1 Z2	0,009	0	0	0	1	0			00010
Z1 Z2 Z2	0,009	0	0	0	0	1			00001

Среднее число символов на блок равно 1,59; а на букву − 0,53; что всего на 12% больше энтропии. Теоретический минимум Н(Z) = 0,47 может быть достигнут при кодировании блоков, включающих бесконечное число букв: .

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

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

Множество вероятностей, приведенных в таблице 3.5, можно было бы разбить иначе, например, так, как это показано в табл. 3.8.

Таблица 3.8.

Буквы	Вероятности	Ступени разбиения								кодовые комбинации
		1	2	3	4	5	6	7
Z1	0,22	1	1						11
Z2	0,20	1	0						10
Z3	0,16	0	0	1					001
Z4	0,16	0	1	0					010
Z5	0,10	0	0	1					001
Z6	0,10	0	0	0	1				0001
Z7	0,04	0	0	0	0	1			00001
Z8	0,02	0	0	0	0	0			00000

При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием m>2 неопределенность становится еще большей.

От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.