5.3. МЕТОДЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ ПРИ ИЗВЕСТНОЙ СТАТИСТИКЕ СООБЩЕНИЙ

Метод Шеннона — Фано.

Код Шеннона — Фано строится следующим образом: все имеющиеся К. букв располагаются в один столбик в порядке убывания вероятностей. Затем эти буквы разбиваются на две группы: верхнюю и нижнюю так, чтобы суммарные вероятности этих групп были по возможности ближе друг к другу. Для букв верхней группы в качестве первого символа кодового слова используется «1», а для нижней — «0». Далее каждую из двух полученных групп нужно разделить на две части по возможности с близкими суммарными вероятностями; в качестве второго символа кодового слова используется «1» или «0» в зависимости от принадлежности букв верхней или нижней подгруппе и т. д. Данный процесс повторяется до тех пор, пока не приходим к группам, каждая из которых содержит по одной-единственной букве.

Пример 5.2. Пусть даны восемь сообщений (букв), имеющих следующие вероятности: 0,2; 0,2; 0,15; 0,13; 0,12; 0,10; 0,07; 0,03. Построение кода Шеннона — Фано дано в табл. 5.2.

Таблица 5.2

Таблица 5.3

Таблица 5.4

Если использовать равномерный код, то на кодирование данных восьми сообщений потребуется по три двоичных символа (бита) при использовании же кода Шсннопа — Фано среднее число «0» и «1», приходящихся на одну букву сообщения, составит

Это меньше, чем при равномерном кодировании и не очень далеко от энтропии бит/сообщ.

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

Применяя метод Шеннона — Фано к исходному двухбуквенному алфавиту, получаем простейший код (табл. 5.3). Этот код требует для передачи каждой буквы одного двоичного символа что на больше минимально возможного значения бит/буква.

Применим метод Шеннона — Фано к кодированию всевозможных двубуквенных комбинаций (табл. 5 4).

Средняя длина кодового слова здесь равна бит. Таким образом, на одну букву приходится бит, что лишь на больше значения 0,722. Еще лучший результат получим при кодировании трех буквенных комбинаций (табл. 5.5).

Таблица 5.5

Средняя длина кодового слова здесь равна т. е. на одну букву текста приходится в среднем 0,728 бит, что только на 0,83 % больше значения бит/букв.