哈夫曼编码

1郑州轻工业学院本科生实验报告实验名称哈夫曼编码课程名称信息论与编码姓名**指导教师***专业、班级***********学号***********实验时间***8实验地点121实验目的1.掌握哈夫曼编码的原理及编码步骤2.练习matlab中哈夫曼编码函数的调用及通信工具箱的使用2实验条件通信的根本问题是如何将信源输出的信息在接收端的信宿精确或近似的复制出来。为了有效地复制信号，就通过对信源进行编码，使通信系统与信源的统计特性相匹配。若接收端要求无失真地精确地复制信源输出的信息，这样的信源编码即为无失真编码。即使对于一个小的时间段内，连续信源输出的信息量也可以是无限大的，所以对其是无法实现无失真编码的；而离散信源输出的信息量却可以看成是有限的，所以只有离散信源才可能实现无失真编码。凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可以称为最佳码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。变字长编码的最佳编码定理：在变字长码中，对于概率大的信息符号编以短字长的码；对于概率小的信息符号编以长字长的码。如果码字长度严格按照符号概率的大小顺序排列，则平均码字长度一定小于俺任何顺序排列方式得到的码字长度。哈夫曼编码就是利用了这个定理，讲等长分组的信源符号，根据其概率分布采用不等长编码。概率大的分组，使用短的码字编码；概率小的分组，使用长的码字编码。哈夫曼编码把信源按概率大小顺序排列，并设法按逆次序分配码字的长度。在分配码字的长度时，首先将出现概率最小的两个符号相加，合成一个概率；第二步把这个合成的概率看成是一个新组合符号的概率，重复上述做法，直到最后只剩下两个符号的概率为止。完成以上概率相加顺序排列后，再反过来逐步向前进行编码。每一步有两个分支，各赋予一个二进制码，可以对概率大的编为0码，概率小的编为1码。反之亦然。哈夫曼编码的具体步骤归纳如下：1.统计n个信源消息符号，得到n个不同概率的信息符号。2.将这n个信源信息符号按其概率大小依次排序：p(x1)≥p(x2)≥…≥p(xn)3.取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列。4.将剩余的信息符号，按概率大小重新进行排序。5.重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排序。6.如此反复重复n-2次，最后只剩下两个概率。7.从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。编码结束。3哈夫曼编码产生最佳整数前缀码，即没有一个码字是另一个码字的前缀，因此哈夫曼编码是唯一码。编码之后，哈夫曼编码的平均码长为：1()niiiKpxK哈夫曼编码的效率为：()=HxK信源熵平均码长例2-1设信源共7个符号消息，其概率如下表所示信源消息符号xix1x2x3x4x5x6x7符号概率P（xi）0.200.190.180.170.150.100.01其编码过程如下所示：该哈夫曼码的平均码长为71()2.72iiiKpxK码元/符号4编码效率为：()2.610.9596/2.72HXK比特码元5实验内容与步骤为某一信源进行哈夫曼编码。该信源的字符集为X={x1,x2,…x6}，相应的概率矢量为：P=(0.30,0.25,0.21,0.10,0.09,0.05)，即X，P的概率空间为：1234560.300.250.210.100.090.05XxxxxxxP根据哈夫曼编码算法对该信源进行哈夫曼编码。并计算其平均码长和编码效率。调用matlab哈夫曼编码函数进行哈夫曼编码，与人工编码结果做比较。1.huffmandict函数：为已知概率分布的信源模型生成哈夫曼编解码索引表。调用方法如下：[dict，avglen]=huffmandict(symbols,p)[dict，avglen]=huffmandict(symbols,p,N)[dict，avglen]=huffmandict(symbols,p,N,variance)6实验结果及分析Maltab代码：symbols=[1:6]prob=[.3.25.21.1.09.05][dict,avglen]=huffmandict(symbols,prob)temp=dict;fori=1:length(temp)temp{i,2}=num2str(temp{i,2});endh=-0.3.*log2(0.3)-0.25.*log2(0.25)-0.21.*log2(0.21)-0.10.*log2(0.10)-0.09.*log2(0.09)-0.05.*log2(0.05);n=h/avglentemp结果如下：symbols=123456prob=0.30000.25000.21000.10000.09000.0500dict=[1][1x2double][2][1x2double][3][1x2double][4][1x3double][5][1x4double][6][1x4double]avglen=2.3800n=0.9894temp=7[1]'00'[2]'01'[3]'11'[4]'101'[5]'1000'[6]'1001'实验日期：2013年*月**日评分：指导教师签字：