Методика Шеннона-Фэно

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

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

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

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

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

Убедимся в этом. Рассмотрим алфавит:

Таблица 3.1

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

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

методика Шеннона-Фэно

Вычислим среднее число символов на букву по формуле:

методика Шеннона-Фэно.

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

В общем случае:

H(Z) ≤ l ≤ log2M,

методика Шеннона-Фэно.

Например, для случая (см. таблицу 3.2):

Таблица 3.2

Буквы Вероятность Кодовые комбинации
Z1 0.22 11 1 2.1
Z2 0.20 101 2.1
Z3 0.16 100
Z4 0.16 01 1 2.2
Z5 0.10 001 2.2
Z6 0.10 0001
Z7 0.04 00001
Z8 0.02 00000

H(Z) = –0.22log2 0.22 – 0.2log2 0.2 – 2 · 0.16log2 0.16 – 2 · 0.1log2 0.1 – 0.04log2 0.04 – 0.02log2 0.02 = 2.76;

lср = 0.22 · 2 + 0.2 · 3 + 0.16 · 3 + 0.16 · 2 + 0.1 · 3 + 0.1 · 4 + 0.04 · 5 + 0.02 · 5 = 0.38 · 2 + 3 · 0.46 + 0.4 + 0.3 = 0.76 + 1.38 + 0.7 = 2.84;

max H(Z): log2 mlсрH(Z) + ε, но H(Z) < lср.

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

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

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из 2-х букв Z1 и Z2 с вероятностями появления соответственно P(Z1) = 0.9 и P(Z2) = 0.1.

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

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

lср = 1 · 0.9 + 1 · 0.1 = 1,

в то время как

H(Z) = –0.9log2 0.9 – 0.1log2 0.1 = 0.47.

Перейдем к кодированию блоками. Сначала рассмотрим блоки из 2-х букв.

Таблица 3.3

Буквы Вероятность Кодовые комбинации
Z1Z1 0.81 1 1
Z1Z2 0.09 01 1 2
Z2Z1 0.09 001 2 3
Z2Z2 0.01 000 3

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

lср.на блок = 1 · 0.81 + 2 · 0.09 + 3 · 0.09 + 3 · 0.01 = 1.29;

методика Шеннона-Фэно.

Еще больший эффект дает кодирование блоков, содержащих по 3-и буквы:

Таблица 3.4

Буквы Вероятность Кодовые комбинации
Z1Z1Z1 0.729 1
Z2Z1Z1 0.081 011
Z1Z2Z1 0.081 010
Z1Z1Z2 0.081 001
Z2Z2Z1 0.009 00011
Z2Z1Z2 0.009 00010
Z1Z2Z2 0.009 00001
Z2Z2Z2 0.1 00000

lср.на блок = 1 · 0.729 + 3 · 0.0081 · (2 + 1) + 5 · (0.009 · 3 + 0.001) = 1.598;

методика Шеннона-Фэно.

Теоретически min H(Z) = 0,47 можно достигнуть при кодировании блоками, содержащими бесконечное число букв методика Шеннона-Фэно.

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

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

Таблицу 3 можно было бы разбить иначе. При этом среднее число символов на букву оказывается равным 2.80, что меньше 2.84, то есть код, построенный по методике Шеннона-Фено, оказывается не самым лучшим. http://peredacha-informacii.ru/ При построении эффективных кодов с основанием m > 2 неопределенность становится еще больше.