信息論與編碼實(shí)驗(yàn)報(bào)告

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

2、邊重還是右邊重，亦或者是兩邊平衡；4)最多只能稱3次。三、解決方案：1 .關(guān)于可行性的分析在這里，我們把稱量的過(guò)程看成一種信息的獲取過(guò)程。對(duì)于 N個(gè)硬幣，他們可能的情況為2N+1種，即重(N種)，輕(N種)或者無(wú)假幣(1種)。由于這2N+1種情況是等概率的，這個(gè)事件的不確定度為：Y=Log(2N+1)對(duì)于稱量的過(guò)程，其實(shí)也是信息的獲取過(guò)程，一是不確定度逐步消除的過(guò)程。每一次稱量只有3種情況：左邊重，右邊重，平衡。這 3種情況也是等概率的， 所以他所提供的信息量為：y=Log3在K次測(cè)量中，要將事件的不確定度完全消除，所以K= Log(2N+1)/Log3根據(jù)上式，當(dāng)N=12時(shí)，K= 2.92&

3、lt; 3所以13只硬幣是可以在3次稱量中達(dá)到目的的。通過(guò)此式，我們還可以計(jì)算得到：通過(guò) 3次測(cè)量而找出異常硬幣，N的 最大值為13.2 .方案的提出為了描述方便，我們給這12枚硬幣分別編號(hào)(1)-(12) o首先，任選8個(gè)比較，如選： 比 1 .若一樣重，則假幣在中，第二步：比(1)若一樣重，則可能的假幣為。則第三步：比a.若一樣重，則沒(méi)有假幣；b.不一樣重，則假幣為：如果(1)>(12),則假幣輕，反之,假幣重；(2)若重，則第三步：比(10)a.若一樣重，則假幣為(11)(較輕)b.不一樣重，則假幣為、中較重者(3)若輕，則第三步：比a.若一樣重，則假幣為(11)(較重)b.不一樣

4、重，則假幣為、中較輕者2 .若重，則第二步： 比(1)若一樣重，則假幣在中，第三步：比 假幣為、中較輕者(2)若端較重，則假幣在中，第三步：比a.若一樣重，則假幣為(較輕)b.不一樣重，則假幣為中較重者(3)若端較重，則假幣在中，第三步： 比a.若一樣重，則假幣為(較輕)b.不一樣重，則假幣為、中較重者3 .若輕，則與上面類似，第二步：比假幣為、中較重(1)若一樣重，則假幣在中，第三步： 比者(2)若端較輕，則假幣在中，第三步：比a.若一樣重，則假幣為(較重)b.不一樣重，則假幣為中較輕者(3)若端較輕，則假幣在中，第三步：比a.若一樣重，則假幣為(較重)b.不一樣重，則假幣為、中較輕者3.用

5、C®言編程實(shí)現(xiàn)上述方案為:#include <stdio.h> void main()int i;float a12;for(i=0;i<12;i+) scanf("%f",&ai);if(a0+a1+a2+a3=a4+a5+a6+a7) if(a0+a1+a2=a8+a9+a10) if(a8=a11)printf("Thereisno specialcoin!n");and it's lighter thanand it's heavier thanelse if(a8>a11)printf(

6、"Thereisa specialcoin:%f(12)others.n",a11); elseprintf("There is a special coin:%f(12) others.n",a11);else if(a0+a1+a2>a8+a9+a10)if(a8=a9)printf("Thereisaspecialcoin:%f(11)andit'slighterthanothers.n",a10);else if(a8>a9)printf("Thereisaspecialcoin:%f(10)an

7、dit'slighterthanothers.n",a9);elseprintf("Thereisaspecialcoin:%f(9)andit'slighterthanothers.n",a8);elseif(a8=a9)printf("Thereisaspecialcoin:%f(11)andit'sheavierthanothers.n",a10);else if(a8>a9)printf("Thereisaspecialcoin:%f(9)andit'sheavierthanothers.

8、n",a8);elseprintf("Thereisaspecialcoin:%f(10)andit'sheavierthanothers.n",a9);else if(a0+a1+a2+a3>a4+a5+a6+a7)if(a0+a2+a5=a1+a4+a8)if(a6=a7)printf("Thereisaspecialcoin:%f(4)andit'sheavierthanothers.n",a3);else if(a6>a7)printf("Thereisaspecialcoin:%f(8)andit

9、'slighterthanothers.n",a7);elseprintf("Thereisaspecialcoin:%f(7)andit'slighterthanothers.n",a6);else if(a0+a2+a5>a1+a4+a8)if(a0=a2)printf("Thereisaspecialcoin:%f(5)andit'slighterthanothers.n",a4);else if(a0>a2)printf("Thereisaspecialcoin:%f(1)andit'

10、;sheavierthanothers.n",a0); elseprintf("Thereisaspecialcoin:%f(3)others.n",a2);elseif(a1>a8)printf("Thereisaspecialcoin:%f(2)others.n",a1);if(a5<a8)printf("Thereisaspecialcoin:%f(6)and it's heavier thanand it's heavier thanand it's lighter thanothers.n

11、",a5); else if(a0+a2+a5=a1+a4+a8)if(a6=a7)printf("There is a special coin:%f(4) others.n",a3);else if(a6>a7) printf("There is a special coin:%f(7) others.n",a6); elseand it's lighter thanand it's heavier thanprintf("Thereis a special coin:%f(8) and it'she

12、avier than othersif(a1<a8).n",a7);elseif(a0+a2+a5卜a1+a4+a8)if(a0=a2) printf("Thereisaspecialothers.n",a4);else if(a0>a2) printf("Thereisaspecialothers.n",a2);elseprintf("Thereisaspecialothers.n",a0);coin:%f(5)andit'sheavierthancoin:%f(3)andit'slighter

13、thancoin:%f(1)andit'slighterthan elseand it'sit's heavier thanprintf("There is a special coin:%f(2) others.n",a1); if(a5>a8)printf("There is a special coin:%f(6) and others.n",a5); 即輸入12個(gè)數(shù)表示這12枚硬幣的重量，最后輸出哪一枚為假幣，并判斷其輕重四、實(shí)驗(yàn)總結(jié)本次實(shí)驗(yàn)首先用信息嫡的角度對(duì)實(shí)驗(yàn)進(jìn)行了理論分析，即理論上要將假幣找出，即消除事件的不

14、確定度，只需要3次即可。然后又通過(guò)實(shí)際的稱重情況對(duì)如 何使用3次來(lái)稱出硬幣進(jìn)行了分類討論。最后附上的 C語(yǔ)言程序則是對(duì)實(shí)際稱重 過(guò)程的描述。通過(guò)本次實(shí)驗(yàn)，我對(duì)信息嫡的理解更深入了，即要要想得到一個(gè)事件最終結(jié) 果，即消除其不確定度便可以實(shí)現(xiàn)。通過(guò)這樣的理解，對(duì)于信息嫡在實(shí)際生活 中的應(yīng)用也得到了拓展。實(shí)驗(yàn)二信道容量的迭代算一、實(shí)驗(yàn)?zāi)康?1)進(jìn)一步熟悉信道容量的迭代算法。(2)學(xué)習(xí)如何將復(fù)雜的公式轉(zhuǎn)化為程序。(3)掌握C語(yǔ)言數(shù)值計(jì)算程序的設(shè)計(jì)和調(diào)試技術(shù)。二、實(shí)驗(yàn)原理1.算法如下記 P(%|X)Pij , p(xi) pi, p(xi |yi) jii=1,2r；j=1,2s初始化信源分布P(0)(

15、P1,P2.PiPr),置迭代計(jì)數(shù)器k=0,設(shè)信道容量相對(duì)誤差門(mén)限為S, 5 >0；(k)(k)Pij Pi(k)Rj Pi(kPi1)exPPj In jik)exPPj In; C(k1) ln exppj ln如果c(k1)C(k1) C(k)(k 1)置迭代序號(hào)k+1f>轉(zhuǎn)向 輸出p(xi)(k 1)的結(jié)果和C(k1)的結(jié)果停止2.算法流程圖如下三、實(shí)驗(yàn)內(nèi)容1 .令pel pe2 0.1和pel pe2 0.01 ,分別計(jì)算該對(duì)稱信道的信道容量和最佳2 .令pel 0.15, pe2 0.1和pel 0.075pe2 0.01 ,分別計(jì)算該信道的信道容量 和最佳分布；信道容

16、量是信息傳輸率的極限，當(dāng)信息傳輸率小于信道容量時(shí)，通 過(guò)信道編碼，能夠?qū)崿F(xiàn)幾乎無(wú)失真的數(shù)據(jù)傳輸；當(dāng)數(shù)據(jù)分布滿足最佳分布時(shí)，實(shí) 現(xiàn)信源與信道的匹配，使得信息傳輸率能夠達(dá)到信道容量。本實(shí)驗(yàn)利用信道容量 的迭代算法，使用計(jì)算機(jī)完成信道容量的計(jì)算。四、實(shí)驗(yàn)程序如下#include<stdio.h>#include<math.h>int main()double Pe1,Pe2,Pa1_=0,Pa2_=0; double b1a1,b2a1,b1a2,b2a2;double Pa1=0,Pa2=0;double I=0,max=0;/平均互信息量，最大平均互信息量int coun

17、t=0;printf("輸入信道容量參數(shù) Pe1： ");scanf("%lf",&Pe1);printf("輸入信道容量參數(shù) Pe2： ");scanf("%lf",&Pe2);printf("信道容量參數(shù)： Pe1=%lf Pe2=%fn",Pe1,Pe2);b1a1=1-Pe1;b2a1=Pe1;b1a2=Pe2;b2a2=1-Pe2;for(Pa1=0.01;Pa1<=1;Pa1=Pa1+0.01) Pa2=1-Pa1;count=count+1;I=Pa1*b1a

18、1*( 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) )/log(2); printf("%10lf",I);if (I>max)max=I;Pa1_=Pa1,Pa2_=Pa2;elsecontinue;printf("n");printf(

19、"一共計(jì)算機(jī)了 ：dn",count);printf("最大互信息、量為:%lfn",max);printf("最大互信息量的P(a1)=%lf;P(a2)=%lfn",Pa1_,Pa2_);五、實(shí)驗(yàn)結(jié)果如圖1.Pe1=Pe2=0.1,計(jì)算結(jié)果如圖:節(jié):'學(xué)習(xí)三下,信息論與若吊傻松犀子，信富買(mǎi)差口由u寸二匕“ 4 f蚱"共計(jì)算機(jī)了an*093902 244868 Jb7'Al43V683 494E01 S2434647031? 402295 305513 17479S13SS17 276293 3H的鈾455

20、S23 534247 5253424? 4K833 3SB948 2762?3 13581?O-lGEGSt 0-2?U72 tL3¥lK48 0.463274 0.6BSE43 0.529342 M-bZbJSJ 0.4995670.JCPE85 0-269A61 0.115243B.11C 243 8.260961 U.369b85 «.447961 B.499EC7 8,521383S.508543 0.4fi3274 O.39198 0.291172 8.155658Pel =0.100600 P/2=UJ 8煙800.174798 0.3O55130.470317

21、 0.C1245S B.53026& U.b2434b 0.494501 H.499&S3 0-3S77E1 O.244860 0.093902B.U917SG 8.22S273 (J.34S437 a.43e9S3 0.4U9Q4C ft.5219370.515994 B.47&95R a.412295 0.319329 a.19324 R.0248580.0d®G7 0.211081 8-332634Q.483200 0.S1?153 U.531UO4 0.519153M.4R320Q0.332634 8.2110S1 0.H4«75?謖鱷0.1

22、932&4 也31y3七y 0.4122?5 0.4796 0.515974a.5219370.43093 0.345437 0.22S273 fl.加i51 ； 8.5310S4JPCal> =M .bUULMU ； P4a 2)=廿 $ 廿卅幽 to continue2.Pe1=Pe2=0.01計(jì)算結(jié)果如圖:節(jié)門(mén)學(xué)習(xí)、大三下信息論與輸詢快建I鵡序信迨陰邕。ubugkW in n eLexe"?CslStPel： 0.01次l相道百黃參數(shù)Pe2： 0.01：Pel =0.A10G00 P史2=g.日10的圃信道容量參圜0.0&9S230.3S247OW.btf

23、lVMy0.7383140.»2?EM0.096643U.91SVJU8.9055 晅a.TGTlE H. 63347電 9.442211 fl.158741二共計(jì)算機(jī)了" 990.3BO£3fi 0.5Z19?6 0.6B4b9 0.8K333 0.87S926 0.9L4769 曰 T147b¥ B.67S926Q.GS94G9 0.5il?6 0.2306360-919267息量 tfjPCal> =U. bMUWH; FOZ)=«.bUtik)U(dPress any key to continue0.111CS9 0.41306

24、1 8-(13086 0.753110 0，847酌£ 0.?0±398 修.¥工¥加， B.?0tL390 0.S47BS.TC3110 0.613886 0.413061 6.111589S.1CS741 0.442211 (J.6J347U B.767195 8.8CG92C B.905585 0.V1B93W «.896£43 0.83Wt9 0.738314 0.5T1787S.3S247Q A.0E95230.2O219G 0.47&0Z6 0.65274 H.780584 U.S64190 0.5092000.8

25、91315 e.fi274£B 0.722780 0.56539 0.35B3130.2426C9 .496596 U.b71t»31 0.793292 8.871854 9.V1226S H.916711B.8SS 4119.7B6513 8.56£?1 B.3164340.316434 0.546291 0.1/K513 O.61G71S Q.885411 0.91G711 (JJ 工EWb8 0.871654 H_79329S 0_671601 0.496596 Q.2426&9O.9&0313 0.569535 0-?22?8H 0.827

26、46U 0.891315 B_918B?8 U.VaVKHH 0.864198 fl.78fKS4 B-G52S74 S-470026 0.221963. Pe1=0.15, Pe2=0.1時(shí)的計(jì)算結(jié)果如圖:共計(jì)算機(jī)了137207 256112 J43fcjy 4B4S09 4424G9 4592B7 45JUB? 427052 379728 313804 215761 093414B.0O2S4 &,201027 (J.3H3417 B.377302 8.42&44S 0.453041 0.458?MB.442GS8 ».4H&1QR 0.3427?7 B.

27、266125 0.158412 0.0198fc30.1tfl739 S.243102 U.3J4217 0.37848? 0.43S9SV B.457470 T454876 0,431455 Q.29AS47 0.330097 0.2£6?85 B.110425Pel-0.l!；0Q0fl F«2=0J0m»).229594 U.324JV/ B.391001 a,435149 0.456J24 H.4bbJ3? «.43552« 0.39210 9.38903 0.217B2 0.12fc?190.043003 B.185436 8-292

28、278 0.J69478 G.421C72 e.459901 B.4ba?YH 0.445777 0.4118470.277686 fe!l. 173437 0.H3911S0.O82S09 0.215575 U.314114 B.384741 0.430972 8.454040 B.-157477 0,-439272 vi.AfmGafi 8.338089 0.2541S9 0.142910；0-4587lJPCaU =U.納(JLMU ；: =M.blUk)UUto continue8.i54346 0.Z6863? U.JS2bb2 0.410?53 B.44Etl7 B.456777

29、U.45W77V 0.422316 fl.72279 B.299G20 O.ZQ2101 0.075B71信道容量蓼 a.aaira &.L7232 H.ZHUb" 8.3C1需53 0.41341 0.446427 W.4bS!?41 0.44854B B.41725B O.3G44G? O.ZBS&l? 0.1B?9?7 R.flG?7?74.Pe1=0.075,Pe2=0.01時(shí)的計(jì)算結(jié)果如下:二共計(jì)算機(jī)了;4069780.2149C9 .4943B1 U.bNlbF?b B.G80224 B.739t71 0.764S日3 H.7bBZby B.72O&1S0.247G92 0.455955 (J.SV63VJ B.6B96I1 0.744627 0.7t576? H.7525H 0,713715 S.A4H3&5 0.532029 0,3眥器6 0.1910630_27Sei»