信息論與編碼實驗報告

1、實驗一 關于硬幣稱重問題的探討一、問題描述：假設有N個硬幣，這N個硬幣中或許存在一個特殊的硬幣，這個硬幣或輕或重，而且在外觀上和其他的硬幣沒什么區(qū)別。 現(xiàn)在有一個標準天平，但是無刻 度?，F(xiàn)在要找出這個硬幣，并且知道它到底是比真的硬幣重還是輕， 或者所有硬 幣都是真的。請冋：1) 至少要稱多少次才能達到目的；2) 如果N=12是否能在3次之將特殊的硬幣找到；如果可以，要怎么稱？二、問題分析：對于這個命題，有幾處需要注意的地方：1) 特殊的硬幣可能存在，但也可能不存在，即使存在，其或輕或重未知；2) 在目的上，不光要找到這只硬幣，還要確定它是重還是輕；3) 天平?jīng)]有刻度，不能記錄每次的讀數(shù)，只能判

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根據(jù)上式，當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語言編程實現(xiàn)上述方案為：#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個數(shù)表示

14、這12枚硬幣的重量，最后輸出哪一枚為假幣，并判斷其輕重。四、實驗總結本次實驗首先用信息熵的角度對實驗進行了理論分析，即理論上要將假幣找出，即消除事件的不確定度，只需要3次即可。然后又通過實際的稱重情況對如 何使用3次來稱出硬幣進行了分類討論。最后附上的 C語言程序則是對實際稱重 過程的描述。通過本次實驗，我對信息熵的理解更深入了，即要要想得到一個事件最終結 果，即消除其不確定度便可以實現(xiàn)。通過這樣的理解，對于信息熵在實際生活 中的應用也得到了拓展。實驗二信道容量的迭代算、實驗目的(1) 進一步熟悉信道容量的迭代算法。(2) 學習如何將復雜的公式轉化為程序。(3) 掌握C語言數(shù)值計算程序的設計和

15、調(diào)試技術。二、實驗原理1. 算法如下記 P(yjlx)Pij ， p(xi) Pi， P(x|yi)ji i=1,2.r;j=1,2.s初始化信源分布P(0)(皿卩:卩山)，置迭代計數(shù)器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訓億網(wǎng)fCrn + Lh) - ln(

16、mux i三、實驗容1. 令pelpe2 0.1和pel pe2 0.01，分別計算該對稱信道的信道容量和最佳分布；2. 令pel0.15，pe2 0.1和pel 0.075pe20.01，分別計算該信道的信道容量和最佳分布；信道容量是信息傳輸率的極限，當信息傳輸率小于信道容量時， 通過信道編碼，能夠實現(xiàn)幾乎無失真的數(shù)據(jù)傳輸；當數(shù)據(jù)分布滿足最佳分布時， 實現(xiàn)信源與信道的匹配，使得信息傳輸率能夠達到信道容量。本實驗利用信道容 量的迭代算法，使用計算機完成信道容量的計算。四、實驗程序如下#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("輸入信道容量參數(shù) Pe1： ");scanf("%lf",&Pe1);printf("輸入信道容量參數(shù) Pe2： ");scanf("%lf",&Pe2);printf(”信道容量參數(shù)： 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尋直吝星勢數(shù)“

23、丄：乩0丄豈道資墓寥數(shù)她：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?二共計算機了道容星夢數(shù)05 道容童寥數(shù)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.