二进制熵编码深度解析

当你在手机上拍摄一段视频、将照片保存为 JPEG、或者将文件压缩成 ZIP 时，背后都运行着同一类核心算法——二进制熵编码。这些算法决定了最终比特流中每一个比特的取值，是压缩效率的"最后一公里"。

在图像和视频压缩管线中，原始像素首先经过变换（如 DCT）和量化，将连续的像素值转换为离散的整数系数。这些整数系数随后需要被转换为二进制比特流以便存储或传输——这正是熵编码的职责。熵编码的目标是：用尽可能少的比特数表示这些离散符号，使平均码长尽可能接近信源的信息熵 #Richardson-2010。

不同的编码算法在复杂度和压缩效率之间存在权衡。Huffman 编码简单但无法达到熵极限；算术编码可以无限逼近熵极限但计算复杂度更高；CABAC 在此基础上引入上下文自适应机制，成为 H.264/HEVC 的核心熵编码器。与此同时，通用文件压缩工具如 ZIP（使用 DEFLATE）和 7z（使用 LZMA）虽然不服务于视频编码，但它们的编码原理与视频编码中的熵编码一脉相承——都建立在"高频符号用短码、低频符号用长码"这一信息论基本思想之上。

本文将系统讲解以下内容：Huffman 编码、Golomb/Rice 编码、指数哥伦布编码（Exp-Golomb）、算术编码、Range Coding、DEFLATE 算法（ZIP）、LZMA 算法（7z），以及 CABAC 和 CAVLC 在 H.264 中的具体应用。每个算法将从直觉出发，给出构造规则，最后说明其工程应用。

Shannon 熵：信息的数学度量

1948 年，Claude Shannon 在《通信的数学理论》中定义了信息熵（Information Entropy），为所有压缩算法提供了理论基础。对于一个离散信源，其符号集为 \(\{s_1, s_2, \ldots, s_n\}\)，各符号出现概率为 \(p(s_i)\)，则信源的熵定义为：

熵的含义是：平均而言，编码该信源的每个符号至少需要 \(H(S)\) 个比特。这是所有无损压缩算法的理论下界——无论你设计多么精巧的编码方案，都无法将平均码长压缩到熵以下 #Shannon-1948。

前缀码与 Kraft 不等式

在实际编码中，我们使用前缀码（Prefix Code）——没有任何一个码字是另一个码字的前缀。这保证了编码的即时可解码性：解码器可以在读到每个码字的最后一位时立即识别出对应的符号，无需回溯。

前缀码的存在性由 Kraft 不等式保证：若码字长度为 \(l_1, l_2, \ldots, l_n\)，则存在对应前缀码的充要条件是：

这意味着，如果我们为高频符号分配短码、低频符号分配长码，且码字长度满足 Kraft 不等式，就能构造出有效的前缀码。Huffman 编码正是这一思想的最优实现。

从整数到比特流：编码的输入

在图像和视频压缩中，熵编码的输入不是原始像素值，而是经过预测 → 变换 → 量化后得到的量化系数和语法元素（如运动向量、宏块类型等）。这些元素的值都是整数，但它们的统计分布各不相同：

不同分布特征需要不同的编码策略。H.264 为此设计了两套熵编码方案——CAVLC（轻量级）和 CABAC（高效率），并用 Exp-Golomb 编码覆盖所有方案中的公共语法元素。这种分层设计是理解 H.264 熵编码的关键。

H.264 中需要编码的主要语法元素参数表（来源：Vcodex, Table 21）

构造算法：自底向上的树构建

Huffman 编码由 David Huffman 在 1952 年提出，是一种构造最优前缀码的贪心算法。"最优"的含义是：在所有可能的前缀码中，Huffman 编码的平均码长最短，且不会超过熵 + 1 bit #Huffman-1952。

构造过程非常直观：

1. 统计每个符号的出现频率（权重）。
2. 将所有符号视为叶节点，放入一个按权重排序的优先队列。
3. 取出权重最小的两个节点，创建一个父节点，其权重 = 两子节点权重之和。
4. 左子节点编码为 0，右子节点编码为 1（或反之）。
5. 将父节点放回优先队列。
6. 重复步骤 3-5，直到队列中只剩一个节点——这就是 Huffman 树的根。

从根到每个叶节点的路径就是该符号的 Huffman 码字。高频符号路径短，低频符号路径长。

一个具体例子

假设有 5 个符号，权重为 A:16, B:32, C:32, D:8, E:8：

第 1 步：取 D(8) 和 E(8)，合并为 DE(16)
第 2 步：取 A(16) 和 DE(16)，合并为 ADE(32)
第 3 步：取 B(32) 和 C(32)，合并为 BC(64)
         （或取 ADE(32) 和 B(32)，取决于实现）
第 4 步：取 ADE(32) 和 BC(64)，合并为根节点(96)

最终编码：
  B → 00 (2 bits)
  C → 01 (2 bits)
  A → 10 (2 bits)
  D → 110 (3 bits)
  E → 111 (3 bits)

平均码长 = (32×2 + 32×2 + 16×2 + 8×3 + 8×3) / 96 = 2.17 bits

Huffman 编码的局限

Huffman 编码虽然最优，但它有一个根本性的局限：每个符号的码长必须是整数比特。这意味着，如果一个符号的概率为 0.4，其最优码长应为 \(-\log_2(0.4) \approx 1.32\) bits，但 Huffman 编码只能给它 1 bit 或 2 bits。

具体来说，Huffman 编码每个符号的码长只能是 \(1, 2, 3, \ldots\) bits，即概率必须是 \(1/2, 1/4, 1/8, \ldots\) 的形式才能达到最优。当符号概率不是 2 的负幂次时，Huffman 编码会浪费最多 1 bit/symbol。这就是算术编码的动机——它突破了整数比特的限制。

在 DEFLATE 中的应用

Huffman 编码是 DEFLATE 算法（ZIP 的核心）的两大组件之一。DEFLATE 将 LZ77 的输出（字面量 + 距离/长度对）再通过 Huffman 编码进一步压缩。DEFLATE 使用两种 Huffman 树：一棵编码字面量/长度符号，一棵编码距离符号。树的编码通过码长序列传输——只需传输每个符号的码长，解码器即可重建完全相同的 Huffman 树 #Feldspar-DEFLATE。

DEFLATE 对 Huffman 编码做了一个关键优化：限制码长不超过 15 bits。这一约束使得解码器可以用固定大小的查找表高效解码，同时通过特殊的码长排列顺序（16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15）来最小化树本身的存储开销。

为什么需要 Golomb 编码？

Huffman 编码需要预先知道符号的概率分布并构建码树。但在某些场景中，符号的取值范围很大（甚至无限），但分布呈现几何分布——即值 \(n\) 出现的概率为 \(p(n) = (1-p)^n \cdot p\)。例如，运动向量的差值在 0 附近最密集，向两侧指数衰减。

对于几何分布，Solomon Golomb 在 1960 年代证明了一种特殊的编码方式可以达到最优：Golomb 编码。其核心思想是将整数 \(n\) 分解为商 \(q\) 和余数 \(r\)，分别用一元码和定长二进制码编码 #Golomb-1966。

编码构造

给定参数 \(m\)，Golomb 编码将非负整数 \(n\) 编码为：

1. 计算 \(q = \lfloor n / m \rfloor\)，\(r = n \bmod m\)
2. 商 \(q\) 用一元码编码：\(q\) 个 0 后跟一个 1（或反之）
3. 余数 \(r\) 用 \(\lceil \log_2 m \rceil\) bits 的二进制码编码

当 \(m = 2^k\) 时，Golomb 编码退化为 Rice 编码，余数部分可以用简单的位操作实现，非常适合硬件加速。参数 \(k\) 的选择取决于分布的"陡峭程度"——分布越集中（\(p\) 越大），\(k\) 越小。

在 JPEG-LS 中的应用

JPEG-LS（ISO/IEC 14495-1）是一种无损/近无损图像压缩标准，其熵编码核心正是 Rice 编码。JPEG-LS 对预测残差使用自适应 Rice 编码：编码器根据已编码残差的统计特性动态调整参数 \(k\)，使其始终匹配当前的分布 #JPEG-LS-Standard。这种自适应机制无需传输码表，同时保持了低计算复杂度。

设计动机

Golomb/Rice 编码虽然对几何分布最优，但需要选择合适的参数 \(m\) 或 \(k\)。在视频编码中，不同语法元素的分布差异很大，为每种元素设计专用参数会增加复杂度。指数哥伦布编码（Exponential-Golomb Coding）是一种通用码（Universal Code），无需预知分布参数即可对任意非负整数进行编码，同时保持良好的编码效率。

Exp-Golomb 编码在 H.264/AVC 和 H.265/HEVC 中被广泛用于编码各种语法元素：宏块类型、参考帧索引、运动向量差、量化参数增量等 #Vcodex-CAVLC。

编码构造

0 阶 Exp-Golomb 编码（H.264 默认使用）将非负整数 \(n\) 编码为：

其中：

码字总长度为 \(2M + 1\) bits。解码过程为：

1. 数前导零的个数 \(M\)，读到 1 停止
2. 读取 \(M\) bits 的 INFO 字段
3. 计算 \(n = 2^M + \text{INFO} - 1\)

前几个码字为：

Exp-Golomb 码字表：code_num 与码字的对应关系（来源：Vcodex, Table 31）

可以看到，Exp-Golomb 编码的结构非常规律：每个"码长组"（1 bit, 3 bits, 5 bits, 7 bits, ...）恰好容纳 \(2^M\) 个码字。值 0 最短（1 bit），值越大码越长，但增长率仅为 \(2\log_2(n)\)。这种结构使得 Exp-Golomb 对小值密集、大值稀疏的分布（即近似几何分布）特别有效。

阶数 k 的推广

0 阶 Exp-Golomb 等价于 Elias Gamma 码。通过引入阶数 \(k\)，可以推广为 \(k\) 阶 Exp-Golomb 编码：

1. 计算 \(q = \lfloor (n + 2^k - 1) / 2^k \rfloor\)（等效于先加偏移再除以 \(2^k\)）
2. 商 \(q\) 用一元码编码
3. 余数 \(r = (n + 2^k - 1) \bmod 2^k\) 用 \(k\) bits 二进制码编码

阶数 \(k\) 越高，对小值的编码效率越低，但对大值的编码效率越高。H.264 主要使用 0 阶 Exp-Golomb，CABAC 中的某些 binarization 方案使用 \(k\) 阶 Exp-Golomb。

H.264 中的三种映射方式

在 H.264 中，Exp-Golomb 编码的实际值通过三种映射方式与 code_num 关联 #Vcodex-CAVLC：

ue(v) 的设计使得最常见的宏块类型（如 Pred_L0_16x16）获得最短的码字（1 bit），而较少见的类型（如 Pred_8x8）获得更长的码字。se(v) 的设计则让 MVD=0 映射到 code_num=0（1 bit），正值和负值交替排列，保证小绝对值的运动向量差获得短码。

为什么 H.264 选择 Exp-Golomb 而非 Huffman？

H.264 选择 Exp-Golomb 编码而非 Huffman 编码有三个关键原因：

第一，无需码表传输。Huffman 编码需要将码树随数据一起传输（或使用预定义表），而 Exp-Golomb 的构造规则是确定的——编码器和解码器只需约定使用 0 阶 Exp-Golomb，无需任何额外信息。这在视频流传输中尤为重要，因为每个 slice 都可能使用不同的统计特性。

第二，硬件实现极简。Exp-Golomb 的解码只需要前导零计数器 + 移位寄存器，无需查找表。这使得解码器可以在极低的硬件复杂度下实现高吞吐率。

第三，对未知分布的鲁棒性。Huffman 编码依赖于精确的概率估计，当实际分布与估计不符时效率急剧下降。Exp-Golomb 作为通用码，对任意几何-like 分布都能保持合理的编码效率——虽然不是最优，但"永远不差"。

核心思想：用区间表示消息

算术编码（Arithmetic Coding）由 Peter Elias 在 1960 年代提出，由 Jorma Rissanen 在 1976 年完善。其核心思想与 Huffman 编码有本质区别：Huffman 为每个符号分配一个独立的码字，而算术编码将整个符号序列映射到一个数值区间。

具体来说，算术编码维护一个当前区间 \([low, high)\)，初始为 \([0, 1)\)。每编码一个符号，根据该符号的概率将当前区间分为若干子区间，选择对应符号的子区间作为新的当前区间。编码完所有符号后，最终区间内的任意一个数都可以唯一地表示整个符号序列。

编码过程示例

假设有三个符号 A(概率 0.5)、B(概率 0.3)、C(概率 0.2)，编码序列 "BAC"：

初始区间：[0, 1)

编码 B (概率 0.3，区间 [0.5, 0.8))：
  [0.5, 0.8)

编码 A (概率 0.5，区间 [0, 0.5) 占据当前区间的左半)：
  [0.5, 0.5 + 0.3×0.5) = [0.5, 0.65)

编码 C (概率 0.2，区间 [0.8, 1.0) 占据当前区间的最后 20%)：
  [0.5 + 0.15×0.8, 0.5 + 0.15×1.0) = [0.62, 0.65)

最终区间 [0.62, 0.65) 中的任意值（如 0.625 = 0.101₂）
都可以唯一解码出 "BAC"

关键洞察是：区间的宽度决定了需要多少比特来表示。如果最终区间宽度为 \(w\)，则需要约 \(-\log_2(w)\) bits 来表示。这与 Huffman 编码的根本区别在于：算术编码不要求每个符号独立占用整数比特——一个概率为 0.4 的符号理论上需要 1.32 bits，算术编码可以精确地"累积"这些小数比特。

与 Huffman 编码的定量对比

考虑一个符号 A 概率 0.99、B 概率 0.01 的信源。信息熵为：

Huffman 编码只能给 A 分配 1 bit、B 分配 1 bit（因为只有两个符号），平均码长 = 1.0 bit。而算术编码可以接近 0.081 bits/symbol——12 倍的压缩效率差距。这就是为什么高偏分布场景下算术编码远优于 Huffman 编码。

二进制算术编码

在视频编码中，实际使用的是二进制算术编码（Binary Arithmetic Coding）——只编码 0 和 1 两个符号。这简化了实现：每次只需要将当前区间分为两部分，根据概率 \(p\) 分配子区间宽度。

对于二进制算术编码，给定当前区间 \([low, high)\)，宽度 \(R = high - low\)，编码符号 0（概率 \(p_0\)）时：

每次编码后区间变窄。为了用有限精度整数实现，需要定期进行重归一化（Renormalization）：当区间宽度低于某个阈值时，将 low 和 R 左移若干位（等效于乘以 2 的幂次），同时输出相应的比特到码流。

精度问题与工程实现

纯算术编码的一个工程挑战是有限精度：在实际实现中，low 和 range 用有限位宽的整数表示（如 16 bits 或 32 bits），当区间不断缩小但尚未输出比特时可能发生溢出。解决方案是重归一化机制——每当 range 小于阈值时，将其左移并补充比特，同时处理进位传播（carry propagation）问题。

CABAC 使用了一个精巧的无乘法方案：将 range 量化为 4 个区间，通过查找表（LUT）预计算乘法结果，避免了实时乘法运算。概率状态用 64 个离散状态表示，通过状态转移表更新——这使得 CABAC 可以在硬件中高效实现 #Vcodex-CABAC。

Range Coding 与算术编码的关系

Range Coding（区间编码）由 G. Nigel N. Martin 在 1979 年提出，其数学本质与算术编码完全等价，但工程实现不同。关键区别在于：传统算术编码使用二进制（base-2）运算，每次输出一个 bit；Range Coding 使用任意进制（通常 base-256，即字节级）运算，每次输出一个字节。这使得 Range Coding 在软件实现中更高效，因为字节级操作比位级操作更适合现代 CPU 架构 #NigelTao-LZMA。

Range Coding 的另一个优势是无专利限制。算术编码曾受多项专利保护（尤其是 IBM 的 Rissanen 专利），而 Range Coding 的实现方式成功规避了这些专利，使其在开源软件中被广泛采用。

LZMA 中的 Range Coding

LZMA（Lempel-Ziv-Markov chain Algorithm）由 Igor Pavlov 于 1998 年开始开发，是 7z 格式的默认压缩算法。其熵编码部分使用 Range Coding 处理二进制符号流（binary symbol stream，LZMA 中称为 "bym"）。

LZMA 的 Range Coding 工作原理可以用一个"寻宝"类比来理解 #NigelTao-LZMA：

1. 初始状态：一个覆盖范围 \([0, 0xFFFF)\) 的区间（用 16-bit 整数表示），以及一个从压缩流中读取的"代码值"（code value），它指向区间内的一个位置。
2. 解码每个符号：根据当前概率 \(p\)（符号 0 的概率），将区间分为两部分。如果 code 落在左半（宽度 = range × p），解码为 0；否则解码为 1，并从 code 中减去左半的宽度。
3. 重归一化：当 range 太小时，将其左移（乘以 256），同时从输入流中读取下一个字节加入 code。这等效于"放大地图"——range 回到足够大的尺寸，但精度（map 的粒度）变细了。

自适应概率模型

LZMA 的 Range Coding 不是使用固定概率，而是自适应的：每编码一个符号后，根据实际值更新概率估计。LZMA 为每个二进制决策维护一个概率计数器，初始值为 0.5（等概率），随着编码的进行逐渐收敛到真实分布。

这种自适应机制使得 LZMA 无需预扫描数据即可适应不同类型的数据——文本、代码、二进制数据都能获得不错的压缩率。与 DEFLATE 的固定 Huffman 树（或每个 block 重建一次）相比，LZMA 的概率模型在每个符号级别都在更新，因此对局部统计变化更敏感。

LZMA 的 Markov 链上下文建模

LZMA 名称中的"Markov chain"指的是其上下文建模策略：概率不仅自适应，还依赖于之前编码的符号。具体来说，LZMA 为不同类型的二进制决策（字面量匹配/不匹配、距离编码的高/中/低位等）维护不同的概率表，形成一个简单的 Markov 链——当前决策的概率取决于之前若干个决策的结果。

这种上下文建模是 LZMA 相比 DEFLATE 获得更高压缩率的核心原因之一。DEFLATE 的 Huffman 编码是"无记忆"的——每个符号的概率不依赖于前文；而 LZMA 的 Range Coding 配合 Markov 链建模，可以利用符号间的条件概率进一步压缩。

LZ77 + Huffman 的经典组合

DEFLATE 由 Phil Katz 在 1990 年代初设计，是 ZIP、gzip、zlib 等广泛使用的压缩工具的核心算法。它的设计哲学是简单高效：将两种经典算法——LZ77 字典压缩和 Huffman 编码——串联使用，前者消除重复数据，后者消除统计冗余 #Feldspar-DEFLATE。

flowchart LR
  A["原始数据"] --> B["LZ77 滑动窗口"]
  B --> C["字面量 + 距离/长度对"]
  C --> D["Huffman 编码"]
  D --> E["压缩比特流"]

LZ77：滑动窗口字典压缩

LZ77 算法（由 Lempel 和 Ziv 在 1977 年提出）的核心思想是用指针替代重复数据。它维护一个滑动窗口（DEFLATE 中为 32KB），在窗口中查找与当前位置匹配的最长字符串。如果找到匹配，就输出一个 (distance, length) 对，指向之前出现过的相同数据；如果没找到，就输出当前字节作为字面量（literal）。

一个经典例子：

输入：Blah blah blah blah blah!

LZ77 输出：
  B, l, a, h, ' ', b        ← 字面量
  [D=5, L=18]               ← 距离=5, 长度=18 的回引
  !                         ← 字面量

注意 LZ77 允许重叠匹配——当 length > distance 时，匹配的数据部分来自正在被编码的区域本身。这种机制使得 "Blah blah blah..." 这样的重复模式可以被高效压缩。

Huffman 编码：消除统计冗余

LZ77 的输出包含三种符号：字面量（0-255）、长度码（3-258）和距离码（1-32768）。DEFLATE 使用两棵 Huffman 树对这些符号进行编码：

• 字面量/长度树：将字面量（0-255）和长度码（256-285）合并为一个字母表，使用同一棵 Huffman 树编码。
• 距离树：距离码（0-29）使用单独的 Huffman 树编码。每个距离码后面可能跟额外的定长 bits 来表示精确距离。

同样，长度码后面也可能跟额外 bits 表示精确长度。这种"码 + 额外 bits"的设计避免了为每个精确值分配独立的 Huffman 码字，保持码表规模可控。

三种压缩模式

DEFLATE 数据被分为若干块（block），每个块可以使用以下三种模式之一：

动态 Huffman 模式中，树的传输本身就是一种压缩：不是传输完整的码树结构，而是只传输每个符号的码长（codelength），解码器根据 DEFLATE 规范的特定排列规则重建树。码长序列再经过一次游程编码（RLE）压缩——连续相同的码长用特殊符号表示，然后对 RLE 后的序列再做一次 Huffman 编码。这种"Huffman 编码 Huffman 树"的设计精巧地最小化了元数据开销。

LZMA 与 DEFLATE 的对比

LZMA（Lempel-Ziv-Markov chain Algorithm）由 Igor Pavlov 开发，是 7z 格式的默认压缩算法。与 DEFLATE 一样，LZMA 也是 LZ77 + 熵编码的架构，但在两个方面做出了关键改进：

更大的滑动窗口

DEFLATE 的滑动窗口固定为 32KB，这意味着它只能在 32KB 范围内寻找重复数据。LZMA 将窗口大小扩展到最高 4GB，可以捕获远距离的数据重复——这在压缩大型文件（如源代码库、文档集合）时尤为有效。

Range Coding 替代 Huffman

LZMA 用 Range Coding 替代 Huffman 编码作为熵编码器，这带来了两方面的改进：

第一，突破整数比特限制。Huffman 编码每个符号至少需要 1 bit，而 Range Coding 可以用不到 1 bit 表示高频符号。例如，如果一个字面量 'e' 在文本中出现概率为 0.15，Huffman 编码至少需要 3 bits，而 Range Coding 只需约 \(-\log_2(0.15) \approx 2.74\) bits。

第二，逐符号自适应概率。DEFLATE 的 Huffman 树在每个 block 开始时重建，block 内概率固定不变。LZMA 的 Range Coding 在每个符号编码后更新概率，能够跟踪局部统计变化。配合 Markov 链上下文建模，LZMA 可以利用符号间的条件概率——例如，字母 'q' 后面几乎总是跟着 'u'，LZMA 可以学到这种模式并给出极低的码率。

LZMA 的完整管线

LZMA 将 LZ77 的输出转换为一系列二进制决策（bym stream），每个决策由 Range Coding 编码。上下文建模决定了每个决策使用哪个概率表——这是 LZMA 名称中 "Markov chain" 的含义。概率表在编码过程中不断自适应更新，使得 LZMA 可以动态适应数据分布的变化。

设计动机：上下文自适应 + 算术编码

CABAC（Context-Adaptive Binary Arithmetic Coding）是 H.264/AVC 标准中两种熵编码模式之一（entropy_coding_mode = 1），也是 H.265/HEVC 中唯一的熵编码器。CABAC 由 Fraunhofer HHI 的 Detlev Marpe 和 Heiko Schwarz 团队设计，其核心创新是将上下文自适应概率建模与二进制算术编码结合 #Marpe-2003。

CABAC 相比 CAVLC 提供了 9-14% 的码率节省（在相同视觉质量下），代价是更高的计算复杂度 #Sze-2013。这个数字在视频编码领域是非常显著的——每节省 10% 的码率意味着同样的带宽可以传输更高质量的视频。

三步编码流程

CABAC 编码一个语法元素需要经历三个阶段：

flowchart LR
  A["语法元素"] --> B["Binarization 二值化"]
  B --> C["bins 序列"]
  C --> D{"Context Model"}
  D --> E["概率模型选择"]
  E --> F["Binary Arithmetic Coder"]
  F --> G["压缩比特流"]
  F -->|"概率更新"| D

Step 1: Binarization（二值化）

二进制算术编码只能编码 0 和 1，因此需要先将非二进制的语法元素（如运动向量差、量化系数）转换为二进制串。CABAC 支持四种二值化方案：

一个常见的组合是 TU + EGk：前缀用截断一元码编码小值部分，后缀用 Exp-Golomb 编码大值部分。这种组合充分利用了一元码对小值的高效性和 Exp-Golomb 对大值的可扩展性。

CABAC 中运动向量差 MVDx 的二值化方案：小值用一元码，大值用 Exp-Golomb（来源：Vcodex）

Step 2: Context Model Selection（上下文模型选择）

二值化后的每个 bin 需要一个概率模型来告诉算术编码器该 bin 为 0 或 1 的概率。CABAC 的关键创新是：概率模型不是固定的，而是根据上下文自适应选择的。

H.264/AVC 中共定义了 267 个上下文模型（编号 0-266），覆盖各种语法元素 #Vcodex-CABAC。选择哪个模型取决于已编码的邻近语法元素的值。以运动向量差 MVDx 为例，其第一个 bin 的上下文模型根据之前两个已编码 MVD 的 L1 范数 \(e_k = |MVD_{k-1}| + |MVD_{k-2}|\) 来选择：

• 如果 \(e_k\) 很小 → 选择 Model 0（偏向 MVDx=0 的概率更高）
• 如果 \(e_k\) 中等 → 选择 Model 1
• 如果 \(e_k\) 很大 → 选择 Model 2（MVDx 非零的概率更高）

这种设计基于一个经验观察：空间上邻近的运动向量往往相似。如果前两个块的 MVD 都很小，当前块的 MVD 也可能很小。

CABAC 上下文模型选择：根据邻近块 MVD 的 L1 范数 ek 选择概率模型，不同 bin 映射到不同上下文模型编号（来源：Vcodex）

Step 3: Binary Arithmetic Coding（二进制算术编码）

选定上下文模型后，该模型提供了 bin 为 0 或 1 的概率估计。算术编码器使用这个概率将当前区间分为两个子区间，选择对应的子区间作为新区间。

CABAC 的算术编码引擎有三个关键设计：

(a) 64 状态概率表示：概率不是用浮点数表示，而是用 64 个离散状态表示最不可能符号（Least Probable Symbol, LPS）的概率。每个状态对应一个 LPS 概率值，从 \(0.5\)（等概率）到接近 \(0\)（极偏分布）。

(b) 量化 range + 查找表：当前区间宽度 \(R\) 被量化为 4 个区间，配合 64 个概率状态，形成一个 \(4 \times 64 = 256\) 项的查找表。这使得 range × probability 的乘法运算可以用一次表查找替代——在硬件实现中意义重大 #Vcodex-CABAC。

(c) 旁路模式：对于概率接近 0.5 的 bin（即近等概率分布），CABAC 跳过上下文建模和概率估计，直接使用简化版的算术编码。这避免了为近随机数据浪费计算资源。

概率更新机制

每个上下文模型在编码完一个 bin 后会更新其概率估计：如果实际编码的 bin 是 LPS，则 LPS 的概率估计增加（向更不偏的方向移动）；如果是 MPS（Most Probable Symbol），则 LPS 概率减少。这种更新通过状态转移表实现——给定当前状态和编码结果，查表得到下一个状态。

当某个模型的累计计数超过阈值时，频率计数会被缩放（右移一位），等效于给最近的观测更高的权重——这是一种指数加权移动平均（EWMA）策略，使 CABAC 能快速适应局部统计变化。

Slice 初始化

在每个 slice 开始时，所有 267 个上下文模型会根据量化参数 QP 初始化为不同的概率状态。这是因为 QP 直接影响量化系数的分布——QP 越大，量化系数越稀疏（更多 0），因此初始概率应该偏向 "零系数" 更常见。QP 相关的初始化确保了 CABAC 在不同质量级别下都能快速收敛到正确的概率分布。

CAVLC 的设计定位

当 H.264 的 entropy_coding_mode 设置为 0 时，使用 CAVLC（Context-Adaptive Variable Length Coding）编码残差数据，用 Exp-Golomb 编码其他语法元素。CAVLC 是 CABAC 的轻量级替代方案，适用于计算资源受限的场景（如移动设备解码）。

CAVLC 的"上下文自适应"体现在：VLC 查找表的选择依赖于已编码的邻近块信息。这与 CABAC 的上下文建模思想一致，但实现更简单——用查表替代算术编码 #Vcodex-CAVLC。

CAVLC 编码残差系数的五个步骤

CAVLC 专门针对量化后的 4×4 DCT 系数块的统计特性进行了优化。编码一个 4×4 块的残差系数包括以下五个步骤：

Step 1: 编码系数数量和尾随 1 的个数（COEFF_TOKEN）

第一个 VLC 同时编码两个信息：非零系数总数（TotalCoeffs，0-16）和尾随 ±1 的个数（T1s，0-3）。VLC 表的选择依赖于邻近块的非零系数数量——如果上下文块中非零系数少，选择偏向小 TotalCoeffs 的表（Num-VLC0）；如果多，选择偏向大 TotalCoeffs 的表。共有 4 种表：Num-VLC0、Num-VLC1、Num-VLC2 和 Num-FLC（定长 6-bit）。

Step 2: 编码每个 T1 的符号

每个尾随 ±1 的符号用 1 bit 编码（0 = +，1 = -），从最高频的 T1 开始逆序编码。

Step 3: 编码非 T1 系数的幅值（Level）

剩余非零系数的幅值（符号 + 绝对值）从最高频向 DC 方向逆序编码。VLC 表的选择是自适应的：初始使用 Level_VLC0（偏向小幅值），每编码一个系数后，如果其幅值超过预设阈值，就切换到更大的 VLC 表。共有 7 个 Level VLC 表（Level_VLC0 到 Level_VLC6），从小到大排列。这种设计利用了量化系数"低频大幅值、高频小幅值"的统计特性。

Step 4: 编码最后一个非零系数前的零总数（TotalZeros）

TotalZeros 是 zig-zag 扫描序列中最后一个非零系数之前的所有零的总数。单独编码 TotalZeros 的好处是：如果块中只有少量非零系数（常见情况），后续的 run_before 编码可以更高效——因为解码器已经知道总共有多少零需要分配。

Step 5: 编码每个非零系数前的零游程（run_before）

每个非零系数前面的零的个数用 VLC 编码，VLC 表的选择依赖于剩余待编码的零数量（ZerosLeft）。如果只剩 2 个零，run_before 最多为 2，VLC 只需 1-2 bits；如果剩 6 个零，可能需要更多 bits。

CAVLC 对量化块特性的利用

CAVLC 的设计深度利用了量化 4×4 块的四个统计特性：

编码算法演进路线

从 Huffman 到 CABAC，二进制编码算法的演进遵循一条清晰的路线：越来越逼近熵极限，但计算复杂度也越来越高。

H.264 熵编码架构总览

H.264 的熵编码系统采用分层设计，不同类型的语法元素使用不同的编码方案：

可以看到，Exp-Golomb 在两种模式中都扮演重要角色：在 CAVLC 模式中直接编码语法元素，在 CABAC 模式中作为二值化方案之一。而 CABAC 的算术编码引擎取代了 CAVLC 的 VLC 查表，通过逐 bin 的概率自适应获得了额外的压缩增益。

flowchart TD
  subgraph MODE0["模式 0: CAVLC"]
    A1["非残差语法元素"] --> B1["Exp-Golomb 编码"]
    C1["残差 4x4 系数块"] --> D1["CAVLC 5步编码"]
  end
  subgraph MODE1["模式 1: CABAC"]
    A2["所有语法元素"] --> B2["Binarization"]
    B2 --> C2["Context Model"]
    C2 --> D2["Binary Arithmetic Coding"]
  end
  B1 --> OUT["比特流"]
  D1 --> OUT
  D2 --> OUT

CABAC vs CAVLC：定量对比

根据 Sze et al. 在 IEEE SIPS 2013 上的系统评估，CABAC 相比 CAVLC 在 H.264/AVC 中提供了 9-14% 的码率节省（BDBitrate 测试），但 CAVLC 的吞吐率显著更高 #Sze-2013：

正是由于 CABAC 的计算复杂度较高，H.264 保留了 CAVLC 作为 Baseline profile 的可选方案。但在 H.265/HEVC 中，CABAC 已成为唯一的熵编码器——随着硬件性能的提升，CABAC 的压缩优势使其成为不可替代的选择。

从 MPEG-4 CAE 到 CABAC：技术传承

CABAC 的设计并非凭空出现。它的"上下文自适应 + 算术编码"范式直接继承了 MPEG-4 Visual 中的 CAE（Context-based Arithmetic Encoding）——用于二值形状编码的熵编码器。CAE 使用 10 像素的上下文模板捕获二值形状的局部空间相关性，CABAC 将这一思想推广到了所有语法元素 #MPEG4-Shape-Coding。

从 CAE 的 10-pel 模板到 CABAC 的 267 个上下文模型，核心思想一脉相承：上下文自适应建模是压缩效率的核心来源。无论是 1997 年的二值形状编码，还是 2020 年代的神经视频编码，上下文建模都是压缩效率提升的关键路径。

1. CABAC 的吞吐率瓶颈

CABAC 的串行特性——每个 bin 的编码依赖于前一个 bin 更新后的概率状态——使得它难以并行化。在 4K/8K 超高清视频编码中，CABAC 的吞吐率成为编码速度的主要瓶颈。HEVC 通过引入波前并行处理（Wavefront Parallel Processing, WPP）部分缓解了这一问题，但 CABAC 引擎本身仍是串行的。未来的研究方向包括概率状态并行化和近似算术编码（允许少量精度损失以换取吞吐率提升）。

2. 神经网络驱动的熵编码

近年来，学习式图像压缩（Learned Image Compression）引入了神经网络熵模型，如 Ballé 的 Scale Hyperprior、Minnen 的 Joint Context Model 等。这些方法使用神经网络替代手工设计的上下文模型，自动学习符号间的条件概率分布。在超低码率场景下，神经熵模型已经超越了 CABAC 的编码效率。然而，神经熵模型通常仍依赖传统的算术编码引擎（如 ranged coder）作为后端——CABAC 的工程智慧并未过时，只是前端建模被神经网络替代。

3. 专用硬件中的编码选择

在移动设备和嵌入式系统中，编码器的功耗和面积预算极为有限。Exp-Golomb 编码因其"无需查找表、仅需前导零计数"的极简实现，仍然是资源受限场景下的首选。而 Range Coding 因其在软件实现中的高效性，被广泛应用于嵌入式 Linux 系统的文件压缩。编码算法的选择本质上是一个效率-复杂度-适应性的三维权衡，没有"一刀切"的最优解。

4. 通用压缩与领域压缩的融合

ZIP/DEFLATE 和 LZMA/7z 是面向通用数据的压缩工具，而 CABAC 是面向视频编码的专用熵编码器。两者的设计哲学不同：通用工具追求"对任何数据都不差"，领域编码器追求"对特定数据最优"。但随着 AI 驱动的语义压缩兴起，这条界限正在模糊——未来的压缩系统可能将通用字典压缩、领域特定建模和神经网络概率估计融合为统一框架。

回顾本文覆盖的七种编码算法，我们可以提炼出几条贯穿始终的核心洞察：

第一，编码效率的上界是信息熵。无论算法多么精巧，平均码长不可能低于信源的熵。Huffman 编码浪费在"整数比特限制"上的冗余最多 1 bit/symbol，而算术编码和 Range Coding 可以无限逼近熵极限。CABAC 通过上下文建模进一步降低了条件熵——即利用符号间的相关性进一步压缩。

第二，自适应是效率的关键。固定概率模型无法适应数据分布的变化。CAVLC 的块级 VLC 表切换、CABAC 的逐 bin 概率更新、LZMA 的 Markov 链上下文——这些自适应机制是现代编码器超越早期固定 Huffman 编码的核心。适应速度（LZMA 的逐符号更新 vs DEFLATE 的块级重建）是压缩效率差距的重要来源。

第三，复杂度决定适用场景。Exp-Golomb 的极简实现使其适合 H.264 中大量低频语法元素的编码；DEFLATE 的 Huffman 编码使其在通用文件压缩中保持高速；CABAC 的 267 个上下文模型和二进制算术编码使其在视频编码中达到最高效率。没有"通用最优"的编码算法——每种方法都是特定约束下的最优选择。

第四，编码算法的演进是"加法"而非"替代"。H.264 同时使用 Exp-Golomb（简单语法元素）、CAVLC（残差系数，轻量级）和 CABAC（残差系数，高效率）。CABAC 内部的二值化方案本身又包含 Unary、TU 和 Exp-Golomb。这种"洋葱式"的分层设计使得编码系统可以灵活地在不同粒度上选择最合适的工具——这正是工程实践的智慧。