Методы эффективного кодирования информации

Информационную избыточность можно ввести разными путями. Рас­смотрим один из путей эффективного кодирования.

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

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

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

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

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

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

Таблица 2.

Вычислим энтропию набора букв:

(z) = -p(z_i)log p(z_i) » 2,76

и среднее число символов на букву

l_cp = -p(z_i) n(z_i) » 2,84

где n(z_i) - число символов в кодовой комбинации, соответствующей букве z_i.

Значения z_i и l_cp не очень различаются по величине.

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

Множество вероятностей в предыдущей таблице можно было разбить иначе (табл. 3).

Таблица 3.

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

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