信息理论与编码-期末试卷A及答案

题号题号一二三四总分统分人题分35102332100得分一、填空题（每空1分，共35分）得分||阅卷人|1、1948年，美国数学家发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。信息论的基础理论是，它属于狭义信息论。2、信号是的载体，消息是的载体。3、某信源有五种符号,,,,abcde，先验概率分别为5.0aP，25.0bP，125.0cP，0625.0edPP，则符号“a”的自信息量为bit，此信源的熵为bit/符号。4、某离散无记忆信源X，其概率空间和重量空间分别为12340.50.250.1250.125XxxxxP和12340.5122Xxxxxw，则其信源熵和加权熵分别为和。5、信源的剩余度主要来自两个方面，一是，二是。6、平均互信息量与信息熵、联合熵的关系是。7、信道的输出仅与信道当前输入有关，而与过去输入无关的信道称为信道。8、马尔可夫信源需要满足两个条件：一、；二、。9、若某信道矩阵为0100010000001100，则该信道的信道容量C=__________。10、根据是否允许失真，信源编码可分为和。11、信源编码的概率匹配原则是：概率大的信源符号用，概率小的信源符号用。（填短码或长码）12、在现代通信系统中，信源编码主要用于解决信息传输中的性，信道编码主要用于解决信息传输中的性，保密密编码主要用于解决信息传输中的安全性。13、差错控制的基本方式大致可以分为、和混合纠错。14、某线性分组码的最小汉明距dmin=4，则该码最多能检测出个随机错，最多能纠正个随机错。15、码字101111101、011111101、100111001之间的最小汉明距离为。16、对于密码系统安全性的评价，通常分为和两种标准。17、单密钥体制是指。18、现代数据加密体制主要分为和两种体制。19、评价密码体制安全性有不同的途径，包括无条件安全性、和。20、时间戳根据产生方式的不同分为两类：即和。二、选择题（每小题1分，共10分）得分||阅卷人|1、下列不属于消息的是（）。A.文字B.信号C.图像D.语言2、设有一个无记忆信源发出符号A和B，已知4341)(,)(BpAp，发出二重符号序列消息的信源，无记忆信源熵)(2XH为（）。A.0.81bit/二重符号B.1.62bit/二重符号C.0.93bit/二重符号D.1.86bit/二重符号3、同时扔两个正常的骰子，即各面呈现的概率都是1/6，若点数之和为12，则得到的自信息为（）。A.－log36bitB.log36bitC.－log(11/36)bitD.log(11/36)bit4、二进制通信系统使用符号0和1，由于存在失真，传输时会产生误码，用符号表示下列事件，x0:发出一个0、x1:发出一个1、y0:收到一个0、y1:收到一个1，则已知收到的符号，被告知发出的符号能得到的信息量是（）。A.H(X/Y)B.H(Y/X)C.H(X,Y)D.H(XY)5、一个随即变量x的概率密度函数P(x)=x/2，V20x，则信源的相对熵为（）。A.0.5bitB.0.72bitC.1bitD.1.44bit信息论与编码6、下面哪一项不属于熵的性质：（）A．非负性B．完备性C．对称性D．确定性7、根据树图法构成规则，（）A．在树根上安排码字B．在树枝上安排码字C．在中间节点上安排码字D．在终端节点上安排码字8、下列组合中不属于即时码的是（）。A.{0，01，011}B.{0，10，110}C.{00，10，11}D.{1，01，00}9、已知某（6，3）线性分组码的生成矩阵011101110001111010G，则不用计算就可判断出下列码中不是该码集里的码是（）。A.000000B.110001C.011101D.11111110、下列保密编码中属于现代密码体制的是（）A.凯撒密码B.Vigenere密码C.韦维纳姆密码D.DES加密算法三、简答题（四小题，共23分）得分||阅卷人|1、请简述现代密码系统应当满足的条件。(4分)2、请简述连续信源最大熵定理的主要内容。（6分）3、请解释最小错误概率译码准则，最大似然译码准则和最小距离译码准则的含义，并说明三者的关系。（5分）答：4、已知密钥为yes，请利用多表代换密码中的Vigenere（维吉尼亚）密码原理分别对下列明文和密文进行编码和译码。明文：AMathematicalTheoryofCommunication；密文：Geeyhgaxgp(需给出码表或编译码过程，8分)信息论与编码四、计算题（四小题，共32分）得分||阅卷人|1、居住在某地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占总数的一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？（5分）2、设离散符号信源为121/43/4xxXP，试求：（1）信源的熵、熵的相对效率以及剩余度；（2）求二次扩展信源的概率空间及其信源熵。(10分)3、已知6符号离散信源的出现概率为321321161814121654321aaaaaa，试写出Huffman编码的码字并求其平均码长。（7分）4、已知一个(5,3)线性分组码C的生成矩阵为：11001G0110100111,（1）求系统生成矩阵及校验矩阵；（2）列出C的信息位与系统码字的映射关系；（3）求收到r=11101时的译码步骤与译码结果。(10分)信息论与编码2015-2016年第2学期《信息论与编码》期末考试A卷参考答案一、填空题（每空1分，共35分）1、香农、香农信息论；2、消息、信息；3、1、15/8；4、7/4、9/4；5、信源符号间的相关性、信源符号的统计不均匀性；6、I(X;Y)=H(X)+H(Y)-H(XY)；7、无记忆；8、某一时刻信源符号的输出只与此时刻信源状态有关，与之前的状态和输出符号无关；信源在t时刻的状态由当前输出符号及t-1时刻信源的状态唯一确定；9、2bit/符号；10、无失真信源编码和限失真信源编码;11、短码、长码；12、有效性、可靠性；13、前向纠错、反馈重发；14、3、1；15、2；16、理论保密性、实际保密性；17、在加密和解密过程中，加、解密密钥相同或从一个容易得出另一个的密码体制；18、公钥体制、私钥体制；填单钥体制、双钥体制）或（对称加密体制、非对称加密体制）也可；19、计算安全性、可证明安全性；20、自建时间戳、具有法律效力的时间戳二、选择题（每小题1分，共10分）BBBACBDADD三、简答题（四小题，共23分）1、请简述现代密码系统应当满足的条件。(4分)答：一个安全的现代密码系统应当满足以下几点要求：(每小点1分)（1）系统即使达不到理论上不可破译，也应当是实际上不可破译的。（2）系统的保密性不依赖于对加密、解密算法和系统的保密，而仅仅依赖于密钥的保密性。、（3）加密、解密算法适用于所有密钥空间的元素。（4）加密、解密运算简单快捷，易于实现。2、请简述连续信源最大熵定理的主要内容。（6分）答：连续信源最大熵定理主要内容如下：（每小点2分）（1）峰值功率受限条件下信源的最大熵定理：若某信源输出信号的峰值功率受限，即信号的取值被限定在某一有限范围（假设为[a,b]）内，则在限定的范围内，当输出信号概率密度分布为均匀分布时，该信源具有最大熵，且为log()ba。（2）平均功率受限条件下信源的最大熵定理：若某信源输出信号的平均功率和均值被限定，则当其输出信号幅度的概率密度函数是高斯分布时，该信源达到最大熵值，且最大熵值为12log2eP。（3）均值受限条件下信源的最大熵定理：若某连续信源X输出非负信号的均值被限定，则其输出信号幅度为指数分布时，信源X具有最大熵，且其值为log2em。3、请解释最小错误概率译码准则，最大似然译码准则和最小距离译码准则的含义，并说明三者的关系。（5分）答：最小错误概率译码准则下，将接收序列译为后验概率最大时所对应的码字（1分）。最大似然译码准则下，将接收序列译为信道传递概率最大时所对应的码字。(1分)最小距离译码准则下，将接收序列译为与其距离最小的码字。（1分）三者关系为：输入为等概率分布时，最大似然译码准则等效于最小错误概率译码准则。（1分）在二元对称无记忆信道中，最小距离译码准则等效于最大似然译码准则。（1分）4、已知密钥为yes，请利用多表代换密码中的Vigenere（维吉尼亚）密码原理分别对下列明文和密文进行编码和译码。明文：AMathematicalTheoryofCommunication；密文：Geeyhgaxgp(需给出码表或编译码过程，8分)答：我们已知26个字母的排列如下表ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425根据提供的明文，可以得出密文YQSRLWKELGGSJXZCSJWSXASEKYFGGSRMGL,编码过程如下表所示（5分）A0M12A0T19H7E4M12A0T19I8C2A0L11T19H7E4O14R17Y24O14F5C2O14M12M12U20N13I8C2A0T19I8O14N13Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24YQSRLWKELGGSJXZCSJWSXASEKYFGGSRMGL根据提供的密文，可以得出译码后的明文为:IAMADOCTOR。译码过程如下表所示：(3分)G6E4E4Y24H7G6A0X23G6P15Y24E4S18Y24E4S18Y24E4S18Y24I8A0M12A0D3O14C2T19O14R17四、计算题（四小题，共32分）1、居住在某地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占总数的一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？（5分）解：设A表示“大学生”这一事件，B表示“身高1.60以上”这一事件，则P(A)=0.25p(B)=0.5p(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分）2、设离散符号信源为4/34/121xxPXX，试求：（1）信源的熵、熵的相对效率以及剩余度；（2）求二次扩展信源的概率空间及其信源熵。（10分）解：（1）22max2()1/4log43/4log(4/3)0.811/()/()()/log2()81.1%11()18.9%HXbitHXHXHXHXRHX符号，（4分）（2）二次扩展信源的概率空间为：（3分）X\X1x2x1x1/163/162x3/169/162222()1/16log163/16log(16/3)3/16log(16/3)9/16log(16/9)2()1.622/HXXHXbit符号（3分）3、已知6符号离散信源的出现概率为321321161814121654321aaaaaa，试写出Huffman编码的码字并计算平均码长。（7分）解:Huffman编码为：a10.5a20.25a30.125a40.0625a50.03125a60.031250.06250.1250.250.51.01111000001符号概率码字10100100010000100000（5分）其他正确的Huffman编码也给分。平均码长符号码元/933.15*3215*3214*1613*812*411*21l（2分）4、已