Энтропийное кодирование в деталях: CAVLC, CABAC и арифметическое кодирование

TL;DR

Энтропийное кодирование – заключительная стадия работы видеоэнкодера, на которой поток мелких целых чисел, пар (run, level) и флагов решений преобразуется в реальные байты битстрима. В старых кодеках применяются таблицы кодовых слов переменной длины (Huffman, Exp-Golomb, CAVLC) – они просты в декодировании, но требуют на 5–15% больше места, чем теоретический минимум. Современные кодеки используют арифметическое кодирование, способное сжимать один бит до доли бита в среднем и работающее в пределах 1% от предела Шеннона – за счёт сложной внутренней state machine, обновляющейся после каждого символа. H.264 использует оба подхода: CAVLC в «дешёвых» профилях и CABAC – во всех остальных. HEVC и VVC отказались от CAVLC и применяют только CABAC; AV1 отказался от бинарного арифметического кодирования и внедрил многосимвольный range coder, заимствованный из проекта Daala. Если вы знаете, какой кодер используется в потоке, вы понимаете, как был собран этот файл, почему он имеет такой размер и как поведёт себя на слабом или мощном оборудовании декодера.

Почему это важно

Энтропийное кодирование – одна из тех тем, где пятиминутный разговор с правильным человеком экономит проекту целый год путаницы. Продакт-менеджер, который различает CAVLC и CABAC, больше не задаёт вопрос: «Почему H.264-файл в профиле Baseline в два раза больше?» – потому что Baseline запрещает CABAC. Основатель, понимающий, что AV1 использует non-binary арифметический кодер из исследовательского проекта Daala, осознаёт, почему hardware-декодеры AV1 сложнее в производстве, чем у HEVC, и почему массовое внедрение AV1 идёт медленнее, чем ожидалось. Стриминг-инженер, умеющий отличать CABAC re-init на slice header от переключения frame_context_idx в AV1, чинит сломанный live-поток за час, а не за неделю. Эта статья – расширенная версия того самого пятиминутного разговора. Начнём с Шеннона и Хаффмана, поднимемся до CABAC, разберём range coder в AV1 и закончим аккуратной сравнительной таблицей, которую можно взять с собой на следующий митинг по выбору кодека.

Что такое «энтропийное кодирование» на самом деле

Каждая предыдущая стадия видеоэнкодера – предсказание, преобразование, квантование, переупорядочение и run-encoding – генерирует последовательность символов. Символы – это разности векторов движения, режимы предсказания, пары (run, level), флаги закодированных блоков, позиция последнего ненулевого коэффициента и сотни других небольших целых чисел, описывающих, как декодер должен восстановить следующий блок. Энтропийное кодирование берёт эту последовательность символов и записывает её в битовый поток, используя минимальное количество бит – без потери информации.

Ключевая идея, сформулированная Клодом Шенноном в 1948 году, заключается в следующем: минимальное среднее число бит на символ – это энтропия его распределения вероятностей: H = -Σ p(x) log₂ p(x), измеряемая в битах на символ. Идеально честная монета требует ровно 1 бит на бросок. Монета, выпадающая орлом в 90% случаев, требует всего 0,47 бита на бросок – но только при условии, что кодер умеет работать с дробными битами и усреднять их по множеству бросков. Двоичный код, использующий целое число бит на символ, не может опускаться ниже 1 бита на бросок монеты, независимо от того, насколько она перекошена.

Энтропийные кодеры решают проблему дробного бита двумя разными способами. Коды переменной длины (Huffman, Exp-Голомб, CAVLC) приближаются к пределу Шеннона с помощью фиксированной таблицы кодовых слов, каждое из которых занимает целое число бит. Они просты, быстры, хорошо поддаются параллелизации и платят небольшой штраф в эффективности – обычно 3–10% сверх энтропии. Арифметические коды (CABAC, range coder в AV1) рассматривают всё сообщение как одно дробное число между нулём и единицей и накапливают биты постепенно, по мере сужения интервала. В реальных условиях они укладываются в 1% от энтропии – ценой сложной внутренней машины состояний, обновляющейся после каждого закодированного бита.

Нажмите, чтобы увеличить

Короткая история

Энтропийное кодирование появилось на десятилетия раньше видео. В 1952 году Дэвид Хафман опубликовал свой алгоритм оптимальных префиксных кодов как курсовую работу в MIT – и с тех пор кодирование по методу Хафмана стало стандартом безпотерьного сжатия, от PKZIP до JPEG. Арифметическое кодирование было независимо разработано Йормой Риссаненом в IBM (1976) и Ричардом Паско в его докторской диссертации (1976). В 1980-х годах арифметическое кодирование активно патентовалось, поэтому в реальных реализациях JPEG использовался Хафман, хотя в спецификации были описаны оба метода. IBM Q-Coder (1988) и QM-Coder (1993) сделали арифметическое кодирование практически применимым на аппаратном уровне того времени.

CABAC появился в H.264/AVC в 2003 году. Его разработали Detlev Marpe, Heiko Schwarz и Thomas Wiegand в Fraunhofer HHI. Они объединили двоичное арифметическое кодирование с context modelling – идеей, что вероятность следующего бита зависит от уже встретившихся битов в локальном окружении. CABAC обеспечил выигрыш в сжатии на 9–14 % по сравнению с CAVLC при одинаковом качестве, но стоил примерно в 1,5 раза дороже в декодировании. HEVC сохранил CABAC и полностью убрал CAVLC. AV1 (2018) заменил двоичную арифметику на многосимвольный range coder, заимствованный из исследовательского кодека Daala: он способен кодировать сразу несколько значений в одном символе и адаптирует вероятности per-symbol, а не per-frame. VVC (2020) остался на binary CABAC, но переработал оценщик вероятностей: теперь он поддерживает несколько параллельных «rate»-дорожек, настроенных под различные режимы битрейта.

Нажмите, чтобы увеличить

Картина – медленное, монотонное улучшение. Все кодеки после H.264 используют арифметическое кодирование; каждый новый арифметический кодер даёт прирост эффективности на один-два процента за счёт более точной настройки моделирования контекста.

Как работает CAVLC – VLC с перемежением

CAVLC, или Context-Adaptive Variable-Length Coding, – это энтропийный кодер, используемый в профилях H.264 Baseline, Extended и младших версиях High. Он разрешён также в профиле High и 10-битных профилях, но применяется обычно в тех случаях, когда декодер работает от батареи (например, смартфон 2007 года или бюджетный set-top box), либо когда для энкодера важнее скорость декодирования, чем размер выходного файла.

CAVLC – это не просто кодирование Хаффмана. Это небольшое семейство кодовых слов, выбор которых зависит от контекста – от того, что энкодер только что закодировал. Энкодер передаёт блок коэффициентов за пять шагов, каждый из которых использует свою VLC-таблицу, выбранную в зависимости от текущего состояния. Разберём эти шаги на примере.

Допустим, zig-zag-скан одного 4×4-блока яркости дал следующий список коэффициентов – от DC и далее:

0, 3, 0, 1, -1, -1, 0, 1, 0, ...  (остальные нули)

Ненулевые значения находятся на позициях 1, 3, 4, 5 и 7. Всего их – 5. Три из них (значения 1, -1, -1) имеют модуль 1 и расположены непосредственно перед хвостом нулей в конце скан-порядка – это trailing ones.

Шаг 1 – coeff_token. Энкодер передаёт одно кодовое слово, которое одновременно кодирует два числа: общее количество ненулевых коэффициентов (здесь – 5) и количество trailing ones (здесь – 3, но ограничено значением 3). Выбор кодового слова осуществляется из одной из четырёх таблиц, индекс которой определяется средним количеством ненулевых коэффициентов в двух соседних 4×4-блоках – сверху и слева. Распространённым состояниям соседей соответствуют короткие кодовые слова (1–6 бит), редким – более длинные.

Шаг 2 – знаки trailing ones. Для каждого trailing one энкодер передаёт один бит: 0 – для плюса, 1 – для минуса. Три trailing ones → три бита.

Шаг 3 – non-trailing levels. Оставшиеся ненулевые коэффициенты (в данном случае – только значение 3) кодируются как знаковые целые числа с использованием одной из семи VLC-таблиц. Начальная таблица выбирается по фиксированному правилу и «поднимается» по мере увеличения модуля следующего уровня. Небольшое значение уровня удерживает энкодер на таблице, оптимизированной для малых чисел; большое значение, напротив, переводит его на таблицу, эффективно кодирующую большие числа, но при этом использующую более длинные коды для малых. Именно это и составляет «контекст» в CAVLC – текущее состояние определяется выбором таблицы.

Шаг 4 – total_zeros. Энкодер передаёт количество нулей между DC-коэффициентом и последним ненулевым коэффициентом (здесь 3 – нули на позициях 0, 2, 6). Это фиксированная VLC-таблица, индексируемая числом ненулевых коэффициентов из шага 1.

Шаг 5 – run_before. Для каждого ненулевого коэффициента (обработка идёт с конца к началу) энкодер передаёт количество нулей, предшествующих ему. VLC-таблица для run_before индексируется по оставшемуся «бюджету нулей» – он быстро исчерпывается, и кодовые слова становятся короче.

Складываем биты: 5-коэффициентный 4×4-блок обычно кодируется в 22–28 бит. Основные затраты идут на уровни больших коэффициентов; накладные расходы run-coding минимальны, поскольку таблицы тщательно настроены.

Хитрость CAVLC заключается в том, что она использует только что закодированные данные в качестве контекста для следующего шага. Энкодеру не нужно обращаться к глобальному состоянию, декодеру – его поддерживать, а весь блок обрабатывается всего пятью короткими табличными запросами. Именно поэтому CAVLC стал стандартом для аппаратных декодеров эпохи 2003–2010 годов – он обрабатывается за несколько тактов на блок и легко параллелится по блокам.

Нажмите, чтобы увеличить

Как работает CABAC – двоичное арифметическое кодирование с «мозгами»

CABAC, или Context-Adaptive Binary Arithmetic Coding, – это сердце H.264 High Profile, а также ключевых технологий HEVC и VVC. Самый изученный энтропийный кодер в современных видеоформатах; его внутренняя структура включает три основные компоненты: бинаризация, моделирование контекста и бинарное арифметическое кодирование. Эти этапы работают последовательно – по каждому символу.

Бинаризация преобразует каждый входной символ – разницу вектора движения, режим предсказания, значение коэффициента – в последовательность битов, называемых bins. Часть бинов кодируется в режиме fixed bypass по одному биту (этот режим используется, когда символ по сути случайный – например, младшие биты величины большого коэффициента). Большинство бинов проходит через полный арифметический кодировщик. Правила бинаризации для каждого синтаксического элемента строго определены стандартом: signed Exp-Golomb для разностей векторов движения, truncated unary для режимов предсказания и так далее. Цель бинаризации – свести многозначный алфавит (требующий сложного арифметического кодера) к двухсимвольному (для которого достаточно простого бинарного кодирования).

Context modelling выбирает модель вероятности для каждого бина на основе его позиции в символе и уже закодированных соседей. В HEVC используется около 130 контекстных моделей только для бинов коэффициентов преобразования luma, плюс ещё несколько сотен – для режимов предсказания, данных движения и флагов. Каждый контекст – это небольшое состояние, обычно состоящее из двух чисел, описывающих текущую оценку вероятности P(bin = 1). Энкодер выбирает подходящий контекст для текущего бина, считывает вероятность и передаёт пару (bin, probability) арифметическому кодировщику. Декодер выполняет те же действия в обратном порядке. Именно правильный выбор контекста отличает CABAC от обычного арифметического кодирования: контекст, говорящий «мы кодируем флаг значимости коэффициента на диагональной позиции 3 в 4×4-подблоке, у которого в верхнем левом соседе два ненулевых коэффициента», предсказывает P(bin = 1) значительно точнее, чем единая глобальная вероятность.

Binary arithmetic coding использует единый интервал – пару (low, high), представляющую закодированное на текущий момент сообщение. Когда энкодер выдаёт бит, он делит интервал на две части пропорционально вероятностям 0 и 1, выбирает ту, что соответствует реальному биту, и сужает интервал до неё. Как только интервал сдвигается ближе чем на 0,5 к 0 или к 1, старший бит фиксируется и записывается в битовый поток, после чего интервал удваивается, и процесс продолжается. Символ с вероятностью 0,9 сужает интервал на 10% – в среднем это около 0,15 бита, что заметно меньше минимально возможного значения в 1 бит у кодов переменной длины. Оценка вероятности контекста обновляется после каждого бита: конечный автомат (state machine) переходит «вверх» к более уверенным предсказаниям, если предсказанный бит совпал, и «вниз» – если нет. В H.264 / HEVC используется state machine с 64 состояниями; в VVC оценщик работает на двух параллельных rate-каналах для разных режимов битрейта.

Эффект впечатляющий. CABAC кодирует bins типичного HEVC-потока примерно на 9–14% эффективнее, чем CAVLC тот же материал в H.264 при одинаковом качестве, и на 6–8% эффективнее, чем CABAC в H.264 High Profile – поскольку HEVC использует более тонкую сетку контекстов. Однако есть и цена: CABAC-декодер обрабатывает bins последовательно, выбор контекста каждого бина зависит от предыдущего, и эта последовательная зависимость – главная причина, по которой hardware-декодеры HEVC обрабатывают меньше мегапикселей в секунду на ту же площадь кремния, чем CAVLC-декодеры.

Нажмите, чтобы увеличить

Цена CABAC – снижение пропускной способности. Выбор контекста для каждого бина зависит от предыдущего значения; обновление состояния контекста – от реального значения бина; обновление интервала – от обоих факторов. На обработку одного бина в декодере уходит около 10–20 тактов, а в одном 4K-кадре HEVC таких бинов – миллионы в секунду. Исследование Сзе и Будагави из MIT 2012 года показывает, что архитектура CABAC в HEVC позволяет уменьшить максимальное число context-coded бинов в 8 раз и объём памяти line buffer в 20 раз по сравнению с CABAC в H.264 – именно потому, что стандарт изначально проектировался с учётом аппаратных декодеров для 4K.

Range coder AV1 – не бинарный, адаптивный на уровне символов

Энтропийный движок AV1 принципиально отличается от CABAC на всех уровнях. Арифметический кодировщик – range coder – представляет собой вариант двоичного арифметического кодирования, работающий с целочисленными интервалами, а не с дробными; он проще реализуется на fixed-point аппаратуре. От двоичной бинаризации отказались: AV1 кодирует символы длиной до 16 значений алфавита напрямую, без предварительной бинаризации. Оценка вероятностей обновляется по каждому символу, а не по кадру – как только декодер обрабатывает коэффициент, вероятность следующего пересчитывается.

Арифметический движок взят из Daala – экспериментального кодека, разработанного в Mozilla (позже xiph.org) Тимоти Терриберри, Жан-Марком Валином и другими в начале 2010-х. У Daala было три ключевые инновации, перешедшие в AV1: арифметический кодер, работающий с не-бинарными символами и способный за один вызов закодировать один из до 16 символов; адаптация вероятностей на уровне каждого символа; реализация без умножений – только с помощью сдвигов и табличных lookup-ов. По обзору AV1 в Proceedings of the IEEE 2021 года (Han et al.), сочетание этих идей примерно эквивалентно параллельному кодированию четырёх бинарных бинов – то есть AV1-декодер может обеспечивать ту же пропускную способность энтропийного декодера, что и HEVC CABAC, при этом обрабатывая алфавит в четыре раза больше.

Per-символ адаптация – вторая значительная перемена. В H.264 / HEVC состояние вероятности каждого контекста инициализируется в начале каждого slice по умолчанию из стандартной таблицы и затем обновляется по мере декодирования этого slice. AV1 использует схожую модель, но обновляет вероятности после каждого закодированного символа с небольшим фиксированным шагом. В результате: в длинном, статистически однородном кадре энтропийное кодирование завершается с распределением, очень близким к эмпирическому – ближе, чем у CABAC, который остаётся привязанным к начальной таблице инициализации в начале slice.

Битстрим AV1 поддерживает несколько таблиц контекстов кадров, индексируемых через frame_context_idx. Типичный энкодер хранит в памяти четыре или восемь контекстов и переключается между ними в зависимости от содержимого предыдущего кадра – это полезно при смене сцены и в временных слоях с резко отличающейся статистикой. Однако это накладывает дополнительные требования на декодер: аппаратный декодер AV1 должен хранить эти таблицы в быстрой on-chip памяти и переключаться между ними по сигналу. Именно это стало одной из причин, по которой аппаратные декодеры AV1 долгое время не выходили в массовое производство даже после стабилизации спецификации.

Разберём пример. Допустим, энкодер кодирует коэффициент из алфавита {0, 1, 2, 3, 4}. Текущие вероятности, масштабированные на 32768 (fixed-point база AV1), – {16384, 8192, 4096, 2048, 2048}. Энкодер выбирает коэффициент 2 (вероятность 4096/32768 = 12,5%). Арифметический движок сужает диапазон до слайса, соответствующего символу 2 – это стоит примерно 3 бита – и обновляет таблицу вероятностей: P(2) увеличивается примерно на 100, а остальные ячейки уменьшаются примерно на 25 каждая. Следующий коэффициент в том же контексте начинает обработку уже с слегка изменённого распределения.

Выигрыш по компрессии по сравнению с CABAC в HEVC зависит от того, как энкодер выполняет motion estimation, выбирает преобразование и квантование. В тесте «яблоки с яблоками», описанном в обзоре AV1, энтропийная стадия AV1 обеспечивает экономию битрейта на уровне 3–5% по сравнению с CABAC в HEVC при одинаковом качестве. Это дополнительно к значительным выигрышам за счёт больших размеров блоков, большего числа форм преобразований и адаптивного квантования – но сам по себе этот результат является прямым доказательством того, что сам энкодер существенно эффективнее.

Нажмите, чтобы увеличить

Типичный подводный камень – утечка контекстного состояния через границу slice

Самый частый баг энтропийного кодирования в стриминговом пайплайне – это состояние вероятностей, которое «пережило» границу, где ему не положено оставаться. Slice-заголовки в HEVC, frame-заголовки в AV1 и флаги CABAC re-init в H.264 существуют именно для того, чтобы сбросить энтропийный движок в нужных местах – там, где декодер может подключиться к потоку посередине: при tune-in в live-стриминге, при seek в VOD или в точке случайного доступа (random access point) в транспортном потоке.

Если энкодер пропустил пересчёт, декодер подключается к потоку с неверным состоянием вероятностей. Первые символы декодируются неправильно, потому что интервал у энкодера уже не совпадает с интервалом у декодера. Ошибка распространяется по всей слайсе, вызывая известный эффект «блочный мусор от одной точки до конца слайса» – его видел любой, кто хоть раз работал с HEVC в эфире.

Лечится тщательным аудитом IDR/CRB/BLA-кадров в энкодере и соответствующим аудитом разбора заголовков слайсов в декодере. В AV1 релевантный флаг – error_resilient_mode, он заставляет декодер использовать стандартные таблицы контекста, а не унаследованные. В HEVC – это entry_point_offsets в слайсе и повторная инициализация CABAC в начале каждого слайса. В H.264 – cabac_init_idc в заголовке слайса. Сделать это правильно – и энтропийная стадия становится прозрачной. Сделать неправильно – и поток будет выглядеть повреждённым настолько, что без инструментов анализа на уровне битов выявить причину практически невозможно.

Сравнительная таблица

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

Из таблицы видны два факта. Во-первых, выигрыши уменьшаются – лёгкие улучшения уже были получены в 2003 году, и каждый следующий кодек добивается лишь долей процента. Во-вторых, только AV1 нарушил шаблон binary-аритметики. VVC остался на binary CABAC, потому что комитет посчитал, что предельный выигрыш от перехода к non-binary не стоит разрушения аппаратной архитектуры. Оба решения обоснованы; оба сейчас используются в production.

Где Фора Софт в этой картине

Мы строим пайплайны для конференц-связи, OTT, видеонаблюдения, e-learning и телемедицины на базе H.264, HEVC и всё чаще AV1, и в каждом проекте работаем с энтропийно-закодированными битовыми потоками. Когда у клиента в live-трансляции HEVC появляется блочный шум, начинающийся в одной и той же точке каждой GOP, первое, куда мы обращаем внимание, – это CABAC re-init в заголовке слайса. Когда AV1-файл корректно декодируется в одном плеере, но ломается в другом, след почти всегда ведёт к frame_context_idx и плееру, который не реализовал полный набор таблиц вероятностей. Двадцать лет отладки битовых потоков по H.263, MPEG-2, MPEG-4 Part 2, H.264, HEVC, VP8, VP9 и AV1 научили нас одному: энтропийная стадия – последнее место, где должен находиться баг, и первое, куда должен заглянуть отладчик.

Ключевые мысли

• Энтропийное кодирование – заключительная lossless-стадия, упаковывающая поток мелких целых чисел в минимально возможный битовый поток.
• Коды переменной длины (CAVLC, Huffman) находятся примерно на 5–10% выше энтропийного предела, но легко декодируются и хорошо поддаются параллелизации.
• Арифметические коды (CABAC, AV1 range coder) приближаются к пределу с погрешностью около 1%, но требуют последовательной работы state machine.
• HEVC и VVC используют исключительно CABAC; H.264 поддерживает оба метода; AV1 применяет non-binary range coder, заимствованный из Daala.
• Моделирование контекста – подбор правильной вероятности для каждого символа на основе его соседей – и отличает «энтропийный кодер видеокодека» от обычного арифметического кодера.
• Перенос энтропийного состояния на границе slice/frame – одно из самых уязвимых мест в live-обработке.

Что читать дальше

• Переупорядочение, zig-zag scan и run-length coding – этап, на котором формируются символы для энтропийного кодирования.
• Квантование: где теряется качество – этап, определяющий, сколько ненулевых значений останется в блоке.
• H.265 / HEVC: технически и про патенты – кодек, сделавший CABAC стандартом по умолчанию.