信息论与编码试卷及答案

信息论与编码试卷及 一、概念简答题(每题5分，共40分) 1.什么是平均自信息量与平均互信息，比较一下这两个概念的异同, 2.简述最大离散熵定理。对于一个有m个符号的离散信源，其最大熵是多少, 3.解释信息传输率、信道容量、最佳输入分布的概念，说明平均互信息与信源的概率分布、信道的传递概率间分别是什么关系, 4.对于一个一般的通信系统，试给出其系统模型框图，并结合此图，解释数据处理定理。 5.写出香农公式，并说明其物理意义。当信道带宽为5000Hz，信噪比为30dB时求信道容量。 6.解释无失真变长信源编码定理。 7.解释有噪信道编码定理。 8.什么是保真度准则,对二元信源，其失真矩阵，求a>0时率失真函数的和, 二、综合题(每题10分，共60分) 1.黑白气象传真图的消息只有黑色和白色两种，求: 1) 黑色出现的概率为0.3，白色出现的概率为0.7。给出这个只有两个符号的信源X的数学模型。假设图上黑白消息出现前后没有关联，求熵; 2) 假设黑白消息出现前后有关联，其依赖关系为:，， ，，求其熵 ; 2.二元对称信道如图。 ; 1)若，，求和; 2)求该信道的信道容量和最佳输入分布。 3.信源空间为，试分别构造二元和三元霍夫曼码，计算其平均码长和编码效率。 4.设有一离散信道，其信道传递矩阵为，并设，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。 5.已知一(8，5)线性分组码的生成矩阵为。 求:1)输入为全00011和10100时该码的码字;2)最小码距。 6.设某一信号的信息传输率为5.6kbit/s，在带宽为4kHz的高斯信道中传输，噪声功率谱NO=5×10,6mw/Hz。试求: (1)无差错传输需要的最小输入功率是多少, (2)此时输入信号的最大连续熵是多少,写出对应的输入概率密度函数的形式。 一、 概念简答题(每题5分，共40分) 1.答:平均自信息为 表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2.答:最大离散熵定理为:离散无记忆信源，等概率分布时熵最大。 最大熵值为。 3.答:信息传输率R指信道中平均每个符号所能传送的信息量。信道容量是一个信道所能达到的最大信息传输率。信息传输率达到信道容量时所对应的输入概率分布称为最佳输入概率分布。 平均互信息是信源概率分布的?型凸函数，是信道传递概率的U型凸函数。 4.答:通信系统模型如下: 数据处理定理为:串联信道的输入输出X、Y、Z组成一个马尔可夫链，且有， 。说明经数据处理后，一般只会增加信息的损失。 5.答:香农公式为，它是高斯加性白噪声信道在单位时间内的信道容量，其值取决于信噪比和带宽。 由得，则 6.答:只要，当N足够长时，一定存在一种无失真编码。 ,C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 7.答:当R 8.答:1)保真度准则为:平均失真度不大于允许的失真度。 2)因为失真矩阵中每行都有一个0，所以有，而。 二、综合题(每题10分，共60分) 1.答:1)信源模型为 2)由得 则 2.答:1) 2)，最佳输入概率分布为等概率分布。 3.答:1)二元码的码字依序为:10，11，010，011，1010，1011，1000，1001。 平均码长，编码效率 2)三元码的码字依序为:1，00，02，20，21，22，010，011。 平均码长，编码效率 4.答:1)最小似然译码准则下，有， 2)最大错误概率准则下，有， 5.答:1)输入为00011时，码字为00011110;输入为10100时，码字为10100101。 2) 6.答:1)无错传输时，有 即则 2)在时，最大熵 对应的输入概率密度函数为 信息论习题集 一、名词解释(每词2分)(25道) 1、“本体论”的信息(P3) 2、“认识论”信息(P3) 3、离散信源(11) 4、自信息量(12) 5、离散平稳无记忆信源(49) 6、马尔可夫信源(58) 7、信源冗余度 (66) 8、连续信源 (68) 9、信道容量 (95) 10、强对称信道 (99) 11、对称信道 (101-102)12、多符号离散信道(109) 13、连续信道 (124) 14、平均失真度 (136) 15、实验信道 (138) 16、率失真函数 (139) 17、信息价值率 (163) 18、游程序列 (181) 19、游程变换 (181) 20、L-D编码(184)、 21、冗余变换 (184) 22、BSC信道 (189) 23、码的最小距离 (193)24、线性分组码 (195) 25、循环码 (213) 二、填空(每空1分)(100道) 1、 在认识论层次上研究信息的时候，必须同时考虑到 形式、含义和效用 三个方面的因素。 2、 1948年，美国数学家 香农 发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。 3、 按照信息的性质，可以把信息分成 语法信息、语义信息和语用信息 。 4、 按照信息的地位，可以把信息分成 客观信息和主观信息 。 5、 人们研究信息论的目的是为了 高效、可靠、安全 地交换和利用各种各样的信息。 6、 信息的 可度量性 是建立信息论的基础。 7、 统计度量 是信息度量最常用的方法。 8、 熵 是香农信息论最基本最重要的概念。 9、 事物的不确定度是用时间统计发生 概率的对数 来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用 随机矢量 描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为 其发生概率对数的负值 。 12、自信息量的单位一般有 比特、奈特和哈特 。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ? 。 15、两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 。 16、数据处理定理:当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量 趋于变小 。 17、离散平稳无记忆信源X的N次扩展信源的熵等于离散信源X的熵的 N倍 。 limH(X/XX？X)N12N,1H,N,,,18、离散平稳有记忆信源的极限熵，。 m19、对于n元m阶马尔可夫信源，其状态空间共有 n 个不同的状态。 20、一维连续随即变量X在[a，b]区间内均匀分布时，其信源熵为 log(b-a) 。 2 1log2,eP2221、平均功率为P的高斯分布的连续信源，其信源熵，H(X)=。 c 22、对于限峰值功率的N维连续信源，当概率密度 均匀分布 时连续信源熵具有最大值。 23、对于限平均功率的一维连续信源，当概率密度 高斯分布 时，信源熵有最大值。 P24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P和信源的熵功率 之比 。 25、若一离散无记忆信源的信源熵H(X)等于2.5，对信源进行等长的无失真二进制编码，则编码长度至少为 3 。 n,kim,1,,1i26、m元长度为k，i=1，2，???n的异前置码存在的充要条件是:。 i 27、若把掷骰子的结果作为一离散信源，则其信源熵为 log6 。 2 28、同时掷两个正常的骰子，各面呈现的概率都为1/6，则“3和5同时出现”这件事的自信息量是 log182(1+2 log3)。 2 x,1mp(x),emx,029、若一维随即变量X的取值区间是[0，?]，其概率密度函数为，其中:，m是 H(X),logmeC2X的数学期望，则X的信源熵。 30、一副充分洗乱的扑克牌(52张)，从中任意抽取1张，然后放回，若把这一过程看作离散无记忆信源， log522则其信源熵为 。 31、根据输入输出信号的特点，可将信道分成离散信道、连续信道、半离散或半连续 信道。 32、信道的输出仅与信道当前输入有关，而与过去输入无关的信道称为 无记忆 信道。 33、具有一一对应关系的无噪信道的信道容量C= logn 。 2 34、强对称信道的信道容量C= logn-H。 2ni 35、对称信道的信道容量C= logm-H。 2mi N36、对于离散无记忆信道和信源的N次扩展，其信道容量C= NC 。 N C,kk,137、对于N个对立并联信道，其信道容量 C = 。 N 38、多用户信道的信道容量用 多维空间的一个区域的界限 来表示。 39、多用户信道可以分成几种最基本的类型: 多址接入信道、广播信道 和相关信源信道。 40、广播信道是只有 一个输入端和多个输出端 的信道。 41、当信道的噪声对输入的干扰作用表现为噪声和输入的线性叠加时，此信道称为 加性连续信道 。 P1Xlog(1)，22PN42、高斯加性信道的信道容量C=。 43、信道编码定理是一个理想编码的存在性定理，即:信道无失真传递信息的条件是 信息率小于信道容量 。 1/21/20，， ,,001，，44、信道矩阵代表的信道的信道容量C= 1 。 10，， ,,10,, ,,01，，45、信道矩阵代表的信道的信道容量C= 1 。 46、高斯加性噪声信道中，信道带宽3kHz，信噪比为7，则该信道的最大信息传输速率C= 9 kHz 。 t47、对于具有归并性能的无燥信道，达到信道容量的条件是 p(y)=1/m) 。 j 10，， ,,015，，48、信道矩阵代表的信道，若每分钟可以传递6*10个符号，则该信道的最大信息传输速率C= t10kHz 。 49、信息率失真理论是量化、数模转换、频带压缩和 数据压缩 的理论基础。 50、求解率失真函数的问题，即:在给定失真度的情况下，求信息率的 极小值 。 51、信源的消息通过信道传输后的误差或失真越大，信宿收到消息后对信源存在的不确定性就 越大 ，获得的信息量就越小。 52、信源的消息通过信道传输后的误差或失真越大道传输消息所需的信息率 也越小 。 53、单符号的失真度或失真函数d(x，y)表示信源发出一个符号x，信宿再现y所引起的 误差或失真 。 ijij 0i,j, ,1i,j,54、汉明失真函数 d(x，y)= 。 ij255、平方误差失真函数d(x，y)=(y- x)。 ijji 56、平均失真度定义为失真函数的数学期望，即d(x，y)在X和Y的 联合概率空间P(XY)中 的统ij 计平均值。 57、如果信源和失真度一定，则平均失真度是 信道统计特性 的函数。 DD,DD,D58、如果规定平均失真度不能超过某一限定的值D，即:。我们把称为 保真度准则 。 59、离散无记忆N次扩展信源通过离散无记忆N次扩展信道的平均失真度是单符号信源通过单符号信道的平均失真度的 N 倍。 ,,p(y/x):D,D;i,1,2,？,n,j,1,2,？,mji60、试验信道的集合用P来表示，则P= 。 DD 61、信息率失真函数，简称为率失真函数，即:试验信道中的平均互信息量的 最小值 。 62、平均失真度的下限取0的条件是失真矩阵的 每一行至少有一个零元素 。 63、平均失真度的上限D取{D:j=1，2，???，m}中的 最小值 。 maxj 64、率失真函数对允许的平均失真度是 单调递减和连续的 。 65、对于离散无记忆信源的率失真函数的最大值是 logn 。 2 66、当失真度大于平均失真度的上限时D时，率失真函数R(D)= 0 。 max InfI(X;Y),p(y/x)PD67、连续信源X的率失真函数R(D)= 。 2,1log22R(D),D,,2D68、当时，高斯信源在均方差失真度下的信息率失真函数为 。 69、保真度准则下的信源编码定理的条件是 信源的信息率R大于率失真函数R(D) 。 X010a，，,,，，,,,,,,,P(X)1/21/2a0，，,,，，70、某二元信源其失真矩阵D=，则该信源的D= a/2 。 max X010a，，,,，，,,,,,,,P(X)1/21/2a0，，,,，，71、某二元信源其失真矩阵D=，则该信源的D= 0 。 min X010a，，,,，，,,,,,,,P(X)1/21/2a0，，,,，，72、某二元信源其失真矩阵D=，则该信源的R(D)= 1-H(D/a) 。 73、按照不同的编码目的，编码可以分为三类:分别是 信源编码、信道编码和安全编码 。 74、信源编码的目的是: 提高通信的有效性 。 75、一般情况下，信源编码可以分为 离散信源编码、连续信源编码和相关信源编码 。 76、连续信源或模拟信号的信源编码的理论基础是 限失真信源编码定理 。 ,logp(x),k,1,logp(x)2ii2i77、在香农编码中，第i个码字的长度k和p(x)之间有 关系。 ii Xxxxxxxxx，，,,12345678,,,,,(1/41/41/81/81/161/161/161/16PX)，，,,78、对信源进行二进制费诺编码，其编码效率为 1 。 79、对具有8个消息的单符号离散无记忆信源进行4进制哈夫曼编码时，为使平均码长最短，应增加 2 个概率为0的消息。 80、对于香农编码、费诺编码和哈夫曼编码，编码方法惟一的是 香农编码 。 81、对于二元序列0011100000011111001111000001111111，其相应的游程序列是 23652457 。 82、设无记忆二元序列中，“0”和“1”的概率分别是p和p，则“0”游程长度L(0)的概率为 01 (0)1L,p[L(0)],pp01 。 83、游程序列的熵 等于 原二元序列的熵。 84、若“0”游程的哈夫吗编码效率为η，“1”游程的哈夫吗编码效率为η，且η>η对应的二元序列的0101编码效率为η，则三者的关系是 η>η>η。 01 85、在实际的游程编码过程中，对长码一般采取 截断 处理的方法。 86、“0”游程和“1”游程可以分别进行哈夫曼编码，两个码表中的码字可以重复，但 C码 必须不同。 87、在多符号的消息序列中，大量的重复出现的，只起占时作用的符号称为 冗余位 。 88、“冗余变换”即:将一个冗余序列转换成一个二元序列和一个 缩短了的多元序列 。 89、L-D编码是一种 分帧传送冗余位序列 的方法。 90、L-D编码适合于冗余位 较多或较少 的情况。 91、信道编码的最终目的是 提高信号传输的可靠性 。 92、狭义的信道编码即:检、纠错编码 。 93、BSC信道即:无记忆二进制对称信道 。 94、n位重复码的编码效率是 1/n 。 95、等重码可以检验 全部的奇数位错和部分的偶数位错 。 mind(c,c')c,c'96、任意两个码字之间的最小汉明距离有称为码的最小距d，则d=。 minmin d,1,,min,,2，，97、若纠错码的最小距离为d，则可以纠正任意小于等于t= 个差错。 min 98、若检错码的最小距离为d，则可以检测出任意小于等于l= d-1 个差错。 minmin 99、线性分组码是同时具有 分组特性和线性特性 的纠错码。 100、循环码即是采用 循环移位特性界定 的一类线性分组码。 三、判断(每题1分)(50道) 1、 必然事件和不可能事件的自信息量都是0 。错 p(x)i2、 自信息量是的单调递减函数。对 3、 单符号离散信源的自信息和信源熵都具有非负性。对 4、 单符号离散信源的自信息和信源熵都是一个确定值。错 5、 单符号离散信源的联合自信息量和条件自信息量都是非负的和单调递减的。对 6、 自信息量、条件自信息量和联合自信息量之间有如下关系: I(xy),I(x)，I(y/x),I(y)，I(x/y)ijijijij 对 7、 自信息量、条件自信息量和互信息量之间有如下关系: I(x;y),I(x),I(x/y),I(y),I(y/x)ijiijjji 对 8、 当随即变量X和Y相互独立时，条件熵等于信源熵。对 9、 当随即变量X和Y相互独立时，I(X;Y)=H(X) 。错 10、信源熵具有严格的下凸性。错 11、平均互信息量I(X;Y)对于信源概率分布p(x)和条件概率分布p(y/x)都具有凸函数性。 对 iji12、m阶马尔可夫信源和消息长度为m的有记忆信源，其所含符号的依赖关系相同。 错 13、利用状态极限概率和状态一步转移概率来求m阶马尔可夫信源的极限熵。 对 14、N维统计独立均匀分布连续信源的熵是N维区域体积的对数。 对 15、一维高斯分布的连续信源，其信源熵只与其均值和方差有关。 错 16、连续信源和离散信源的熵都具有非负性。 错 17、连续信源和离散信源都具有可加性。 对 18、连续信源和离散信源的平均互信息都具有非负性。 对 19、定长编码的效率一般小于不定长编码的效率。 对 20、若对一离散信源(熵为H(X))进行二进制无失真编码，设定长码子长度为K，变长码子平均长度为KK，一般>K。 错 21、信道容量C是I(X;Y)关于p(x)的条件极大值。 对 i 22、离散无噪信道的信道容量等于logn，其中n是信源X的消息个数。 错 2 1py(),jm23、对于准对称信道，当时，可达到信道容量C。错 24、多用户信道的信道容量不能用一个数来代表。 对 25、多用户信道的信道容量不能用一个数来代表，但信道的信息率可以用一个数来表示。错 26、高斯加性信道的信道容量只与信道的信噪有关。 对 27、信道无失真传递信息的条件是信息率小于信道容量。对 28、最大信息传输速率，即:选择某一信源的概率分布(p(x))，使信道所能传送的信息率的最大值。 错 i 29、对于具有归并性能的无燥信道，当信源等概率分布时(p(x)=1/n)，达到信道容量。 错 i 30、求解率失真函数的问题，即:在给定失真度的情况下，求信息率的极小值。对 31、信源的消息通过信道传输后的误差或失真越大，信宿收到消息后对信源存在的不确定性就越小，获得的信息量就越小。 错 32、当p(x)、p(y/x)和d(x，y)给定后，平均失真度是一个随即变量。 错 ijiij 33、率失真函数对允许的平均失真度具有上凸性。对 34、率失真函数没有最大值。 错 35、率失真函数的最小值是0 。对 36、率失真函数的值与信源的输入概率无关。错 37、信源编码是提高通信有效性为目的的编码。 对 38、信源编码通常是通过压缩信源的冗余度来实现的。 对 39、离散信源或数字信号的信源编码的理论基础是限失真信源编码定理。 错 40、一般情况下，哈夫曼编码的效率大于香农编码和费诺编码。 对 41、在编m(m>2)进制的哈夫曼码时，要考虑是否需要增加概率为0的码字，以使平均码长最短。 对 42、游程序列的熵(“0”游程序列的熵与“1”游程序列的熵的和)大于等于原二元序列的熵。 错 43、在游程编码过程中，“0”游程和“1”游程应分别编码，因此，它们的码字不能重复。 错 44、L-D编码适合于冗余位较多和较少的情况，否则，不但不能压缩码率，反而使其扩张。 对 45、狭义的信道编码既是指:信道的检、纠错编码。 对 46、对于BSC信道，信道编码应当是一对一的编码，因此，消息m的长度等于码字c的长度。 错 47、等重码和奇(偶)校验码都可以检出全部的奇数位错。 对 48、汉明码是一种线性分组码。对 49、循环码也是一种线性分组码。 对 50、卷积码是一种特殊的线性分组码。 错 四、简答(每题4分)(20道) 1、 信息的主要特征有哪些,(4) 2、 信息的重要性质有哪些,(4) 3、 简述几种信息分类的准则和方法。(5) 4、 信息论研究的主要有哪些,(8) 5、 简述自信息的性质。(13) 6、 简述信源熵的基本性质。(23) 7、 简述信源熵、条件熵、联合熵和交互熵之间的关系。(48) 8、 信道的分类方法有哪些,(93-94) 9、 简述一般离散信道容量的计算步骤。(107) 10、简述多用户信道的分类。(115-116) 11、简述信道编码定理。(128) 12、简述率失真函数的性质。(140-145) 13、简述求解一般离散信源率失真函数的步骤。(146-149) 14、试比较信道容量与信息率失真函数。(164) 15、简述编码的分累及各种编码的目的。(168) 16、简述费诺编码的编码步骤。(170) 17、简述二元哈夫曼编码的编码步骤。(173) 18、简述广义的信道编码的分类及各类编码的作用。(188) 19、简述线性分组码的性质。(196) 20、简述循环码的系统码构造过程。(221) “信息论与编码”试题 2007级硕士研究生 2008年6月14日 一、基本概念题(闭卷部分，每题4分，共40分。1小时内完成并交卷) 1.试证明n维随机变量的共熵，不大于它们各自的熵之和。 证明: n 即证明 H(X,X,？,X),H(X)12,ni,1i 因为 0 , I (X; Y) = H(X) – H(X/Y)， 所以 H(X/Y) ,H(X)。 由共熵的定义和熵的链接准则，有 H(X, X) = H(X) +H(X/ X) ,H(X1)，H(X2) 1 2 1 2 1 H(X, X, X) = H(X)+H(X, X/ X) 1 2 3 1 2 3 1 = H(X)+H(X/ X)+H(X/ X, X) , H(X)+H(X) +H(X) 1 2 1 3 2 1 1 2 3 „ nn H(X,X,？,X),H(X/X,？,X),H(X),,12nii,11ii,1i,1证毕。 2.请给出信源编码器的主要任务以及对信源编码的基本。解:信源编码器的主要任务是 完成输入消息集合与输出代码集合之间的映射。 对信源编码有如下基本要求: (1)选择合适的信道基本符号，以使映射后的代码适应信道。例如，ASCII码选用了 16进制数。 (2)寻求一种方法，把信源发出的消息变换成相应的代码组。这种方法就是编码，变 换成的代码就是码字。 (3)编码应使消息集合与代码组集合中的元素一一对应。 3.请给出平均码长界定定理及其物理意义。解:平均码长界定定理:若一个离散无记忆信源 X，具有熵H(X)，对其编码用D种基本符号，则总可以找到一种无失真信源编码，构成单 义可译码，使其平均码长满足 H(X)H(X),b,，1 logDlogD 平均码长界定定理的物理意义: 编码所追求的，是在单义可译前提下寻求尽可能小的平均码长。平均码长界定定理指出， H()Xb平均码长的下界值。对于给定信源空间{X，P(X)}的离散信源，其熵H(X)是确,minlogD b定的数值，如果信道基本符号也是确定的，即D也是给定的，则也就定了。这意味着，min 如果不改变信源的统计特性，减小的潜力，到了其下界值也就到了极限了。因此，如果要b进一步提高编码效率，必须对信源本身进行研究，例如改变信源本身的统计特性，对其进行 扩展。 4.请给出连续信源分别为均匀分布、高斯分布和指数分布时信源的相对熵。解:(1)均匀分 布连续信源的相对熵为 bh(x),,p(x)logp(x)dx,a ,log(b,a) (2)高斯分布连续信源X的相对熵为 ,hxpxpxdx()()ln(),,,,, 2,,,，，1()xm,,,,,,pxdx()lnexp,,,,2,2,,2,,,2π,，，,, 2,,1()xm,,,，pxdxpxdx()ln()2,,2,,,,22π,,22,,，ln2π 中间步骤可以省略 ,22, 112,，ln(2π),22 112,，ln(2π)lne,22 12,ln(2πe),2 (3)指数分布连续信源X的相对熵为 , h(x),,p(x)lnp(x)dx,0 xx,，，，，,,11aa,,,,,elnedx,aa,,,,0，，，， xx,,,,11aa,lna,edx，xedx 中间步骤可以省略 ,,2aa00 ,lna，lne ,lnae 5.请给出失真函数、平均失真度、保真度准则、信息率失真函数的定义。解:失真函数定义:对于有失真的信息传输系统，对应于每一对(a,b)(n = 1, 2, …r;j=1, 2, …, s)，定义一个i j 非负实值函数 dabirjs(,)0(1,2,;1,2,),,,,,,,,, ij 表示信源发出符号a而经信道传输后再现成信道输出符号集合中的b所引起的误差或失真，ij 称之为a和b之间的失真函数(Distortion Function)，简写为d。 ijij 平均失真度定义:若信源和信宿的消息集合分别为X:{a, a, …, a}和Y:{b, b, …, b}，12r12s其概率分别为P (a)和P (b) (i=1, 2, …, r ; j=1, 2, …, s )，信道的转移概率为P (b /a)，失真ijji函数为d (a, b)，则称随机变量X和Y的联合概率P (a b )对失真函数d (a, b)的统计平均值ijijij D为该通信系统的平均失真度。 保真度准则定义:从平均的意义上来说，信道每传送一个符号所引起的平均失真，不能 DD,超过某一给定的限定值D，即要求，称这种对于失真的限制条件为保真度准则。 信息率失真函数定义:用给定的失真D为自变量来描述的信息传输速率，称为信息率失真函数，用R(D)表示。 n6. 试证明(n, k)循环码的生成多项式g(x)是x+1的因式。 k证明:将生成多项式g (x)乘以，得 x kkn()xgxgxqxx()()()(1),，， k()kxgx()gx()由于次数为n，故上式中q(x) = 1，而是g (x)循环左移k次所得，它是g(x) ()knkgxuxgx()()(),xxuxgxfxgx，,，,1[()]()()()的倍式，设，故有 证毕。 7. 请给出域的定义并说明集合{0, 1, 2}可否构成域及其理由。 解:域的定义:非空元素集合F，若在F中定义了加和乘两种运算，且满足 (1) F关于加法构成Abel 群，其加法恒元记为0; ; (2) F中非零元素全体对乘法构成Abel 群，其乘法恒元记为1 (3) 加法和乘法间有如下分配律:a(b+c)=ab+ac，(b+c)a=ba+ca， 则称F是一个域。 或者说，域是一个可换的、有单位元的、非零元素有逆元的环。 集合{0, 1, 2}可以构成域。对该集合中的元素定义模3加和模3乘这两种运算，完全符合域必须满足的3个条件。 8. 请给出本原多项式的定义，并用一个实例来说明它的性质。 nm解:本原多项式的定义:若m次既约多项式p(x)除尽的x+1的最小正整数n满足n=2–1，称p(x)为本原多项式。 用实例来说明本原多项式有如下性质: 1)本原多项式一定是既约的(因为它是用既约多项式来定义的)，但既约多项式不一定是本原的。 415n4例如:4次既约多项式x+x+1能除尽x +1，但除不尽任何1 ? n < 15的x +1，所以x 432155+x +1是本原的;但同样是4次既约多项式x+x +x+x+1，能除尽x +1，但也能除尽 x+1， 432所以x+x +x+x+1是既约的但不是本原的。 2)对于给定的m，可能有不止一个m次本原多项式。 5352例如，对于m = 5，x+x +1是本原多项式，x +x +1也是。 (,)nk9. 试说明循环码对突发错误的检测能力。 (,)nk解:(1)循环码能检测长为n – k或更短的任何突发错误，包括首尾相接突发错误。 – ( n – k +1)(,)nk(2)循环码对n – k +1位长的突发错误不能被检出所占的概率最大是2。 – ( n – (3)如果l > n – k +1，则循环码不能检测长为l的突发错误所占的比值为2 (,)nk k )。 因此，循环码检测突发错误非常有效。 10. 请给出最佳自由距离卷积码的定义并简要说明如何获得具有最佳自由距离的卷积码。 解:最佳自由距离卷积码的定义:对于相同的码率R和相同的电路复杂性(存储单元总数m等)的各种卷积码，使得自由距离d最大的编码称为最佳自由距离(OFD，Optimal Free f Distance)码。 为了得到各种OFD码，通常采用计算机搜索的方法，即对于给定的存储单元总数m所有可能的卷积码编码器，首先排除恶性卷积码，然后对应每一可能的卷积码编码器求其自由距离d，逐一比较得到自由距离d最大者即为最佳自由距离卷积码编码器。 ff 二、综合题(开卷部分，每题10分，共60分。闭卷部分交卷后方可参阅参考资料) 1. 某通信系统的信源输出仅有2个符号a、b，拟采用Lempel-Ziv编码后送信道传输，若某次通信需传输的符号序列为“aaaaaaa bbbbbbb aaaaaaaa bbbbbbb a b aaaaaa bbbbbbb aaaaaaaaaaaaaaaaab”，请给出其Lempel-Ziv编码结果并简要说明该编码的性能。 解: 编码结果 编码包 <0,7,b> <1,6,a> <15,15,b> <15,14,a> <1,15,b> 内容 aaaaaaa b bbbbbb a aaaaaaab bbbbbba b aaaaaabbbbbbba a aaaaaaaaaaaaaaab 码段符号 8 7 16 15 16 数 如果把a、b看作为1、0，对编码结果(即每个编码包)可以用4+4+1=9-bit表示，传输该序列用5个编码包即45-bit，而该序列有62-bit，因此该编码起到压缩作用。 2(若题1信源符合a、b的出现概率分别为0.9和0.1，拟对其采用3重扩展后再进行霍夫曼编码，请给出编码过程及结果，并求该种信源编码的效率。 解: aaa:0.729 aab:0.081 aba:0.081 abb:0.009 baa:0.081 bab:0.009 bba:0.009 bbb:0.001 设aaa、aab、???bbb分别为x、x、???x，按照概率大小依此排列，有 129 x 1 x 2 x 3 x5 x 4 x 6 x 7 x8 具体编码过程、结果、编码效率―略。 3. 为了在有噪信道中获得可靠的通信，拟对题2的霍夫曼编码结果再进行信道编码，若霍夫曼编码的输出序列为aabb baaa baba bbaa bbba abbb abab???，试给出采用戈莱码(23，12)编码的第一个码字;如果信道编码不是采用戈莱码而是采用缩短的BCH(120，78)编码，试给出构造该种编码的生成多项式的方法以及缩短的方法，分析其纠错和检错能力，简述其编码和译码过程。 解: 11106542(1)对戈莱码(23，12)采用生成多项式为g(x) = x+ x+ x+ x+ x + x+1，即110001110101 令a,1，b,0，则要编码的序列为1100 0111 0101 0011 0001 1000 1010 ???;由于戈莱码是非本原BCH码，其编码规则与BCH码相同，现采用系统码，第一个码字的编码过程如下: 110001110101 00000000000 110001110101 ――――――――――――― 00000000000 因此第一个戈莱码码字为110001110101 00000000000，即监督位为全0(11位)。 (2)缩短的BCH(120，78)原码为BCH(127，85)，构造该种编码的生成多项式，可以由 6 g(x) =LCM{, (x) +, (x) + , (x) x+???+, (x)} 1232 t 77i357对于本题，127,2，(x)是GF(2)上的元素 的最小多项式，求出、 、 、 的最小,,,,,,i 多项式，将它们相乘即得到该种编码能够纠5个错的生成多项式(次数为127,85,42)。 缩短的方法取原码BCH(127，85)中的一个子集，其消息位的前7位均为0，编码方法与原码相同，只是传输时前7位0不要传送。 由求其生成多项式的过程已知该种编码的原码能够纠5个随机错误，至少能够检测10个随机错误，由于其监督位的个数位42，它能够检测42个突发错误并依概率检测大于42个突发错误。 其编码方法上面已经说明，可以采用系统码的编码方法，只是传输时前7位0不要传送。 解码时通常先补上缩短的0的位数，再按照原码的译码方法进行译码，通常采用伴随式译码方法。即:先求出接收序列的伴随式;然后根据伴随式求错误位置，本题用查表法将很复杂，拟采用错误位置多项式的方法来求错误位置;得到错误位置后纠正之。 4. 假设对题2的霍夫曼编码输出进行卷积编码，采用的卷积码编码器为(3，1，2)，请给出你设计的卷积码编码器并说明其是最佳自由距离卷积码，用状态图方法给出输入序列(aabbabab???)的编码输出和用网格图方法给出接收序列(aba abb aab baa abb aba???)的译码输出。 解: 可以将教材中图12.7变成系统卷积码，说明它不是恶性卷积码并通过与其他各类抽头方式比较知它的自由距离为最大，故是最佳自由距离卷积码。 具体的编码器、状态图、网格图―略。 5. (1)试根据香农第二定理说明为什么交织虽然没有注入冗余度但却提高了纠突发错误能力;(2)试给出利用信息加密技术进行保密通信的系统框图(加密信道模型)并简述其工作原理，说明为什么非通信对像虽然收到了密文但在不能成功破译时其获得的信息量为0。 解:(1)设交织深度为,，则交织的结果等效为编码长度扩大了, 倍，其禁用码组与许用码组之比也扩大了, 倍，根据香农第二定理，在R