Алгоритм Фано префиксного кодирования

Пусть кодируемое сообщения таково, что известны вероятности вхождения каждого символа, причем, p₁ ≥ p₂ ≥… ≥ p_n (1)

При этом

=1 (2)

То есть прежде чем производить кодирование, необходимо расположить буквы алфавита А так, чтобы удовлетворялось условие (1). Затем проверить равенство (2 ), после чего назначать коды.

Итак, имеем

p₁ = 0,…

p₂ = 0,…

….

p_n = 0,….

p_i =1

Алгоритм.

Разобьем вероятности на две части так, чтобы суммы вероятностей каждой из частей были примерно равны. Пусть это будет после вероятности: p_i p_j. Назначим коды: в верхней части 0, а в нижней 1. Теперь разбиваем верхнюю часть на две части, с примерно равными суммами вероятности: p_i p_j.

И вновь делаем то же самое: для данного деления: к имеющимся кодам добавляем в верхней части 0, а в нижней 1. И так далее до тех пор, пока в верхней части не останется одна строка. Добавим в нее 0, а в нижнюю часть 1. Последнюю нижнюю часть опять разбиваем на две части (если она содержит более одной строки) и так далее, пока в нижней части не останется одна строка. После этого переходим к делению предыдущей нижней части и повторяем процедуру назначения кодов.

Полученная схема кодирования является префиксной, так как код первой строки и код второй строки отличаются друг от друга, по крайней мере, в последнем знаке, то эти коды не могут быть префиксами друг друга. Аналогично, так как в верхней части разбиения добавляется 0, а в нижней 1, то ни один из кодов верхней части не может быть префиксом кода нижней части. Таким образом, схема префиксная, следовательно, разделимая.

Пример: пусть заданы вероятности

0,25 0,15 0,12 0,11 0,08 0,06 0,06 0,06 0,06 0,05.

После первого разбиения получим

вероятности коды

0,25 0

0,15 0

0,12 0

0,11 1

0,08 1

0,06 1

0,06 1

0,06 1

0,06 1

0,05 1

После второго разбиения

вероятостити коды

0,25 0 00 код назначен

0,15 0 01

0,12 0 01

0,11 1

0,08 1

0,06 1

0,06 1

0,06 1

0,06 1

0,05 1

После третьего разбиения

0,25 0 00

0,15 0 01 010 код назначен

0,12 0 01 011 код назначен

0,11 1

0,08 1

0,06 1

0,06 1

0,06 1

0,06 1

0,05 1

После четвертого разбиения

0,25 0 00 00

0,15 0 01 010

0,12 0 01 011

0,11 1 1 10

0,08 1 1 10

0,06 1 1 10

0,06 1 1 11

0,06 1 1 11

0,06 1 1 11

0,05 1 1 11

Окончательно получим:

0,25 0 00

0,15 0 01 010

0,12 0 01 011

0,11 1 1 10 100

0,08 1 1 10 101 1010

0,06 1 1 10 101 1011

0,06 1 1 11 11 11 110 1100

0,06 1 1 11 11 11 110 1101

0,06 1 1 11 11 11 111 111 1110

0,05 1 1 11 11 11 111 111 1111

Если кодирование равномерное, то цена кодирования по формуле Хартли равна:= log 104. По алгоритму Фано:= p_i l _i =3,12, что меньше 4, а значит, общая длина кода будет меньше.

Дата добавления: 2014-01-06