Алгоритм построения кода Шеннона
p0:=0, Q0:=0
DO (i=1,…,n)
Qi := Qi-1+pi
Li:= -élog2pi ù
OD
DO (i=1,…,n)
DO (j=1,…,Li)
Qi-1:=Qi-1 *2
C[i,j]:= éQi-1ù
IF (Qi-1>1) Qi-1:=Qi-1-1 FI
OD
OD
Код Фано
Метод Фано построения префиксного почти оптимального кода заключается в следующем. Упорядоченный по убыванию вероятностей список букв алфавита источника делится на две части так, чтобы суммы вероятностей букв, входящих в эти части, как можно меньше отличались друг от друга. Буквам первой части приписывается 0, а буквам из второй части – 1. Далее также поступают с каждой из полученных частей. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве.
Пример. Пусть дан алфавит A={ a1, a2, a3, a4, a5, a6 } с вероятностями p1 =0.36, p2 =0.18, p3 =0.18, p4 =0.12, p5 =0.09, p6 =0.07. Построенный код приведен в таблице и на рисунке.
Таблица 12 Код Фано
ai | Pi | кодовое слово | Li | |||
a1 | 0.36 | |||||
a2 | 0.18 | |||||
a3 | 0.18 | |||||
a4 | 0.12 | |||||
a5 | 0.09 | |||||
a6 | 0.07 |
|
|
Рисунок 69 Кодовое дерево для кода Фано
Полученный код является префиксным и почти оптимальным со средней длиной кодового слова
Lср =0.36 . 2+0.18 . 2+0.18 . 2+0.12 . 3+0.09 . 4+0.07 . 4=2.44