|
Методика Шеннона-ФэноКод строится следующим образом: буквы алфавита сообщения выписываются в таблицу в порядке убывания вероятностей. Затем они разбиваются на две группы так, чтобы суммы вероятностей в каждой из групп были бы по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 0, а всем нижним 1, или наоборот, это не принципиально, но правило должно оставаться до завершения кодирования всех букв. Каждая из полученных групп в свою очередь разбивается на две подгруппы с одинаковыми суммарными вероятностями и так далее. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве. Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется 3 символа. Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии источника. Убедимся в этом. Рассмотрим алфавит: Таблица 3.1
Вычислим энтропию алфавита: Вычислим среднее число символов на букву по формуле: .В более общем случае для алфавита из 8 букв среднее число символов на букву будет меньше 3, но больше энтропии алфавита H(Z). В общем случае: H(Z) ≤ l ≤ log2M, .Например, для случая (см. таблицу 3.2): Таблица 3.2
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 m ≥ lср ≥ 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
Так как буквы статистически не связаны, то вероятности появления блоков определяются как произведение вероятностей составляющих букв: lср.на блок = 1 · 0.81 + 2 · 0.09 + 3 · 0.09 + 3 · 0.01 = 1.29; .Еще больший эффект дает кодирование блоков, содержащих по 3-и буквы: Таблица 3.4
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 неопределенность становится еще больше. |