哈夫曼编码教学文案.ppt
哈夫曼编码方法第一页，共19页。哈夫曼编码(bin m)1952年哈夫曼提出了一种构造(guzo)最佳码的方法称之为哈夫曼编码。哈夫曼编码适用于多元独立信源对于独立信源来说，哈夫曼编码是最佳码他充分的利用了信源的概率特性进行编码，第二页，共19页。编码方法(1)将信源消息符号将信源消息符号(fho)按其出现的概率大按其出现的概率大小依次排列小依次排列(2)取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两个两个码元，并将这两个概率相加作为一个新字码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号母的概率，与未分配的二进符号(fho)的的字母重新排队字母重新排队第三页，共19页。编码方法(3)对对重重排排后后的的两两个个概概率率最最小小符符号号(fho)重重复复步骤步骤(2)的过程。的过程。(4)不不断断继继续续上上述述过过程程，直直到到最最后后两两个个符符号号(fho)配以配以0和和1为止。为止。(5)从从最最后后一一级级开开始始，向向前前返返回回得得到到各各个个信信源源符符号号(fho)所所对对应应的的码码元元序序列列，即即相相应应的的码字。码字。第四页，共19页。例5-7信源符号概率编码过程码字码长a10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.010111411100.110.180.150.170.180.190.20100.170.190.200.26100.190.200.260.35100.260.350.39100.390.61101.0第五页，共19页。该哈夫曼编码的平均(pngjn)码长 信息传输速率 码元/符号(fho)Bit/码元第六页，共19页。哈夫曼编码方法得到(d do)的码并非唯一的1 每次对信源缩减时，赋予信源最后两个概率最小的符号，用每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。的长度。2 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置符号的概率相同时，这两者在缩减信源中进行概率排序，其位置(wi zhi)放置次序是可以任意的，故会得到不同的哈夫曼码。此时放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。小的码方差。第七页，共19页。设有离散设有离散(lsn)(lsn)无记无记忆信源忆信源第八页，共19页。信源符号概率编码过程码字码长a10.411a20.2012a30.20003a40.100104a50.100114信源符号概率编码过程码字码长a10.4002a20.2102a30.2112a40.10103a50.10113100.20.20.20.4100.20.40.4100.40.6101.0100.20.20.20.4100.20.40.4100.40.6101.0第九页，共19页。两种哈夫曼码的平均(pngjn)码长相等编码效率(xio l)也相等码元/符号(fho)第十页，共19页。码方差 码字长度(chngd)偏离平均长度(chngd)的程度第一种哈夫曼码的码方差(fn ch)第二种哈夫曼码的码方差(fn ch)第十一页，共19页。哈夫曼编码(bin m)的特点用概率分配方法对信源进行编码用概率分配方法对信源进行编码1 1 哈哈夫夫曼曼码码的的编编码码方方法法保保证证(bozhng)(bozhng)了了概概率率大大的的符符号号对对应应于于短短码码，概概率率小小的的符符号号对对应应于于长长码码，充充分分利利用用了了短码。短码。2 2 缩缩减减信信源源的的最最后后二二个个码码字字总总是是最最后后一一位位不不同同，从从而而保保证证(bozhng)(bozhng)了哈夫曼码是即时码。了哈夫曼码是即时码。3 3 每次缩减信源的最长两个码字有相同的码长。每次缩减信源的最长两个码字有相同的码长。三个特点保证三个特点保证(bozhng)(bozhng)了哈夫曼码是最佳码了哈夫曼码是最佳码第十二页，共19页。多进制哈夫曼编码(bin m)对于多进制哈夫曼码，为了提高编码效率，就要(ji yo)使长码的符号数量尽量少、概率尽量小，所以信源符号数量尽量满足 m=(r-1)n+r 信源符号数 进制数 缩减的次数不满足时 m+t=(r-1)n+r 需添置概率为0的虚拟符号t个第十三页，共19页。例 对信源S进行(jnxng)四进制哈夫曼编码 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.02 码字 1 2 3 00 01 02 030 031 第十四页，共19页。例5-9信源输出2个符号，概率分布为P=（0.9,0.1)，信源熵H（X）=H（0.9)=0.469。采用二进制哈夫曼编码(bin m)。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的增加，平均码长迅速降低，接近信息源熵值，编码(bin m)效率接近于1.第十五页，共19页。一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码后，会造成编码输出每秒的比特数不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器。将编码输出暂存在缓冲器中，然后(rnhu)再由信道传输，使输入和输出的速率保持平衡。溢出：当信源连续输出低概率符号时，因为码长较长，有可能使缓冲器存不下而溢出。取空：当信源连续输出高概率符号时，有可能输入比特数小于信道中传输的比特数，以致缓冲器取空。第十六页，共19页。缓冲器信道传输速率R 信源输出符号速率S 平均码长 1 当R=S 时 存储器容量C应满足(mnz)C 6.16N 其中 N为信源符号数，为码方差2 当RS 时，平均来说，输出大于输入，易被取空3 当RS 时，输入大于输出，易于溢出第十七页，共19页。其他(qt)1 变长码只适合有限长的信息传输 时间T越长，N越大，要求存储器的容量也越大。当容量设定后，随着(su zhe)时间的增长，存储器溢出和取空的概率都将增大。当T很大时，几乎一定会溢出或取空造成损失。因而，对于无限长的信息，很难采用变长码而不出现差错。2 差错的扩散 变长码由信道传输的过程中，一个码字前面有某一个码元错了，就可能误认为是另一个码字而断点，结果后面一系列码字也会易错，称之为差错的扩散。第十八页，共19页。谢谢(xi xie)大家！第十九页，共19页。
