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

Буквы алфавита сообщений Х={х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), построенный код практически не имеет избыточности.

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

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

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

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

Проектирование цифровых устройств
1. Произвести синтез цифрового устройства управления (ЦУУ) в базисах мультиплексоров, логических элементов Шеффера и Пирса в соответствии с заданным вариантом (приложения №1 и №2). 2. Произвести схемотехническое моделирование синтезированных схем ЦУУ с помощью программы Electronics Wor ...