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

TL;DR

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

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

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

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

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

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

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

Энтропийное кодирование старше видео на десятилетия. David Huffman опубликовал свой алгоритм оптимальных префиксных кодов в 1952 году как курсовое задание в MIT – и Huffman стал стандартом lossless-сжатия от PKZIP до JPEG. Арифметическое кодирование независимо изобрели Jorma Rissanen в IBM (1976) и Richard Pasco в своей PhD-диссертации (1976), после чего арифметика плотно патентовалась в 1980-х – поэтому JPEG в реальной жизни использовал Huffman, хотя в спецификации описывал оба варианта. 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) заменил binary-арифметику на многосимвольный range coder, портированный из исследовательского кодека Daala – он умеет кодировать сразу несколько значений в одном символе и адаптирует вероятности per-symbol, а не per-frame. VVC (2020) остался при binary CABAC, но переработал probability estimator: теперь он держит несколько параллельных «rate» дорожек, настроенных под разные битрейт-режимы.

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

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

Как работает CAVLC – VLC с поворотом

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

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

Допустим, zig-zag-скан одного 4×4-luma-блока дал такой список коэффициентов, от 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, но capped at 3). Кодовое слово выбирается из одной из четырёх таблиц; таблица – по среднему количеству ненулевых коэффициентов в двух соседних 4×4-блоках сверху и слева. Распространённые состояния соседей получают короткое (1–6 бит) кодовое слово; редкие – длиннее.

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

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

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

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

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

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

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

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

CABAC, или Context-Adaptive Binary Arithmetic Coding, – это сердце H.264 High profile, всего HEVC и всего VVC. Самый изученный энтропийный кодер современного видео; внутри у него три движущиеся части: бинаризация, context modelling и binary arithmetic coding. Они работают конвейером по каждому символу.

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

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

Binary arithmetic coding держит единый интервал – пару (low, high) – представляющую сообщение, закодированное на текущий момент. Когда энкодер выдаёт бин, он делит интервал на два куска пропорционально вероятностям 0 и 1, выбирает кусок, соответствующий реальному биту, и сужает интервал до этого куска. Когда интервал сходится за 0,5 в ту или иную сторону, старший бит фиксируется и пишется в битстрим, после чего интервал удваивается и работа продолжается. Символ с вероятностью 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-овская работа Sze и Budagavi 2012 года сообщает, что архитектура HEVC CABAC уменьшает максимальное число context-coded бинов в 8 раз и память line buffer в 20 раз относительно H.264 CABAC – именно потому, что стандарт сознательно настраивали под 4K hardware decoder.

Range coder AV1 – non-binary, per-symbol adaptive

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

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

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

Битстрим AV1 поддерживает несколько frame context tables, индексируемых через frame_context_idx. Типичный энкодер держит в памяти четыре или восемь контекстов и переключается между ними по содержимому предыдущего кадра – это помогает на сценоразделах и в temporal-layer-ах с резко разной статистикой. Цена – на стороне декодера: hardware-декодер AV1 должен хранить эти таблицы в быстрой on-chip памяти и переключаться между ними по сигналу, что и есть одна из причин, почему hardware-декодеры 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, выбором transform и квантованием. В apples-to-apples-тесте, описанном в AV1-обзоре, энтропийная стадия AV1 даёт примерно 3–5% экономии битрейта по сравнению с CABAC HEVC при том же качестве. Это сверху больших выигрышей от больших block sizes, большего числа transform-форм и adaptive quantisation, – но это чистое доказательство, что сам движок материально эффективнее.

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

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

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

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

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

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

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

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

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

Мы строим конференц-, OTT-, surveillance-, e-learning- и telemedicine-пайплайны вокруг H.264, HEVC и всё чаще AV1, и читаем энтропийно-закодированные битстримы в каждом проекте. Когда live HEVC-трансляция клиента показывает блочный мусор, начинающийся в одной и той же точке каждой GOP, первое место, куда мы смотрим, – CABAC re-init в slice-заголовке. Когда файл 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.
• Context modelling – выбор правильной вероятности под каждый символ по его соседям – отличает «энтропийный кодер видеокодека» от обычного арифметического.
• Пересев энтропийного состояния на границе slice/frame – одно из самых ошибкоопасных мест в live-пайплайне.

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

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