Коды Шеннона-Фэно

Оптимальные неравномерные коды

Определения.

Неравномерными называют коды, кодовые слова которых имеют различную длину.

Оптимальность можно понимать по-разному, в зависимости от критерия. В данном случае таким критерием является средняя длина кодового слова. Оптимальность с учетом этого критерия понимается в смысле минимальной длины средней длины кодового слова.

Дальнейшие выводы будем делать при следующих условиях:

Пусть буквы первичного источника a₁ a₂.,.., а_к имеют вероятности появления p₁, р₂,..., р_к. Упорядочим буквы в порядке убывания вероятностей их появления в сообщении и пронумеруем их в этом порядке. В результате p₁ > р₂ >...> р_к. Для кодирования будем использовать вторичный алфавит, состоящий из 2 букв - 0 и 1, т.е. двоичный код.

Пусть x₁, х₂,..., х_k - множество кодовых слов, имеющих длину n₁, n₂,..., n_k. Ограничимся также рассмотрением только префиксных кодов. Результаты, полученные в отношении длин кодовых слов для префиксных кодов, можно распространять на весь класс однозначно декодируемых кодов, а результаты, полученные для двоичных кодов можно обобщить на коды с любым объемом вторичного алфавита.

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

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

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

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

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

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

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

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

p₁=1/2; p₂=1/4; p₃=1/8; p₄=1/16; p₅=1/32; p==1/64; p₇=1/128; p₈=1/128/

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

Убедимся в этом, вычислив энтропию для нашего примера:

и среднее число символов на букву первичного алфавита.

где n(z_i) —число символов в кодовой комбинации, соответствующей букве z _i. Характеристики такого ансамбля и коды букв представлены в таблице 4.2.

Таблица 4.2.

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

Таблица 4.3.

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

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

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

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

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

Таблица 4.4.

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

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

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

Таблица 4.5.

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

lim l_cp=H(Z), при m→∞

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

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

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

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

Дата добавления: 2014-01-04