哈夫曼编码

哈夫曼编码方法哈夫曼编码1952年哈夫曼提出了一种构造最佳码的方法称之为哈夫曼编码。哈夫曼编码适用于多元独立信源对于独立信源来说，哈夫曼编码是最佳码他充分的利用了信源的概率特性进行编码，编码方法(1)将信源消息符号按其出现的概率大小依次排列(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队编码方法(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。例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该哈夫曼编码的平均码长信息传输速率72.2)(71iiiKapK96.072.261.2)(KXHR码元/符号Bit/码元哈夫曼编码方法得到的码并非唯一的1每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。2对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。设有离散无记忆信源1.01.02.02.04.054321aaaaaPX信源符号概率编码过程码字码长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.02.2)(71iiiKapK965.0)(KXH两种哈夫曼码的平均码长相等编码效率也相等码元/符号码方差码字长度偏离平均长度的程度qiiiilKkapKkE1222))((36.121l16.022l第一种哈夫曼码的码方差第二种哈夫曼码的码方差哈夫曼编码的特点用概率分配方法对信源进行编码1哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码。2缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。3每次缩减信源的最长两个码字有相同的码长。三个特点保证了哈夫曼码是最佳码多进制哈夫曼编码对于多进制哈夫曼码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以信源符号数量尽量满足m=(r-1)n+r信源符号数进制数缩减的次数不满足时m+t=(r-1)n+r需添置概率为0的虚拟符号t个例对信源S进行四进制哈夫曼编码SS1S2S3S4S5S6S7S8P0.220.200.180.150.100.080.050.02码字123000102030031例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.KKKK一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码后，会造成编码输出每秒的比特数不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器。将编码输出暂存在缓冲器中，然后再由信道传输，使输入和输出的速率保持平衡。溢出：当信源连续输出低概率符号时，因为码长较长，有可能使缓冲器存不下而溢出。取空：当信源连续输出高概率符号时，有可能输入比特数小于信道中传输的比特数，以致缓冲器取空。缓冲器信道传输速率R信源输出符号速率S平均码长1当R=S时存储器容量C应满足C6.16√Nσ其中N为信源符号数，σ为码方差2当RS时，平均来说，输出大于输入，易被取空3当RS时，输入大于输出，易于溢出KKKK其他1变长码只适合有限长的信息传输时间T越长，N越大，要求存储器的容量也越大。当容量设定后，随着时间的增长，存储器溢出和取空的概率都将增大。当T很大时，几乎一定会溢出或取空造成损失。因而，对于无限长的信息，很难采用变长码而不出现差错。2差错的扩散变长码由信道传输的过程中，一个码字前面有某一个码元错了，就可能误认为是另一个码字而断点，结果后面一系列码字也会易错，称之为差错的扩散。谢谢大家！