Статистическое кодирование

Буквы алфавита сообщений Х={х1, х2,…, хг}, имеющие соответствующие вероятности их появления р(х1), р(х2),…, р(хr), выписывают в основной столбец в порядке убывания вероятностей. Две последние самые маловероятные буквы хr-1 и хr объединяют в одну вспомогательную (укрупненную) букву а, которой приписывают суммарную вероятность, равную сумме вероятностей букв хr-1 и хr, т.е. р(а)=р(хr-1|)+р(хr). Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце. Процесс повторяется до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице. Для наглядности строим кодовое дерево. Двигаясь по кодовому дереву от корня к вершинам, т.е. сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию.

Для осуществления статистического кодирования методом Хаффмана образуем трёхбуквенные комбинации, состоящие из элементов двоичного кода 1 и 0 (всего 8 таких комбинаций: 000, 001, 010, 011, 100, 101, 110, 111), вычислим их вероятности (по теореме умножения вероятностей), используя исходные данные. Процесс кодирования в соответствии с вышеприведённым алгоритмом поясняется таблицей 6.1. Для составления кодовой комбинации, соответствующей данному знаку, необходимо проследить путь перехода знака по строкам и столбцам таблицы. Для наглядности строим кодовое дерево. Из точки, соответствующей вероятности 1, направляем на две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей - 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до вероятности каждой буквы. Кодовое дерево для алфавита букв, рассматриваемого в таблице 6.1, приведено на рисунке 6.1. Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию. Дополним кодовую таблицу 6.1 промежуточными вычислениями, необходимыми для определения коэффициента избыточности.

Средняя длина кодовой комбинации:

(6.6)

Энтропия сообщения источника:

(6.7)

Минимальная средняя длина кодовой комбинации определяется из равенства:

(6.8)

Коэффициент избыточности:

(6.9)

Как видно из выражения (6.9), построенный код практически не имеет избыточности.

Но у системы эффективного кодирования есть свои недостатки.

Причиной одного из недостатков является различие в длине кодовых комбинаций. Если моменты снятия информации с источника неуправляемы (например, при непрерывном съеме информации с запоминающего устройства на магнитной ленте), кодирующее устройство через равные промежутки времени выдает комбинации различной длины. Так как линия связи используется эффективно, только в том случае, когда символы поступают в нее с постоянной скоростью, то на выходе кодирующего устройства должно быть предусмотрено буферное устройство («упругая» задержка). Оно запасает символы по мере поступления и выдает их в линию связи с постоянной скоростью. Аналогичное устройство необходимо и на приемной стороне. Второй недостаток связан с возникновением задержки в передаче информации

Другие стьтьи в тему

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

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