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

Буквы алфавита сообщений Х={х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 2 3 4 5

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

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

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

Разделы

Радиоэлектроника и телекоммуникации © 2019 : www.techelements.ru