学 安徽大学 2011—2012 学年第 1 学期 《信息论》考试试卷(A 卷)
(闭卷
时间 120 分钟)
院 院/ 系
年级
专业
姓名
学号
题 题
号 一 一 二 二 三 三 四 四 五 五 总 总 分
得
分
题 一、填空题(每小题 2 分,共 20 分)
1、香农信息的定义
。
2、在已知事件 z Z 的条件下,接收到 y 后获得关于事件 x 的条件互信息 ( ; | ) I x y z 的表达式为
。
3、研究信息传输系统的目的就是要找到信息传输过程的共同规律,以提高信息传输的可靠性、有效性、
和
,使信息传输系统达到最优化。
4、某信源 S 共有 32 个信源符号,其实际熵 H =1.4 比特/符号,则该信源剩余度为
。
5、信源固定的情况下,平均互信息 ( ; ) I X Y 是信道传递概率 ( | ) P y x 的
型凸函数。
6、已知信源 X 的熵 H(X)=0.92 比特/符号,则该信源的五次无记忆扩展信源 X 5 的信息熵5( ) H X =
。
7、根据香农第一定理,对于离散无记忆信源 S,用含 r 个字母的码符号集对 N 长信源符号序列进行变长编码,总能找到一种无失真的唯一可译码,使每个信源符号所需平均码长满足:
。
8 、 多 项 式 剩 余 类 环 [ ] ( 1)nqF x x 的 任 一 理 想 的 生 成 元 ( ) g x 与 1nx 关 系为
。
9、有限域122F 的全部子域为
。
10、国际标准书号(ISBN)由十位数字1 2 3 4 5 6 7 8 9 10aa a a a a a a a a 组成(诸ia 11F ,满足:1010(mod11)iiia),其中前九位均为 0-9,末位 0-10,当末位为 10 时用 X 表示。《Coding and Information Theory》的书号为 ISBN:7-5062-3392-
。
得 分
题 二、判断题(每小题 2 分,共 10 分)
1、离散信源的信息熵是信源无失真数据压缩的极限值。
(
)
2、对于有噪无损信道,其输入和输出有确定的一一对应关系。
(
)
3、在任何信息传输系统中,最后获得的信息至多是信源所提供的信息。如果一旦在某一过程中丢失一些信息,以后的系统不管如何处理,如不触及到丢失信息过程的输入端,就不能再恢复已丢失的信息。
(
)
4、码 C={0,10,1100,1110,1011,1101}是唯一可译码。
(
)
5、一定存在码长分别为 1,3,3,3,4,5,5 的二元即时码。
(
)
题 三、计算题(每小题 8 分,共 32 分)
1、有一离散无记忆信源 1 2 32 1 13 6 6x x xXP x ( ) , 31( ) 1iip x 。
求该信源的二次扩展信源,并计算二次扩展信源的信源熵。
得 分
得 分
2、设二元对称信道的传递矩阵为2 13 31 23 3 ,求此信道的信道容量及相应的最佳输入概率分布。当输入概率分布为3 10 14 4P P ( ) , ( ) 时,求 | H X Y I X Y ( )和 ( ; ) 。
3、设有一马尔可夫信源,其状态集为 1 2 3, , S S S ,符号集为 3 2 1a a a , , 。在某状态下发某符号的概率为 | , , 1,2,3k iP a S i k 。见下图:
计算此马尔可夫信源熵 H 。
S 1
S 2
S 3
a 3 :1/4 a 1 :1 a 3 :1/2 a 2 :1/4 a 1 :1/2 a 2 :1/2
4、求以 2 x 为生成多项式的长为 3 的三元循环码 C 的全体码字。
题 四、综合题(每小题 10 分,共 30 分)
1、设有一离散信道,其信道传递矩阵为1 1 13 6 21 1 12 3 61 1 16 2 3 ,并设11( )2P x ,2 31( ) ( )4P x P x 。试分别按最小错误概率准则和最大似然译码准则确定译码函数,并计算相应的平均错误概率。
得 分
2、信源空间为1 2 3 4 5 6 7 8, , , , , , ,( ) 0.4, 0.2, 0.1, 0.1, 0.05, 0.05, 0.05, 0.05S s s s s s s s sP s ,码符号为{0,1,2} X ,试构造一种三元紧致码,并计算平均码长。
3、设 C 是二元 [6,3] 线性码,其校验矩阵为1 0 0 1 1 00 1 0 1 0 10 0 1 0 1 1H 。试求全体码字,列简明译码表;当收到的字为 010011 ,如何译码?
题 五、证明题(每小题 4 分,共 8 分)
1、证明:最大离散熵定理,即 1 21 1 1( , , , ) ( , , , ) logqH p p p H qq q q 。
2、设 C 是 q 元 [ , ] n k 线性码,证明:
( ) ( ) d C W C , 其中 ( ) min{ ( , )| , , }i j i j i jd C D c c c c C c c , ( ) min{ ( )| , 0} W C W c c C c 。
学 安徽大学 2011—2012 学 学第 年第 1 学期 《信息论》考试试卷(B 卷)
(闭卷
时间 120 分钟)
院 院/ 系
年级
专业
姓名
学号
题 题
号 一 一 二 二 三 三 四 四 五 五 总 总 分
得
分
得 分
题 一、填空题(每小题 2 分,共 20 分)
1、接收端收到 y 后,获得关于发送的符号是 x 的信息量是
。
2、在已知事件 z Z 的条件下,接收到 y 后获得关于事件 x 的条件互信息 ( ; | ) I x y z 的表达式为
。
3、通信系统模型主要分成五个部分分别为:
。
4、某信源 S 共有 32 个信源符号,其实际熵 H =1.4 比特/符号,则该信源剩余度为
。
5、信道固定的情况下,平均互信息 ( ; ) I X Y 是输入信源概率分布 ( ) P x 的
型凸函数。
6、当信源与信道连接时,若信息传输率达到了信道容量,则称此信源与信道达到匹配。信道剩余度定义为
。
7、将 H ,6H ,0H ,4H ,1H 从大到小排列为
。
8、多项式剩余类环 [ ] ( ( ))qF x f x 是域的充要条件为
。
9、有限域122F 的全部子域为
。
10、国际标准书号(ISBN)由十位数字1 2 3 4 5 6 7 8 9 10aa a a a a a a a a 组成(诸ia 11F ,满足:1010(mod11)iiia),其中前九位均为 0-9,末位 0-10,当末位为 10 时用 X 表示。《Handbook of Applied Cryptography》的书号为 ISBN:7-121-01339-
。
得 分
题 二、判断题(每小题 2 分,共 10 分)
1、互信息 ( ; ) I x y 与平均互信息 ( ; ) I X Y 都具有非负性质。
(
)
2、对于无噪无损信道,其输入和输出有确定的一一对应关系。
(
)
3、设有噪信道的信道容量为 C,若信息传输率 R C ,只要码长 n 足够长,必存在一种信道编码和相应的译码规则,使译码平均错误概率EP 为任意小。反之,若 R C 则不存在以 R 传输信息而EP 为任意小的码。
(
)
4、对于离散信道 [ , ( | ), ] X p y x Y ,有 ( | ) ( ) log( 1)E EH X Y H P P r ,并且不管采用什么译码规则,上述费诺不等式成立。
(
)
5、一定存在码长分别为 1,2,3,3,3,4,5,5 的二元即时码。
(
)
题 三、计算题(每小题 8 分,共 32 分)
1、 设 1 2~1/2 1/2a aX ,1 2 3 4~1/4 1/4 1/4 1/4b b b bY , , 1 2 3 4 5 6 7 8~1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8c c c c c c c cZ 。
。
计算 ) ( ), ( ), ( Z H Y H X H 。
。
当 Z Y X , , 为统计独立时,计算 ) (XYZ H 。
。
得 分
得 分
2、求下述两信道的信道容量及其达到信道容量时的输入概率分布。
(1)
(2)
3、一阶马尔可夫信源的状态图如下图所示,信源 X 的符号集为{0,1,2}并定义 1 p p 。
(1)求信源平稳后的概率分布 P(0),P(1),P(2); (2)求此信源的熵。
0
2
1 p/2 p
p/2 p/2 p/2 p/2 p
p p/2
4、求以 1 x 为生成多项式的长为 3 的二元循环码 C 的全体码字。
题 四、综合题(每小题 10 分,共 30 分)
1、设有一离散信道,其信道传递矩阵为1 1 13 6 21 1 12 3 61 1 16 2 3 ,并设11( )2P x ,2 31( ) ( )4P x P x 。试分别按最小错误概率准则和最大似然译码准则确定译码函数,并计算相应的平均错误概率。
得 分
2、信源空间为1 2 3 4 5 6 71 1 1 1 1 1 1( )3 3 9 9 27 27 27s s s s s s sSP s ,码符号为 {0,1,2} X ,试构造一种三元紧致码,并计算平均码长。
3、设 C 是二元 [6,3] 线性码,其校验矩阵为1 0 0 1 1 00 1 0 1 0 10 0 1 0 1 1H 。试求全体码字,列简明译码表;当收到的字为 010011 ,如何译码?
题 五、证明题(每小题 4 分,共 8 分)
1、证明:条件熵不大于无条件熵,即2 1 2( | ) ( ) H X X H X 。
2、循环码 C 的对偶码 C 仍为循环码。
得 分