Context-Based Adaptive Binary Arithmetic Coding in the H.264/A VC
简称Cabac，H264中的一种熵编码方式：基于上下文的自适应二进制算术编码内容安排：1，介绍算术编码2，介绍二进制算术编码3介绍Cabac及其一些实用的实现方式（参考JSVM代码，也可以参考JM）
一，算术编码
算术编码是一种常用的变字长编码，它是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman 编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman 编码。它和Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1] 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。举例如下：
S S S S为例
以符号
3324
在算术编码中通常采用二进制分数表示概率，每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如S1对应[0, 0.001)，S2 对应[0.001, 0.01) 等。
算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。
S S S S…… 的第一个符号S3 用指向第3 个子区间的指针 符号序列
3324
来代表，可以用这个区间内的任意一个小数来表示这个指针，这里约定这个区间的左端点代表这个指针，因此得到第一个码字.011。
⏹后续的编码将在前面编码指向的子区间内进行，将[.011, .111] 区间再按
概率大小划分为4 份，第二个符号S3 指向.1001 (S3 区间的左端），输出码字变为.1001。
⏹然后，S3 对应的子区间又被划分为4 份，开始对第三个符号S2 进行
编码，…….
⏹两个参量：编码点（指针所指处）C 和区间宽度A。
初始状态
编码点（指针所指处）C = 0
区间宽度A = 1.0
新编码点C = 原编码点C ＋原区间A×Pi
新区间A = 原区间A×pi
⏹序列S3S3S2S4 …… 的编码过程：
第1个符号(S3): C = 0 + 1×.011 = .011
A = 1×.1 = .1
第2个符号(S3): C = .011 + .1×.011 = .1001
A = .1×.1 = .01
第3个符号(S2): C = .1001 + .01×.001 = .10011
A = .01×.01 = .0001
第4个符号(S4): C = .10011 + .0001×.111 = .1010011 （输出的码字）
A = .0001×.001 = .0000001
解码过程
⏹算法解码采取与编码过程相反的步骤
把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即为解码后的符号。
即从码字串中减去已解码符号的子区间的左端点的数值（累积概率），
并将差值除以该子区间的宽度（概率值），得到新的码字串。
⏹上述例子
当收到字码串(.1010011) 时，其指向子区间[.011, .111]，对应于S3，因此，得到第1 个符号为S3。
新码字串：（.1010011 - .011) ÷(.1) = 0.100011 ，新码字串仍然指向子区间[.011, .111]，因此，第2 个符号仍为S3。
其它符号依次类推
二，二进制算术编码
二进制算术编码的输入的字符只有两种，如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。
这两个符号构成的序列的编码与算术编码基本原理相同，仍是不断划分概率子区间的递归过程。
在两个输入字符中，出现概率较大的为MPS (More Probable Symbol)，MPS
的概率为Pe；出现概率较小的为LPS (Less Probable Symbol)，LPS 的概率为Qe，Pe=1-Qe。
编码初始化子区间为[0，1]，MPS与LPS 分配如图所示：
编码时，设置两个专用寄存器（C，A）
C 寄存器的值为编码点（指针所指处），初时化为0
A 寄存器的值为子区间的宽度(该宽度恰好是已输入符号串的概率)，初时化为1 随着被编码数据源输入，C 和 A 的内容按以下编码规则修正：
当低概率符号LPS 到来时：
C=C ，A=AQe
当高概率符号MPS到来时：
C=C + AQe ，A=Ape = A（1-Qe）
例: 信源符号序列11011111
0 为LPS Qe = 1/8 =（0.001）b
1 为MPS Pe = 7/8 =（0.111）b
初始状态：C=0 (子区间起始位置) A=1 （子区间宽度）
1，第1个符号1为MPS
C = C + AQe = 0 + 1 ⨯0.001 = 0.001
A = APe = 1 ⨯0.111 = 0.111
2，第2个符号1仍为MPS
C=C+AQe = 0.001 + 0.111 ⨯0.001=0.001111
A=APe= 0.111 ⨯0.111 =0.110001
3，第3个符号0为LPS
C=C=0.001111
A=A Qe = 0.110001 ⨯0.001 =0.000110001
4，继续下去……. 最后得
C= 0.010001111110111100000001
A= 0.000011001001000010111111
此时区间的尾为C+A=0.010101000111111111000000，编码区间[C, C+A)
编码输出可以是最后一个编码区间中的任意小数值，但为了取得最好的编码效率，选择的小数应有最短的比特长度。上面区间我们可取0.0101,即输出为0101 解码过程
按Qe、Pe 分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号。设c’ =（0.0101) b是被解码的值，初始值A=1 Qe = 0.001
当c’ 落在0-QeA 之间，解码符号为D=0，则C’ = C’， A = Qe A
当c’ 落在QeA-A 之间，解码符号为D=1，则C’ = C’-Qe A ，A = A（1-Qe）1，c’ = 0.0101落在Qe A -A 之间，解码符号为D = 1
c’ = c’-QeA = 0.0101 - 0.001 = 0.0011 ， A = A（1-Qe）= 0.111
2，c’= 0.0011 落在Qe A -A 之间，解码符号为D=1
c’=c’-QeA= 0.0011 -0.000111=0.000101 ，A=A（1-Qe）= 0.111⨯0.111=0.110001 3，c’ = 0.000101 落在0-QeA 之间，解码符号为 D = 0
