4. Эффективное кодирование неравновероятных символов сообщений.

Если символы кодируемого сообщения неравновероятны, в общем виде правило получения оптимального эффективного кода неизвестно.

Эффективное кодирование будет оптимальным, если неравномерное распределение с помощью определенным образом выбранного кода перевести в равновероятное распределение вероятностей появления. В этом случае среднее количество инфор­мации, приходящееся на один элемент символа кода, будет максимальным. Для определения вида кода, удовлетворяющего этому требованию, можно рассмот­реть «функцию стоимости» (цены передачи символов сообщения) в виде:

, (2.5)

где P(x_i) — вероятность появления i-го символа алфавита исходного кодируемого сообщения;

m — объем алфавита;

W_i — стоимость передачи i-го символа алфавита, которая пропорциональна длине кодового слова.

Построение эффективно­го кода должно основываться на следующих принципах:

1. Длина кодового символа (n_i) должна быть обратно пропорциональна вероятности появления соответствующего символа исходного кодируемого сообщения (x_i);

2. Начало более длинного кодового символа не должно совпадать с началом более короткого (для возможности разделения кодовых символов без применения разделительных знаков);

3. В длинной последовательности элементы символов кода должны быть независимы и равновероятны.

5. Алгоритмы эффективного кодирования неравновероятных взаимнонезависимых символов источников сообщений

Алгоритм Шеннона-Фено. Суть этого алгоритма, при использовании двоичного кода (объем алфавита элементов символов кода равен 2), заключается в следующем.

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

Алгоритм Хаффмена. Суть этого алгоритма, при использовании двоичного кода, состоит в следующем. Все символы алфавита источника сообщений ранжируют, т.е. выписывают в столбец в порядке убывания вероятностей их появления. Два последних символа объединяют в один вспомогательный символ, которому приписывают суммарную вероятность.

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

Строим граф кодирования (кодовое дерево), который иллюстрирует ранжирование символов на группы и отдельные символы, причем из точки, соответствующей вероятности 1, направляем две ветви: одной из них (с большей вероятностью) присваиваем символ 1, а второй – символ 0. Различные символы, генерируемые источником сообщения, и соответствующие им кодовые символы.