Теорема об эффективном кодировании

Теоретическую основу эффективного кодирования составляет основная теорема К.Шеннона для канала без шума. Суть этой теоремы состоит в следующем.

Пусть источник имеет энтропию H (бит на символ), а канал имеет пропускную способность C (бит в секунду). Тогда можно закодировать сообщения на выходе источника таким образом, чтобы передавать символы (элементы) по каналу со средней скоростью C/H-E символов в одну секунду, где E – сколь угодно мало. Передавать элементы сообщения со средней скоростью, больше чем C/H, невозможно.

Рисунок 10.1

Отметим, что при кодировании элементов ДС, передаваемых по каналу связи без помех, необходимо выполнить следующие два условия:

1) кодовые комбинации должны быть различны (т.е. однозначно декодироваться на приеме) и однозначно связаны с соответствующими элементами ДС;

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

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

. (10.6)

Причем среднее число кодовых символов конкретного кода, приходящихся на один элемент (символ) сообщения, определяют так:

. (10.7)

Для оптимального двоичного эффективного кода (в=2, m=2)

. (10.8)

В этом случае условие оптимальности n=n_min достигается, если в (11.7) и (11.8) принять

. (10.9)

Итак, в оптимальном эффективном коде значность n_i кодовой комбинации, соответствующий элементу сообщения А, зависит от вероятности p_i ее наступления. Чем больше вероятность, тем меньше значность кодовой комбинации и наоборот. С учетом этого, подобные коды называют еще статистическими (вероятностными). Кроме того, эффективные (статистические) коды относятся к неравномерным.

Избыточность кодера источника оценивают так:

. (10.10)

Примерами двоичных эффективных кодов, близких к оптимальным и обеспечивающих избыточность, близкую к нулю, являются коды Шеннона-Фано и Хаффмена.

Разберем принцип двоичного кодирования по методу Шеннона-Фано. Элементы, ДС располагаются вначале в виде столбца (группы) в порядке убывания их вероятностей. При кодировании на первом этапе эта группа разбивается на две подгруппы, по возможности с равными суммарными вероятностями. Всем элементам первой подгруппы приписывается первый кодовый символ 0, для второй подгруппы I. На втором этапе каждая из подгрупп также разбивается на две подгруппы с примерно равными вероятностями, и частная подгруппа определяет второй двоичный символ. Этот процесс продолжается до тех пор, пока не получатся подгруппы, содержащие только по одному элементу сообщения.

В таблице 10.1 приведен пример построения эффективного кода Шеннона-Фано для источника ДС с распределением вероятностей:

,,,.

Для данного источника: Н (А)=1,75 бит, H_max= 2 бит, r(A) =0.125.

Для построенного кода: бит, n_min= 1.75 бит,. Следовательно, данный код оптимален. В табл. 1.1 для сравнения построен равномерный примитивный код: бит. Отношение / = к_сж называют коэффициентом сжатия. Здесь К_сж=1,15.

Таблица 10.1