Оптимальные коды Шеннона-Фано

Принцип построения оптимального кода Шеннона-Фано следующий.

1. Сообщения, входящие в ансамбль, располагаются в строку (в столбец) по мере убывания вероятностей.
2. Выбирается основание кода K.
3. Все сообщения ансамбля разбиваются на K групп с равными суммарными вероятностями внутри каждой группы. Всем сообщениям первой группы в качестве первого символа присваивается 0, сообщениям второй группы – символ 1, а сообщениям K-й группы – символ (K – 1); тем самым обеспечивается равная вероятность появления всех символов 0, 1,…, K на первой позиции в кодовых словах.
4. Каждая из групп делится на K подгрупп с равной суммарной вероятностью в каждой подгруппе. Всем сообщениям первых подгрупп в качестве второго символа присваивается 0, всем сообщениям вторых подгрупп – 1, а сообщениям K -х подгрупп – символ (K – 1).
5. Процесс продолжается до тех пор, пока в каждой подгруппе не окажется по одной комбинации.

Пример 1. Пусть дан ансамбль сообщений

Построить двоичный оптимальный код.

Оптимальный код строится в соответствии с приведенными правилами:

Наиболее вероятное сообщение кодируется самым коротким сигналом.

Для двоичного кода условие оптимальности выглядит так:

С другой стороны,

То есть в данном случае n_CP = H_И.

Полученный оптимальный код является неравномерным. Возникает проблема распознавания сообщений в сигнале. В этом случае для упрощения процедуры декодирования сообщений по принятой последовательности символов необходимо выполнить условие однозначной различимости кодовых комбинаций. Один из способов выполнения этого условия заключается в таком построении кодовых слов, чтобы никакая кодовая комбинация не являлась началом другой. Альтернативой этому служит введение специальных разделительных знаков, которые должны выдаваться в конце каждого кодового слова. Для передачи таких префиксов понадобится еще какой-то символ, помимо 1 и 0, что приведет к увеличению основания кода. Различимость кодов Шеннона-Фано достигается первым методом. Таким образом, при кодировании методом Шеннона-Фано любой последовательности символов можно поставить в соответствие ряд сообщений, что легко проверить.

Пример 2. Дан ансамбль сообщений:

Построить двоичный оптимальный код.

Пример решается аналогично предыдущему:

Для данного кода

.

Код является равномерным. Принимаемая последовательность делится на блоки по три символа в каждом. Ни одна из комбинаций не является началом другой, так как длина всех комбинаций одинакова.

Коды Шеннона-Фано могут быть построены для любого основания K по той же методике.

Пример 3. Построить оптимальный троичный код для ансамбля сообщений

Решение:

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

В приведенных примерах оптимальность достигается за счет пропорциональности вероятностей сообщений основанию кода, то есть

Только в этом случае осуществляется точное разделение всех групп сообщений на подгруппы с равной суммарной вероятностью сообщений в каждой подгруппе. Когда это условие не выполняется (то есть когда сообщения имеют произвольную вероятность), разбиение на группы возможно только с приближенным равенством суммарных вероятностей. В результате все символы кода будут иметь лишь приближенно равные вероятности появления, и

Такие коды называются квазиоптимальными. Это означает, что существует возможность построения более оптимального кода. Таким кодом является код Хафмена.

---