45. Критерий оптимальности кода.

Таким образом, оптимальное согласование сообщения с каналом будет при выборе длительностей символов сообщения в соответствии с выражением

(II1-60}

или в другой записи для случая, когда

(111-61)

Из (II1-60) следует, что длительности символов сообщения должны быть пропорциональны логарифму вероятности их появления, т. е. наиболее вероятные символы должны иметь наименьшую длительность, а наименее вероятные — большую длительность. Это правило можно отнести и к сообщениям, длительность которых должна быть пропорциональна логарифму их вероятности. Если символы данного сообщения не удовлетворяют условиям оптимального согласования, они могут быть при согласовании заменены другими символами в соответствии с условиями (111-60) или (111-61). Такая замена называется оптимальным кодированием.

Соотношения (111-60) и (111-61) лишь указывают направление для получения наилучшего согласования дискретного сигнала, с каналом. Методов практической реализации оптимального кодирования, однако, они не указывают.

46. Код Шеннона-Фано. Код Хаффмена.

Для двоичного канала с отсутствием статистических связей между символами этим требованиям удовлетворяет код Шеннона — Фано.

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

В результате такого разбиения как бы образовано новое сооб­щение, состоящее всего из двух элементов, вероятности появления которых примерно одинаковы. Всем символам первой группы приписывается 0 и всем символам второй группы—1. Каждая из полученных групп затем разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс деления повторяется до тех пор, пока в каждой подгруппе останется по одному символу.

Методика построения кода Шеннона — Фано для случая передачи четырех символов сообщения с вероятностями р (x₁) = 0,5; p(x₂) = 0,25; р(х₃) = 0,125 и p(x₄) = 0,125 иллюстрируется табл. Для удобства построения все символы сообщения выписываются в таблицу в порядке убывания вероятностей. При разбиении верхним половинам групп приписывается символ 0 и нижним — сим­ол 1.

Как видно из табл., полученный код является неравномерным, так как длина кодовых комбинаций находится в обратной зависимости от их вероятности. Для любой позиции всей совокупности кодовых комбинаций вероятности передачи 0 и 1 одинаковы.

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

Подсчитаем скорость передачи информации, которая обеспечивается полученным кодом.

Пусть длительность символов кодовых комбинаций равна t. Тогда средняя длительность кодовых комбинаций

Средняя энтропия на символ сообщения

Таким образом, скорость передачи информации

В оптимальном коде, называемом кодом Шеннона — Фано, используются символы 0 или 1, т. е. оптимальный код является двоичным. Правило построения кода состоит в следующем:

1.Символы исходного сообщения (буквы) располагаются в порядке убывания их вероятности и разбиваются на две группы так, чтобы суммы вероятностей в группах были примерно одинаковы.

2.В качестве первого символа кода всем буквам, вошедшим в первую группу, приписывается единица, а буквам второй группы — нуль.

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

4.Буквам первых подгрупп в качестве следующего символа кода приписывается единица, а к буквам второй подгруппы — нуль и т. д.

Разбиение на подгруппы производится до тех пор, пока в каждой .подгруппе не останется по одной букве.

Код Шеннона — Фано рассчитан на использование двоичного алфавита. Хаффменом предложена методика, позволяющая построить оптимальный код с минимальной избыточностью при любом основании кода m.

Правило построения кода заключается в следующем:

1.Символы сообщений (буквы) располагаются в порядке убывания вероятностей.

2.n₀ наименее вероятных букв объединяются в одну вспомогательную, вероятность которой определяется суммой вероятностей входящих в нее букв. Число n₀ определяется из условия 2 ≤ n₀ ≤ m, так чтобы выполнялось соотношение

где М — число символов сообщения; j — целое число.

3.В качестве последних символов кода, приписываемых буквам, вошедшим во вспомогательную букву, выбирается n₀ различных символов кода.

4.Оставшиеся буквы и вспомогательная буква располагаются в порядке убывания вероятностей.

5. Составляется вторая вспомогательная буква, в которую входят m наименее вероятных букв. Вошедшим буквам присваиваются различные символы кода и т. д.

Образование вспомогательных букв производится до тех пор, пока не будет получена одна буква с вероятностью, равной единице. Образование кодовых комбинаций производится с учетом всех символов, приписанных буквам на всех этапах их объединения. Процедура кодирования представлена на табл, составленной для основания кода m = 4.

Анализ методик построения оптимальных кодов показывает, что во всех случаях более вероятным буквам соответствуют более короткие кодовые комбинации. При этом длина кодовых комбинаций оказывается различной. Нетрудно заметить, что, несмотря на различную длину комбинаций, установка разделительных символов между комбинациями не является необходимой, поскольюши одна более короткая комбинация не совпадает с началом более, длинной. Коды, которых удовлетворяется это условие, называются префиксными. К их числу относятся коды Шеннона — Фано и Хаффмена.