Метод Шеннона - Фано
Для определенности будем рассматривать кодирование в двоичном алфавите (m = 2). Буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записывают в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивают на две части так, чтобы суммарные вероятности этих подмножеств были примерно равны. Всем знакам (буквам) верхней половины в качестве первого символа присваивают кодовый элемент 1, а всем нижним - 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей и с тем же условием присваивания кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества - 0.
Пример. Провести эффективное кодирование ансамбля из восьми знаков:
|
Буква (знак) xi |
Вероят-ность pi |
Кодовые последовательности |
Длина li |
рi li |
-рilog рi | |||
|
Номер разбиения | ||||||||
|
1 |
2 |
3 |
4 | |||||
|
x1 |
0,25 |
1 |
1 |
|
|
2 |
0,5 |
0,50 |
|
x2 |
0,25 |
1 |
0 |
|
|
2 |
0,5 |
0,50 |
|
x3 |
0,15 |
0 |
1 |
1 |
|
3 |
0,45 |
0,41 |
|
x4 |
0,15 |
0 |
1 |
0 |
|
3 |
0,45 |
0,41 |
|
x5 |
0,05 |
0 |
0 |
1 |
1 |
4 |
0,2 |
0,22 |
|
x6 |
0,05 |
0 |
0 |
1 |
0 |
4 |
0,2 |
0,22 |
|
x7 |
0,05 |
0 |
0 |
0 |
1 |
4 |
0,2 |
0,22 |
|
x8 |
0,05 |
0 |
0 |
0 |
0 |
4 |
0,2 |
0,22 |
=
2,7 и 
.
Как видно, lср = H, следовательно, полученный код является оптимальным.
Заметим, что при равномерном (не учитывающем статистических характеристик) кодировании с использованием m=2 знаков количество элементов в кодовой последовательности будет l logm n = log2 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.
При кодировании по методике Шеннона - Фано некоторая избыточность в последовательностях символов, как правило, остается (lср > H).
Эту избыточность можно устранить, если перейти к кодированию достаточно большими блоками.
Пример. Рассмотрим процедуру эффективного кодирования сообщений, образованных с помощью алфавита, состоящего всего из двух знаков x1 и x2 с вероятностями появления соответственно
p(х1) = 0,9; p(x2) = 0,1.
Так
как вероятности не равны, то
последовательность из таких букв будет
обладать избыточностью. Однако, при
побуквенном кодировании мы никакого
эффекта не получим. Действительно, на
передачу каждой буквы требуется символ
либо 1, либо 0, в то время как энтропия
равна 
,
т.е. оказывается 
.
При кодировании блоков, содержащих по две буквы, получим коды:
|
Блоки |
Вероятности |
Кодовые комбинации | ||
|
номер разбиения | ||||
|
1 |
2 |
3 | ||
|
x1x1 |
0,81 |
1 |
|
|
|
x1x2 |
0,09 |
0 |
1 |
|
|
x2x1 |
0,09 |
0 |
0 |
1 |
|
x2x2 |
0,01 |
0 |
0 |
0 |
Так
как знаки статистически не связаны,
вероятности блоков определяют как
произведение вероятностей составляющих
знаков. Среднее число символов на блок
а на букву
1,29/2 = 0,645, т.е. приблизилось к Н
= 0,47, и таким образом удалось повысить
эффективность кодирования.
Кодирование блоков, содержащих по три знака, дает еще больший эффект:
|
Блоки |
Вероятность |
кодовые комбинации | ||||
|
номер разбиения | ||||||
|
1 |
2 |
3 |
4 |
5 | ||
|
x1x1x1 |
0,729 |
1 |
|
|
|
|
|
x2x1x1 |
0,081 |
0 |
1 |
1 |
|
|
|
x1x2x1 |
0,081 |
0 |
1 |
0 |
|
|
|
x1x1x2 |
0,081 |
0 |
0 |
1 |
|
|
|
x2x2x1 |
0,009 |
0 |
0 |
1 |
1 |
|
|
x2x1x2 |
0,009 |
0 |
0 |
0 |
1 |
0 |
|
x1x2x2 |
0,009 |
0 |
0 |
0 |
0 |
1 |
|
x2x2x2 |
0,001 |
0 |
0 |
0 |
0 |
0 |
Среднее число символов на блок равно 1,59, а на знак - 0,53, что всего на 12% больше энтропии.