信息论与编码实验报告

实验一 关于硬币称重问题的探讨一、问题描述：假设有N 个硬币，这N 个硬币中或许存在一个特殊的硬币，这个硬币或轻或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问：1）至少要称多少次才能达到目的；2）如果N=12，是否能在3 次之内将特殊的硬币找到；如果可以，要怎么称？二、问题分析：对于这个命题，有几处需要注意的地方：1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知；2）在目的上，不光要找到这只硬币，还要确定它是重还是轻；3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡；4）最多只能称3 次。三、解决方案：1.关于可行性的分析在这里，我们把称量的过程看成一种信息的获取过程。对于N 个硬币，他们可能的情况为2N+1 种，即重（N 种），轻（N 种）或者无假币（1 种）。由于这2N+1 种情况是等概率的，这个事件的不确定度为：Y=Log(2N+1)对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。每一次称量只有3 种情况：左边重，右边重，平衡。这3 种情况也是等概率的，所以他所提供的信息量为：y=Log3在K 次测量中，要将事件的不确定度完全消除，所以K= Log(2N+1)/ Log3根据上式，当N=12 时，K= 2.92(12)，则假币轻，反之，假币重； (2)若重，则第三步： 比 a.若一样重，则假币为（较轻） b.不一样重，则假币为、中较重者 (3)若轻，则第三步： 比 a.若一样重，则假币为（较重） b.不一样重，则假币为、中较轻者 2.若重，则第二步： 比 (1)若一样重，则假币在中，第三步： 比 假币为、中较轻者 (2)若端较重，则假币在中，第三步：比 a.若一样重，则假币为（较轻） b.不一样重，则假币为中较重者 (3)若端较重，则假币在中，第三步： 比 a.若一样重，则假币为（较轻） b.不一样重，则假币为、中较重者 3.若轻，则与上面类似，第二步：比 (1)若一样重，则假币在中，第三步： 比 假币为、中较重者 (2)若端较轻，则假币在中，第三步： 比 a.若一样重，则假币为（较重） b.不一样重，则假币为中较轻者 (3)若端较轻，则假币在中，第三步： 比 a.若一样重，则假币为（较重） b.不一样重，则假币为、中较轻者3.用C语言编程实现上述方案为：#includevoidmain()inti;floata12;for(i=0;ia11)printf(Thereisaspecialcoin:%f(12)anditslighterthanothers.n,a11);elseprintf(Thereisaspecialcoin:%f(12)anditsheavierthanothers.n,a11);elseif(a0+a1+a2a8+a9+a10)if(a8=a9)printf(Thereisaspecialcoin:%f(11)anditslighterthanothers.n,a10); elseif(a8a9)printf(Thereisaspecialcoin:%f(10)anditslighterthanothers.n,a9);elseprintf(Thereisaspecialcoin:%f(9)anditslighterthanothers.n,a8);elseif(a8=a9)printf(Thereisaspecialcoin:%f(11)anditsheavierthanothers.n,a10);elseif(a8a9)printf(Thereisaspecialcoin:%f(9)anditsheavierthanothers.n,a8);elseprintf(Thereisaspecialcoin:%f(10)anditsheavierthanothers.n,a9);elseif(a0+a1+a2+a3a4+a5+a6+a7)if(a0+a2+a5=a1+a4+a8)if(a6=a7)printf(Thereisaspecialcoin:%f(4)anditsheavierthanothers.n,a3);elseif(a6a7)printf(Thereisaspecialcoin:%f(8)anditslighterthanothers.n,a7);elseprintf(Thereisaspecialcoin:%f(7)anditslighterthanothers.n,a6);elseif(a0+a2+a5a1+a4+a8)if(a0=a2)printf(Thereisaspecialcoin:%f(5)anditslighterthanothers.n,a4);elseif(a0a2)printf(Thereisaspecialcoin:%f(1)anditsheavierthanothers.n,a0);elseprintf(Thereisaspecialcoin:%f(3)anditsheavierthanothers.n,a2);elseif(a1a8)printf(Thereisaspecialcoin:%f(2)anditsheavierthanothers.n,a1);if(a5a7)printf(Thereisaspecialcoin:%f(7)anditsheavierthanothers.n,a6);else printf(Thereisaspecialcoin:%f(8)anditsheavierthanothers.n,a7);elseif(a0+a2+a5a2)printf(Thereisaspecialcoin:%f(3)anditslighterthanothers.n,a2);elseprintf(Thereisaspecialcoin:%f(1)anditslighterthanothers.n,a0);else if(a1a8)printf(Thereisaspecialcoin:%f(6)anditsheavierthanothers.n,a5); 运行结果如图：即输入12个数表示这12枚硬币的重量，最后输出哪一枚为假币，并判断其轻重。四、实验总结本次实验首先用信息熵的角度对实验进行了理论分析，即理论上要将假币找出，即消除事件的不确定度，只需要3次即可。然后又通过实际的称重情况对如何使用3次来称出硬币进行了分类讨论。最后附上的C语言程序则是对实际称重过程的描述。通过本次实验，我对信息熵的理解更深入了，即要要想得到一个事件最终结果，即消除其不确定度便可以实现。通过这样的理解，对于信息熵在实际生活中的应用也得到了拓展。实验二 信道容量的迭代算一、实验目的（1）进一步熟悉信道容量的迭代算法。（2）学习如何将复杂的公式转化为程序。（3）掌握C语言数值计算程序的设计和调试技术。二、实验原理1.算法如下记 ， i=1,2.r;j=1,2.s 初始化信源分布，置迭代计数器k=0，设信道容量相对误差门限为，0;如果，转向置迭代序号k+1 k,转向输出的结果和的结果停止2.算法流程图如下三、实验内容1 令pe1=pe2=0.1和pe1=pe2=0.01，分别计算该对称信道的信道容量和最佳分布；2 令pe1=0.15，pe2=0.1和pe1=0.075pe2=0.01，分别计算该信道的信道容量和最佳分布；信道容量是信息传输率的极限，当信息传输率小于信道容量时，通过信道编码，能够实现几乎无失真的数据传输；当数据分布满足最佳分布时，实现信源与信道的匹配，使得信息传输率能够达到信道容量。本实验利用信道容量的迭代算法，使用计算机完成信道容量的计算。四、实验程序如下#include#includeint main()double Pe1,Pe2,Pa1_=0,Pa2_=0; double b1a1,b2a1,b1a2,b2a2;double Pa1=0,Pa2=0;double I=0,max=0;/平均互信息量,最大平均互信息量int count=0;printf(输入信道容量参数Pe1：);scanf(%lf,&Pe1);printf(输入信道容量参数Pe2：);scanf(%lf,&Pe2);printf(信道容量参数：Pe1=%lf Pe2=%fn,Pe1,Pe2);b1a1=1-Pe1;b2a1=Pe1;b1a2=Pe2;b2a2=1-Pe2;for(Pa1=0.01;Pa1max)max=I;Pa1_=Pa1,Pa2_=Pa2;elsecontinue;printf(n);printf( 一共计算机了：%dn,count);printf( 最大互信息量为：%lfn,max);printf( 最大互信息量的P(a1)=%lf;P(a2)=%lfn,Pa1_,Pa2_);五、实验结果如图1.Pe1=Pe2=0.1,计算结果如图：2.Pe1=Pe2=0.01计算结果如图：3. Pe1=0.15，Pe2=0.1时的计算结果如图：4.Pe1=0.075,Pe2=0.01时的计算结果如下：六、实验总结本次实验通过信道容量迭代算法