7.2.6. Энтропийное кодирование

7.2.6.1. Кодирование кодами переменной длины

В гл. 3 была описана концепция энтропийного кодирования (сжатия без потерь) с помощью кодов переменной длины VLC. В MPEG- 4 Visual и Н.264 эти коды, используемые при кодировании символов данных, предопределены стандартом. В процессе кодирования каждый символ данных заменяется на соответствующий код VLC, который определяется с помощью контекста (например, в зависимости от типа этого символа: параметр заголовка, коэффициент преобразования, компонента вектора движения и т.п.) и конкретного значения данного символа. В гл. 3 приведены некоторые примеры заранее вычисленных таблиц VLC из стандарта MPEG-4 Visual.

Таблица 7.1. Пример кодирования кодами VLC.

Входной VLC		R (до выхода)		R (после выхода)		Выход
Значение, V	Длина, L	Значение	Размер	Значение	Размер
—		—	0	—	0	—
101	3	101	3	101	3	—
11100	5	11100101	8		0	11100101
100	3	100	3	100	3
101	3	101100	6	101100	6
101	3	101101100	9	1	1	01101100
11100	5	111001	6	111001	6	—
1101	4	1101111001	10	11	2	01111001
и т.д.

Коды VLC (по своему определению) содержат переменное число бит, однако при транспортировке данных по сетям бывает необходимо отобразить последовательности кодов VLC, порожденных кодером, в поток байтов или слов. Механизм осуществления этой операции показан на рис. 7.14. Входной регистр R накапливает коды VLC до тех пор, пока не соберется достаточный объем данных для их записи в один или несколько выходных байтов потока. При кодировании новых символов значения V соответствующих кодов VLC присоединяются к предыдущему содержанию регистра R (новые коды VLC заносятся в старшие разряды). Счетчик числа занесенных в R битов увеличивается на число L (длина нового кода VLC в битах). Если R содержит более S байтов (здесь S обозначает число байтов, которые единовременно записываются в выходной поток), то S младших байтов из R записываются в выходной поток, а содержимое регистра R сдвигается вправо на S байтов.

Рис. 7.14. Блок-схема кодирования VLC.

Рис. 7.15. Архитектура кодирования переменными кодами VLC.

На рис. 7.15 показана основная архитектура выполнения процесса кодирования кодами переменной длины. Новые символы данных и контекстные указатели (выбранная таблица) поступают в модуль табличного поиска, который возвращает значение V и длину L соответствующего кодового слова. Модуль укладчика выстраивает коды VLC друг за другом и подает на выход по S байтов за один шаг (как описано в предыдущем примере).

Рис. 7.16. Блок-схема декодирования VLC

При практической разработке энтропийных кодеров переменной длины следует обращать внимание на вычислительную эффективность алгоритмов и на объем поисковых таблиц. На программном уровне процедуры энтропийного кодирования могут сильно нагружать процессор из-за частого использования побитных операций, используемых для укладки и сдвига кодов. Построение хороших таблиц поиска также является определенной проблемой по причине нерегулярной структуры таблицы кодов VLC. Например, таблица TCOEF в MPEG-4 Visual (см. гл. 3) индексируется по трем параметрам: «серия» (длина предшествующей серии нулей), «значение» (величина следующего за этими нулями ненулевого коэффициента) и «конец» (флаг последнего ненулевого коэффициента в блоке). Всего имеется только 102 доступных кода VLC и свыше 16 ООО допустимых комбинаций троек («серия», «значение», «конец»), которым ставится в соответствие или код LVC переменной длины до 13 бит, или фиксированный 20 битовый escape-код. Поэтому хранение соответствующей поисковой таблицы потребует значительного объема памяти. В стандарте Н.264 используется схема кодов переменной длины, в которой многие символы представляются «универсальными» экспоненциальными кодами Голомба, которые непосредственно вычисляются по значению символа данных (значит, не нужно строить таблицы поиска) (см. гл. 6).

 

7.2.6.2. Декодирование кодов переменной длины

 

Декодирование кодов VLC основано на «сканировании» принятого битового потока в целях разделения его на разрешенные кодовые слова, которым ставятся в соответствие подходящие синтаксические элементы. Как и при кодировании, необходимо знать текущий контекст для правильного выбора таблицы кодовых слов. На рис. 7.16 изображен простой метод декодирования одного кодового слова VLC. Декодер считывает последовательные биты входного потока до обнаружения (типичная ситуация) допустимого кода VLC или до выявления недопустимого кода VLC (т.е. кода, который отсутствует в текущем контексте). Например, код, начинающийся девятью или более нулями, не допустим, если декодер ожидает коэффициент преобразования MPEG-4. Декодер возвращает на выходе подходящий синтаксический элемент, если обнаружен допустимый код, и индикатор ошибки, если выявлен недопустимый код VLC.

Таблица 7.2. Пример декодирования кодов VLC в MPEG-4 Visual TCOEF.

Состояние	Вход	Следующее состояние	VLC	Выход
0	0	1	0..	-
	1	2	1..
1	0	...более позднее	00..
	1	...более позднее	01..
2	0	0	10s	(0,0,s1)
	1	3	11..
3	0	0	110s	(0,1,s1)
	1	4	111..	—
4	0	0	1110s	(0,2,s1)
	1	0	1111s	(0,0, s2)
и т.д.	...	...	...	...

Декодирование VLC может требовать высоких вычислительных затрат, или большой памяти, или и того и другого. Один возможный метод реализации такого декодера заключается в использовании конечного автомата. Декодер находится в начальном состоянии и переходит из состояния в состояние в зависимости от значения очередного бита. В какой-то момент декодер приходит в состояние, которое соответствует допустимому коду VLC или недопустимому коду VLC. Декодированный элемент синтаксиса (или индикатор ошибки) выдается на выход, а декодер опять возвращается в начальное состояние. В табл. 7.2 приведена первая часть декодирования последовательности контекста MPEG-4 Visual TCOEF (коэффициентов преобразования) с начальным состоянием 0. Если входной бит равен 0, то следующее состояние будет 1, а если входной бит равен 1, то следующее состояние — 2. Из состояния 2, если входной бит 0, декодер «обнаруживает» допустимый код VLC, а именно 10. В этом контексте требуется декодировать еще один бит после каждого VLC (это знаковый бит коэффициента преобразования). В итоге декодер возвращает соответствующий синтаксический элемент и переходит в состояние 0. Заметим, что если декодер декодирует синтаксический элемент, для которого «конец» = 1, то это указывает на конец блока ненулевых коэффициентов, поэтому следует обновить или поменять контекст.

В этом примере декодер может обрабатывать один бит в каждом состоянии (т.е. один бит за такт аппаратной реализации). Это может оказаться слишком медленной процедурой для некоторых приложений. В этом случае более продвинутая архитектура может анализировать несколько бит (или все слово VLC) за один такт. Примеры архитектур для кодирования и декодирования VLC приведены в [26 - 29].

7.2.6.3. Арифметическое кодирование

Арифметический кодер (см. гл. 3) кодирует каждый синтаксический элемент путем последовательного повышения точности кодирующего дробного числа. Потенциально арифметическое кодирование (сжатие) является более эффективным по сравнению с кодированием кодами переменной длины (это связано с более точным представлением распределения вероятностей символов). На практике обычно бывает необходимым представлять длинные дробные числа, генерируемые арифметическим кодером, с использованием целочисленных значений конечной арифметики, имеющей ограниченную разрядность представления целых чисел. В работе [30] приведен детальный анализ реализаций алгоритма контекстного арифметического кодирования (САВАС), адаптированного к основному профилю Н.264, который обсуждался в гл. 6.