Методы эффективного кодирования
некоррелированной последовательности знаков

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

Следовательно, каждый символ должен принимать значения 0 и 1 по возможности с равными вероятностями, и каждый выбор должен быть независим от значений предыдущих символов.

Конструктивные методы построения эффективных кодов для случая отсутствия взаимосвязи между элементами сообщений были впервые предложены американскими учеными Шенноном и Фано. Их методики существенно не различаются и поэтому соответствующий код получил название кода Шеннона – Фано.

Код строят следующим образом: знаки алфавита сообщений выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве соответствующего разряда кодовой комбинации приписывают 0, а всем нижним – 1. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку.

Пример 2.1.

Проведем эффективное кодирование группы из восьми элементов, характеристики которой представлены в табл. 2.3.При равномерном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных разряда. Используя методику Шеннона – Фано, получаем совокупность кодовых комбинаций, приведенных в столбце VII табл. 2.3.

Так как вероятности появления знаков в сообщении представляют собой целочисленные отрицательные степени двойки, то избыточность при кодировании устраняется полностью. Среднее число разрядов на знак в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию:

и среднее число разрядов на знак

,

где n(z_i) – число разрядов в кодовой комбинации, соответствующей знаку z_i, p(z_i) – вероятность, соответствующая z_i.

Таблица 2.3

В более общем случае для алфавита из восьми знаков среднее число разрядов на знак будет меньше трех, но больше энтропии алфавита H ( z ).

Пример 2.2.

Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля, приведенного в табл. 2.4. Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона – Фано (табл. 2.4) получаем среднее число разрядов на знак, равное 2,84.

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

Таблица 2.4

Пример 2.3.

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

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

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

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

Таблица 2.5

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

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

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

Таблица 2.6

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

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

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

Таблица 2.7

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

Порядок построения кода сводится к следующему:

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

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

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

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

Пример 2.4.

Используя алгоритм Хаффмена, осуществить эффективное кодирование ансамбля знаков, приведенного в табл. 2.4.

Процесс кодирования поясняется табл. 2.8.

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

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

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

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