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

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

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

Расчет настроек типовых регуляторов в одноконтурной автоматической системе реагирования
автоматический Цель работы: Определить настроечные параметры (настройки) типового (ПИ, ПИД, ПД) регулятора в одноконтурной АСР, обеспечивающие минимум интегрального квадратичного критерия I0 при заданном ограничении запаса устойчивости m≥mзад. Выбрать промышленный регулят ...

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

Разделы

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