CABAC: что скрывается за этими пятью буквами, часть вторая

Мы уже начали разбираться, что такое контекстно--адаптивное двоичное арифметическое кодирование. Часть первая тут. Сегодня попробуем представить последовательность действий в виде блок-схемы.

Пусть алфавит передаваемого сообщения состоит из набора символов {x1} (в рассмотренных выше примерах этот алфавит состоял из трех символов {a,b,EOF}, при этом для символа a значение i равно 1, для символа b — i = 2, для EOF — i = 3). Сформируем массив из значений Pi

где fi относительная частота появления в сообщении i-го символа. P0 положим равным нулю, а Pn=1, где N – количество символов в алфавите. (Опять, если вернуться к рассмотренному выше примеру кодирования, то N=3, а P = {0, 0.1, 0.95, 1}. При введенных обозначениях последовательность действий при арифметическом кодировании каждого символа можно представить в виде диаграммы (рис. 1).

Процедура EncodeSymbol() принимает два аргумента: i – номер кодируемого символа в алфавите, P – массив значений Pi. Как видно из блок-схемы, на первом этапе кодирования вычисляется длина текущего интервала R (при этом используются текущие значения его нижней L и верхней H границ). Величина H используется для вычисления новых обновленных значений границ интервала. Таким образом, на первом этапе кодирования каждого символа сообщения выполняется деление текущего отрезка. Второй этап кодирования представляет собой процедуру ренормализации (рис. 2).

Как уже было сказано при описании процедуры ренормализации, если текущий интервал полностью лежит в диапазоне [0, 1), т. е. если H<1/2, то в выходной битовый поток записывается значение 0 и последовательность из значений 1, длина которой равна значению переменной bitsOutstanding. Все эти действия выполняются процедурой put_bits(), блок-схема которой представлена на рис. 3. Значения границ интервала L и H удваиваются.

Если текущий интервал полностью лежит в диапазоне [1/2, 1), т. е. если L больше или равно 1/2, то в выходной поток записывается 1 и последовательность из 0, длина которой равна значению переменной bitsOutstanding (здесь опять используется процедура put_bits()). Изменение значений границ интервала в этом случае происходит таким образом, чтобы в два раза увеличилось расстояние от L и H до 1. Обновленные значения L и H, таким образом, можно рассчитать как:

L = 1 – 2(1 – L) = 2L – 1 = 2(L – 1/2),

H = 1 – 2(1 – H) = 2H – 1 = 2(H – 1/2),

что и выполняется в этой ветви процедуры RenormE.

Наконец, если текущий интервал полностью лежит в дипазоне [1/4, 3/4), т. е. если L больше или равно 1/4, и H<3/4, то значение величины bitsOutstanding увеличивается на 1, а границы интервала сдвигаются таким образом, чтобы в два раза увеличилось расстояние от L и H до 1/2:

L = 1/2 – 2(1/2 – L) = 2L – 1/2 = 2(L – 1/4),

H = 1/2 + 2(H – 1/2) = 2H – 1/2 = 2(H – 1/4),

что и выполняется в этой ветви процедуры RenormE.

На рис. 3 представлена блок-схема процедуры put_bits(). Эта процедура принимает в качестве аргумента значение бита (0 или 1) и записывает его в выходной битовый поток, представляющий результат арифметического кодирования. Процедура записи бита в поток на блок-схеме условно обозначена как write_bit(). После выполнения записи производится проверка значения переменной bitsOutstanding. Производится запись в поток последовательности значений !b (здесь в блок-схеме использовано обозначение операции «НЕ» из языка C), длина которой равна значению bitsOutstanding.

Олег Пономарев — специалист в области распространения радиоволн, статистической радиофизики, доцент кафедры радиофизики НИ ТГУ, кандидат физико-математических наук. 16 лет занимается вопросами видео кодирования и цифровой обработки сигналов. Руководитель исследовательской лаборатории Elecard.