信息论与编码试卷及答案.doc

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

2、元错误，最多能纠正_1_个码元错误。（8） 设有一离散无记忆平稳信道，其信道容量为 C，只要待传送的信息传输率 R_小于_C（大于、小于或者等于） ，则存在一种编码，当输入序列长度 n 足够大，使译码错误概率任意小。（9） 平均错误概率不仅与信道本身的统计特性有关，还与_译码规则_和_编码方法_有关3、 （5）居住在某地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6 米以上的，而女孩中身高 1.6 米以上的占总数的一半。假如我们得知“身高 1.6 米以上的某女孩是大学生”的消息，问获得多少信息量？解：设A表示“大学生”这一事件，B表示“身高1.60以上”这一事件，则P(A)

3、=0.25 p(B)=0.5 p(B|A)=0.75 （2分）故 p(A|B)=p(AB)/p(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=0.375 （2分）I(A|B)=-log0.375=1.42bit （1分）四、 （5）证明：平均互信息量同信息熵之间满足I(X;Y)=H(X)+H(Y)-H(XY)证明：2（2分）YXHyxpxpyxYXI XYjijiijiYijji loglogl;同理（1分）I;则YXIHY;因为（1分）X故 YXIHY;即（1分）XI;五、 （18 ）.黑白气象传真图的消息只有黑色和白色两种，求：1） 黑色出现的概率为 0.3，白色出现的

4、概率为 0.7。给出这个只有两个符号的信源 X 的数学模型。假设图上黑白消息出现前后没有关联，求熵 ；XH2） 假设黑白消息出现前后有关联，其依赖关系为 ， ， ，求其熵 。3）分别求上述两种信源的冗余度，比较它们的大小并说明其物理意义。解：1）信源模型为 （1分）32）由题意可知该信源为一阶马尔科夫信源。 （2分）由 （4分）得极限状态概率（2分）（3分）3）（1分）19.02log)(1XH（1分）47.l)(22。说明：当信源的符号之间有依赖时，信源输出消息的不确定性减弱。而信源冗余度正是12反映信源符号依赖关系的强弱，冗余度越大，依赖关系就越大。 （2分）六、 （18 ）.信源空间为，

5、试分别构造二元香农码和二元霍夫1234567()0.9.8017.01.XxxxP 曼码，计算其平均码长和编码效率（要求有编码过程） 。414.3)(71iilapL8.0.62XHR5七（6）.设有一离散信道，其信道传递矩阵为 ，并设 ，试分别2/163/41)(2)(31xp按最大后验概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。1） （3分）最小似然译码准则下，有，2） （3分）最大后验概率准则下，有，八（10）.二元对称信道如图。 1）若 ， ，求 、 和 ；430p1XHY|XI;2）求该信道的信道容量。解：1）共6分2） ， （3分）此时输入概率分布为等概率分布

6、。 （1分）九、 （18）设一线性分组码具有一致监督矩阵 101H1）求此分组码 n=?,k=?共有多少码字？2）求此分组码的生成矩阵 G。3）写出此分组码的所有码字。4）若接收到码字（101001） ，求出伴随式并给出翻译结果。解：1）n=6,k=3,共有8个码字。 （3分）符 号/749.0|bitYXH62）设码字 由 得012345CTH（3 分）01354令监督位为 ，则有012C（3分）34051生成矩阵为 （2分）103）所有码字为000000，001101，010011，011110，100110，101011，110101，111000。 （4分）4）由 得THRS， （2分

7、）该码字在第5位发生错误， （101001）纠正为（101011） ，即译码为10（101001） （1分）一、填空题（本题10空,每空1分,共10分）1、必然事件的自信息量是_0_，不可能事件的自信息量是_无穷_。2、一信源有五种符号a，b，c，d，e ，先验概率分别为Pa=0.5，Pb=0.25，Pc=0.125，Pd=Pe =0.0625。符号“a”的自信息量为_1_bit，此信源的熵为_1.875_bit/符号。3、如某线性分组码的最小汉明距dmin=6，最多能纠正_2_个随机错。4、根据密码算法所使用的加密密钥和解密密钥是否相同，可将密码体制分成_对称（单密钥）_和_非对称（双密钥）

8、_。5、平均互信息量I(X;Y)与信源熵和条件熵之间的关系是_I(X:Y)=H(X)-H(X/Y)_。6、克劳夫特不等式是唯一可译码_存在_的充要条件。00，01，10，11 是否是唯一可译码？_是_。三、单项选择题(本题共10小题；每小题2分，共20分)1、对连续集的熵的描述不正确的是（A）A 连续集的熵和离散集的熵形式一致，只是用概率密度代替概率，用积分代替求和B 连续集的熵值无限大C 连续集的熵由绝对熵和微分熵构成D 连续集的熵可以是任意整数72、设信道输入为xm，输出为 y，若译码准则是当P (y | xm)P(y | xm)，对所有m m时，将y判为m ，则称该准则为（ D）A 最大

9、后验概率译码准则B 最小错误概率准则C 最大相关译码准则D 最大似然译码准则3、线性分组码不具有的性质是（C）A 任意多个码字的线性组合仍是码字B 最小汉明距离等于最小非0重量C 最小汉明距离为3D 任一码字和其校验矩阵的乘积 cmHT=04、关于伴随式的描述正确的是（A）A 伴随式s与传送中信道出现的错误图样e有关B 通过伴随式s可以完全确定传送中信道出现的错误图样eC 伴随式s 与发送的具体码字有关D 伴随式s与发送的具体码字有关，与传送中信道出现的错误图样e也有关5、率失真函数的下限为（B）AH(U) B0 CI(U; V) D没有下限6、纠错编码中，下列哪种措施不能减小差错概率（D）A

10、 增大信道容量 B 增大码长 C 减小码率 D 减小带宽7、已知某无记忆三符号信源 a,b,c 等概分布，接收端为二符号集，其失真矩阵为,则信源的最大平均失真度 Dmax 为（ D）A 1/3 B 2/3 C 3/3 D 4/38、一珍珠养殖场收获 240 颗外观及重量完全相同的特大珍珠，但不幸被人用外观相同但重量仅有微小差异的假珠换掉 1 颗。一人随手取出 3 颗，经测量恰好找出了假珠，不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多 6 次能找出，结果确是如此，这一事件给出的信息量（ A） 。A 0bit B log6bit C 6bit D log240bit9、已知随机

11、噪声电压的概率密度函数 p(x) =1/2，x 的取值范围为1V 至+1V，若把噪声幅度从零开始向正负幅度两边按量化单位为 0.1V 做量化，并且每秒取 10 个记录，求该信源的时间熵（B ）A 21.61bit/s B 43.22bit/s C 86.44 bit /s D 以上都不对10、彩色电视显像管的屏幕上有 5105 个像元，设每个像元有 64 种彩色度，每种彩度又有 16种不同的亮度层次，如果所有的彩色品种和亮度层次的组合均以等概率出现，并且各个组合之间相互独立。每秒传送 25 帧图像所需要的信道容量（C ）A 50.106 B 75.106 C 125.106 D 250.106

12、第 7 章 线性分组码1. 已知一个(5, 3)线性码 C 的生成矩阵为：8101G（1）求系统生成矩阵；（2）列出 C 的信息位与系统码字的映射关系；（3）求其最小 Hamming 距离，并说明其检错、纠错能力；（4）求校验矩阵 H；（5）列出译码表，求收到 r=11101 时的译码步骤与译码结果。解：（1）线性码 C 的生成矩阵经如下行变换： 231321010101010 将 第 、 加 到 第 行将 第 加 到 第 行 得到线性码 C 的系统生成矩阵为 101SG（2）码字 的编码函数为),(10ncc 1010( 2mmmf 生成了的 8 个码字如下信息元 系统码字000 00000

13、001 00111010 01010011 01101100 10011101 10100110 11001111 11110(3) 最小汉明距离 d=2，所以可检 1 个错，但不能纠错。(4) 由 ，得校验矩阵, )()( knTkknk IAHIG9101H(5) 消息序列 m=000,001,010,011,100,101,110,111，由 c=mGs 得码字序列c0=00000, c1=00111,c2=01010, c3=01101,c4=10011, c5=10100,c6=11001, c7=11110则译码表如下：00000 00111 01010 01101 10011 1

14、0100 11001 1111010000 10111 11010 11101 00011 00100 01001 0111001000 01111 00010 00101 11011 11100 10001 1011000001 00110 01011 01100 10010 10101 11000 11111当接收到 r =(11101)时，查找码表发现它所在的列的子集头为 (01101)，所以将它译为 c=01101。2设（7, 3）线性码的生成矩阵如下 0101G（1）求系统生成矩阵；（2）求校验矩阵；（3）求最小汉明距离；（4）列出伴随式表。解：（1）生成矩阵 G 经如下行变换 13

15、23010010010100 交 换 第 、 行交 换 第 、 行得到系统生成矩阵： 1010SG（2）由 ，得校验矩阵为, )()( knTkknk IAHIG101001H（3）由于校验矩阵 H 的任意两列线性无关，3 列则线性相关，所以最小汉明距离 d=3。（4） （7, 3）线性码的消息序列 m=000,001,010,011,100,101,110,111，由 c=mGs 得码字序列：c0=0000000，c 1=0010111，c 2=0101010，c 3=0111101，c 4=1001101， c5=1011010，c 6=1100111，c 7=1110000。又因伴随式有

16、 24=16 种组合，差错图样为 1 的有 ，差错图样为 2 的有 ，而由 ，则7种 71种 THre计算陪集首的伴随式，构造伴随表如下：伴随式 陪集首 伴随式 陪集首0000 0000000 0101 10010001101 1000000 1001 10001001010 0100000 1111 00110000111 0010000 1100 00011001000 0001000 1110 01001000100 0000100 1011 01000010010 0000010 0011 00101000001 0000001 0110 00001103已知一个(6, 3)线性码 C 的生成矩阵为： .0 1 0 1G（1） 写出它所对应的监督矩阵 H；（2） 求消息 M=(101)的码字；（3） 若收到码字为 101010，计算伴随式，并求最有可能的发送码字。解：（1）线性码 C 的生成矩阵 G 就是其系统生成矩阵 GS，所以其监督矩阵 H 直接得出：1001H（2）消息 M=(m0,m1,m2)=(101)，则码字 c 为：