哈夫曼编码课件

哈夫曼编码方法哈夫曼编码方法哈夫曼编码1952年哈夫曼提出了一种构造最佳码的方法称之为哈夫曼编码。哈夫曼编码适用于多元独立信源对于独立信源来说，哈夫曼编码是最佳码他充分的利用了信源的概率特性进行编码，哈夫曼编码1952年哈夫曼提出了一种构造最佳码的方法称之为哈编码方法(1)将信源消息符号按其出现的概率大小依次排列(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队编码方法(1)将信源消息符号按其出现的概率大小依次排列编码方法(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。编码方法(3)对重排后的两个概率最小符号重复步骤(2)的过程例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例5-7信源符号概率编码过程码字码长a10.20102a20该哈夫曼编码的平均码长

信息传输速率

码元/符号Bit/码元该哈夫曼编码的平均码长码元/符号Bit/码元哈夫曼编码方法得到的码并非唯一的1每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。2对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。哈夫曼编码方法得到的码并非唯一的1每次对信源缩减时，赋予设有离散无记忆信源设有离散无记忆信源信源符号概率编码过程码字码长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信源符号概率编码过程码字码长a10.411a20.2012a两种哈夫曼码的平均码长相等编码效率也相等码元/符号两种哈夫曼码的平均码长相等编码效率也相等码元/符号码方差码字长度偏离平均长度的程度第一种哈夫曼码的码方差第二种哈夫曼码的码方差码方差码字长度偏离平均长度的程度第一种哈夫曼码的码方差第11哈夫曼编码的特点用概率分配方法对信源进行编码1哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码。2缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。3

每次缩减信源的最长两个码字有相同的码长。三个特点保证了哈夫曼码是最佳码哈夫曼编码的特点用概率分配方法对信源进行编码多进制哈夫曼编码

对于多进制哈夫曼码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以信源符号数量尽量满足

m=(r-1)n+r

信源符号数进制数缩减的次数不满足时m+t=(r-1)n+r

需添置概率为0的虚拟符号t个多进制哈夫曼编码对于多进制哈夫曼码，为了提高编码效率，就要例对信源S进行四进制哈夫曼编码

SS1S2S3S4S5S6S7S8

P0.220.200.180.150.100.080.050.02码字123000102030031

例对信源S进行四进制哈夫曼编码例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.例5-9

信源输出2个符号，概率分布为P=（0.9,0.1)15一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码后，会造成编码输出每秒的比特数不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器。将编码输出暂存在缓冲器中，然后再由信道传输，使输入和输出的速率保持平衡。溢出：当信源连续输出低概率符号时，因为码长较长，有可能使缓冲器存不下而溢出。取空：当信源连续输出高概率符号时，有可能输入比特数小于信道中传输的比特数，以致缓冲器取空。一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码缓冲器信道传输速率R信源输出符号速率S平均码长1当R=S时存储器容量C应满足C>6.16√Nσ其中N为信源符号数，σ为码方差2当R>S时，平均来说，输出大于输入，易被取空3当R<S时，输入大于输出，易于溢出缓冲器信道传输速率R信源输出符号速率S平均码长17其他1变长码只适合有限长的信息传输

时间T越长，N越大，要求存储器的容量也越大。当容量设定后，随着时间的增长，存储器溢出和取空的概率都将增大。当T