信息论与编码试卷及答案解析.docx

《信息论与编码试卷及答案解析.docx》由会员分享，可在线阅读，更多相关《信息论与编码试卷及答案解析.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、p(AB)/p(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=0.3752分I(A|B)=-log0.375=1.42bit1分四、5证明：平均互信息量同信息熵之间满足I(X;Y)=H(X)+H(Y)-H(XY)证明：I (X ;Y )= p(x y()(i)log p x y jijp xXYi()= - p(x y )log p(x- - p(x y )log p x y2分=( )()ijiijXYXYH X- H X Yij 同理I (X ;Y )= H (Y )- H (Y X )1分则H (Y X )= H (Y )- I (X ;Y )由于H (XY )= H

4、 (X )+ H (Y X )1分故H (XY )= H (X )+ H (Y )- I (X ;Y )即I (X ;Y )= H (X )+ H (Y )- H (XY )1分五、18.黑白气象 图的消息只有黑色和白色两种，求：1） 黑色消灭的概率为 0.3，白色消灭的概率为0.7。给出这个只有两个符号的信源X 的数学模型。假设图上黑白消息消灭前后没有关联，求熵H (X )；2） 假设黑白消息消灭前后有关联，其依靠关系为，.，求其熵 H(X )。解：1信源模型为1分3） 分别求上述两种信源的冗余度，比较它们的大小并说明其物理意义。2由题意可知该信源为一阶马尔科夫信源。2分由4分2分得极限状态

5、概率3分3g= 1 - H ( X ) = 0.1191log221分g= 1 -H ( X )=0.4472log221分21g g 。说明：当信源的符号之间有依靠时，信源输出消息的不确定性减弱。而信源冗余度正是反映信源符号依靠关系的强弱，冗余度越大，依靠关系就越大。2分六、18.信源空间为X xxxxxxxP( X ) = 1234567 ，试分别构造二元香农码和二元霍夫0.20.190.180.170.150.10.01曼码，计算其平均码长和编码效率要求有编码过程。L = 7i=1p(a )lii= 3.14R = H (X ) = 2.61 = 0.831L3.14 p(x ) = 1

6、1/ 21/ 31/ 614七6.设有一离散信道，其信道传递矩阵为1/ 61/ 21/ 3 ，并设() = 1 ，试分别按1/ 31/ 61/ 2 p x221 p(x ) =3413分最小似然译码准则下，有，最大后验概率准则与最大似然译码准则确定译码规章，并计算相应的平均错误概率。23分最大后验概率准则下，有，八10.二元对称信道如图。1假设 p(0)= 3 ， p(1)= 1 ，求 H (X )、 H (X | Y )和 I (X ;Y )；2求该信道的信道容量。44解：1共6分H (X | Y )= 0.749bit / 符号2，3分此时输入概率分布为等概率分布。1分000111九、18

7、设一线性分组码具有全都监视矩阵H = 0110011010111） 求此分组码 n=?,k=?共有多少码字？2） 求此分组码的生成矩阵G。3） 写出此分组码的全部码字。.4） 假设接收到码字101001，求出伴随式并给出翻译结果。解：1n=6,k=3,共有8个码字。3分543210由2设码字C = (C C C C C C )得HCT = 0TC C C= 0210C C C= 0C430 C C C= 053103分(C C C )令监视位为210，则有C= C C253C = C C 154043C= C C3分100110010011生成矩阵为0011012分3全部码字为000000，0

8、01101，010011，011110，100110，101011，110101，111000。4分4由ST= HRT 得S = (101)，2分该码字在第5位发生错误，101001订正为101011，即译码为1010011分一、填空题此题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”的自信息量为1bit，此信源的熵为1.875bit/符号。3、如某线性分组码的最小汉明距dmin=6，最多能订正2个随机错。4、依据密码算

9、法所使用的加密密钥和解密密钥是否一样，可将密码体制分成对称单密钥和非对称双密钥。5、平均互信息量I(X;Y)与信源熵和条件熵之间的关系是I(X:Y)=H(X)-H(X/Y)。6、克劳夫特不等式是唯一可译码存在的充要条件。00，01，10，11是否是唯一可译码？是。三、单项选择题(此题共10小题；每题2分，共20分) 1、对连续集的熵的描述不正确的选项是AA 连续集的熵和离散集的熵形式全都，只是用概率密度代替概率，用积分代替求和B 连续集的熵值无限大C 连续集的熵由确定熵和微分熵构成D 连续集的熵可以是任意整数2、设信道输入为xm，输出为y，假设译码准则是当P(y | xm)P(y | xm)，

10、对全部mm时，将y判为m，则称该准则为DA 最大后验概率译码准则B 最小错误概率准则C 最大相关译码准则D 最大似然译码准则3、线性分组码不具有的性质是C A 任意多个码字的线性组合仍是码字B 最小汉明距离等于最小非0重量C 最小汉明距离为3D 任一码字和其校验矩阵的乘积 cmHT=0 4、关于伴随式的描述正确的选项是AA 伴随式s与传送中信道消灭的错误图样e有关B 通过伴随式s可以完全确定传送中信道消灭的错误图样e C 伴随式s与发送的具体码字有关D 伴随式s与发送的具体码字有关，与传送中信道消灭的错误图样e也有关5、率失真函数的下限为BAH(U)B0CI(U; V)D没有下限6、纠错编码中

11、，以下哪种措施不能减小过失概率D A 增大信道容量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 log240b

12、it9、随机噪声电压的概率密度函数 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

13、.106第 7 章线性分组码（1） 求系统生成矩阵；（2） 列出 C 的信息位与系统码字的映射关系；111. 一个(5, 3)线性码 C 的生成矩阵为：1100G = 0110 00111（3） 求其最小 Hamming 距离，并说明其检错、纠错力量；（4） 求校验矩阵 H；（5） 列出译码表，求收到 r=11101 时的译码步骤与译码结果。解：（1） 线性码 C 的生成矩阵经如下行变换：1100110011001101 将第2、3加到第1行 11010011100111100111001101 将第3加到第2行 001110100011100111得到线性码 C 的系统生成矩阵为10011G

14、= 01010S00111（2） 码字 c = (c0, c , c1n-1) 的编码函数为c = f (m) = m0信息元系统码字生成了的 8 个码字如下10011+ m101010+ m2001110000000000100111010010100110110110010011101101001101100111111110(3) 最小汉明距离 d=2，所以可检 1 个错，但不能纠错。(4) 由 G = In-k, Ak(n-k ), H = Ak(n-k )T , In-k，得校验矩阵10101H = 11110(5) 消息序列 m=000,001,010,011,100,101,11

15、0,111，由 c=mGs 得码字序列c0=00000, c1=00111,c2=01010, c3=01101, c4=10011, c5=10100,c6=11001, c7=1111000000011010101101100110101100111101000000010111100110000100101100101011001101110010111001010110001110001011011111则译码表如下：01010101000101111011110000100100100011101011010当接收到 r =(11101)时，查找码表觉察它所在的列的子集头为(0110

16、1)，所以将它译为 c=01101。2. 设7, 3线性码的生成矩阵如下（1） 求系统生成矩阵；（2） 求校验矩阵；（3） 求最小汉明距离；（4） 列出伴随式表。解：（1） 生成矩阵 G 经如下行变换0101010010111001101G = 010100101000011 交换第01010100110110111、3行 001011101101010101001101100110110112、3行 01010100101000101111 交换第得到系统生成矩阵：1001101G= 0101010S0010111（2） 由 G = In-k, Ak(n-k ), H = Ak(n-k )T

17、 , In-k，得校验矩阵为110100010101000110010H = 1010001（3） 由于校验矩阵 H 的任意两列线性无关，3 列则线性相关，所以最小汉明距离 d=3。47, 3线性码的消息序列 m=000,001,010,011,100,101,110,111，由 c=mGs 得码字序列：c0=0000000，c1=0010111，c2=0101010，c3=0111101，c4=1001101，c5=1011010，c6=1100111，c7=1110000。又因伴 7 7 随式有 24=16 种组合，过失图样为 1 的有 = 7种，过失图样为 2 的有 = 21种，而由 H

18、rT= HeT ，则计算陪集首的伴随式，构造伴随表如下： 1 2 伴随式0000陪集首00000001000000010000000100000001000伴随式010111011001101011110111110010001110陪集首100100010001000011000000110001001000100001000001000000010000000110110011000101100100001001010000001103. 一个(6, 3)线性码 C 的生成矩阵为：100101G = 010011.（1） 写出它所对应的监视矩阵 H；（2） 求消息 M=(101)的码字；0

19、01110 （3） 假设收到码字为 101010，计算伴随式，并求最有可能的发送码字。解：1线性码 C 的生成矩阵 G 就是其系统生成矩阵 GS，所以其监视矩阵 H 直接得出：0110011010100011H = 012消息 M=(m0,m1,m2)=(101)，则码字 c 为：c = f (m) = 100101+ 001110= 1010113收到码字 r=(101010)，则伴随式rH101T = (101010) 10001110010 = (001)1001又6, 3线性码的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列：c0=

20、000000，c1=001110，c2=010011，c3=011101，c4=100101，c5=101011，c6=110110，c7=111000。伴随式有 23=8种状况，则计算伴随式得到伴随表如下：伴随式000陪集首000000101011110100010001111100000010000001000000100000010000001100010伴随式001对应陪集首为000001，而 c=r+e，则由收到的码字 r=(101010)，最有可能发送的码字 c 为：c=101011。4. 设(6, 3)线性码的信息元序列为 x1x2x3，它满足如下监视方程组x + x+ x= 0

21、 124x+ x+ x= 0 235 x + x+ x= 0136（1） 求校验矩阵，并校验 10110 是否为一个码字；（2） 求生成矩阵，并由信息码元序列 101 生成一个码字。解：（1） 由监视方程直接得监视矩阵即校验矩阵为：1010011010010011H = 01由于收到的序列 10110 为 5 位，而由6, 3线性码生成的码字为 6 位，所以 10110 不是码字。（2） 由 G = In-k, Ak(n-k ), H = A100101010110001011k(n-k )G = T , In-k，则生成矩阵为：= GS信息码元序列 M=101，由 c=mGs 得码字为 c：

22、c = m0(100101)+ m1(010110)+ m2(001011)= (101110)第 8 章循环码1. (8, 5)线性分组码的生成矩阵为11G = 00111100000001000100010001000101100001（1） 证明该码是循环码；（2） 求该码的生成多项式 g (x) 。（1） 证明如下：1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 (1)+(2) 0 1 0 0 0 1 0 0 (2) +(3) 0 0 1 0 0 0 1 0 0 0 1 0

23、0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 (3) +(4) 0 0 1 1 1 1 0 0 (1)+(5) 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 (4)

24、 +(5) 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 由生成矩阵可知为8、5循环码。（2） 生成多项式如下：g(x) = x3 + x2 + x +12. 证明： x10 + x8 + x5 + x 4 + x 2 + x + 1为(15, 5)循环码的生成多项式，并写出信息多项式为m(x) = x 4 + x + 1时的码多项式按系统码的形式。由定理 8-1 可知n，k循环码的生成多项式g(x)为 xn+1 的因子， g(x)为 n-k 次多项式，此题目中知： g (x) =

25、 x10 + x8 + x5 + x4 + x2 + x + 1为一个 10 次多项式，n-k=15-5=10并且： (x15 +1)mod( x10 + x8 + x5 + x4 + x2 + x + 1) = 0所以： x10 + x8 + x5 + x4 + x2 + x +1 是 x15 +1的一个因子，也是循环码的生成多项式。按系统码构造多项式如下：m(x) = x4 + x + 1m(x) xn-k = (x4 + x +1) x10 = x14 + x11 + x10b(x) = (m(x) xn-k ) mod(x10 + x8 + x5 + x4 + x2 + x +1)=

26、x8 + x7 + x6 + xc(x) = m(x) xn-k + b(x) = x14 + x11 + x10 + x8 + x7 + x6 + x3. (7, 4)循环码的生成多项式为 g (x) = x 3 码电路和代数计算求其相应的码多项式C(x)。 由题目可知代数计算求解过程如下：m(x) = x3 +1m(x) xn-k = x6 + x3b(x) = (m(x) xn-k ) mod(x3 + x +1) = x2 + x c(x) = m(x) xn-k + b(x) = x6 + x3 + x2 + x c = (1001110)+ x + 1，信息多项式为 m(x) =

27、x 3 + 1，分别由编由编码电路进展求解： 编码电路如下所示：门1D0+D1D2+或门c(x)m编码过程存放器码字如下：时钟信息元输出码字0D00D10D20111101200110301110410111500116000170000可得： c(x) = x6 + x3 + x2 + x4. 令(15, 11)循环码的生成多项式为 g (x) = x 4+ x + 1 ，计算（1） 假设信息多项式为m(x) = x10 + x8 + 1，试求编码后的系统码字；（2） 求接收码组R(x) = x14+ x 4 + x + 1 的校正子多项式。(1)解题过程如下：m(x) = x10 + x8

28、 +1m(x) xn-k = m(x) x4 = x14 + x12 + x4b(x) = (m(x) xn-k ) mod(x4 + x +1) = x2 +1 c(x) = m(x) xn-k + b(x) = x14 + x12 + x4 + x2 +1 c = (1010000000010101)2校正多项式如下所示：R(x)x14 + x4 + x +1S (x) =mod(g(x) = x3 +1g (x)x4 + x +15. 码长为n=15 的本原 BCH 码，求不同纠错力量下的 BCH 码各自的生成多项式g (x) 。n = 2m -1 = 15 m = 4纠错力量： t 2

29、m-1 = 8 ，所以最多能订正 7 个错误码。有限域 GF24，4 次本原多项式 f (x) = x4 + x +1 ，为 f(x)的一个根，可知：a4 + a +1 = 0 ，计算 2t=14 个连续幂次为a1a 3a 5a 7a 9a 11a 13 对应的最小多项式：a1 = m (x) = x4 + x +1,a2 = m(x) = x4 + x +1,a3 = m(x) = x4 + x3 + x2 + x +11a4 = m42(x) = x4 + x +1,a5 = m53(x) = x2 + x +1,a6 = m6(x) = x4 + x3 + x2 + x +1a7 = m

30、7(x) = x4 + x3 +1,a8 = m8(x) = x4 + x +1,a9 = m9(x) = x4 + x +1a10 = m10(x) = x2 + x +1,a11 = m11(x) = x4 + x3 + x2 + x +1a12 = m12(x) = x4 + x3 + x2 + x +1,a13 = m13(x) = x2 + x +1,a14 = m3(x) = x4 + x3 +1(1) t=1 的码字： (15，11)BCH 码g (x) = Lcm(m11(x) = x4 + x + 1(2)t=2 的码字：(15，7)BCH 码g (x) = Lcm(m21(

31、x)m3(x) = x8 + x7 + x6 + x4 + 1(3)t=3 的码字：(15，5)BCH 码g (x) = Lcm(m31(x)m3(x)m5(x) = x10 + x8 + x5 + x4 + x2 + x +1(4) t=4 的码字：(15，1)BCH 码g (x) = x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 14(5) t=5 的码字：(15，1)BCH 码g (x) = x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6

32、+ x5 + x4 + x3 + x2 + x + 15(6) t=6 的码字：(15，1)BCH 码g (x) = x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 16(7) t=7 的码字：(15，1)BCH 码g (x) = x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 176. 构造一个能订正t=3 个错误符号，码长为 15，m=4 的 RS 码，并求其生成矩阵。码长：n=q-1， q

33、= 2md= 2t +1 = 7min= 16 ，m=4n-k=2t=6k=n-2t=15-6=9可知 RS 码为：5，9码设为本原多项式 f (x) = x4 + x +1 的根，即： a4 = a +1t=3，生成多项式 g(x)有 6 个连续的根， a,a 2 ,a 3,a 4 ,a 5 ,a 6g(x) = (x - a)( x - a2 )( x - a3 )( x - a4 )( x - a5 )( x - a6 )= x6 + a10 x5 + a14 x4 + a4 x3 + a6 x2 + a9 x + a615，9的 RS 码的生成矩阵如下：1 10144 69 60 0 0 0 0 0 0 0 110 14 4696 0 00000001 10 14 4 6 9 6000000001101446960000000000001101446960000000001 10 144 6 9 60000 0 0 0 0 0 1 10 14 4 6 9 6 0 000000001101446960000000001 10 14 4 6 9 6