Алгоритм на псевдокоде
Алгоритм построения кода Шеннона
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