信息论与编码实验报告

1、实验一 关于硬币称重问题的探讨一、问题描述：假设有N个硬币，这N个硬币中或许存在一个特殊的硬币，这个硬币或轻或重，而且在外观上和其他的硬币没什么区别。 现在有一个标准天平，但是无刻 度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻， 或者所有硬 币都是真的。请冋：1) 至少要称多少次才能达到目的；2) 如果N=12是否能在3次之将特殊的硬币找到；如果可以，要怎么称？二、问题分析：对于这个命题，有几处需要注意的地方：1) 特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知；2) 在目的上，不光要找到这只硬币，还要确定它是重还是轻；3) 天平没有刻度，不能记录每次的读数，只能判

2、断是左边重还是右边重，亦 或者是两边平衡；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=

3、2.92< 3所以13只硬币是可以在3次称量中达到 目的的。通过此式，我们还可以计算得到：通过 3次测量而找出异常硬币，N的 最大值为13.2. 方案的提出为了描述方便，我们给这12枚硬币分别编号(1)-(12)。 首先，任选8个比较，如选： 比 1. 若一样重，则假币在(12)中，第二步：比(11)(1) 若一样重，贝U可能的假币为2。贝U第三步：比2a. 若一样重，则没有假币；b. 不一样重，则假币为2：如果(1)>(12)，则假币轻，反之，假币重；(2) 若重，贝U第三步： 比a. 若一样重，则假币为(11)(较轻)b. 不一样重，贝U假币为、中较重者(3) 若轻，贝U第三步

4、： 比a. 若一样重，则假币为(11)(较重)b. 不一样重，贝M假币为、中较轻者假币为、中较轻2. 若重，则第二步：比(1) 若一样重，则假币在中，第三步：比者若端较重，则假币在中，第三步：比a. 若一样重，则假币为(较轻)b. 不一样重，则假币为中较重者(3)若端较重，则假币在中，第三步：比a. 若一样重，则假币为(较轻)b. 不一样重，则假币为、中较重者3. 若轻，则与上面类似，第二步：比假币为、中较重比比(1) 若一样重，则假币在中，第三步：比者(2) 若端较轻，则假币在中，第三步：a. 若一样重，则假币为(较重)b. 不一样重，则假币为中较轻者(3) 若端较轻，则假币在中，第三步：a

5、. 若一样重，则假币为(较重)b. 不一样重，则假币为、中较轻者3. 用C语言编程实现上述方案为：#in elude<stdio.h>voidmai n()int i;float a12;for(i=0;i<12;i+)scan f("%f", &ai);if(a0+a1+a2+a3=a4+a5+a6+a7) if(a0+a1+a2=a8+a9+a10)if(a8=a11)prin tf("Thereisnospecialcoin!n");else if(a8>a11)prin tf("There others.

6、n",a11);elseisaspecialcoin :%f(12)andit'slightertha nprin tf("Thereothers.n",a11);isaspecialcoin :%f(12)andit'sheaviertha nelse if(a0+a1+a2>a8+a9+a10)if(a8=a9)prin tf("Thereisa specialcoin :%f(11)andit'slightertha nothers.n",a10);else if(a8>a9) prin tf(&quo

7、t;Thereisaspecialcoin :%f(10)andit'slightertha nothers.n",a9);elseprin tf("Thereisaspecialcoin :%f(9)andit'slightertha nothers.n",a8);elseif(a8=a9)prin tf("Thereisaspecialcoin :%f(11)andit'sheaviertha nothers.n",a10);else if(a8>a9)prin tf("Thereisaspecial

8、coi n:%f(9)andit'sheaviertha nothers.n",a8);elseprin tf("Thereisaspecialcoin :%f(10)andit'sheaviertha nothers.n",a9);else if(a0+a1+a2+a3>a4+a5+a6+a7)if(a0+a2+a5=a1+a4+a8)if(a6=a7)prin tf("Thereisaspecialcoin :%f(4)andit'sheaviertha nothers.n",a3);else if(a6>

9、;a7)prin tf("Thereisaspecialcoi n:%f(8)andit'slightertha nothers.n",a7);elseprin tf("Thereisaspecialcoi n:%f(7)andit'slightertha nothers.n",a6);/else if(a0+a2+a5>a1+a4+a8)if(a0=a2)prin tf("Thereisaspecialcoi n:%f(5)andit'slightertha nothers.n",a4);else if

10、(a0>a2)prin tf("Thereisaspecialcoin:%f(1)andit'sheaviertha nothers.n",a0); elseprin tf("Thereisaspecialcoi n:%f(3)andit'sheaviertha nothers.n",a2);elseif(a1>a8) prin tf("Thereisaspecialcoi n:%f(2)andit'sheaviertha nothers.n",a1);if(a 5<a8)prin tf(&q

11、uot;Thereisaspecialcoin :%f(6)andit'slightertha nothers.n",a5);elseif(a0+a2+a5=a1+a4+a8)if(a6=a7)prin tf("Thereisa specialcoin :%f(4)andit'slightertha nothers.n",a3);else if(a6>a7)prin tf("Thereisa specialcoin :%f(7)andit'sheaviertha nothers.n",a6); elseprin t

12、f("Thereis a special coin: %f(8) and it'sheavier tha nothers.n ",a7);else if(a0+a2+a5<a1+a4+a8)if(a0=a2)prin tf("Thereisaspecialcoi n:%f(5)andit'sheavierothers.n",a4);else if(a0>a2)prin tf("Thereisaspecialcoi n:%f(3)andit'slighterothers.n",a2);elseprin

13、 tf("Thereisaspecialcoin:%f(1)andit'slightertha ntha ntha nothers.n",a0); elseif(a1<a8)prin tf("There others.n",a1);if(a5>a8)prin tf("There others.n",a5);isa specialcoi n:%f(2)andit'slightertha nisa specialcoin :%f(6)andit'sheaviertha n运行结果如图：即输入12个数表示

14、这12枚硬币的重量，最后输出哪一枚为假币，并判断其轻重。四、实验总结本次实验首先用信息熵的角度对实验进行了理论分析，即理论上要将假币找出，即消除事件的不确定度，只需要3次即可。然后又通过实际的称重情况对如 何使用3次来称出硬币进行了分类讨论。最后附上的 C语言程序则是对实际称重 过程的描述。通过本次实验，我对信息熵的理解更深入了，即要要想得到一个事件最终结 果，即消除其不确定度便可以实现。通过这样的理解，对于信息熵在实际生活 中的应用也得到了拓展。实验二信道容量的迭代算、实验目的(1) 进一步熟悉信道容量的迭代算法。(2) 学习如何将复杂的公式转化为程序。(3) 掌握C语言数值计算程序的设计和

15、调试技术。二、实验原理1. 算法如下记 P(yjlx)Pij ， p(xi) Pi， P(x|yi)ji i=1,2.r;j=1,2.s初始化信源分布P(0)(皿卩:卩山)，置迭代计数器k=0,设信道容量相对误差门限为3,5>0;(ik)(k)Pij Pi(k)Pj Pii(kPi(1)expPj InjexpPj In 律j C(k 1)lnexppj ln (ik)i如果C(k1)C(k1)C(k)C(k1),转向 置迭代序号k+1知转向 输出P()(k °的结果和C(k1)的结果 停止2. 算法流程图如下- -t-cm十k町=M F訓亿网fCrn + Lh) - ln(

16、mux i三、实验容1. 令pelpe2 0.1和pel pe2 0.01，分别计算该对称信道的信道容量和最佳分布；2. 令pel0.15，pe2 0.1和pel 0.075pe20.01，分别计算该信道的信道容量和最佳分布；信道容量是信息传输率的极限，当信息传输率小于信道容量时， 通过信道编码，能够实现几乎无失真的数据传输；当数据分布满足最佳分布时， 实现信源与信道的匹配，使得信息传输率能够达到信道容量。本实验利用信道容 量的迭代算法，使用计算机完成信道容量的计算。四、实验程序如下#in clude<stdio.h>#in clude<math.h>int mai n

17、()double Pe1,Pe2,Pa1_=0,Pa2_=0; double b1a1,b2a1,b1a2,b2a2;double Pa1=0,Pa2=0;double l=0,max=0;平均互信息量，最大平均互信息量int coun t=0;printf("输入信道容量参数 Pe1： ");scanf("%lf",&Pe1);printf("输入信道容量参数 Pe2： ");scanf("%lf",&Pe2);printf(”信道容量参数： Pe1=%lf Pe2=%fn",Pe1,P

18、e2);b1a1=1-Pe1;b2a1=Pe1;b1a2=Pe2;b2a2=1-Pe2;for(Pa 仁0.01;Pa1<=1;Pa仁Pa1+0.01) Pa2=1-Pa1;coun t=co un t+1;l=Pa1*b1a1*( log( b1a1/(Pa1*b1a1+Pa2*b1a2) )/log(2)+Pa1*b2a1*( log(b2a1/(Pa1*b2a1+Pa2*b2a2) )/log(2)+Pa2*b1a2*( log(b1a2/(Pa1*b1a1+Pa2*b1a2) )/log(2)+Pa2*b2a2*( log(b2a2/(Pa1*b2a1+Pa2*b2a2) )/l

19、og(2);prin tf("%10lf",l);if (I>max)max=I;Pa1_=Pa1,Pa2_=Pa2;elsecon ti nue;prin tf("n");prin tf("一共计算机了：%dn",cou nt);prin tf("最大互信息量为：%lfn",max);printf(”最大互信息量的P(a1)=%lf;P(a2)=%lfn",Pa1_,Pa2_);五、实验结果如图1.Pe仁Pe2=0.1,计算结果如图:0.1747990.355丄3 M-4嗽怡 0.4703170.

20、C1245SU-b2434b0-494501fl_429 加O.Z448600-0939020.228273 (J.34b437 0.430983 8.489B4CB.5219370.S1S994B.47&95R0.4122950.3193290.1932(40-2911720.4632740_52?34£U_5Zb38J0.4995£70_447961O.26M610-115243S.S93902 0.244868M.dbVAl0.43V683U.494010.S24346K).302bfa0.5124G80.-4703178.4022950.3055130.17

21、4798O_L12430.260061U. 3695850.447961«.5£63aaS.508543O.4fi32740.391980.a?11728-1556580.1559170.276293M.3SU94S0.455S230.5342470.52B9480.53424?fl.483?0.390948B.2762930.13581?a.1932540.3193290.4122?5 0.4M9 彊 0.5159740.521937R.4GB4£0.4309330.3454370.228273B. 071755二共计算机了lASSIWPel： 0.1iAi=*

22、m容量参敎P也 0.1：=Pel =0.100600 Pe2=0-ifl0AM 0.0d®7&?0.211081(d.3326340.42185G6.4832000.S1?1530.5191S30.4R320Q0.421BSG0.3326340.211Q810.H4S75?991 ； 8.531064 ?<41> =U .btJULMU ； <a2 J =M.bUdkJUM Press an key to cont inue2.Pe仁Pe2=0.01计算结果如图:Pei-0.01 neen蔺00Press any key to continue寻直吝星势数“

23、丄：乩0丄岂道資墓寥数她：0-010.111C89S.1CS7410.20219(&.2426C90.99OCM0.21E4340.903130.3S247O0.4130610.4422110.470026H.4965960.5Z1996Q.54B2910.569539w.byivsy8-(13086(J.6J347UH.65Zy74U_b71b310.6S4b¥7K513H.722?«y8.7313140.7531100.767195H.7805840.7932920.8K3330.8174600.a75&9e.»470&G8.8CG92

24、CU.S64190&.8718540.97V926Q.884110.8913150.0966430.?0±398B.9055850.5092000.9122CS0.914769Q.0u.vieyjuO.91B930M.皿酣ifM.91fc?ll0.91476?(J.yiiikbau9,9055950.?0tL390«.896£43H.S913158.885411B.67S92£0-8716540.864198BtSS592£0.S4?BSB.83Wt9e.fi274£BBfl.RK3?0_79339!(1_7ftKfl4a.7

25、G71?50.9E31100.7383140.7227800.7QGG13Q.GS94G90.6716010_G£2?740.6334700.6丄孑0.5?丄7找宁0.565390.54G2910.5il?6S.4965960.4700260.4422L14130618.3824700.35B313-316434B.2SB63A0.2436698.232196R.15S7410.111SS9B.AS9S23二共计算机了;. 99”乍？X 0.919267E 军 ij al> =0.bUUWM;V<&2=«.bUtiDUU3. Pe1=0.15, Pe2=

26、0.1时的计算结果如图:0.O82S090.215575 U. 314114B.3847410.4309728.454040B.-<1574770.-439272 vi.AfmGafi 8.338089 0.2541S9 0.1429100.1G1&1&0.22594 U.324JV/ B.391001 Q.4芻 29 0.456J24 H.4bbJ3?«.43552« a.i92bia 9.38903 0.217B2B.1367190_137207Q_25bll2W_3436jy0.4046030.4424G90.45920?0.453BBf0.42

27、7852H_37?72a Q_313804 0_215761 0-0934140.1tfl739 0.243102U.3J42170.37848? 0.43S9SV B.4574700,431455Q.29AS470.33009?0.2£6?850.110425B.0O2S4 a.20丄027 (J.3H3417B.3773028.42&44S0.453041B4426*8».4H&1QR0.3427?78.2661250.158412 fl.019«630.1C404G0.268637H_JS2bb2 0.410753 0.44Ctl?B.456

28、777 U .45IW7V 0.422318 fl.72279 0.29920 0.ZQ2LS1 0.075B71信道容量參0.0Q192C 0.丄7&292 k*.2HUby B«3fil2B3 0.41341 0.446427 W.4bS!?41 0.44854B B.41725B 0.3G44G? 0.ZBS&1?0.1B?9?7RrflG77?二共计算机了道容星夢数05 道容童寥数2： 0-1：=Pel =0.150600 Pe2=0Jfl0ftftfi0.0438090.18593GU.2y22'/H0.369478G.421C72e.HsaaLB.

29、45S77H0.445777G.411S470：咗的苗0.2776860.1734370.B3911599、；8-458-1 丄 JPCal> =U.费BLMU；P32 J =M.blUk)UUPress an* key to cont inue4.Pe1=0.075,Pe2=0.01时的计算结果如下:f _工-w-wk-哥'E:字刁试三下信思诲与篦咼傻辭匡和佶追实Debug>charmel.wffi”亠-同夢賁攵PeJL： 0.075 参教Pe斷P-01：Fe1 =A.075G0B P蛇詡”刖0加tfia.m930B.3625B68.K32918fl.£48225G.7215840.75924BB.7b4J¥B0.7383810.81121B.E9109C0.464663B.3956760.H69149990.140C770.3876$3W.b4yybbB.6S9S190.72S1S70.761G270.7b2«39B.732949A.£717090.G773SG O.446255 8.270937 R.