Технологическая автоматизация

Методы цифровых технологий

Энтропийное кодирование видеосигнала по методу Хаффмана

Первый известный метод эффективного кодирования символов известен как кодирование Шеннона - Фано Он основан на знании вероятности каждого символа, присутствующего в сообщении. Зная эти вероятности, строят таблицу кодов, обладающую следующими свойствами:

- различные коды имеют различное количество бит;

- коды символов, обладающих меньшей вероятностью, имеют больше бит, чем коды символов с большей вероятностью,

- хотя коды имеют различную битовую длину, они могут быть де кодированы единственным образом.

Этими свойствами обладает алгоритм Хаффмана , основанный на элегантной и простой процедуре построения дерева вероятностей.

Средняя длина слов L, находится в диапазоне: Н(В) < L < Н(В)+1 бит/пиксел и L, >1 бит/пиксел, т.е. средняя длина слов не более чем на 1 бит/пиксел больше энтропии, но не менее 1 бит/пиксел (в предельном случае, когда энтропия равна нулю).

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

Р(b0) - Р(b5) = Р(b6) = Р(b7) = 0,06; Р (b,) = 0,23; Р(b2) = 0,30; Р(bЗ) = 0.15; Р(b4) = 0,08.

Дерево строится справа налево следующим образом (рисунок 9 - верхняя диаграмма):

в секции I уровни пикселов сортируются по вероятности от наибольшей к наименьшей сверху вниз; при равенстве Р(bi) = P(bj) выше ставится уровень bi < bj;

в секции II две самые нижние ветви объединяются в узел, их вероятности складываются, и узел образует новую ветвь; общее количество

количество ветвей уменьшается на одну и они вновь сортируются по вероятности от наибольшей к наименьшей; в секциях III и IV и т.д. производятся операции, аналогичные проводимым в секции II до тех пор, пока не останется одна ветвь с вероятностью, равной 1.

Все это дерево можно перестроить (рисунок 9 - нижняя диаграмма), убрав пересечения.

Кодирование осуществляется движением слева направо по дереву каждому кодируемому уровню bi.

При этом на каждом узле коду приписывается, например, двоичный «0» если осуществляется шаг вверх и «1», если осуществляется шаг вниз. Таким образом, для данного случая наиболее вероятные значения и b2 кодируются двухбитовым кодом, величины b3 и b4 - трехбитовым кодом, а наименее вероятные значения b0, b5, b6 и b7 - четырехбитовым кодом (на рисунке 9 - нижняя диаграмма, - указаны справа). Не трудно понять, что эти коды легко различимы: если второй бит кода является двоичным нулем, то код - двухбитовый; в противном случае количество бит в коде более двух; - если третий бит кода является двоичным нулем, то код трехбитовый; в противном случае количество бит в коде равно четырем. Приемник декодирует информацию, используя то же самое дерево, двигаясь вверх при получении «0» и вниз при получении «1». Средняя битовая скорость в данном случае L, =2,71 бит/пиксел при энтропии =2,68 бит/пиксел (т.е. L, практически совпадает с Н).

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

Другие статьи по теме:

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

Технологический процесс изготовления платы интегральной микросхемы-фильтра Микроэлектроника как современное направление проектирования и производства электронной аппаратуры различного назначения является катализатором научно-технического прогресса. Автоматизац ...

Устройство управления шаговым двигателем На сегодняшнем этапе развития информационных технологий, все шире внедряются в производство с системой автоматизированного управления. На ряду с такими важными элементами, как первичные ...