《哈夫曼编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《哈夫曼编码ppt课件.ppt（19页珍藏版）》请在三一办公上搜索。
1、哈夫曼编码方法,哈夫曼编码,1952年哈夫曼提出了一种构造最佳码的方法称之为哈夫曼编码。哈夫曼编码适用于多元独立信源对于独立信源来说，哈夫曼编码是最佳码他充分的利用了信源的概率特性进行编码，,编码方法,(1)将信源消息符号按其出现的概率大小依次排列(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队,编码方法,(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,例5-7,1,1,1,0,0
2、.11,0.18,0.15,0.17,0.18,0.19,0.20,1,0,0.17,0.19,0.20,0.26,1,0,0.19,0.20,0.26,0.35,1,0,0.26,0.35,0.39,1,0,0.39,0.61,1,0,1.0,该哈夫曼编码的平均码长 信息传输速率,码元/符号,Bit/码元,哈夫曼编码方法得到的码并非唯一的,1 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。2 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可
3、以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。,设有离散无记忆信源,1,0,0.2,0.2,0.2,0.4,1,0,0.2,0.4,0.4,1,0,0.4,0.6,1,0,1.0,1,0,0.2,0.2,0.2,0.4,1,0,0.2,0.4,0.4,1,0,0.4,0.6,1,0,1.0,两种哈夫曼码的平均码长相等,编码效率也相等,码元/符号,码方差 码字长度偏离平均长度的程度,第一种哈夫曼码的码方差,第二种哈夫曼码的码方差,哈夫曼编码的特点,用概率分配方法对信源进行编码1 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符
4、号对应于长码，充分利用了短码。2 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。3 每次缩减信源的最长两个码字有相同的码长。三个特点保证了哈夫曼码是最佳码,多进制哈夫曼编码,对于多进制哈夫曼码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以信源符号数量尽量满足 m = (r-1) n + r 信源符号数 进制数 缩减的次数不满足时 m + t =(r-1)n + r 需添置概率为0的虚拟符号t个,例 对信源S进行四进制哈夫曼编码 S S1 S2 S3 S4 S5 S6 S7 S8 P 0.22 0.20 0.18 0.15 0.10 0.08 0.05 0
5、.02 码字 1 2 3 00 01 02 030 031,例5-9,信源输出2个符号，概率分布为P=（0.9,0.1)，信源熵H（X）=H（0.9)=0.469。采用二进制哈夫曼编码。 L=1, 1=1bit/符号； L=2,P=(0.81,0.09,0.09,0.01), 2=0.645bit/符号； L=3, 3=0.533bit/符号； L=4, 4=0.493bit/符号。 随着序列长度L的增加，平均码长迅速降低，接近信息源熵值，编码效率接近于1.,一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码后，会造成编码输出每秒的比特数不是常量，因而不能直接由信道来传送。为了适应信
6、道，必须增加缓冲寄存器。将编码输出暂存在缓冲器中，然后再由信道传输，使输入和输出的速率保持平衡。溢出：当信源连续输出低概率符号时，因为码长较长，有可能使缓冲器存不下而溢出。取空：当信源连续输出高概率符号时，有可能输入比特数小于信道中传输的比特数，以致缓冲器取空。,缓冲器,信道传输速率R 信源输出符号速率S 平均码长 1 当R=S 时 存储器容量C应满足 C 6.16N 其中 N为信源符号数，为码方差2 当RS 时，平均来说，输出大于输入，易被取空3 当RS 时，输入大于输出，易于溢出,其他,1 变长码只适合有限长的信息传输 时间T越长，N越大，要求存储器的容量也越大。当容量设定后，随着时间的增长，存储器溢出和取空的概率都将增大。当T很大时，几乎一定会溢出或取空造成损失。因而，对于无限长的信息，很难采用变长码而不出现差错。2 差错的扩散 变长码由信道传输的过程中，一个码字前面有某一个码元错了，就可能误认为是另一个码字而断点，结果后面一系列码字也会易错，称之为差错的扩散。,谢谢大家！,
