信息论与编码学考试试题

1. 信息的概念
信息：是指各个事物运动的状态及状态变化的方式。

（具有不确定性，任何已经确定的事物都不含有信息）
2. 相对熵的概念及计算
连续信源可以假设是一个不可数的无限多个幅度值的信源，需要无限多个二进制数来表示，因此它的熵为无穷大。

连续信源的熵具有相对性，有时也叫相对熵。

连续信源熵（相对熵）：Hc(X)=x p x P X X )(log )(⎰∞∞--
3. 信源熵的概念及计算
信源中各个符号不确定度的数学期望叫做信源熵
H(X)=E[I(X)]= )(log )()()(21i i n
i i i i x p x p x I x p ∑∑=-= 单位：比特/符号 其中：0≤ )p(x i ≤1，当信源中只含一个符号x 时，必定有)p(x i =1.
4. 分组码
将信源消息分成若干组，即符号序列X i ，X i =（X 1，X 2...X l ...X L ),序列中的每个符号取自于符号集A,X l ∈{a 1,a 2,...,a i ,...,a n }.而每个符号序列X i 依照固定的码表映射成一个码字Y i ，这样的码称为分组码，也叫快码。

只有分组码才有对应的码表，而非分组码中不存在。

5. 唯一可译码
任意有限长的码元序列，只能被唯一的分割成一个个的码字，便称为唯一可译码。

唯一可译码分为：非即时码和即时码
6. 唯一可译码存在的充分必要条件的概念及应用
用树的概念可导出唯一可译码存在的充分必要条件，即各码字的长度Ki 应符合克劳夫特不等式：∑=-n K i m
1i ≤1 （m 是进制数，n 是信源符号数）
7. 疑义度的概念及计算
条件熵H(X/Y)可以看做是信道上的干扰和噪声所造成的对信源符号x 的不确定度，故又称为疑义度或损失熵。

H(X/Y)=E[I(x i /y i )]= )/()(j ,i i i i
i y x I y x p ∑ =)/(log )(-j
,i i i i i y x p y x p ∑ 散布度或噪声熵
H(Y/X)=E[I(y i /x i )]= )/y ()(j ,i i i i
i x I y x p ∑ =)/y (log )(-j
,i i i i i x p y x p ∑
8. 恒重码的概念
如果码集的所有码字都具有相同的重量，这种码就叫做恒重码
9. 平均自信息量的概念及计算
平均自信息量是消除信源不确定度时所需要的信息的量度，即收到一个信源符号，全部解除了这个符号的不确定度。

和信源熵在数值上相等，含义不同。

10. 平均互信息的概念及计算
互信息量I(xi;yi)在联合概率空间P （XY ）上的统计平均值被称为平均互信息量，用I （X;Y ）表示。

I （X;Y ）=);()(i i i j i i y x I y x p
∑∑=)()y p(x log )(i i i i j i i x p y x p ∑∑单位：比特/消息
平均互信息量克服了互信息量的随机性，成为一个确定的量，因此可作为信道中流通信息量的整体测度。

11. 密码体制中的保密性
保密性要求密码分析员无法从截获的密文中求出明文。

包括两个要求：
1. 即使截获了一段密文C ，甚至知道了与它对应的明文M,密码分析员要从中系统地求出解
密变换任然是计算上不可能的。

2. 密码分析员要由截获的密文C 系统地求出明文M 是计算上不可能的。

无论被截获的密文消息的数量和长度是多少，为了实现保密性，这两个要求都必须成立。

保密性只要求对变换D k (解密密钥)加以保密，只要不影响D k 的保密性，变换E K 可以公布于众。

12. DES 的概念
DES 的明文长度是64bit ，密钥长度是56bit ，加密后的密文长度也是64bit ，脱密过程则相反，它首先按照分组进行脱密，然后去除填充信息并进行连接。

13. 定长编码定理和应用
定长编码定理：由L 个符号组成的、每个符号的熵为H L （X ）的无记忆平稳信源符号序列X 1X 2...X l ...X L ，可用K L 个符号
Y 1，Y 2，...,Y k ...L K Y (每个符号有m 种可能值）进行定长编码。

对于任意ε>0,δ>0,只要
)(log X H m L K L L ≥+ε,则当L 足够大时，必使译码差错小于δ；反之，当)(log X H m L
K L L ≤-2ε，译码差错一定是有限值，而当L 足够大时，译码几乎必定出错。

14. 计算无记忆信源信息量
15. 自信息量的概念及计算
自信息量为一个随机事件出现概率对数的负数。

即
I(x i )=-logp(x i ) 单位和所用的对数底有关，底数通常为2
以2为底时，单位是比特（bit ） 以e 为底时，单位是奈特（nat ）
以10为底时，单位是笛特（det ）
转换关系为：1 nat=log 2e ≈ 1.433bit ; 1det=log 210 ≈3.322bit
16. 构造霍夫曼码
霍夫曼编码的步骤如下：
⑴ 将n 个信源消息符号按其出现的概率大小依次排列p(x 1)≥p(x 2)≥…≥ p(x n )
⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。

⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。

⑷不断继续上述过程，直到最后两个符号配以0和1为止。

⑸ 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。

17. 码组的平均长度,信息传输速率的计算
平均码长K 表示编码后的每个信源符号平均所需的码元个数： K =
i i K x p )(q 1i ∑= 单位：码元/信源符号， K i 为码字长度（i=1,2,...,q)
信息传输率R 是指编码后每个码元载荷的信息量： R=K
X H )( 单位：比特/码元 或 比特/码符号 18. 游程编码的概念及应用
游程编码，指数字序列中连续出现相同符号的一段。

二元序列只有两种符号0和1.游程编码是变长码需有大量的缓冲和优质的信道。

19. 信源的冗余度概念
冗余度，也叫多余度或剩余度，它表示给定信源在实际发出消息时所包含的多余信息。

冗余度来自两方面：一是信源符号间的相关性；二是信源符号分布的不均匀性。

20. 最佳编码的概念
凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳编码。

21. 数据处理定理即信息不增原理的证明
证明：x 是输入信息集合，y 是第一级处理器的输出消息集合，z 是第二级处理器的输出消息集合，假设在y 条件小x 与z 相互独立。

因为三维联合集xyz 上的平均户信息量有
I(X;YZ)=I(X;Y)+I(X;Z/Y) (1) I(YZ;X)=I(Y;X)+I(Z;X/Y) (2)
I(X;YZ)=I(X;ZY)=I(X;Z)+I(X;YZ) (3)
由(1)(3)得 I(X;Z)=I(X;Y)+I(X;Z/Y)-I(X;Y/Z)
将(2)中集合符号替代(X 代Y ，Y 代Z ，Z 代X)得
I(XY;Z)=I(X;Z)+I(Y;Z/X) (4) 将(4)式右边的x 和y 互换得
I(XY;Z)=I(Y;Z)+(X;Z/Y) (5) 由(4)(5)得I(X;Z)=I(Y;Z)+I(X;Z/Y)-I(Y;Z/Y) 因为已假设在Y 条件下X 与Z 相互独立，即I(X;Z/Y)=0,而且I(X;Y/Z)和I(Y;Z/X)均为非负量，得出I(X;Z)≤I(Y;Z),I(X;Z)≤I(X;Y) 说明当信息通过多级处理器时，随着处理器数目的增多，输入信息与输出信息之间的平均信息量趋于变小。

故在数据处理过程中只会丢失一些信息，绝不会创造出新的信息，这就是信息不增性。

22. 二元信源熵的极大值的计算
二元信源是离散信源的特例，该信源X 输出符号只有两个0和1，输出符号发生的概率
分别是p,q ，p+q=1.二元信源熵：H(X)=-plogp-qlogq=-plogp-(1-p)log(1-p)=H(p) 当二元信源熵符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。

23. 设最小距离为7，证明不存在这样一种编码：同时纠错4个，检错4个。

证明: 最小距离为d min 的（n,k ）分组码有能力纠正t=INT[(min d -1)/2]个差错，纠错能力总是小于检错能力。

因为min d =7,故t=3,可以纠错3个，又因为最小距离min d 的码能同时检d e 个，纠纠c e 个差错。

c e 个差错，必须有d e + c e ≤min d -1 及c e ≤d e 。

而题中c e =4,d e =4,故4+4=8>(7-1)所以不能同时纠错4个，检错4个。

一、名词解释（每题4分，共20分）
二、概念简答题（每题10分，共30分）
三、综合题（每题10分，共30分）
四、证明题（每题10分，共20分）。