Теория информации

1.3.5. Код Шеннона – Фано Для построения кода Шеннона-Фано все символы алфавита сообщений записывают в порядке убывания вероятностей их появления. Полученную ранжированную (упорядоченную) последовательность символов разбивают на две группы так, чтобы суммы вероятностей групп были примерно одинаковыми. Алгоритм оптимального кодирования Шеннона-Фано включает следующие основные шаги: 1шаг) Все буквы, символы алфавита записываются в порядке убывания их вероятностей, упорядочиваются в порядке убывания вероятности их появления. Суммарная вероятность появления символов алфавита должна равняться 1. 2шаг) Затем все буквы делятся на равновероятные (приблизительно равновероятные) группы, так, чтобы суммы вероятностей групп были примерно одинаковыми. 3шаг) Для символов первой группы (из верхней подгруппы) в качестве первого кодового символа присваивают «0», а для символов второй группы (из нижней подгруппы) – «1». 4шаг) Полученные группы символов сообщений опять разбивают таким же образом на две подгруппы и опять кодируют. При этом каждому символу из верхней подгруппы присваивается код «0», а из нижней ‒ «1». 5шаг) Это продолжается до тех пор, пока в последних подгруппах не останется по одному символу сообщений. 6шаг) В результате кодовые слова записываются слева направо по кодам подгрупп, соответствующих кодируемому символу. Пример 1.22. Закодируем буквы алфавита из примера 1.21 в коде Шеннона  Фано. Пусть, например , имеется алфавит сообщений: X = ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 ) с распределением вероятностей появления символов: