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

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

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

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

3、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)证明：.-.word.zl-YXHXHyxpyxpxpyxpxpyxpyxpYXIXXYjijiYijiXYijijilogloglog;2分 同理 XYHYHYXI;1分 那么 YXIYHXYH;因为 XYHXHXYH 1分 故 YXIYHXHXYH;即 XYHYHXHYXI;1分 五、18.黑白气象

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

5、赖关系的强弱，冗余度越大，依赖关系就越大。2分 六、18.信源空间为 1234567()0.20.190.180.170.150.10.01XxxxxxxxP X，试分别构造二元香农码和二元霍夫曼码，计算其平均码长和编码效率要求有编码过程。.-.word.zl-14.3)(71iiilapL831.014.361.2)(LXHR.-.word.zl-七6.设有一离散信道，其信道传递矩阵为2/16/13/13/12/16/16/13/12/1，并设41)(21)(41)(321xpxpxp，试分别按最大后验概率准那么与最大似然译码准那么确定译码规那么，并计算相应的平均错误概率。1 3分最小似然译

6、码准那么下，有，2 3分最大后验概率准那么下，有，八10.二元对称信道如图。1假设 430 p，411 p，求 XH、YXH|和YXI;；2求该信道的信道容量。解：1共6分 2，3分此时输入概率分布为等概率分布。1分 九、18设一线性分组码具有一致监视矩阵110101100110111000H 1求此分组码 n=?,k=?共有多少码字？2求此分组码的生成矩阵 G。3写出此分组码的所有码字。4假设接收到码字101001，求出伴随式并给出翻译结果。解：1n=6,k=3,共有8个码字。3分 2设码字012345CCCCCCC 由TTHC0得 0000135034012CCCCCCCCCC3分 符号/

7、749.0|bitYXH.-.word.zl-令监视位为012CCC，那么有 340451352CCCCCCCCC3分 生成矩阵为1011001100100110012分 3所有码字为000000，001101，010011，011110，100110，101011，110101，111000。4分 4由TTHRS得 101S，2分该码字在第5位发生错误，101001纠正为101011，即译码为101001 1分 一、填空题此题10空,每空1分,共10分 1、必然事件的自信息量是_0_，不可能事件的自信息量是_无穷_。2、一信源有五种符号a，b，c，d，e，先验概率分别为Pa=0.5，Pb=0

8、.25，Pc=0.125，Pd=Pe=0.0625。符号“a的自信息量为_1_bit，此信源的熵为_1.875_bit/符号。3、如某线性分组码的最小汉明距dmin=6，最多能纠正_2_个随机错。4、根据密码算法所使用的加密密钥和解密密钥是否一样，可将密码体制分成_对称单密钥_和_非对称双密钥_。5、平均互信息量I(X;Y)与信源熵和条件熵之间的关系是_I(X:Y)=H(X)-H(X/Y)_。6、克劳夫特不等式是唯一可译码_存在_的充要条件。00，01，10，11是否是唯一可译码？_是_。三、单项选择题(此题共10小题；每题2分，共20分).-.word.zl-1、对连续集的熵的描述不正确的选

9、项是A A 连续集的熵和离散集的熵形式一致，只是用概率密度代替概率，用积分代替求和 B 连续集的熵值无限大 C 连续集的熵由绝对熵和微分熵构成 D 连续集的熵可以是任意整数 2、设信道输入为xm，输出为y，假设译码准那么是当P(y|xm)P(y|xm)，对所有mm时，将y判为m，那么称该准那么为D A 最大后验概率译码准那么B 最小错误概率准那么 C 最大相关译码准那么D 最大似然译码准那么 3、线性分组码不具有的性质是C A 任意多个码字的线性组合仍是码字 B 最小汉明距离等于最小非0重量 C 最小汉明距离为3 D 任一码字和其校验矩阵的乘积cmHT=0 4、关于伴随式的描述正确的选项是A

10、A 伴随式s与传送XX道出现的错误图样e有关 B 通过伴随式s可以完全确定传送XX道出现的错误图样e C 伴随式s与发送的具体码字有关 D 伴随式s与发送的具体码字有关，与传送XX道出现的错误图样e也有关 5、率失真函数的下限为B AH(U)B0 CI(U;V)D没有下限.-.word.zl-6、纠错编码中，以下哪种措施不能减小过失概率D A 增大信道容量 B 增大码长 C 减小码率 D 减小带宽 7、某无记忆三符号信源 a,b,c 等概分布，接收端为二符号集，其失真矩阵为,那么信源的最大平均失真度 Dmax 为 D A 1/3 B 2/3 C 3/3 D 4/3 8、一珍珠养殖场收获 240

11、 颗外观及重量完全一样的特大珍珠，但不幸被人用外观一样但重量仅有 微小差异的假珠换掉 1 颗。一人随手取出 3 颗，经测量恰好找出了假珠，不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多 6 次能找出，结果确是如此，这一事件给出的 信息量 A。A 0bit B log6bit C 6bit D log240bit 9、随机噪声电压的概率密度函数 p(x)=1/2，x 的取值范围为1V 至+1V，假设把噪声幅度从 零开场向正负幅度两边按量化单位为 0.1V 做量化，并且每秒取 10 个记录，求该信源的时间熵 B A 21.61bit/s B 43.22bit/s C 86.44

12、bit/s D 以上都不对 10、彩色电视显像管的屏幕上有 5105 个像元，设每个像元有 64 种彩色度，每种彩度又有 16 种不同的亮度层次，如果所有的彩色品种和亮度层次的组合均以等概率出现，并且各个组合之 间相互独立。每秒传送 25 帧图像所需要的信道容量C A 50.106 B 75.106 C 125.106 D 250.106 第 7 章线性分组码 1.一个(5,3)线性码C的生成矩阵为：11001G0110100111 1求系统生成矩阵；2列出C的信息位与系统码字的映射关系；3求其最小 Hamming 距离，并说明其检错、纠错能力；4求校验矩阵 H；5列出译码表，求收到r=111

13、01 时的译码步骤与译码结果。解：1线性码 C 的生成矩阵经如下行变换：.-.word.zl-2 3132110011001101101011010011100111100111001101101010100011100111 将第、加到第 行将第 加到第 行 得到线性码 C 的系统生成矩阵为 111000101011001SG 2码字),(110ncccc的编码函数为 111000101011001)(210mmmmfc 生成了的 8 个码字如下 信息元 系统码字 000 00000 001 00111 010 01010 011 01101 100 10011 101 10100 110

14、11001 111 11110(3)最小汉明距离d=2，所以可检 1 个错，但不能纠错。(4)由,)()(knTknkknkknIAHAIG，得校验矩阵 1010101111H(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 10100 11001 11110 10000 10111 11010 11101 00011

15、00100 01001 01110 01000 01111 00010 00101 11011 11100 10001 10110 00001 00110 01011 01100 10010 10101 11000 11111 当接收到r=(11101)时，查找码表发现它所在的列的子集头为(01101)，所以将它译为c=01101。.-.word.zl-2设7,3线性码的生成矩阵如下 010101000101111001101G 1求系统生成矩阵；2求校验矩阵；3求最小汉明距离；4列出伴随式表。解：1生成矩阵G经如下行变换 1 32 301010101001101001011100101111

16、0011010101010100110110011010010111010101001010100010111 交换第、行交换第、行 得到系统生成矩阵：100110101010100010111SG 2由,)()(knTknkknkknIAHAIG，得校验矩阵为 1101000101010001100101010001H 3由于校验矩阵H的任意两列线性无关，3 列那么线性相关，所以最小汉明距离d=3。4 7,3线性码的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列：c0=0000000，c1=0010111，c2=0101010，c3=01

17、11101，c4=1001101，c5=1011010，c6=1100111，c7=1110000。又因伴随式有 24=16 种组合，过失图样为 1 的有771 种，过失图样为 2 的有7212 种，而由TTHrHe，那么计算陪集首的伴随式，构造伴随表如下：伴随式 陪集首 伴随式 陪集首 0000 0000000 0101 1001000.-.word.zl-1101 1000000 1001 1000100 1010 0100000 1111 0011000 0111 0010000 1100 0001100 1000 0001000 1110 0100100 0100 0000100 10

18、11 0100001 0010 0000010 0011 0010100 0001 0000001 0110 0000110 3一个(6,3)线性码C的生成矩阵为：.0 1 1 1 0 01 1 0 0 1 01 0 1 0 0 1G 1 写出它所对应的监视矩阵 H；2 求消息M=(101)的码字；3 假设收到码字为 101010，计算伴随式，并求最有可能的发送码字。解：1线性码C的生成矩阵G就是其系统生成矩阵GS，所以其监视矩阵H直接得出：101100011010110001H 2消息M=(m0,m1,m2)=(101)，那么码字c为：()100 10 100 1 1 1010 10 1 1

19、cf m 3收到码字r=(101010)，那么伴随式 101011110101010001100010001TrH 又6,3线性码的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列：c0=000000，c1=001110，c2=010011，c3=011101，c4=100101，c5=101011，c6=110110，c7=111000。伴随式有 23=8 种情况，那么计算伴随式得到伴随表如下：伴随式 陪集首 000 000000.-.word.zl-101 100000 011 010000 110 001000 100 000100 0

20、10 000010 001 000001 111 100010 伴随式001对应陪集首为000001，而c=r+e，那么由收到的码字r=(101010)，最有可能发送的码字c为：c=101011。4设(6,3)线性码的信息元序列为x1x2x3，它满足如下监视方程组 000631532421xxxxxxxxx 1求校验矩阵，并校验 10110 是否为一个码字；2求生成矩阵，并由信息码元序列 101 生成一个码字。解：1由监视方程直接得监视矩阵即校验矩阵为：110100011010101001H 因为收到的序列 10110 为 5 位，而由6,3线性码生成的码字为 6 位，所以 10110 不是码

21、字。2由,)()(knTknkknkknIAHAIG，那么生成矩阵为：100101010110001011SGG 信息码元序列 M=101，由c=mGs 得码字为c：012100101010110001011101110cmmm 第 8 章 循环码 1.(8,5)线性分组码的生成矩阵为.-.word.zl-1000011101000100001000100001000100001111G 1证明该码是循环码；2求该码的生成多项式)(xg。1证明如下：(1)(2)(2)1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0

22、1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 00 0 1 0 0 0 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 1(3)(3)(4)1 1 1 1 0 0 0 01 1 1 1 0 0 0 00 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 1 0 0 0 1 00 0 0 1 1 1 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 1 (1)(5)(4)(5)1 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1

23、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 00 0 0 1 1 1 1 00 0 0 1 0 0 0 10 0 0 0 1 1 1 1 由生成矩阵可知为8、5循环码。2生成多项式如下：32()1g xxxx 2.证明：1245810 xxxxxx为(15,5)循环码的生成多项式，并写出信息多项式为1)(4xxxm时的码多项式按系统码的形式。由定理 8-1 可知n，k循环码的生成多项式 g(x)为 xn+1 的因子，g(x)为 n-k 次多项式，此题目中.-.word.zl-知：108542

24、()1g xxxxxxx为一个 10 次多项式，n-k=15-5=10 并且：15108542(1)mod(1)0 xxxxxxx 所以：1085421xxxxxx是151x的一个因子，也是循环码的生成多项式。按系统码构造多项式如下：4()1m xxx 410141110108542876()(1)()()mod(1)n kn km xxxxxxxxb xm xxxxxxxxxxxx 141110876()()()n kc xm xxb xxxxxxxx 3.(7,4)循环码的生成多项式为1)(3xxxg，信息多项式为1)(3 xxm，分别由编码电路和代数计算求其相应的码多项式C(x)。由题目

25、可知代数计算求解过程如下：36332632()1()()()mod(1)()()()(1001110)n kn kn km xxm xxxxb xm xxxxxxc xm xxb xxxxxc 由编码电路进展求解：编码电路如下所示：D0门1或门D2D1+mc(x)编码过程如下：时钟 信息元 存放器码字 输出码字 D0 D1 D2 0 0 0 0 1 1 1 1 0 1.-.word.zl-2 0 0 1 1 0 3 0 1 1 1 0 4 1 0 1 1 1 5 0 0 1 1 6 0 0 0 1 7 0 0 0 0 可得：632()c xxxxx 4.令(15,11)循环码的生成多项式为1)

26、(4xxxg，计算 1假设信息多项式为1)(810 xxxm，试求编码后的系统码字；2求接收码组1)(414xxxxR的校正子多项式。(1)解题过程如下：10841412442141242()1()()()()mod(1)1()()()1(1010000000010101)n kn kn km xxxm xxm xxxxxb xm xxxxxc xm xxb xxxxxc 2校正多项式如下所示：14434()1()mod()1()1R xxxxS xg xxg xxx 5.码长为n=15 的本原 BCH 码，求不同纠错能力下的 BCH 码各自的生成多项式)(xg。21154mnm 纠错能力：1

27、28mt，所以最多能纠正 7 个错误码。有限域 GF24，4 次本原多项式4()1f xxx，为 f(x)的一个根，可知：410 ，计算 2t=14 个连续幂次为 对应的最小多项式：.-.word.zl-4443212342432456434478924321011()1,()1,()1()1,()1,()1()1,()1,()1()1,()1m xxxm xxxm xxxxxm xxxm xxxm xxxxxm xxxm xxxm xxxmxxxmxxxxxm 43224312133()1,()1,()1xxxxxmxxxm xxx(1)t=1 的码字：(15，11)BCH 码 411()(

28、)1g xLcm m xxx(2)t=2 的码字：(15，7)BCH 码 8764213()()()1gxLcm m x m xxxxx(3)t=3 的码字：(15，5)BCH 码 1085423135()()()()1gxLcm m x m x m xxxxxxx(4)t=4 的码字：(15，1)BCH 码 1413121110987654324()1gxxxxxxxxxxxxxxx(5)t=5 的码字：(15，1)BCH 码 1413121110987654325()1gxxxxxxxxxxxxxxx(6)t=6 的码字：(15，1)BCH 码 1413121110987654326()1

29、gxxxxxxxxxxxxxxx(7)t=7 的码字：(15，1)BCH 码 1413121110987654327()1gxxxxxxxxxxxxxxx 6 构造一个能纠正t=3 个错误符号，码长为 15，m=4 的 RS 码，并求其生成矩阵。码长：n=q-1，216mq，m=4 min217dt n-k=2t=6 k=n-2t=15-6=9 可知 RS 码为：5，9码 设为本原多项式4()1f xxx的根，即：41 t=3，生成多项式 g(x)有 6 个连续的根，61054436296()()g xxxxxxxxxxxxx .-.word.zl-15，9的 RS 码的生成矩阵如下：10144696101446961014469610144696101446961 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 00 0 0 1 0 0 0 0 00 0 0 0 1 0 0 0 0 0 0 0 0 0 1 10144696101446961014469610144696 0 0 0 0 0 0 0 0 0 1 0 00 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 1