实验二哈弗曼编码

信息论与编码技术实验报告姓名:学号:专业班级:学院:联系方式:Huffman编码软件实现实验报告一、实验目的进一步熟悉Huffman编码过程；掌握Matlab程序的设计和调试技术。二、实验要求输入：信源符号个数r、信源的概率分布P；输出：每个信源符号对应的Huffman编码的码字，编码效率。三、实验原理：1.二进制Huffman编码的基本原理设信源S={ss,...s}，其中对应的概率分布为P(s)={pp,...p}，则其编码步1,2qi1,2q骤如下：将q个信源符号按概率递减的方式排列。用0、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而的得到的只含q-1个符号的新信源，称为S信源的缩减信源S1将缩减信源s中的符号仍按概率大小以递减次序排列，在将其最后两个概率1最小的符号合并成一个符号，并分别用0、1码符号表示，这样由形成了由q-2个符号构成的缩减信源s2重复(2)(3)两步骤，直至缩减信源只剩下两个符号为止，将这最后两个符号分别用0、1码字表示。从最后一级缩减信源开始，向前返回，沿信源缩减过程的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。2.二进制Huffman编码程序设计的原理(编码步骤)(1)程序的输入：以一维数组的形式输入要进行Huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。(2)Huffman编码具体实现原理：<1>在输入的概率矩阵p正确的前提条件下，对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。<2>新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行Huffman编码：将c矩阵的第n-1行的第一和第二个元素分别令为0和1(表示在编码时，根节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则)然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码(该编码即为第n-i-1行第一、二个元素的根节点)，则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成Huffman编码。<3>计算信源熵和平均码长，其比值即为编码密码效率。部分伪代码(算法知识)：节点信息结构体structHuffNode{intweight;〃信源符号的概率intparent;intlchild;intrchild;};算法voidHuffman(intweight[],intn,HuffNodehn[],HuffCodehc[]){for(i=0;i!=2*n-1;++i)//createHuffmanNode,step1{}for(i=0;i!=n-1;++i)//createHuffmanNode,step2{for(j=0;j!=n+i;j++){if(hn[j].weight<min1&&hn[j].parent==0){}elseif(hn[j].weight<min2&&hn[j].parent==0){}else;}}在此逆序存储Huffman编码inttemp[maxlen];for(i=0;i!=n;++i){intparent=hn[i].parent;while(hn[child].parent!=0){}Huffman编码方法的特征★它是一种分组码，各个信源符号都被映射成一组固定次序的马符号。★它是一种唯一可解的码，任何符号序列只能以一种方式译码。★它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即Huffman编码所得的码字为即时码。★Huffman码的译码：对接受到的哈弗曼码序列可通过从左到右检查各个符号进行译码。★哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和尽量处于高的位置，这样可使合并的元素重复编码次数减少，使短码得到充分利用。四、实验内容对离散无记忆信源5=*'S3S4'进行Huffman编码。P(s)0.40.20.20.10.1—i—II——画出Huffman编码的程序流程图(如下)2.写出Huffman编码的源程序(如下)p=input('pleaseinputanumber:')n=length(p);fori=1:nifp(i)<0fprintf('\nTheprobabilitiesinhuffmancannotlessthan0!\n');p=input('pleaseinputanumber:，)%若输入的概率数组中有小于0的值，则重新输入概率数组endendifabs(sum(p)-1)>0fprintf('\nThesumoftheprobabilitiesinhuffmancanmorethan1!\n');p=input('pleaseinputanumber：')%如果输入的概率数组总和大于1,则重新输入概率数组endq=p;a=zeros(n-1,n);%生成一个n-1行n列的数组fori=1:n-1[q,l]=sort(q)%对概率数组q进行从小至大的排序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号a(i,:)=[l(1:n-i+1),zeros(1,i-1)]%由数组l构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码q=[q⑴+q(2),q(3:n),1上％将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列endc(i,l.n*n)=blanks(n*n),%生成一个n-1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码，并且在编码中与a矩阵有一定的对应关系endc(n-1,n)=0；%由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最后两个概率，因此其值为0或1，在编码时设第n-1行的第一个空白字符为0,第二个空白字符1。c(n-1,2*n)='1';fori=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1)))%矩阵c的第n-i的第一个元素的n-1的字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编码值c(n-i,n)='0'%根据之前的规则，在分支的第一个元素最后补0c(n-i,n+1:2*n-1)=c(n-i,1:n-1)%矩阵c的第n-i的第二个元素的n-1的字符与第n-i行的第一个元素的前n-1个符号相同，因为其根节点相同c(n-i,2*n)=1%根据之前的规则，在分支的第一个元素最后补1forj=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1))%矩阵c中第n-i行第j+1列的值等于对应于a矩阵中，第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值endend%完成huffman码字的分配fori=1:nendh(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n)%用h表示最后的huffman编码，矩阵h的第i行的元素对应于矩阵c的第一行的第i个元素ll(i)=length(find(abs(h(i，:))~=32))%计算每一个huffman编码的长度endl=sum(p.*ll);%计算平均码长fprintf('\nhuffmancode:\n');hhh=sum(p.*(-log2(p)));%计算信源熵fprintf('\nthehuffmaneffciency:\n');t=hh/l3.运行源程序后，实验过程中的测试结果p=0.40000.20000.20000.10000.1000q=0.10000.10000.20000.20000.4000q=0.20000.20000.20000.40001.0000q=0.20000.40000.40001.00001.0000q=0.40000.60001.00001.00001.0000ll=13244huffmancode:h=01111011001101thehuffmaneffciency:t=0.96454.实验结果分析信源(sssss)的码字长度分别为13244；12345所对应的码字为01111011001101；编码效率为0.9645。五、总结实验过程遇到的问题及解决方法在实验过程中，遇到以下几个问题：信源缩减不知怎么表示；不知如何运用矩