视频压缩

2. 算术编码
霍夫曼编码的每个代码都要使用一个整数位， 如果一个符号只需要用2.5位就能表示， 但在霍夫曼编码中却必须用3个符号来表示， 因此它的效率较低。 与其相比， 算术编码并不是为每个符号产生一个单独的代码， 而是使整条信息共用一个代码， 增加到信息上的每个新符号都递增地修改输出代码。

假设信源由4个符号S1、 S2、 S3和S4组成， 其概率模型如表6-1所示。 把各符号出现的概率表示在如图6-3所示的单位概率区间之中， 区间的宽度代表概率值的大小， 各符号所对应的子区间的边界值， 实际上是从左到右各符号的累积概率。 在算术编码中通常采用二进制的小数来表示概率， 每个符号所对应的概率区间都是半开区间， 如S1对应［0， 0.001)， S2对应［0.001， 0.011)。 算术编码所产生的码字实际上是一个二进制小数值的指针， 该指针指向所编的符号所对应的概率区间。

表6-1 信源概率模型和算术编码过程

图 6-3 算术编码过程示意图

若将符号序列S3S3S2S4进行算术编码， 序列的第一个符号为S3， 我们用指向图6-3中第3个子区间的指针来代表这个符号， 由此得到码字0.011。 后续的编码将在前面编码指向的子区间内进行。 将［0.011， 0.111)区间再按符号的概率值划分成4份， 对第二个符号S3， 指针指向0.1001,码 字串变为0.1001。 然后S3所对应的子区间又被划分为4份， 开始对第3个符号进行编码……。

算术编码的基本法则如下：
(1) 初始状态： 编码点(指针所指处)C0=0， 区间宽度A0=1。
(2) 新编码点： Ci= Ci-1 + Ai-1×Pi。
式中, Ci-1是原编码点；　Ai-1是原区间宽度；　
Pi所编符号对应的累积概率。
新区间宽度Ai= Ai-1×pi
式中， pi为所编符号对应的概率。

根据上述法则， 对序列S3S3S2S4进行算术编码的过程如下：
第一个符号S3：
C1=C0+A0×P1=0+1×0.011=0.011
A1=A0×p1=1×0.1=0.1
［0.011,0.111］