信息论与编码试卷及答案

1、一、(11)填空题(1)1948年，美国数学家香农 发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。(2 )必然事件的自信息是 0。(3 ) 离散平稳无记忆信源 x的n次扩展信源的嫡等于离散信源 x的嫡的n倍 。(4 ) 对于离散无记忆信源，当信源嫡有最大值时，满足条件为_信源符号等概分布。(5 ) 若一离散无记忆信源的信源嫡h (x)等于2.5,对信源进行等长的无失真二进制编码，则编码长度至少为3。(6 ) 对于香农编码、费诺编码和霍夫曼编码，编码方法惟一的是香农编码。7) 已知某线性分组码的最小汉明距离为3,那么这组码最多能检测出 2 个码元错误，最多能纠正个码元错误。(8 )

2、设有一离散无记忆平稳信道，其信道容量为c,只要待传送的信息传输率 r_小于 c (大于、小于或者等于)，则存在一种编码，当输入序列长度n足够大，使译码错误概率任意小。(9 ) 平均错误概率不仅与信道本身的统计特性有关，还与译码规则 和编码方法_有关二、(9r)判断题(1) 信息就是一种消息。(父)(2 ) 信息论研究的主要问题是在通信系统设计中如何实现信息传输、存储和处理的有效性和可靠性。()(3 ) 概率大的事件自信息量大。(m )(4 ) 互信息量可正、可负亦可为零。()(5 ) 信源剩余度用来衡量信源的相关性程度，信源剩余度大说明信源符号间的依赖关系较小。( )(6) 对于固定的信源分布

3、，平均互信息量是信道传递概率的下凸函数。( )(7) 非奇异码一定是唯一可译码，唯一可译码不一定是非奇异码。(x)(8) 信源变长编码的核心问题是寻找紧致码(或最佳码)，霍夫曼编码方法构造的是最佳码。( i。说明：当信源的符号之间有依赖时，信源输出消息的不确定性减弱。而信源冗余度正是反映信源符号依赖关系的强弱，冗余度越大，依赖关系就越大。（2分）六、（18）.信源空间为xx1x2 x3x4 x5x6 x7八 一工一一一 r i 1=1，试分力1j构造兀香农码和兀霍夫jp（x）_j0.20.190.180.170.150.10.01曼码，计算其平均码长和编码效率（要求有编码过程）信源消息 存号符

4、号概 率(4)累加概 率p,0,20020.190.2%0.180.39%0.170.57程0450*74%0.100.890.010,99log以可)码字长 度l码字232300023930012473r on2631002.743101332411106.6471111110l 八 p(aji =3.14h(x) 2.61r = =0.831l 3.140. 200. 190. 180. 170. 150. 200. 190. 180, 170. 15.0. 260.200. 190. 180.1700, 350. 39 k 61 i/0.26 a 350.39/1 0. 20 1/ 0.

5、 26。j 0. 19 上o.0. 11 aj0. 01 .ul = p(a)l = 2?2i=l码元/符号人吧兄竺1 = 0.96l 2.72信源符号概率以叩码字w,码长l0,2010240491120.18000340,170013%0.150103a60.1001104久0.0101114比特/符号1/2七（6）.设有一离散信道，其信道传递矩阵为1/61/3最大后验概率准则与最大似然译码准则确定译码规则，1/31/21/61/61/31/2一，、1 p（x。4、,一1，并设: p（x2）=1p（x3）=-4试分别按并计算相应的平均错误概率。1） （3分）最小似然译码准则下，有,心* 22

6、） （3分）最大后验概率准则下，有，人110 ）.二元对称信道如图。311）若 p0= , p1 =一，求 hx、h x|y 湘 i x;y ； 44勺 t 2/3 y2 = 1解：1)共6分- 0 8113 加符号h x |y )=0.749bit /符号1x x) = 00616 加”符号2）,c - 0 082 bi f符号（3分）此时输入概率分布为等概率分布。（1分）000111九、（18 ）设一线性分组码具有一致监督矩阵h = 01100110 10 111）求此分组码门=?k=?共有多少码字？2）求此分组码的生成矩阵 go3）写出此分组码的所有码字。4）若接收到码字（101001）

7、,求出伴随式并给出翻译结果。解：1） n=6,k=3,共有8个码字。（3分）2）设码字 c=（c5c4c3c2cle0 ）由 hct=0t 得c2 二 c1 二 c0 =0c45c39c0 = 0c5 c3 $ c1 c0 = 0（3分）令监督位为（c2。1。0）,则有c2 = c5 二 c3c1 = c5 g c4c0 = c4 巳 c3（3分）10 0 1100 10 0 1 1生成矩阵为p 0 1 1 0 11（2分）3）所有码字为 000000, 001101 , 010011, 011110, 100110, 101011,110101, 111000o （4分）s =（1 0 1

8、（2分）该码字在第5位发生错误，（101001）纠正为（101011）,即译码为（101001）（1分）1 .在无失真的信源中， 信源输出由 h4x）一来度量；在有失真的信源中， 信源输出由 rd3来度量。2 .要使通信系统做到传输信息有效、可靠和保密，必须首先 信源编码，然后 加密 编码，再信道编码，最后送入信道。3 .带pm awgn波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是c =wlog(1 +snr);当归一化信道容量 c/w趋近于零时，也即信道完全丧失了通信能力，此时eb/no为-1.6 db,我们将它称作香农限，是一切编码方式所能达到的理论极限。4 .保

9、密系统的密钥量越小，密钥嫡h(k)就越其密文中含有的关于明文的信息量i(m; c)就越大。42.则信息位长度k为3,校验多项式5 .已知n= 7的焉环码g(x)=x +x +x+1,3,h(x)=_xx 16.设输入符号表为 x=0, 1,输出符号表为真函数为 d(0, 0) = d(1, 1) = 0, d(0, 1) =2y=0, 1。输入信号的概率分布为p= (1/2, 1/2),失 ,d(1, 0) = 1,则 dmin = 0, r(dmin)= 1bit/symbol相应的编码器转移概率矩阵p(y/x)=1 0由 ；dmax=0.5 , r(d max) = 0、相应的编码徐f转移

10、概率矩阵p(y/x)= 1 01 1 0,他的秘密密钥(d,n)8 。7.已知用户 a 的 rsa 公开密钥(e,n)=(3,55), p = 5, q = 11，则 1(n) =40=(27,55)。若用户b向用户a发送m=2的加密消息，则该加密后的消息为二、判断题1 .可以用克劳夫特不等式作为唯一可译码存在的判据。( h (x,y (x;y )解：p(x =0) =2/3 p(x = 1 )= 1 / 3p(y=0)=1/3 p(y = 1)= 2/3h x =h y =h(1/3,2/3) =0.918 bit/symbolh x ,y = h (1/3,1/ 3,1/ 3) =1.58

11、5 bit/symboli x;丫 尸h(x) h (y)-h (x,y) =0.251 bit/symbol五、计算题一阶齐次马尔可夫信源消息集x w a1, a2, a3,状态集s ws,，s2，s3,且令si =ai,i =1,2,3 ,条件转移概率为1 4 1 4 1 2111(1)画出该马氏链的状态转移图；p(aj / ) j= 1/3 1/3 1/32/3 1/30(2)计算信源的极限嫡。.叫 + .w2 + 3w3 = w#w1 +w2 + 3w3 = ww1=0.4 |w1+=w2=w3 一1w2=0.3.w3=0.3(w1 + w2 + w3 = 1lh(x|s1)=h(1/

12、4,1/4,1/2)=1.5 比特/符号h(x|s2)=h(1/3,1/3,1/3)=1.585 比特/符号h(x|s3)=h(2/3,1/3)= 0.918 比特/符号h 年=3 wih(x |si )=0.4父1.5+0.3父1.585+0.3父0.918 7.351 比特/符号 i =1六、计算题xxxc若有一信源= 12 i,每秒钟发出2.55个信源符号。：p_0.8 0.2将此信源的输出符号送入某一个二元信道中进行传输(假设信道是无噪无损的，容量为1bit/二元符号)，而信道每秒钟只传递2个二元符号。(1) 试问信源不通过编码(即 x1t0,xa1在信道中传输)(2) 能否直接与信道

13、连接？(3) 若通过适当编码能否在此信道中进行无失真传输？(4) 试构造一种哈夫曼编码(两个符号一起编码)，(5) 使该信源可以在此信道中无失真传输。解：1.不能，此时信源符号通过0, 1在信道中传输，2.55二元符号/s2二元符号/s2.从信息率进行比较，2.55* h (0.8,0.2) = 1.84 1*2可以进行无失真传输3.011100101x1x1x1x2x2x1x2x20.641h 0.640.64010.16 0rl0.加0.160/ * 0.161_4k= rki =0.64 +0.16*2 +0.2*3 =1.56 二元符号/2 个信源符号i 1此时 1.56/2*2.55

14、=1.989 二元符号 /s 0,有ln zwz-1,当且仅当z=1时等式成立。3 .设信源为x=0 , 1, p (0) =1/8,则信源的嫡为_1/8log2 8+7/8log2(7/8)比特/符号,如信源发出由m个“0”和(100-m)个“1”构成的序列，序列的自信息量为 mlog28 + (100 m)log2(7/8) 比特/符号。4 .离散对称信道输入等概率时，输出为 等概 分布。5 .根据码字所含的码元的个数，编码可分为定长 编码和 变长 编码。u u1u2 u3u4u5 u6e 一一弘 l 6 . 设 dms 为 |l=.|，用一兀付万表pu _10.370.25 0.180.

15、100.07 0.03_x =x1 =0,x2 =1对其进行定长编码，若所编的码为 000 , 001, 010, 011, 100, 101,则编码器输出码元的一维概率p(xi)=0.747, p(x2)=0.253。二、简答题(30分)1.设信源为,x =卜1x2 i试求(1)信源的嫡、信息含量效率以及冗余度;1pxi j/4 3/4_(2) 求二次扩展信源的概率空间和嫡。解：1 1)h(x) =1/4log24 3/4log2(4/3)= h(x)/log22 = h(x)=1- =1-h(x)(2)二次扩展信源的概率空间为：xxxix2xi1/163/16x23/169/16h(xx)

16、 =1/1610g2 16 3/1610g2(16/3) 3/16*(16/3) 9/1610g2 (16/9)2 .什么是损失嫡、噪声嫡？什么是无损信道和确定信道？如输入输出为r父s,则它们的分别信道容量为多少？答：将h (x|y)称为信道x,py|x,y的疑义度或损失嫡，损失嫡为零的信道就是无损信道，信道容量为logr。将h (y|x)称为信道 x , py|x , y的噪声嫡，噪声嫡为零的信道就是确定信道，信道容量为logs。3 .信源编码的和信道编码的目的是什么？答：信源编码的作用：(1)符号变换：使信源的输出符号与信道的输入符号相匹配；(2)冗余度压缩：是编码之后的新信源概率均匀化，

17、信息含量效率等于或接近于100%。信道编码的作用：降低平均差错率。4 .什么是香农容量公式？为保证足够大的信道容量，可采用哪两种方法？ps答：香农信道容量公式：c(ps) =blog2(1+), b为白噪声的频带限制，no为常数，输入xnob(t)的平均功率受限于 ps o由此，为保证足够大的信道容量，可采用(1)用频带换信噪比；(2)用信噪比换频带。5 .什么是限失真信源编码？答：有失真信源编码的中心任务：在允许的失真范围内把编码的信息率压缩到最小。三、综合题(20+15+15)1 .设随机变量x =x1，x2 =0,1和y=y1，y2 =0,1的联合概率空间为?丫=俨，丫1)(xl) m,

18、%) %,丫2)以1 1/83/83/81/8 1定义一个新的随机变量 z = x my (普通乘积)(1) 计算嫡 h (x), h (y), h (z), h (xz), h (yz),以及 h (xyz);(2) 计算条件嫡 h (x|y), h (y|x), h (x|z), h (z|x), h (y|z), h (z|y), h (x|yz),h (y|xz )以及 h (z|xy);(3) 计算平均互信息量 i (x; y), i (x: z), i (y: z), i (x; y|z), i (y; z|x)以及 i (x:,z|y)。解：(1)xy0101/83/81/213

19、/81/81/21/21/2h(x) =1/2log22 1/2log22 =1h(y) =1/2log22 1/2log2 2 =1xyz 0000010100111001011101111/803/803/8001/8z 017/8 1/8h(z) =7/8log2(8/7) 1/8log28xz 00 0110111/2 0 3/8 1/8h(xz) =1/2皿2 3/8log2(8/3) 1/8log2 8yz 000110111/2 0 3/8 1/8h(yz) =1/2log2 2 3/8log2(8/3) 1/8log28(2)h(x |y) =1/2(1/4log2 4 3/4

20、log2(4/3) 1/2(1/4log 24 3/4log 2 (4/3)h (y | x) =1/2(1/4log2 4 3/4log2(4/3) 1/2(1/4log2 4 3/4log 2(4/3)xz001/213/87/8101/21/81/21/8h(x |z) =7/8(4/7log2(7/4) 3/7log 2(7/3) 1/8(0log2 0 1log 21)h(z | x) =1/2(1log21 0log20) 1/2(3/4log 2(4/3) 1/4log24)yz0101/201/213/81/81/27/81/8h(z |y) =1/2(1log21 0log2

21、0) 1/2(3/4log2(4/3) 1/4log24)h(x |yz) =1/2(1/4log 2 4 3/4log2(4/3) 3/8(1脸1 010g 2 0) 1/8(1log 2i 010g 2 0)h(y|xz) =1/2(1/41og24 3/41og2(4/3) 3/8(1 log 21 010g2 0) 1/8(1 log 21 010g2 0)h(z | xy) =0i(x;y) =h(x) -h (x |y)i(x;z) =h(x) -h(x |z)i(y；z) =h(y)-h(y|z)i(x;y | z) =h(x |z) -h(x |yz)i(x;z | y) =h

22、 (x |y) -h (x |zy)2 .设二元对称信道的输入概率分布分别为px =3/4 1/4,转移矩阵为p _；2/3 1/3y|x %/3 2/3(1)求信道的输入嫡，输出嫡，平均互信息量；(2) 求信道容量和最佳输入分布；(3 ) 求信道剩余度。解：(1)信道的输入嫡 h (x) =3/41og2(4/3)+1/41og24 ；1/2 1/4丫=1/12 1/6.py =7/12 5/12h(y) =7/12log2(12/7) 5/12log2(12/5)h (y | x ) =3/4h (1/2,1/4) 1/4h (1/12,1/6)i(x;y)=h (y) - h (y |

23、x)(2)最佳输入分布为px=1/2 1/2,此时信道的容量为 c =1 h (2/3,1/3)信道的剩余度：c -i(x;y)1/2 1/3 1/63 .设有d m c ,其转移矩阵为 py|x = 1/6 1/2 1/3 ,若信道输入概率为1/3 1/6 1/2px i- 0.5 0.25 0.25 l试确定最佳译码规则和极大似然译码规则，并计算出相应的平均差错率。1/41/61/12解：pxy=1/241/81/12j/121/241/8-l-f (b1) = a1最佳译码规则：f(b2) =a1 ,平均差错率为1-1/4-1/6-1/8=11/24 ;f(b3)=a3|f (b1) =

24、 a1极大似然规则：(f(b2) =a2，平均差错率为1-1/4-1/8-1/8=1/2。f (b3 ) = a3拟试题二参考答案试日期成绩号任课教师8立)班级多少信息量。ri = 2k r 2 = 5kw1 = 1/ 8 w2 =解：根据题意有rw =0.70.3| 0.640.3由 p(w1) = p(r1) p(w1/ri); p(r2) p(w1/r2)= p(w1/r2) = 4/15所以 p(w2/r2) =1 _ p(w1/r2) =11/15得知5ka电阻的功耗为1/4w,获得的自信息量为 b(p(w2/要用于解决信息传输中的有效性，信道编码主要用，加密编码主要用于解决信息传输

25、中的安全性 。x i,则信源的嫡为1.75b倒符号 。/8n,输出符号数为m,信道转移概率矩阵为pj,则该信nki,码字个数为n,则克劳夫特不等式为m m-k 0,有lnzz-1,当且仅当z = 1时等式成立。3.设信源为x=0 , 1, p (0) =1/8,则信源的嫡为_1/8log2 8+7/8log2(7/8)比特/符号,如信源发出由m个“0”和(100-m)个“1”构成的序列，序列的自信息量为 mlog28 + (100 _m)log2(7/8)比特/符号。:号学 ：名姓 ：级班业专 ：号线4.离散对称信道输入等概率时，输出为二5根据码字所含的码元的个数，编码可分为等概 分布。定长

26、编码和 变长编码。u 1 - uiu2 u36 .设 dms 为 i = . i0.37 0.25 0.18u4u5u60.10 0.07 0.03元符号表x =x1 =0,x2 =1对其进行定长编码，若所编的码为 000, 001, 010, 011, 100, 101,则编码器输出码元的一维概率 p(x1)=0.747, p(x2)=0.253封4.1/2 1/3 1/6设有d m c ,其转移矩阵为 py|x l 1/6 1/2 1/3 ,若信道输入概率为1/3 1/6 1/2px】=0.5 0.25 0.25，试确定最佳译码规则和极大似然译码规则，并计算出相应的平均 差错率。一 1/4

27、1/61/12解：pxy = 1/24 1/81/12j/12 1/24 1/81最佳译码规则:极大似然规则:| f (b1) = a1f(b2) =a1 ,平均差错率为 1-1/4-1/6-1/8=11/24 ;f )=a3f(b1) =a1f(b2) =a2，平均差错率为 1-1/4-1/8-1/8=1/2。f(bs) =a3河南理工大学万方学院 2008-2009学年第1学期信息论与编码考试卷(b卷)总分题号一二三四五六七八九十核分人得分考试方式：闭卷本试卷考试分数占学生总评成绩的80 %总分 总复查人、填空题(共20分，每空2分)1. 信息的基本概念在于它的不确定性 。2 .按照信源发

28、出的消息在时间和幅度上的分布情况，可将信源分成离散 信源和连续信源两大类。3 . 一个随机事件的自信息量 定义为其出现概率对数的负值。4 .按树图法构成的码一定满足即时码的定义。5 .有扰离散信道编码定理称为香农第二极限定理。6 .纠错码的检、纠错能力是指检测、纠正错误码元的数目。7 .信道一般指传输信息的物理媒介，分为 有线 信道和 无线 信道。8 .信源编码的主要目的是提高通信系统的有效性。得分评卷人、选择题(共10分，每题2分)1 .给定xi条件下随机事件”所包含的不确定度和条件自信息量p(yj 仅)，(d)a.数量上不等，单位不同c.数量上相等，单位不同2 .条件嫡和无条件嫡的关系是：

29、a. h(y/x)vh(y)c. h(y/x)wh(y)3 .根据树图法构成规则，a.在树根上安排码字c.在中间节点上安排码字4 . 下列说法正确的是：a.奇异码是唯一可译码c.非奇异码不一定是唯一可译码5 .下面哪一项不属于嫡的性质：a.非负性b.数量上不等，单位相同d.数量上相等，单位相同(c)b. h(y/x)h(y)d. h(y/x)h(y)(d)b.在树枝上安排码字d.在终端节点上安排码字(c)b.非奇异码是唯一可译码d .非奇异码不是唯一可译码(b)b.完备性c.对称性d,确定性得分评卷人1.三、名词解释（共15分，每题5分）奇异码包含相同的码字的码称为奇异码。2.码距两个等长码字

30、之间对应码元不相同的数目，称为码距。3.输出对称矩阵转移概率矩阵的每一列都是第一列的置换（包含同样元素），则该矩阵称为输出对称矩阵。得分评卷人简答题（共20分，每题10分）1 .简述信息的特征。答：信息的基本概念在于它的不确定性，任何已确定的事物都不含信息。接收者在收到信息之前，对它的内容是不知道的，所以信息是新知识、新内容。信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识。信息可以产生，也可以消失，同时信息可以被携带、贮存及处理。信息是可以量度的，信息量有多少的差别。2 .简单介绍哈夫曼编码的步骤。将信源消息符号按其出现的概率大小依次排列p（x1）p（x2）p（xn）1,并将这两

31、个概率相加作为一个新符号的概率，与未分2的过程。0和1为止。取两个概率最小的符号分别配以0和配码元的符号重新排队。对重排后的两个概率最小符号重复步骤 继续上述过程，直到最后两个符号配以 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。得分评卷人四、计算题(共35分)1 .设有一个二进制一阶马尔可夫信源，其信源符号为x (0,1),条件概率为p(0/0)= p(1/0)=0.5 p(1/1)=0.25p(0/1)=0.75画出状态图并求出各符号稳态概率。(15分)0.25w0 =0.5wo 0.75ww0 皿=1wo= 0.6w1 =0.42 .设输入符号与输出符号为x=

32、yc 0,1,2,3,且输入符号等概率分布。设失真函数为汉明失真。求 dmax 和 dmin 及 r(dmax)和 r(dmin) (20 分) 有1斛：p x0 = p xi = p x2 = p x3 41 1 1 0 1 11 0 1110-失真矩阵的每一行都有0,因此dmin=0r dmin =r 0 = h x =logz4=2bit/符号111 =-43111dmax =min p(x)d(。yj) =a- 1 +1+1),-(1+1 + 1 j i444r dmax =0一、填空题1 .设信源x包含4个不同离散消息，当且仅当x中各个消息出现的概率为 1/4时，信源嫡达 到最大值，

33、为 _2_,此时各个消息的自信息量为 _2 _。2 .如某线性分组码的最小汉明距dmin=4,则该码最多能检测出 3 个随机错，最多能纠正_1 个随机错。3 .克劳夫特不等式是唯一可译码存在的充要条件。4 .平均互信息量i(x;y)与信源嫡和条件嫡之间的关系是 (x;y)=h(x)-h(x/y )。5 .信源_提高通信的有效性，_信道 目的是提高通信的可靠性，_加密_编码的目的是保证通信的安全性。6 .信源编码的目的是提高通信的有效性 ，信道编码的目的是提高通信的可靠性 ，加密编码的目的是保证通信的 安全的 。7 .设信源x包含8个不同离散消息，当且仅当x中各个消息出现的概率为 _1/8时，信

34、源嫡达到最大值，为 3。8 .自信息量表征信源中各个符号的不确定度，信源符号的概率越大，其自信息量越_小。9 .信源的冗余度来自两个方面，一是信源符号之间的_相关性_,二是信源符号分布的_不均匀性_。10 .最大后验概率译码指的是译码器要在已知r的条件下找出可能性最大的妗码作为译码估值 ，即令 =maxp( |r)。11 .常用的检纠错方法有 前向纠错、反馈重发和混合纠错三种。二、单项选择题1 .下面表达式中正确的是（a ）。a； p（yj /x） =1cp（xi,yj） = （yj）br p(yj/xj=1dp(x,yj)=q(xj2 .彩色电视显像管的屏幕上有5x105个像元，设每个像元有64种彩色度，每种彩度又有16种不同的亮度层次，如果所有的彩色品种和亮度层次的组合均以等概率出现，并且各个组合之间相互独立。每秒传送25帧图像所需要的信道容量（c ）。a. 50 106b. 75 106c. 125 1063 .已知某无记忆三符号信源a,b,c