《信息论与编码matlab(共14页).docx》由会员分享，可在线阅读，更多相关《信息论与编码matlab(共14页).docx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上信息论实验报告姓名 胡小辉 班级 电子信息工程0902学号 1. 实验目的 1、掌握哈夫曼编码、费诺编码、汉明码原理；2、熟练掌握哈夫曼树的生成方法；3、学会利用matlab、C语言等实现Huffman编码、费诺编码以及hamming编码。2. 实验原理Huffman编码：哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树； 实现Huffman编码原理的步骤如下：1.首先将信源符号集中的符号按概率大小从大到小排列。2.用0和1表示概率最小的两个符号。可用0表示概率小的符号，也可用
2、1表示概率小的符号，但整个编码需保持一致。3.将这两个概率最小的符号合并成一个符号，合并符号概率为最小概率之和，将合并后的符号与其余符号组成一个N-1的新信源符号集，称之为缩减符号集。4.对缩减符号集用步骤1,2操作5.以此类推，直到只剩两个符号，将0和1分别赋予它们。6.根据以上步骤，得到0,1赋值，画出Huffman码树，并从最后一个合并符号回朔得到Huffmaan编码。 费诺编码： 费诺编码的实现步骤：1、将信源消息符号按其出现的概率大小依次排列： 。2、将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。3、将每一大组的信源符号
3、再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。4、如此重复，直至每个组只剩下一个信源符号为止。5、信源符号所对应的码字即为费诺码。hamming编码： 若一致监督矩阵H 的列是由不全为0且互不相同的所有二进制m(m2的正整数)重组成，则由此H矩阵得到的线性分组码称为2m-1,2m-1-m，3汉明码。 我们通过（7，4）汉明码的例子来说明如何具体构造这种码。设分组码（n，k）中，k = 4，为能纠正一位误码，要求r3。现取r3，则nkr7。我们用a0ala2a3a4a5a6表示这7个码元，用S1、S2、S3表示由三个监督方程式计算得到的校正子，并假设三
4、位S1、S2、S3校正子码组与误码位置的对应关系如表1所示。S1S2S3错码位置S1S2S3 错码位置 001 a0 101 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 无错码 表1 校正子和错码位置关系由表可知，当误码位置在a2、a4、a5、a6时，校正子S11；否则S10。因此有S1a6a5a4a2，同理有S2a6a5a3a1和S3a6a4a3a0。在编码时a6、a5、a4、a3为信息码元，a2、a1、a0为监督码元。则监督码元可由以下监督方程唯一确定 a6a5a4a2 = 0 a6a5a3a1 = 0 (1.1.1) a6a4a3a0 = 0 也即
5、a2a6a5a4 a1a6a5a3 （ 1.1.2）a0 = a6a4a3由上面方程可得到表2所示的16个许用码组。在接收端收到每个码组后，计算出S1、S2、S3，如果不全为0，则表示存在错误，可以由表1确定错误位置并予以纠正。举个例子，假设收到码组为，可算出S1S2S3=011,由表1可知在a3上有一误码。通过观察可以看出，上述（7，4）码的最小码距为dmin3，纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码. 信息位 监督位 信息位 监督位 a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a000000001 0010 0011 0100 0101 0
6、1100111 000 011 101 110 110 101 011 00010001001101010111100110111101111 111100010001001010100111 表2 （7,4）汉明码的许用码组(7,4)汉明码的编码就是将输入的四位信息码编成七位的汉明码，即加入三位监督位。根据式(2.2.0）A = a6 a5 a4 a3 G可知，信息码与生成矩阵G的乘积就是编好以后的(7,4)汉明码，而生成矩阵G又是已知的，由式(1.1.9)得1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1所以，可以得出如
7、下方程组 a6 = a6 a5 = a5 a4 = a4 a3 = a3 a2 = a6 + a5 + a4 a1 = a6 + a5 + a3 a0 = a6 + a4 + a3根据此式子编出编码程序。3. 实验过程及结果1、 哈弗曼编码例如：当p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4则根据其原理得到的matlab程序如下：clc;clear;A=0.3,0.15,0.05,0.1,0.4;%信源消息的概率序列A=fliplr(sort(A);%按降序排列T=A;m,n=size(A);B=zeros(n,n-1);%空的编码表（矩阵）for i=1:n B(
8、i,1)=T(i);%生成编码表的第一列endr=B(i,1)+B(i-1,1);%最后两个元素相加T(n-1)=r;T(n)=0;T=fliplr(sort(T);t=n-1;for j=2:n-1%生成编码表的其他各列 for i=1:t B(i,j)=T(i); end K=find(T=r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在%该列的位置 r=(B(t-1,j)+B(t,j);%最后两个元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T); t=t-1;endB;%输出编码表END1=sym(0,1);%给最后一列的
9、元素编码END=END1;t=3;d=1;for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码 for i=1:t-2 if i1 & B(i,j)=B(i-1,j) d=d+1; else d=1; end B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp=B(i,j); END(i)=END1(x(d); end y=B(n,j+1); END(t-1)=char(END1(y),0; END(t)=char(END1(y),1; t=t+1; END1=END;end A%排序后的原概率序列 END%编码结果for i=1:n a,
10、b=size(char(END(i); L(i)=b;endavlen=sum(L.*A)%平均码长 H1=log2(A);H=-A*(H1)%熵P=H/avlen%编码效率输出结果：费诺编码： 同样，例如：p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4时 根据其原理所得到的matlab程序如下： clc;clear;A=0.3,0.15,0.05,0.1,0.4;A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n B(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1)/2;for k=1:n-1
11、 if abs(sum(B(1:k,1)-a)=abs(sum(B(1:k+1,1)-a) break; endendfor i=1:n%生成B第2列的元素 if i=k B(i,2)=0; else B(i,2)=1; endend%生成第一次编码的结果END=B(:,2);END=sym(END);%生成第3列及以后几列的各元素j=3;while (j=0) p=1; while(p=n) x=B(p,j-1); for q=p:n if x=-1 break; else if B(q,j-1)=x y=1; continue; else y=0; break; end end end i
12、f y=1 q=q+1; end if q=p|q-p=1 B(p,j)=-1; else if q-p=2 B(p,j)=0; END(p)=char(END(p),0; B(q-1,j)=1; END(q-1)=char(END(q-1),1; else a=sum(B(p:q-1,1)/2; for k=p:q-2 if abs(sum(B(p:k,1)-a)=abs(sum(B(p:k+1,1)-a); break; end end for i=p:q-1 if i=k B(i,j)=0; END(i)=char(END(i),0; else B(i,j)=1; END(i)=char
13、(END(i),1; end end end end p=q; end C=B(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendBAENDfor i=1:n u,v=size(char(END(i); L(i)=v;endavlen=sum(L.*A)输出结果：汉明码：clc;clear;close;N=100;display(随机产生二进制信源消息序列:);a=randint(1,100); %*转换矩阵afor i=0:(length(a)/4-1) for j=0:(4-1) P(i+1,j+1)=a(j+i*
14、4+1); endendP%function g=hammingdecod(R)%H=input(生成汉明码:);H=1 1 1 0 1 0 0;1 1 0 1 0 1 0;1 0 1 1 0 0 1;%生成汉明码G=1 0 0 0 1 1 1;0 1 0 0 1 1 0;0 0 1 0 1 0 1;0 0 0 1 0 1 1 %(7,4)汉明码的生成矩阵%t=input(输入0或1:); %t=0则产生（7，4）汉明码，t=1则对输入序列进行编码%if t=1 c=mod(P*G,2); %编码的码字c %function X=turnRow(c) n=size(c);for i=0:(n(
15、1)-1) for j=0:(n(2)-1) X(j+i*n(2)+1)=c(i+1,j+1); endend X1=randerr(1,175,1); %*相加 Q=mod(X1+X,2); %*转换矩阵X1 %*编码 for i=0:(length(Q)/7-1) for j=0:(7-1) Q1(i+1,j+1)=Q(j+i*7+1); end enddisp(输出编码后序列为：);Q1Z=mod(Q1*H,2);Z%*编码n=size(Z);%T=T();for i=0:(n(1)-1) T(i+1)=4*Z(i+1,1)+2*Z(i+1,2)+Z(i+1,3); if T(i+1)
16、Q1(i+1,8-T(i+1)=1-Q1(i+1,8-T(i+1); endendT=Q1;disp(经过信道后变为：);T%*译码function C=yima(B,k)n=size(T);for i=1:n(1) for j=1:4 C(i,j)=T(i,j); endenddisp(输出译码序列:);disp(C);输出结果：实验心得： 通过这次实验，我更深入了解了哈夫曼编码的构造原理。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。同时，进一步使用了matlab这
17、个软件工具，进一步熟悉了在matlab中的编程的语法和结构。认识到了软件工具在通信科研仿真方面的重要作用和方便性。正所谓“纸上得来终觉浅，觉知此事要躬行。”学习任何知识，仅从理论上去求知，而不去实践、探索是不够的。在整个实验过程中我懂得了许多东西，虽然很多东西都是从网上找的，但是在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生活有非常大的帮助，并且提高了自己的动手实践操作能力， 使自己充分体会到了在实验过程中的成功喜悦。虽然这个实验做的不怎么好，但是在过程中所学到的东西是这次实验的最大收获和财富，使我终身受益。专心-专注-专业