2020-01-15
151
Принцип построения оптимального кода Шеннона-Фано следующий.
Для заданного сообщения необходимо составить вспомогательную таблицу вероятностей появления букв в сообщении.
Таблица 5.1
| А | К | С | Е | Н | Е | Н | К | О | _ | И |
| 0.062 | 0.028 | 0.045 | 0.072 | 0.053 | 0.072 | 0.053 | 0.028 | 0.09 | 0.175 | 0.062 |
Все символы сообщения, входящие в ансамбль, располагаются в порядке убывания вероятности их появления, определяется сумма всех вероятностей. Чтобы кодирование было оптимальным, необходимо выполнение условия нормировки:
(5.1)
Это означает, что необходимо ввести паузу, вероятность которой будет рассчитана, как:
P1 = 0.26
Т.к. код Шеннона-Фано двоичный, следовательно, основание кода k = 2.
Далее все символы ансамбля разбиваются на k групп с таким расчетом, чтобы суммарные вероятности в группах были приблизительно одинаковы. Каждая из групп делится на подгруппы, чтобы в каждой из k подгрупп суммарные вероятности были бы равны. Такое разбиение осуществляется до тех пор, пока в подгруппах не останется по одному символу.
|
|
|
В подгруппах каждый символ или группа кодируется следующим образом. Всем символам первой подгруппы присваивается 0, всем символам второй подгруппы – 1, третьей – 2, и т.д. до k-ой группы, которой присваивается (k – 1).
По этим данным можно составить таблицу разработки кода:
Таблица 5.2
| Буква | Символ | Pi | 1 | 2 | 3 | 4 | 5 | аi 
| n |
| пауза | а1 | 0.26 | 0 | 0 | а1 
| 2 | |||
| _ | а2 | 0.175 | 0 | 1 | 0 | а2 
| 3 | ||
| О | а3 | 0.09 | 0 | 1 | 1 | а3 
| 3 | ||
| Е | а4 | 0.072 | 1 | 0 | 0 | 0 | а4 
| 4 | |
| Е | а5 | 0.072 | 1 | 0 | 0 | 1 | а5 
| 4 | |
| А | а6 | 0.062 | 1 | 0 | 1 | 0 | а6 
| 4 | |
| И | а7 | 0.062 | 1 | 0 | 1 | 1 | а7 
| 4 | |
| Н | а8 | 0.053 | 1 | 1 | 0 | 0 | а8 
| 4 | |
| Н | а9 | 0.053 | 1 | 1 | 0 | 1 | а9 
| 4 | |
| С | а10 | 0.045 | 1 | 1 | 1 | 0 | а10 
| 4 | |
| К | а11 | 0.028 | 1 | 1 | 1 | 1 | 0 | а11 
| 5 |
| К | а12 | 0.028 | 1 | 1 | 1 | 1 | 1 | а12 
| 5 |
Таким образом, можно окончательно записать сообщение, закодированное методом Шеннона-Фано:
0010101111011101000110010011101111110110101011
Процесс кодирования методом Шеннона-Фано обеспечивает оптимальность кода засчет того, что символам с более высокой вероятностью появления ставится в соответствие более короткая кодовая комбинация.
Обычно после разработки системы кодирования определяют среднее количество разрядов, необходимое для передачи одного символа, следующим образом:
(5.2)
|
|
|
