熵编码详解-huffman和变长编码.ppt

《熵编码详解-huffman和变长编码.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、熵编码变长编码&算术编码利用信源的统计特性进行码率压缩的编码就称为熵编码，也叫统计编码。视频编码常用的两种：变长编码（也称哈夫曼编码）及算术编码。现分别讨论其基本原理。变长编码1952年，哈夫曼提出变长编码方法。其重要的编码原则即：对出现概率大的符号分配短字长的二进制码，对出现概率小的符号分配长字长二进制码，得到符号平均码长最短的码。变长编码也称最佳编码。具体编码方法如下所示例子。哈夫曼编码举例：可得：因此我们可以看出哈夫曼编码的步骤：第一步，将信息符号按其出现概率从大到小排列；第二步，将两个最小概率组成一组，划成

2、2个分支域，并标以0和1；再把2个分支域合并成1个支域，标以两个概率之和；第三步，依次类推，直到概率之和等于1.0；第四步，找出概率和1.0到各信息符号的路径，记下各路径从右到左各分支域的0和1，即得到信息符号相应的码字。（反向编码）理论上，这种编码是最佳的。实际上，利用硬件实现时，出现概率不可能精确到小数后多少位，而最小存储单元为1bit，会引起概率匹配不准确及编码效率的下降。算术编码算术编码和哈夫曼编码不同，不采用一个码字代表一个输入信息符号的办法，而采用一个浮点数来代替一串输入符号，经算术编码后输出一个小于1

3、，大于或等于0的浮点数，在解码端被正确地唯一的解码，恢复原符号序列。举例如下。设：输入序列为abaca，p(a)=1/2，p(b)=p(c)=1/4，求算术编码输出序列。解：编码：（1）列出各符号出现概率值（2）在（0，1）区间内，每个字符根据其概率选定范围，如上表所示（3）开始时，浮点范围：R0＝H0－L0＝1，H0＝1，L0＝0。（4）当第一个字符“a”被传送时，其范围为[0.00,0.50)，H＝0.05，L＝0.00，可得发"a"字符的范围H和L：L1＝L0＋R0×L＝0+1*0=0.00H1＝L0＋R0×

4、H＝0+1*0.05=0.50范围R1＝H1－L1＝0.50对a编码后，编码范围从[0,1）变为[0.00,0.50)。（5）当第二个字符“b”被传送时，范围为[0.50,0.75)，H＝0.75，L＝0.50。L2＝L1＋R1×L＝0+0.50*0.50=0.25H2＝L1＋R1×H＝0+0.50*0.75=0.375R2＝H2－L2＝0.125于是对“ab”编码后，编码范围从[0.00,0.50)变为[0.25,0.375)。（6）依次类推：“a”：L3＝0.25＋0.125×0＝0.25H3＝0.25＋0.1

5、25×0.50＝0.3125R3＝0.0625“c”：L4＝0.25＋0.0625×0.75＝0.296875H4＝0.25＋0.0625×1.00＝0.3125R4＝0.015625“a”：L5＝0.296875＋0.015625×0＝0.296875H5＝0.296875＋0.015625×0.50＝0.3046875R5＝0.0078125最后输出码字为：0.3046875。由上述过程可以总结出来：若已知的字符范围【L,H），则第i个字符传送时：Li=Li-1+Ri-1*L;Hi=Li-1+Ri-1*H;Ri

6、=Hi-Li;编码结果：解码：（1）接受到浮点数0.3046875，对照表1，在范围中查得第一个字符为"a"，其概率为0.5。（2）从接收值减去"a"的概率范围L，并除以p(a)，（0.3046875－0.00）/0.5＝0.609375该值为下一字符范围内的值，查得为"b"（3）依此类推（0.609375-0.50）/0.25=0.4375---"a"（0.4375-0.00）/0.5=0.875----"c"（0.875-0.75）/0.25=0.5----"a"解码出序列“abaca”。解码结果：