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维随机变量的共熵，不大于它们各自的熵之和。
证明：
即证明错误！未找到引用源。 因为 0 ? I (X; Y) = H(X) – H(X/Y)， 所以 H(X/Y) ?H(X)。 由共熵的定义和熵的链接准则，有
H(X 1, X 2) = H(X 1) +H(X 2/ X 1) 错误！未找到引用源。 H(X 1, X 2, X 3) = H(X 1)+H(X 2, X 3/ X 1)
= H(X 1)+H(X 2/ X 1)+H(X 3/ X 2, X 1) ? H(X 1)+H(X 2) +H(X 3)
…
错误！未找到引用源。 证毕。
2.请给出信源编码器的主要任务以及对信源编码的基本要求。解：信源编码器的主要任务是完成输入消息集合与输出代码集合之间的映射。
对信源编码有如下基本要求：
（1）选择合适的信道基本符号，以使映射后的代码适应信道。例如，ASCII码选用了16进制数。
（2）寻求一种方法，把信源发出的消息变换成相应的代码组。这种方法就是编码，变换成的代码就是码字。
（3）编码应使消息集合与代码组集合中的元素一一对应。
3.请给出平均码长界定定理及其物理意义。解：平均码长界定定理：若一个离散无记忆信源X，具有熵H(X)，对其编码用D种基本符号，则总可以找到一种无失真信源编码，构成单义可译码，使其平均码长满足
错误！未找到引用源。
平均码长界定定理的物理意义：
编码所追求的，是在单义可译前提下寻求尽可能小的平均码长。平均码长界定定理指出，平均码长的下界值错误！未找到引用源。。对于给定信源空间{X，P(X)}的离散信源，其熵H(X)是确定的数值，如果信道基本符号也是确定的，即D也是给定的，则错误！未找到引用源。也就定了。这意味着，如果不改变信源的统计特性，减小错误！未找到引用源。的潜力，到了其下界值也就到了极限了。因此，如果要进一步提高编码效率，必须对信源本身进行研究，例如改变信源本身的统计特性，对其进行扩展。
4.请给出连续信源分别为均匀分布、高斯分布和指数分布时信源的相对熵。解：（1）均匀分布连续信源的相对熵为
h(x)??p(x)dx?p(x)logab
?log(b?a)
（2）高斯分布连续信源X的相对熵为 错误！未找到引用源。 中间步骤可以省略
（3）指数分布连续信源X的相对熵为 错误！未找到引用源。 中间步骤可以省略
5.请给出失真函数、平均失真度、保真度准则、信息率失真函数的定义。解：失真函数定义：对于有失真的信息传输系统，对应于每一对（ai, bj）（n = 1, 2, …r；j=1, 2, …, s），定义一个非负实值函数
错误！未找到引用源。
表示信源发出符号ai而经信道传输后再现成信道输出符号集合中的bj所引起的误差或失真，称之为
ai和bj之间的失真函数（Distortion Function），简写为dij。
平均失真度定义：若信源和信宿的消息集合分别为X:{a1, a2, …, ar}和Y:{b1, b2, …, bs}，其概率分别为P (ai)和P (bj) (i=1, 2, …, r ; j=1, 2, …, s )，信道的转移概率为P (bj /ai)，失真函数为d (ai, bj)，则称随机变量X和Y的联合概率P (ai bj )对失真函数d (ai, bj)的统计平均值为该通信系统的平均失真度错误！未找到引用源。。
保真度准则定义：从平均的意义上来说，信道每传送一个符号所引起的平均失真，不能超过某一给定的限定值D，即要求错误！未找到引用源。，称这种对于失真的限制条件为保真度准则。
信息率失真函数定义：用给定的失真D为自变量来描述的信息传输速率，称为信息率失真函数，用R(D)表示。
6. 试证明(n, k)循环码的生成多项式g(x)是xn+1的因式。
证明：将生成多项式g (x)乘以错误！未找到引用源。，得
错误！未找到引用源。
由于错误！未找到引用源。次数为n，故上式中q(x) = 1，而错误！未找到引用源。是g (x)循环左移k次所得，它是g(x)的倍式，设错误！未找到引用源。，故有错误！未找到引用源。
证毕。
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. 请给出本原多项式的定义，并用一个实例来说明它的性质。
解：本原多项式的定义：若m次既约多项式p(x)除尽的xn+1的最小正整数n满足n=2m–1，称p(x)为本原多项式。
用实例来说明本原多项式有如下性质：
1）本原多项式一定是既约的（因为它是用既约多项式来定义的），但既约多项式不一定是本原的。
例如：4次既约多项式x4+x+1能除尽x15 +1，但除不尽任何1 ≤ n < 15的xn +1，所以x4 +x +1是本原的；但同样是4次既约多项式x4+x3 +x2+x+1，能除尽x15 +1，但也能除尽 x5+1，所以x4+x3 +x2+x+1是既约的但不是本原的。
2）对于给定的m，可能有不止一个m次本原多项式。
例如，对于m = 5，x5+x3 +1是本原多项式，x5 +x2 +1也是。 9. 试说明错误！未找到引用源。循环码对突发错误的检测能力。
解：（1）错误！未找到引用源。循环码能检测长为n – k或更短的任何突发错误，包括首尾相接突发错误。
（2）错误！未找到引用源。循环码对n – k +1位长的突发错误不能被检出所占的概率最大是2–
( n – k +1)
。
（3）如果l > n – k +1，则错误！未找到引用源。循环码不能检测长为l的突发错误所占的比值为2 – ( n – k )。
因此，循环码检测突发错误非常有效。
10. 请给出最佳自由距离卷积码的定义并简要说明如何获得具有最佳自由距离的卷积码。
解：最佳自由距离卷积码的定义：对于相同的码率R和相同的电路复杂性（存储单元总数m等）的各种卷积码，使得自由距离df最大的编码称为最佳自由距离（OFD，Optimal Free Distance）码。
为了得到各种OFD码，通常采用计算机搜索的方法，即对于给定的存储单元总数m所有可能的卷积码编码器，首先排除恶性卷积码，然后对应每一可能的卷积码编码器求其自由距离df，逐一比较得到自由距离df最大者即为最佳自由距离卷积码编码器。
二、综合题（开卷部分，每题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 bbb：0.001
设aaa、aab、···bbb分别为x1、x2、···x9，按照概率大小依此排列，有 x1 x2 x3 x5 x4 x6 x7 x8
具体编码过程、结果、编码效率―略。
bba：0.009
3. 为了在有噪信道中获得可靠的通信，拟对题2的霍夫曼编码结果再进行信道编码，若霍夫曼编码的输出序列为aabb baaa baba bbaa bbba abbb abab···，试给出采用戈莱码（23，12）编码的第一个码字；如果信道编码不是采用戈莱码而是采用缩短的BCH（120，78）编码，试给出构造该种编码的生成多项式的方法以及缩短的方法，分析其纠错和检错能力，简述其编码和译码过程。 解：
（1）对戈莱码（23，12）采用生成多项式为g(x) = x11+ x10+ x6+ x5+ x4 + x2+1，即110001110101 令a＝1，b＝0，则要编码的序列为1100 0111 0101 0011 0001 1000 1010 ···；由于戈莱码是非本原BCH码，其编码规则与BCH码相同，现采用系统码，第一个码字的编码过程如下：
110001110101 110001110101
―――――――――――――
00000000000 00000000000
因此第一个戈莱码码字为110001110101 00000000000，即监督位为全0（11位）。
（2）缩短的BCH（120，78）原码为BCH（127，85），构造该种编码的生成多项式，可以由
6
g(x) =LCM{? 1(x) +? 2(x) + ? 3(x) x+···+? 2 t (x)}
77i
对于本题，127＝2，?i(x)是GF(2)上的元素? 的最小多项式，求出?、? 3、? 5、? 7的最小多项式，将它们相乘即得到该种编码能够纠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 （2）信息加密技术进行保密通信的系统框图如图所示（教材图14.1）。 其工作原理为：明码文本M利用密钥，通过某种可逆变换EK加密成密文C，即C =EK（M）；密文通过不安全的或公共信道进行传输，在传输过程中可能出现密文截取（截取密文又称为攻击或入侵），当合法用户得到C后，用逆变换DK = EK-1进行解密得到原来的明码文本消息，即错误！未找到引用源。；参数K是由码元或字符组成的密钥，它规定了密码变换集合中特定的一种加密变换EK。 错误！未找到引用源。 图14.1 加密信道模型 非通信对像收到了密文但在不能成功破译时，其不确定性集合中的元素没有任何变化，根据自信息量和平均互信息量的定义，他所获得的信息量为0。 6. 试从收、发双方联合优化的出发点来说明为什么信源编码通常其编码较为复杂而信道编码通常其译码较为复杂的原因。 解： 通常信源编码的信道基本符号数目较少，而根据收发联合优化的考虑，克服信道产生的影响（对数字通信而言主要表现在误码上）主要由信道编码完成，故对信源译码没有提出纠错或检错的要求，因此在收端有一个与发端完全相同的信道基本符号集合就足以完成译码；因为单译可译的编码工作在发端完成而收端只要按照编码规则对收到的码进行比对就可以了，因此通常编码比译码要复杂些。 对于信道编码，选定编码规则后，编码所要处理的主要是消息序列（把消息序列映射为码字），以 kn 分组码为例共2个；而译码需要处理的是所有可能接收到的序列（仍以分组码为例则共有2个），考虑到信道的复杂性，译码均依从最大似然准则，故其比对过程比编码的映射运算复杂很多。 1. 在无失真的信源中，信源输出由 H(X) 来度量；在有失真的信源中，信源输出由 R(D) 来度量。 2. 要使通信系统做到传输信息有效、可靠和保密，必须首先 信源 编码， 然后_____加密____编码，再______信道_____编码，最后送入信道。 3. 带限AWGN波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是错误！未找到引用源。；当归一化信道容量C/W趋近于零时，也即信道完全丧失了通信能力，此时Eb/N0为 -1.6 dB，我们将它称作香农限，是一切编码方式所能达到的理论极限。 4. 保密系统的密钥量越小，密钥熵H(K)就越 小 ，其密文中含有的关于明文的信息量I(M；C)就越 大 。 5. 已知n＝7的循环码错误！未找到引用源。，则信息位长度k为 3 ，校验多项式 h(x)= 错误！未找到引用源。 。