搜索
信息论与编码技术实验报告实验题目香浓编码学生专业班级信息与计算科学1001学生姓名（学号）曹雪萍（20104590）指导教师吴慧完成时间2013年5月18日2013年5月18日信息论与编码技术实验报告实验题目Huffman编码软件实现学生专业班级信息与计算科学1001学生姓名（学号）曹雪萍（20104590）指导教师吴慧完成时间2013年5月19日2013年5月19日实验一香农编码的实验报告一、实验目的1.了解香农编码的基本原理及其特点；2.熟悉掌握香农编码的方法和步骤；3.掌握C语言或者Matlab编写香农编码的程序。二、实验要求对于给定的信源的概率分布,按照香农编码的方法进行计算机实现.三、实验原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码1．信源符号按概率从大到小排列2.对信源符号求累加概率，表达式：Gi=Gi-1+p(xi)3.求自信息量，确定码字长度。自信息量I(xi)=-log(p(xi));码字长度取大于等于自信息量的最小整数。4.将累加概率用二进制表示，并取小数点后码字的长度的码。四、实验内容离散无记忆信源符号S的概率分布：S1S2S3S4s5s6S7sP(S)=0.200.190.180.170.150.100.01对离散无记忆信源分布S进行香农编码1.画出程序设计的流程图，开始输入信源符号的个数输入对应符号的概率P（i）判断概率和S是否等于1按概率分布大小对信源排序计算平均码长计算编码效率计算累加概率将累加概率转化为二进制码字输出累加概率，码长，码字，自信息量，平均码长，编码效率计算自信息量结束2.写出程序代码，N=input('N=');%输入信源符号的个数s=0;l=0;H=0;fori=1:Np(i)=input('p=');%输入信源符号概率分布矢量,p(i)1s=s+p(i)H=H+(-p(i)*log2(p(i)));I(i)=-log2(p(i));%计算信源信息熵endifabs(s-1)0,error('不符合概率分布')endfori=1:N-1forj=i+1:Nifp(i)p(j)m=p(j);p(j)=p(i);p(i)=m;endendend%按概率分布大小对信源排序fori=1:Na=-log2(p(i));ifmod(a,1)==0w=a;elsew=fix(a+1);end%计算各信源符号的码长l=l+p(i)*w;%计算平均码长endl=l;n=H/l;%计算编码效率P(1)=0fori=2:NP(i)=0;forj=1:i-1P(i)=P(i)+p(j);endend%计算累加概率fori=1:Nforj=1:wW(i,j)=fix(P(i)*2);P(i)=P(i)*2-fix(P(i)*2);endend%将累加概率转化为L(i)位二进制码字disp(W)%显示码字disp(l)%显示平均码长disp(n)%显示编码效率disp(I)%显示自信息量3.写出在调试过程中出现的问题，问题1：自信量程序不会编写问题2：累加概率时注意P(1)=0问题3：程序运行时要依次输入各个符号概率4.对实验的结果进行分析由程序运行结果，得2.342.412.482.562.743.346.66所以我们得到每个信源符号的自信息量为I(s1)=2.34I(s2)=2.41I(s3)=2.48I(s4)=2.56I(s5)=2.74I(s6)=3.34I(s7)=6.66根据公式log()log()1iiipslps,我们得到每个信源符号的码长为l1=3l2=3l3=3l4=3l5=3l6=4l7=7由程序运行结果，0000000001100001100001001000101100011100001111110我们得到每个信源符号的为iG对应的二进制数为：G1=0.0000000G2=0.0011000G3=0.0110000G4=0.1001000G5=0.1011000G6=0.1110000G7=0.1111110所以我们得到每个信源符号的码字为：S1=000s2=001s3=011s4=100s5=101s6=1110s7=1111110平均码长为：3.14编码效率为：0.831五、实验结论与心得此次实验让我认识和熟悉了及步骤，对MATLAB软件也有更加深刻的掌握，会用它求某个符号信源的香农编码程序算法，对我的实验能力有所提高。Huffman编码软件实现实验报告一、实验目的1.进一步熟悉Huffman编码过程；2.掌握Matlab程序的设计和调试技术。二、实验要求1.输入：信源符号个数r、信源的概率分布P；2.输出：每个信源符号对应的Huffman编码的码字，编码效率。三、实验原理：1．二进制Huffman编码的基本原理设信源s={654321,,,,,ssssss}其中对应的概率分布为P(iS)={654321,,,,,pppppp}则其编码步骤如下：(1)将q个信源符号按概率递减的方式排列。(2)用0、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而的得到的只含q-1个符号的新信源，称为S信源的缩减信源1S(3)将缩减信源1S中的符号仍按概率大小以递减次序排列，重复步骤（2）(4)重复（1）(2)(3)三步骤，直至缩减信源只剩下两个符号为止，将这最后两个符号分别用0、1码字表示。(5)从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。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计算信源熵和平均码长，其比值即为编码密码效率。3.部分伪代码：（1）节点信息结构体structHuffNode{intweight;//信源符号的概率intparent;intlchild;intrchild;};（2）算法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].weightmin1&&hn[j].parent==0){}elseif(hn[j].weightmin2&&hn[j].parent==0){}else;}}在此逆序存储Huffman编码inttemp[maxlen];for(i=0;i!=n;++i){intparent=hn[i].parent;while(hn[child].parent!=0)4.Huffman编码方法的特征（1）它是一种分组码，各个信源符号都被映射成一组固定次序的马符号。（2）它是一种唯一可解的码，任何符号序列只能以一种方式译码。（3）它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即Huffman编码所得的码字为即时码。（4）Huffman码的译码：对接受到的哈弗曼码序列可通过从左到右检查各个符号进行译码。（5）哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和尽量处于高的位置，这样可使合并的元素重复编码次数减少，四、实验内容对离散无记忆信源04.016.032.022.008.018.0s654321ssssssp进行Huffman编码。1.画出Huffman编码的程序流程图（如下）开始输入信源符号对应概率P（i）判断P(i)是否0判别概率总和是否=1对概率数组q升序排序用0，1表示概率最小的两个信源符号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');将数组q前两项加和，得到新的概率序列判断信源符号是否只剩两个符号进行Huffman编码，并完成码字分配计算一个Huffman码字的平均码长计算信源熵和编码效率生成n-1行n列，每个元素含有n个字符的空白矩阵结束p=input('pleaseinputanumber:')endq=p;a=zeros(n-1,n);%生成一个n-1行n列的数组fori=1:n-1[q,l]=sort(q)a(i,:)=[l(1:n-i+1),zeros(1,i-1)]q=[q(1)+q(2),q(3:n),1];endfori=1:n-1c(i,1:n*n)=blanks(n*n);endc(n-1,n)='0';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)='0'c(n-i,n+1:2*n-1)=c(n-i,1:n-1)c(n-i,2*n)='1'forj=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))endendfori=1:nh(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n)ll(i)=length(find(abs(h(i,:))~=32))endl=sum(p.*ll);fprintf('\nhuffmancode:\n');hhh=sum(p.*(-log2(p)));fprintf('\nthehuffmaneffciency:\n');t=hh/l3.运行源程序后，实验过程中的测试结果p=0.320.220.180.160.080.04q=0.040.080.1