Теория информации |
Конспект лекций |
5. ПОЧТИ ОПТИМАЛЬНОЕ КОДИРОВАНИЕ
5.2 Код Фано
Метод Фано построения префиксного почти оптимального кода, для которого , заключается в следующем.
Пример 5.2.1. Пусть источник имеет алфавит с вероятностями
Построенный код приведен в таблице 7 и на рисунке 6.
Таблица 7 Код Фано
Рисунок 6 Кодовое дерево для кода Фано
Полученный код является префиксным и почти оптимальным со средней длиной кодового слова
Алгоритм на псевдокоде
Построение кода Фано
Обозначим
Функция Med находит медиану части массива P, т.е. такой индекс , что величина
минимальна.