5.1 Код Шеннона

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

Код Шеннонапозволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме  Шеннона  

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита  по убыванию их вероятностей .

2. Вычислим величины ,  которые называются кумулятивные вероятности

3. Представим  в двоичной системе счисления и возьмем в качестве кодового слова первые  двоичных знаков после запятой, .

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова Li из соотношения

Пример 5.1.1. Пусть источник имеет алфавит  с вероятностями

Построенный код приведен в таблице 6.

Таблица 6 Код Шеннона

 

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона

что полностью соответствует утверждению теоремы Шеннона.

 

Алгоритм на псевдокоде

 Построение кода Шеннона

Обозначим
n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
Q– массив для величин Qi
L – массив длин кодовых слов
C – матрица элементарных кодов

5.2 Код Фано

Метод Фано построения префиксного почти оптимального кода, для которого , заключается в следующем.

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

Пример 5.2.1. Пусть источник имеет алфавит  с вероятностями

Построенный код приведен в таблице 7 и на рисунке 6.

Таблица 7 Код Фано

Рисунок 6 Кодовое дерево для кода Фано

Полученный код является префиксным и почти оптимальным со средней длиной кодового слова

 

Алгоритм на псевдокоде

Построение кода Фано

Обозначим

Функция Med находит медиану части массива P, т.е. такой индекс , что величина  минимальна.