Статистическое (эффективное) кодирование

Статистическое кодирование – прямая противоположность помехоустойчивому кодированию.

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

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

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

Энтропия является мерой количества информации, переносимой в среднем одной буквой сообщения, является также и мерой неопределенности, существовавшей до появления очередного сообщения, что устраняло эту неопределенность.

    Вычислим энтропию источника с учетом вероятности передачи элементов "1" и "0" и его производительность

Р(1) = 0.1 - вероятность передачи сигнала "1"

Р(0) = 0.9 - вероятность передачи сигнала "0"

Т = 5 мкс - длительность элементарной посылки

Энтропия источника равна

H(A) = - 0.1 log₂ 0.1 - 0.9log₂ 0.9 = 0.469 бит

Методика Шеннона-Фано не всегда приводит к однозначному построению кода. От указанного недостатка свободна методика построения кода Хаффмана. Она гарантирует однозначное построение кода с наименьшим, для данного распределения вероятностей, средним числом символов на группу.

Суть его сводится к тому, что наиболее вероятным исходным комбинациям присваиваются более короткие преобразованные комбинации, а наименее вероятным - более длинные. За счет этого среднее время, затраченное на посылку одной кодовой комбинации, становится меньше.

Для двоичного кода методика сводится к следующему:

1. Буквы алфавита выписываются в основной столбец в порядке убывания вероятностей.

2. Две последние буквы, с наименьшими вероятностями, объединяют в одну и приписывают ей суммарную вероятность объединяемых букв.

3. Буквы алфавита сортируются заново.

4. Операции 1-3 повторяются.

Процесс повторяется до тех пор, пока не получим единственную букву с вероятностью равной 1.

Таблица 6.1

Согласно таблице 6.1. строим граф кодового дерева по следующему правилу:

Из точки с вероятностью "1" направляем две ветви. Ветви с большей вероятностью приписываем 1 и откладываем влево, а ветви с меньшей вероятностью приписываем 0 и откладываем вправо. Такое последовательное ветвление продолжим до тех пор, пока не дойдем до вероятности каждой отдельной буквы. Кодовое дерево изображено на рисунке 6.1. Теперь двигаясь по кодовому дереву с верху вниз можно для каждой буквы записать новую кодовую комбинацию.

Рисунок 6.1 Граф кодового дерева.

Получили новые кодовые комбинации:

Определим среднюю длину кодовых комбинаций.

 где n-количество разрядов кодовой комбинации

р - вероятность

Т - длительность импульса

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

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