信息论与编码实验报告

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= 2.92(

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

4、者(2)若端较轻，则假币在中，第三步：比a.若一样重，则假币为(较重)b.不一样重，则假币为中较轻者(3)若端较轻，则假币在中，第三步：比a.若一样重，则假币为(较重)b.不一样重，则假币为、中较轻者3.用c言编程实现上述方案为:#include void main()int i;float a12;for(i=0;ia11)printf(thereisa specialcoin:%f(12)others.n,a11); elseprintf(there is a special coin:%f(12) others.n,a11);else if(a0+a1+a2a8+a9+a10)if(a8

5、=a9)printf(thereisaspecialcoin:%f(11)anditslighterthanothers.n,a10);else if(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);else if(a8a9)

6、printf(thereisaspecialcoin:%f(9)anditsheavierthanothers.n,a8);elseprintf(thereisaspecialcoin:%f(10)anditsheavierthanothers.n,a9);else if(a0+a1+a2+a3a4+a5+a6+a7)if(a0+a2+a5=a1+a4+a8)if(a6=a7)printf(thereisaspecialcoin:%f(4)anditsheavierthanothers.n,a3);else if(a6a7)printf(thereisaspecialcoin:%f(8)and

7、itslighterthanothers.n,a7);elseprintf(thereisaspecialcoin:%f(7)anditslighterthanothers.n,a6);else if(a0+a2+a5a1+a4+a8)if(a0=a2)printf(thereisaspecialcoin:%f(5)anditslighterthanothers.n,a4);else if(a0a2)printf(thereisaspecialcoin:%f(1)anditsheavierthanothers.n,a0); elseprintf(thereisaspecialcoin:%f(3

8、)others.n,a2);elseif(a1a8)printf(thereisaspecialcoin:%f(2)others.n,a1);if(a5a7) printf(there is a special coin:%f(7) others.n,a6); elseand its lighter thanand its heavier thanprintf(thereis a special coin:%f(8) and itsheavier than othersif(a1a2) printf(thereisaspecialothers.n,a2);elseprintf(thereisa

9、specialothers.n,a0);coin:%f(5)anditsheavierthancoin:%f(3)anditslighterthancoin:%f(1)anditslighterthan elseand itsits heavier thanprintf(there is a special coin:%f(2) others.n,a1); if(a5a8)printf(there is a special coin:%f(6) and others.n,a5); 即输入12个数表示这12枚硬币的重量，最后输出哪一枚为假币，并判断其轻重四、实验总结本次实验首先用信息嫡的角度对实

10、验进行了理论分析，即理论上要将假币找出，即消除事件的不确定度，只需要3次即可。然后又通过实际的称重情况对如 何使用3次来称出硬币进行了分类讨论。最后附上的 c语言程序则是对实际称重 过程的描述。通过本次实验，我对信息嫡的理解更深入了，即要要想得到一个事件最终结 果，即消除其不确定度便可以实现。通过这样的理解，对于信息嫡在实际生活 中的应用也得到了拓展。实验二信道容量的迭代算一、实验目的(1)进一步熟悉信道容量的迭代算法。(2)学习如何将复杂的公式转化为程序。(3)掌握c语言数值计算程序的设计和调试技术。二、实验原理1.算法如下记 p(%|x)pij , p(xi) pi, p(xi |yi)

11、jii=1,2r；j=1,2s初始化信源分布p(0)(p1,p2.pipr),置迭代计数器k=0,设信道容量相对误差门限为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)置迭代序号k+1f转向 输出p(xi)(k 1)的结果和c(k1)的结果停止2.算法流程图如下三、实验内容1 .令pel pe2 0.1和pel pe2 0.01 ,分别计算该对称信道的信道容量和最佳2 .令pel 0.15, pe2 0.1和pel 0.075pe2 0.01 ,分别计

12、算该信道的信道容量 和最佳分布；信道容量是信息传输率的极限，当信息传输率小于信道容量时，通 过信道编码，能够实现几乎无失真的数据传输；当数据分布满足最佳分布时，实 现信源与信道的匹配，使得信息传输率能够达到信道容量。本实验利用信道容量 的迭代算法，使用计算机完成信道容量的计算。四、实验程序如下#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

13、(输入信道容量参数 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)=

14、%lfn,pa1_,pa2_);五、实验结果如图1.pe1=pe2=0.1,计算结果如图:节:学习三下,信息论与若吊傻松犀子，信富买差口由u寸二匕“ 4 f蚱共计算机了an*093902 244868 jb7al43v683 494e01 s2434647031? 402295 305513 17479s13ss17 276293 3h的铀455s23 534247 5253424? 4k833 3sb948 2762?3 13581?o-lgegst 0-2?u72 tl3lk48 0.463274 0.6bse43 0.529342 m-bzbjsj 0.4995670.jcpe85 0-

15、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 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.

16、47&95r a.412295 0.319329 a.19324 r.0248580.0dg7 0.211081 8-332634q.483200 0.s1?153 u.531uo4 0.519153m.4r320q0.332634 8.2110s1 0.h475?谡鳄0.1932&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计算结果如图:节门学习、大

17、三下信息论与输询快建i鹉序信迨阴邕。ubugkw in n elexe?cslstpel： 0.01次l相道百黄参数pe2： 0.01：pel =0.a10g00 p史2=g.日10的圃信道容量参圜0.0&9s230.3s247ow.btflvmy0.7383140.2?em0.096643u.91svju8.9055 晅a.tgtle h. 63347电 9.442211 fl.158741二共计算机了 990.3bo3fi 0.5z19?6 0.6b4b9 0.8k333 0.87s926 0.9l4769 曰 t147b b.67s926q.gs94g9 0.5il?6 0.230636

18、0-919267息量 tfjpcal =u. bmuwh; foz)=.butik)u(dpress any key to continue0.111cs9 0.413061 8-(13086 0.753110 0，847酌 0.?0398 修.工加， b.?0tl390 0.s47bs.tc3110 0.613886 0.413061 6.111589s.1cs741 0.442211 (j.6j347u b.767195 8.8cg92c b.905585 0.v1b93w .89643 0.83wt9 0.738314 0.5t1787s.3s247q a.0e95230.2o219g

19、0.47&0z6 0.65274 h.780584 u.s64190 0.5092000.891315 e.fi274b 0.722780 0.56539 0.35b3130.2426c9 .496596 u.b71t31 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.5

20、69535 0-?22?8h 0.82746u 0.891315 b_918b?8 u.vavkhh 0.864198 fl.78fks4 b-g52s74 s-470026 0.221963. pe1=0.15, pe2=0.1时的计算结果如图:共计算机了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

21、b.266125 0.158412 0.0198fc30.1tfl739 s.243102 u.3j4217 0.37848? 0.43s9sv b.457470 t454876 0,431455 q.29as47 0.330097 0.26?85 b.110425pel-0.l!；0q0fl f2=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-292278 0.j69478 g.421c72 e.4599

22、01 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 u.45w77v 0.422316 fl.72279 b

23、.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时的计算结果如下:二共计算机了;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 0.476595 m.lkl3hb 0/9鸣丽 0.74907 0.7g615i 0-75176s 0.70&317 q_29fl6! 0_51g?7j 0_364808 0.16237?8.3口 0.456271 0.623676o.?hb