熵编码原理 算术编码的唯一性和效率
• 长度为n的序列的算术编码的平均码长为：
lA P (x)l x
P (x ) lo g
P
1 (x
)
1
P
(
x
)
lo
g
P
1 (x
)
1
1
P (x ) lo g P (x ) 2 P (x )
H X n 2 n H X 2
n H X lA n n H X 2 H X lA H X n 2
Zeroleft: 当前非零系数之前所有零的个数，初始值为TotalZeros
HR.2un6_b4eforCe：A游V程 LC 下面两种情况不需要编码： 最后一个非零系数（反Z方向）前零的个数 没有剩余的零可以编码，∑ Run_before=total_zeros
本例题中：0 3 0 1 -1 -1 0 1 0 0 0 。。。。。
HEVC视频编码标准之熵编码
——基于上下文的自适应二进制算术编码CABAC （Context-based Adapting Binary Arithmetic Coding）
郑明魁
数字电视智能化技术国家地方联合工程研究中心
熵编码基础
目前的视频编码标准主要通过去除空间冗余、时间冗余与编码冗余 来实现压缩。编码器将多种算法有效的结合起来达到较高的压缩性能 ，主要相关技术包括预测编码、变换编码、量化和熵编码技术。
熵编码原理
1.算术编码 Arithmetic Coding（二进制）
在编码过程中，输入数据流中 的信源符号被分为大概率符号 (MPS)和小概率符号(LPS)。
LPS的概率记为Q， MPS的概率记为P=1-Q
熵编码原理 算术编码的唯一性和效率
• 上述产生的标识可以唯一表示一个序列，这意味着该标识 的二进制表示为序列的唯一二进制编码
自适应算术编码在扫描符号序列前并不知道各符号的统计概率，这时假定每 个概率相等，并平均分配区间[0,1],然后在扫描符号序列的过程中不断调整各个符 号的概率。
1.调整概率后，再进行进行区间分配，随着编(译)码过程的进行。 2.概率分配将逐渐趋于信源的实际概率分布。这种方法对于无法进行概率统计的信 源比较合适。
序号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
码字长度
2 2 3 3 5 5 5 5 5 6 7 7 7 7 7 7 8
码字
00 01 100 101 11000 11001 11010 11011 11100 111010
权值
0x00 0x01 0x11 0x02 0x21 0x03 0x31 0x41 0x12 0x51 0x61 0x71 0x81 0x91 0x22 0x13 0x32
算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵
算术编码基础
2.自适应算术编码 Adapting Arithmetic Coding
在前面讨论的算术编码中，我们把信源的统计特性被看作是固定不变的，这在 实际应用中显然不太实际。为解决使编码技术适应信源统计特性变化的问题，前人 提出了自适应算术编码方法，自适应算术编码在一次扫描中可完成两个过程，即概 率模型的建立过程和扫描编码过程。
熵编码基础
游程编码：游程编码在传真文件压缩中的应用
例:０００１０００１１１０１１１１１００００
3 1 3 31
54电ຫໍສະໝຸດ 网熵编码原理H.264基于上下文的自适应变长编码CAVLC（Context-based Adapting Variable Length Coding）游程编码思想的应用： 5、run before：以反z向扫秒零的个数，类似游程编码。注意两个参数，Zeroleft和Run_before
run_before(4) ZerosLeft=3; run_before=1 run_before(3) ZerosLeft=2; run_before=0 run_before(2) ZerosLeft=2; run_before=0 run_before(1) ZerosLeft=2; run_before=1 run_before(0) ZerosLeft=1; run_before=1 No code required; last coefficient.
哈夫曼编码(Huffman Coding)，霍夫曼编码是可变字长编码(VLC) 的一种。出现机率高的字母使用较短的编码，反之出现机率低的则
使用较长的编码。现在流行的很多压缩方法都使用了范式哈夫曼编 码技术，如 GZIB、ZLIB、PNG、JPEG、MPEG 等。在直流 DC 系数经过上面的 DPCM 编码，交流 AC 系数经过 RLE 编码后，得 到的数据，还可以再进一补压缩，即使用 Huffman 编码来处理。
• 但二进制表示的精度可以是无限长：保证唯一性但不够有 效
• 为了保证有效性，可以截断二进制表示，但如何保证唯一 性？
• 答案：为了保证唯一性和有效性，需取小数点后l位数字 作为信源序列的码字，其中
lx
log
P(1x)1
– 注意：P(x)为最后区间的宽度，也是该符号串的概率
– 符合概率匹配原则：出现概率较大的符号取较短的码字，而对出 现概率较小的符号取较长的码字
预测
变换
量化
熵编码
熵编码基础
熵编码是按照熵原理进行的一种无失真压缩编码方式，生成的 码流可以通过解码过程无失真的将原始数据解析出来。常见的熵编 码主要有：香农编码(Shannon Coding)、哈夫曼编码(Huffman Coding)和算术编码(Arithmetic Coding)等。
熵编码基础
算术编码基础
3.基于上下文自适应算术编码
在实际的视频编码过程中，由于冗余的存在（特别是时间冗余和空间冗余 ，于是在自适应算术编码的基础上引入了context model的概念，通 过信源前后（时间或空间上）消息的预测分布来调整并适应信源统计特性的 变化，这就是所谓的基于上下文的自适应算术编码。
Context model是根据当前符号周围的已编(译)码符号的情况构造的，每 个context model内，概率随着编(译)码的进行而进行自适应的更新。对于不 同的context model，其概率分配也是不同的，此时的概率即为条件概率。