信息论与编码实验报告(共24页).doc

《信息论与编码实验报告(共24页).doc》由会员分享，可在线阅读，更多相关《信息论与编码实验报告(共24页).doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上信息论与编码实验讲义宋 毅淮阴师范学院物电学院2012年9月15日专心-专注-专业序言本实验讲义配合电子信息类专业开设的专业课信息论与编码而编写，作为信息论与编码的配套讲义，供该课程配套实验用。信息论与编码是现代信息科学的基础技术之一，也是理论与实践不可分离的一门学科，本讲义力求注重实践和培养学生动手能力，同时注重信息技术的仿真应用实验。由于水平限制，书中难免有不足和差错之处，恳请广大师生批评指正。编 者2012年9月实验一、 绘制二进制熵函数曲线一、实验目的1掌握二进制符号熵的计算；2掌握MATLAB的应用；3掌握Matlab绘图函数；4掌握、理解熵函数表达式及其性

2、质二、实验条件计算机一台，MATLAB仿真软件。三、实验内容（1）MATLAB的应用（请参阅相关书籍）（2）打开MATLAB，在命令窗口中输入eidt，弹出编辑窗口，如图1：图1 MATLAB的编辑窗口 （3）输入源程序：clear;x=0.001:0.001:0.999y=-x.*log2(x)-(1-x).*log2(1-x);plot(x,y);grid on（4）保存文件为entropy.m；（5）单击Debug菜单下的Run，或直接按F5执行；（6）执行后的结果图2：四、实验分析clear;x=0.001:0.001:0.999y=-x.*log2(x)-(1-x).*log2(1-

3、x);plot(x,y);xlabel(p);ylabel(H(p);title(H(p);grid onclear;x=0.001:0.02:0.999y=-x.*log2(x)-(1-x).*log2(1-x);plot(x,y);xlabel(p);ylabel(H(p);title(H(p);grid onclear;x=0.009:0.002:0.991y=-x.*log2(x)-(1-x).*log2(1-x);plot(x,y);xlabel(p);ylabel(H(p);title(H(p);grid on 分析总结： （1）熵函数是一个严格上凸函数 （2）熵的极大值，二进符号

4、的熵在p(x1)=p(x2)=0.5取得极大值 （3）调调整p(x1)的取值步长，重画该曲线。当步长改变为0.02，步长变大的时候，可以看到函数图像有一段缺失,且图像不对称。（4）调整p(x1)的取值区间可以发现（3）的问题就解决了，函数图像仍有缺失，但是图像对称。可以发现当步长改变时，p(x1)取值区间也应该改变，否则图像不对称（5）当二元信源符号0和1以等概率发生的时候，信源熵达到极大值，等于1bit信息量。（6）实验需要多次操作，不断改变数值，观察图像，会有意想不到的结果出现。例如概率p的取值以及取p时的步长的改变，图像也随之改变，另外p是对称出现的而不是只有一端缺失。 实验二、一般信道

5、容量计算一、实验目的1熟悉工作环境及Matlab软件2理解平均互信息量表达式及其性质3理解信道容量的含义二、 实验原理1.平均互信息量(I(X;Y)是统计平均意义下的先验不确定性与后验不确定性之差，是互信息量的统计平均:2.离散信道的数学模型离散信道的数学模型一般如图1所示。图中输入和输出信号用随机矢量表示，输入信号为X= (X1, X2, XN)，输出信号为Y= (Y1, Y2, YN)；每个随机变量Xi和Yi又分别取值于符号集A=a1, a2, , ar和B=b1, b2, , bs，其中r不一定等于s；条件概率P(y|x) 描述了输入信号和输出信号之间的统计依赖关系，反映了信道的统计特性

6、。YX信道 图1离散信道模型二元对称信道这是很重要的一种特殊信道（简记为BSC），。它的输入符号X取值于0,1，输出符号Y取值于0,1，r=s=2， a1=b1=0，a2=b2=1，传递概率为, , 其中，表示信道输入符号为0而接收到的符号为1的概率，表示信道输入符号为1而接受到的符号为0的概率，它们都是单个符号传输发生错误的概率，通常用p表示。而和是无错误传输的概率，通常用表示。X 1-p Y 二元对称信道用矩阵来表示，即得二元对称信道的传递矩阵为依此类推，一般离散单符号信道的传递概率可用以下形式的矩阵来表示，即b1 b2 bs并满足式 （）。为了表述简便，记，信道的传递矩阵表示为而且满足

7、平均互信息平均互信息表示接收到输出符号后平均每个符号获得的关于输入变量X的信息量，也表示输入与输出两个随机变量之间的统计约束程度。 其中X是输入随机变量，Y是输出随机变量。平均互信息是互信息（即接收到输出符号y后输入符号x获得的信息量）的统计平均值，所以永远不会取负值。最差情况是平均互信息为零，也就是在信道输出端接收到输出符号Y后不获得任何关于输入符号X的信息量。对于每一个确定信道，都有一个信源分布，使得信息传输率达到最大值，我们把这个最大值称为该信道的信道容量。相应的输入概率分布称为最佳输入分布。三、实验内容1绘制平均互信息量图形对于二元对称信道的输入概率空间为平均互信息：根据：所以： 请绘

8、制当从0到1之间变化时的平均互信息熵曲线2. 信道容量图形一个信道是一个二进制输入，二进制输出的信道，输入和输出字母表，且该信道特性由发送1码和0码的两个错误转移概率和来表征。绘出当时的平均互信息和间的函数关系。确定每种情况下的信道容量。四、实验报告要求你能从实验图形中了解它的一些什么性质？五、实验结果及分析clear;w,p=meshgrid(0.00001:0.003:1);y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p).*log(w.*p+(1-w).*(1-p)+p.*log(p)+(1-p).*log

9、(1-p);meshz(w,p,y);title(二进制信道的信道容量);Xlabel(w);ylabel(p);zlabel(I(W;Y);grid onclear;w=0.5;p=0.001:0.001:0.999;y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p).*log(w.*p+(1-w).*(1-p)+p.*log(p)+(1-p).*log(1-p);plot(p,y);title(二进制信道的信道容量);xlabel(p);ylabel(I(W;Y);grid onclear;p=0.1;w=0.

10、001:0.001:0.999;y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p).*log(w.*p+(1-w).*(1-p)+p.*log(p)+(1-p).*log(1-p);plot(w,y);title(二进制信道的信道容量);Xlabel(w);ylabel(I(W;Y);grid on w=0.9998p=0:0.1:1IXY=-(w.*(1-p)+(1-w).*p).*log2(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p).*log2(w.*p+(1-w).*(1-p)

11、+(p.*log2(p)+(1-p).*log2(1-p)stem(p,IXY);grid ontitle(信道容量)xlable(p)ylable(I(X;Y);grid on分析：从第一个三维图上面可以看出是w,p与I(X;Y)之间的关系。而第二个图和第三个图都是第一个图的侧面图。从第二个侧面图发现当w=0时，错误概率为0，信道容量达到最大，每符号1bit；当w=1/2时，错误概率与正确概率相同，互信息为0，在信道接收端平均每个符号才获得最小的信息量，即信道容量为0；从第三个侧面图发现当固定信道时，只有当输入变量是等概率分布，即p(x=0)=p(x=1)=在信道接收端平均每个符号才获得最大

12、的信息量，即等于1.当w固定时，即信源固定后，I(p;y)是关于信道传递概率p的下凸函数。信道输出端获得关于信源的信息量是信道传递概率的下凸函数。也就是说输出端所获得的信息量最小。当p固定时，即固定某信道时， I(w;y)是关于输入信源的概率分布的上凸函数，即对于每一个确定信道，都存在一个信源分布，使得信息传输率达到最大值，我们把这个最大值称为该信道的信道容量。 三、绘制离散信源信息率失真函数曲线一、实验目的：1.了解率失真函数性质、意义。2.掌握简单的率失真函数计算方法；3.掌握使用Matlab实现一般率失真函数的计算方法；二、实验原理二元对称信源的R(D)函数设二元信源U=0,1，其分布概

13、率 而接收变量v=0,1，设汉明失真矩阵为：因而最小失真度 。并能找到满足该最小失真的试验信道，且是一个无噪无损信道，其信道矩阵为：要达到最大允许失真，唯一确定 此时，可计算得信息传输率一般情况下，当 时可以计算得：二元对称信源信息率失真函数为三、实验内容1.从理论上计算r=s=2。p(u=1)=p,p (u=2)=1-p;d=0,1;1,0的率失真函数R(D)。2.对一般性的DMS信源，计算率失真函数R(D)的理论公式进行推导。3.找出比较合适的方程求解方法。4.使用编制Matlab编制程序求解一般的率失真函数R(D)。5.给定r=s=2。p(u=1)=0.4,p=(u=2)=0.6;d=0

14、,1;1,0，测试程序，即比较程序运行结果与理论计算结果,6.改变参数，画出函数图。四、思考题你能从实验图形中了解它的一些什么性质？五、注意事项1.提前预习实验，认真阅读实验原理。2.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。3.实验报告要求有：l 问题的提出：包括R(D)的物理意义、用途（可以举出具体的用途）、计算的困难性等。l 解决问题的原理方法：包括所有的公式推导的细节。l 解决问题的具体方法：包括程序框图及Matlab源程序。l 实验结果：利用你的程序给出不同参数得到的实验结果。l 结果分析：包括R(D)的性质、程序收敛情况、程序改进的方向等。4.每个同学

15、必须独立完成实验（不能抄袭，否则两人均为零分），实验成绩是该门课程成绩的主要依据。六、实验结果及分析p1=0.4;d1=0:0.001:0.4y1=-p1.*log2(p1)-(1-p1).*log2(1-p1)+d1.*log2(d1)+(1-d1).*log2(1-d1);p2=0.3;d2=0:0.001:0.3grid ony2=-p2.*log2(p2)-(1-p2).*log2(1-p2)+d2.*log2(d2)+(1-d2).*log2(1-d2);plot(d1,y1,k-);hold;plot(d2,y2);grid ontitle(离散信源信息率失真函数)xlabel(D

16、);ylabel(R(D);分析：（1）R(D)在定义域内是失真度D的U型下凸函数；R(D)在定义域内是关于D的连续函数；R(D)的单调递减性，容许的失真度越大，所要求的信息率越小。（2）对于固定的信源分布，平均互信息量I(X;Y)是信道转移概率 p(bj/ai) 的下凸函数。也就是说:存在一个信道使某一特定信源经过此信道传输时，信道的平均互信息达到极小值.性质： R(D)是非负的实数，定义域为0到Dmax，其值为0到H(X)；当DDmax时，R(D)=0。R(D)是关于D的下凸函数，因而也是关于D的连续函数。R（D）是关于D的严格递减函数。对于同一D，信源分布越均匀，R(D)就越大，信源压缩

17、的可能性越小，反之，若信源分布越不均匀，即信源剩余度越大R(D)就越小，压缩的可能性越大。实验四、香农编码一、实验目的（1）了解香农编码的基本原理及其特点；（2）熟悉掌握香农编码的方法和步骤；（3）掌握Matlab编写香农编码的程序。二、实验原理香农编码的步骤如下：将信源符号按概率从大到小的顺序排列, p(a1) p(a2) p(an)确定满足下列不等式的整数Ki , log2 p(ai) Ki 1 temp=temp-1;C(1,i)=1;elseC(1,i)=0;endendn=input(输入信源符号个数n=)p=zeros(1,n);for i=1:np(1,i)=input(输入信源

18、符号概率:);endif sum(p)1error(输入概率不符合概率分布 )endy=fliplr(sort(p); D=zeros(n,4); D(:,1)=y; for i=2:n D(1,2)=0;D(i,2)=D(i-1,1)+D(i-1,2);end for i=1:n D(i,3)=-log2(D(i,1); D(i,4)=ceil(D(i,3); endDA=D(:,2);B=D(:,4);for j=1:nC=deczbin(A(j),B(j) end输入信源符号个数n=7n = 7输入信源符号概率:0.2输入信源符号概率:0.19输入信源符号概率:0.18输入信源符号概率:

19、0.17输入信源符号概率:0.15输入信源符号概率:0.10输入信源符号概率:0.01D = 0.2000 0 2.3219 3.0000 0.1900 0.2000 2.3959 3.0000 0.1800 0.3900 2.4739 3.0000 0.1700 0.5700 2.5564 3.0000 0.1500 0.7400 2.7370 3.0000 0.1000 0.8900 3.3219 4.0000 0.0100 0.9900 6.6439 7.0000C = 0 0 0C = 0 0 1C = 0 1 1C = 1 0 0C = 1 0 1C = 1 1 1 0C = 1 1

20、 1 1 1 1 0香农第一定理指出，选择每个码字的长度Ki满足下式 I(xi)KI(xi)+1,i为任意值就可以得到这种码。这种编码方法就是香农编码。香农编码多余度稍大，效率低，实用性不强。香农编码是码符号概率大的用短码表示，概率小的是用长码表示，程序中对概率排序，最后求得的码字就依次与排序后的符号概率对应。实验五、Huffman编码一、实验目的1. 进一步熟悉Huffman编码过程；2. 掌握Matlab程序的设计和调试技术。二、实验原理1、二进制Huffman编码的基本原理及算法(1) 把信源符号集中的所有符号按概率从大到小排队。(2) 取概率最小的两个符号作为两片叶子合并（缩减）到一个

21、 节点。(3) 视此节点为新符号，其概率等于被合并（缩减）的两个概率之和，参与概率排队。(4) 重复(2)(3)两步骤，直至全部符号都被合并（缩减）到根。 (5) 从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个码字的编码和码长。2、程序设计的原理 (1)程序的输入：以一维数组的形式输入要进行huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。（2）huffman编码具体实现原理： 1在输

22、入的概率矩阵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行

23、中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。3、哈夫曼编码的程序流程图：初始化原始消息数将n个消息进行排序装入哈夫曼数据使左分支编码为1，右分值编码为0码字初始化为0排序列表初始化获得哈夫曼码字分别遍历左右分支节结束

24、将最后两个出现概率最小的消息合成一个消息将消息添加到队列的最后为n-1消息重新进行排列做准备遍历至原始消息，即叶子节点，输出读码字开始三、实验要求1. 输入：信源符号个数r、信源的概率分布P；2. 输出：每个信源符号对应的Huffman编码的码字。四、实验报告要求总结Huffman编码的基本原理及其特点？五、实验结果和总结n=input(输入信源符号数:);p=input(输入信源符号概率:);for i=1:n if p(i)0 error(输入概率不符合概率分布); p=input(输入信源符号概率:) end end if sum(p)1 error(输入概率不符合概率分布)endq=p

25、;q=fliplr(sort(q);disp(排序后的输入信源符号概率:);disp(q)a=zeros(n-1,n);for i=1:n-1q,l=sort(q); a(i,:)=l(1:n-i+1),zeros(1,i-1); q=q(1)+q(2),q(3:n),1;endfor i=1:n-1 c(i,1:n*n)=blanks(n*n);endc(n-1,n)=1;c(n-1,2*n)=0;for i=2:n-1 c(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; c(

26、n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)=0; for j=1:i-1 c(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);endendfor i=1:n h(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);endCode_length=0;for i=1:n Code_length=Code_length+p(1,i

27、)*ll(i);endl=sum(p.*ll);disp(哈夫曼编码:);disp(h)输入信源符号数:7输入信源符号概率:0.19,0.2,0.18,0.15,0.17,0.1,0.01排序后的输入信源符号概率: 0.2000 0.1900 0.1800 0.1700 0.1500 0.1000 0.0100哈夫曼编码: 10 11 000 001 010 0110 0111哈夫曼的编码保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；同时缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码；特点：1、哈夫曼编码并非是唯一的。1)每次对信源缩减时候，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼编码，但是不会影响码字的长度。2)对信源进行缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时候，这两者在缩减信源中进行概率排序，其位置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样获得较小的码方差。2、为了得到方差最小的码，应使合并的符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。3、一般情况下，huffman编码的效率是相当高，但是应当注意，要达到很高的效率仍然需要按照长序列来计算，这样才能使平均码字长度降低。