### 5. Почти оптимальное кодирование

5.1 Код Шеннона
5.2 Код Фано

### 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, т.е. такой индекс , что величина минимальна.