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

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

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

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

Расчет параметров выпрямительно-инверторного преобразователя, выполненного по шестипульсовой мостовой схеме
Трёхфазный мостовой выпрямительно-инверторный преобразователь (ВИП) питается от сети с номинальным напряжением UС=U1Л и заданными пределами колебания этого напряжения %UС Известна мощность короткого замыкания SКЗ, характеризующая реактанс связи точки подключения ВИП и шин бесконечной ...

Разделы

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