一、判断题共 10 小题,满分 20 分.
1. 当随机变量X 和Y 相互独立时,条件熵)|(Y X H 等于信源熵)(X H . ( )
2. 由于构成同一空间的基底不是唯一的,所以不同的基
底或生成矩阵有可能生成同一码集.
( ) 3.一般情况下,用变长编码得到的平均码长比定长编码大得多. ( ) 4. 只要信息传输率大于信道容量,总存在一种信道编译码,可以以所要求的任意小的误差概率实现可靠的通
信.
( ) 5. 各码字的长度符合克拉夫特不等式,是唯一可译码存
在的充分和必要条件. ( ) 6. 连续信源和离散信源的熵都具有非负性.
( ) 7. 信源的消息通过信道传输后的误差或失真越大,信宿
收到消息后对信源存在的不确
定性就越小,获得的信息量就越小. 8. 汉明码是一种线性分组码. ( ) 9. 率失真函数的最小值是0
. ( )
10.必然事件和不可能事件的自信息量都是0.
( )
二、填空题共 6 小题,满分 20 分.
1
、
码
的
检
、
纠
错
能
力
取
决
于 .
2、信源编码的目的是 ;信道编码的目的是 .
3、把信息组原封不动地搬到码字前k 位的),(k n 码就叫做 .
4、香农信息论中的三大极限定理
是 、 、
. 5、设信道的输入与输出随机序列分别为X 和Y ,则),(),(Y X NI Y X I N N =成立的
条件 .
6、对于香农-费诺编码、原始香农-费诺编码和哈夫曼编码,编码方法惟一的是 .
7、某二元信源0
1()1/21/2X P X ????=???
?
????
,其失真矩阵00a D a ??
=????
,则该信源的max D = . 三、本题共 4 小题,满分 50 分. 1、某信源发送端有2种符号i x )2,1(=i ,a x p =)(1;接收端
有3种符号i y )3,2,1(=j ,转移概率矩阵为1/21/201/21/41/4P ??
=????. (1) 计算接收端的平均不确
定度()H Y ; (2) 计算由于噪声产生的不确定度(|)H Y X ;
(3) 计算信道容量以及最佳
入口分布. 2、一阶马尔可夫信源的状态转移图如右图所示, 信源X 的符号集为}2,1,0{.
(1)求信源平稳后的概率分布; (2)求此信源的熵; (3)近似地认为此信源为无记忆时,符号的概率分布为
平
稳分布.求近似信源的熵)(X H 并与H ∞进行比较. 4、设二元)4,7(线性分组码的生成矩阵为
?
?
???
????
???=1000101010011100101100001011G . (1)给出该码的一致校验矩阵,写出所有的陪集首和与之相对应的伴随式;
(2)若接收矢量)0001011(=v ,试计算出其对应的伴随式S 并按照最小距离译码准则 试着对其译码.
(二)
一、填空题(共15分,每空1分)
图2-13
1、信源编码的主要目的是 ,信道编码的主要目的是 。
2、信源的剩余度主要来自两个方面,一是 ,二是 。
3、三进制信源的最小熵为 ,最大熵为 。
4、无失真信源编码的平均码长最小理论极限制为 。
5、当 时,信源与信道达到匹配。
6、根据信道特性是否随时间变化,信道可以分为
和 。 7、根据是否允许失真,信源编码可分为
和 。
8、若连续信源输出信号的平均功率为2σ,则输出信号幅度的概率密度是 时,信源具有最大熵,其值为值 。
9、在下面空格中选择填入数学符号“,,,=≥≤?”或“?”
(1)当X 和Y 相互独立时,H (XY ) H(X)+H(X/Y) H(Y)+H(X)。
(2)()()
1222H X X H X = ()()12333
H X X X H X =
(3)假设信道输入用X 表示,信道输出用Y 表示。在无噪有损信道中,H(X/Y) 0,
H(Y/X) 0,I(X;Y) H(X)。
三、(16分)已知信源
1234560.20.20.20.20.10.1S s s s s s s P ????=????????
(1)用霍夫曼编码法编成二进制变长码;(6分) (2)计算平均码长L ;(4分)
(3)计算编码信息率R ';(2分)
(4)计算编码后信息传输率R ;(2分) (5)计算编码效率η。(2分)
四、(10分)某信源输出A 、B 、C 、D 、E 五种符号,每一个符号独立出现,出现概率分别为1/8、1/8、1/8、1/2、1/8。如果符号的码元宽度为0.5s μ。计算: (1)信息传输速率t R 。(5分)
五、(16分)一个一阶马尔可夫信源,转移概率为
()()()()1121122221
|,|,|1,|033
P S S P S S P S S P S S ====。
(1) 画出状态转移图。(4分)
(2) 计算稳态概率。(4分)
(3) 计算马尔可夫信源的极限熵。(4分) (4) 计算稳态下1H ,2H 及其对应的剩余度。(4分)
六、设有扰信道的传输情况分别如图所示。试求这种信道的信道容量。
X Y
七、(16分)设X 、Y 是两个相互独立的二元随机变量,其取0或1的概率相等。定义另一个二元随机变量Z=XY(一般乘
积)。试计算 (1) ()(),;H X H Z
(2) ()(),;H XY H XZ
(3) ()()|,|;H X Y H Z X
(4) ()();,;I X Y I X Z ;
八、(10分)设离散无记忆信源的概率空间为
120.80.2X x x P ????
=????????
,通过干扰信道,信道输出端的接收符号集为[]12,Y y
y =,信道传输概率如下图所示。
1
x 2
x 1
y 2
y
(1) 计算信源X 中事件1x 包含的自信息量; (2) 计算信源X 的信息熵; (3) 计算信道疑义度()|H X Y ; (4) 计算噪声熵()|H Y X ;
(5) 计算收到消息Y 后获得的平均互信息量。
《信息论基础》2参考答案
一、填空题(共15分,每空1分) 1、信源编码的主要目的是提高有效性,信道编码的主要目的是提高可靠性。 2、信源的剩余度主要来自两个方面,一是信源符号间的相关性,二是信源符号的统计不均匀性。
3、三进制信源的最小熵为0,最大熵为32log bit/符号。
4、无失真信源编码的平均码长最小理论极限制为信源熵(或H(S)/logr= H r (S))。
5、当R=C 或(信道剩余度为0)时,信源与信道达到匹配。
6、根据信道特性是否随时间变化,信道可以分为恒参信道和随参信道。
7、根据是否允许失真,信源编码可分为无失真信源编码和限失真信源编码。
8、若连续信源输出信号的平均功率为2σ,则输出信号幅度的概率密度是高斯分布或正态分布或(
)2
2
2x
f x σ-=
时,
信源具有最大熵,其值为值21
log 22
e πσ。
9、在下面空格中选择填入数学符号“,,,=≥≤?”或“?” (1)当X 和Y 相互独立时,H (XY )=H(X)+H(X/Y)=H(Y)+H(X)。
(2)()()
1222H X X H X =≥()()12333
H X X X H X = (3)假设信道输入用X 表示,信道输出用Y 表示。在无噪有损信道中,H(X/Y)> 0, H(Y/X)=0,I(X;Y) 1234560.20.20.20.20.10.1S s s s s s s P ???? =???????? (1)用霍夫曼编码法编成二进制变长码;(6分) (2)计算平均码长L ;(4分) (3)计算编码信息率R ';(2分) (4)计算编码后信息传输率R ;(2分) (5)计算编码效率η。(2分) (1) 010 10 1 1 1 1.00.20.20.20.20.10.1 1S 2S 3S 4S 5S 6 S 编码结果为: 1234560001100101110111 S S S S S S ====== (2)6 10.420.63 2.6i i i L P ρ===?+?=∑码元 符号 (3)bit log r=2.6R L '=符号 (4)() 2.53 bit 0.9732.6 H S R L = = =码元其中,()()bit 0.2,0.2,0.2,0.2,0.1,0.1 2.53H S H ==符号 (5)()()0.973log H S H S L r L η= == 评分:其他正确的编码方案:1,要求为即时码 2,平均码长最短 四、(10分)某信源输出A 、B 、C 、D 、E 五种符号,每一个符号独立出现,出现概率分别为1/8、1/8、1/8、1/2、1/8。如果符号的码元宽度为0.5s μ。计算: (1)信息传输速率t R 。(5分) (1)()() 1 t X R H X H Y t ??=-? ? ()61111 log 4log 882211 log 8log 22231 log 2log 2222log 22bit 24100.5t H X bit R bps s μ=- ?-=+=+=== =? 五、(16分)一个一阶马尔可夫信源,转移概率为 ()()()()1121122221 |,|,|1,|033 P S S P S S P S S P S S ====。 (1) 画出状态转移图。(4分) (2) 计算稳态概率。(4分) (3) 计算马尔可夫信源的极限熵。(4分) (4) 计算稳态下1H ,2H 及其对应的剩余度。(4分) 解:(1) S 1 (2)由公式()()()2 1 |i i j j j P S P S S P S ==∑ 有 ()()()()()()()()()()()2 111212 2211122|31 |31i i i i i i P S P S S P S P S P S P S P S S P S P S P S P S ==? ==+?? ?==?? ?+=?? ∑∑ 得()()12 341 4 P S P S ? =??? ?=?? (3)该马尔可夫信源的极限熵为: ()()() 22 11 |log |322311log log 43343311 0.578 1.599240.6810.4720.205i j i j i i j H P S P S S P S S bit nat hart ∞===-=-??-??=?+?===∑∑符号符号符号 (4)在稳态下: ()()2 1 3 311log log log 0.8114444i i i P x P x bit =??=-=-?+?= ???∑符号 20.2050.4720.681H H hart nat bit ∞====符号符号符号 对应的剩余度为 1100.811110.1891111log log 2222H H η=- =-=?? ????-+ ? ? ??????? 2200.681110.3191111log log 2222H H η=- =-=?? ????-+ ? ? ??????? 六、设有扰信道的传输情况分别如图所示。试求这种信道的信道容量。 X Y 解:信道传输矩阵如下 |1 10022110022110022110 2 2Y X P ??????????=???????????? 可以看出这是一个对称信道,L=4,那么信道容量为 ()() 111log 4,,0,022log |log |11 log 42log 22 1L j i j i j C H L p y x p y x bit =?? =- ? ?? =+=+?=∑ 七、(16分)设X 、Y 是两个相互独立的二元随机变量,其取0或1的概率相等。定义另一个二元随机变量Z=XY(一般乘积)。试计算 (1) ()(),;H X H Z (2) ()(),;H XY H XZ (3) ()()|,|;H X Y H Z X (4) ()();,;I X Y I X Z ; 解:(1) ()11,122H X H bit ?? == ??? 31(2),0.811344H H bit ?? == ??? (2) ()()()112H XY H X H Y bit =+=+=对 ()()()()1111|11,0, 1.52222H XZ H X H Z X H H bit ?? =+=++= ??? 对 (3) ()()|1H X Y H X bit == ()()1111|1,0,0.52222H Z X H H bit ?? = += ??? (4) ()()()()(),|0I X Y H Y H Y X H Y H Y =-=-= ()()(),|0.81130.50.3113I X Z H Z H Z X bit =-=-= 八、(10分)设离散无记忆信源的概率空间为 120.80.2X x x P ???? =???????? ,通过干扰信道,信道输出端的接收符号集为[]12,Y y y =,信道传输概率如下图所示。 1 x 2 x 1 y 2 y (6) 计算信源X 中事件1x 包含的自信息量; (7) 计算信源X 的信息熵; (8) 计算信道疑义度()|H X Y ; (9) 计算噪声熵()|H Y X ; (10) 计算收到消息Y 后获得的平均互信息量。 解: (3) ()2231,,,31520201.4040.9730.423H XY H bit nat hart ?? = ? ??===符号 ()()49/60,11/600.6870.4760.207H Y H bit nat hart ====符号符号符号 ()()()|0.7170.4970.216H X Y H XY H Y bit nat hart =-===符号 (4) ()()()|0.6820.4730.205H Y X H XY H X bit nat hart =-===符号符号符号 (5) ()()();|0.005040.003490.00152I X Y H X H X Y bit nat hart =-===符号符号 (三) 一、 选择题(共10分,每小题2分) 1、有一离散无记忆信源X ,其概率空间为 ??????=??????125.0125.025.05.04321 x x x x P X ,则其无记忆二次扩展信源的熵H(X 2)=( ) A 、1.75比特/符号; B 、3.5比特/符号; C 、9比特/符号; D 、18比特/符号。 2、信道转移矩阵为 112132425363(/)(/) 000000(/)(/)000000(/)(/)P y x P y x P y x P y x P y x P y x ??????????其中(/)j i P y x 两两不相等,则该信道为 3、A 、一一对应的无噪信道 B 、具有并归性能的无噪信道 C 、对称信道 D 、具有扩展性能的无噪信道 3、设信道容量为C ,下列说法正确的是:( ) A 、互信息量一定不大于C B 、交互熵一定不小于C C 、有效信息量一定不大于C D 、条件熵一定不大于C 4、在串联系统中,有效信息量的值( ) A 、趋于变大 B 、趋于变小 C 、不变 D 、不确定 5、若BSC 信道的差错率为P ,则其信道容量为:( ) A 、 () H p B 、 ()12log 1p p p p -??-?? ???? C 、 () 1H p - D 、log()P P - 二、填空题(20分,每空2分) 1、(7,4)线性分组码中,接受端收到分组R 的位数为____ ,伴随式S 可能的值有____ 种,差错图案e 的长度为 ,系统生成矩阵G s 为____ 行的矩阵,系统校验矩阵H s 为____ 行的矩阵,G s 和H s 满足的关系式是 。 2、香农编码中,概率为 () i P x 的信源符号x i 对应 的码字C i 的长度K i 应满足不等式 。 3、设有一个信道,其信道矩阵为 0.250.50.250.250.250.50.50.250.25?? ???????? ,则它是 信道(填对称,准对称),其信道容量是 比特/信道符号。 三、(20分)12()0.50.5X x x P X ???? =????????,通过一个干扰信道,接受符号集为 {} 12Y y y =,信道转移矩阵为 13443144?? ?????????? 试求(1)H(X),H(Y),H(XY);(7分) (2) H(Y|X),H(X|Y);(5分) (3) I(Y;X)。(3分) (4)该信道的容量C (3分) (5)当平均互信息量达到信道容量时,接收端Y 的熵H (Y )。(2分) 计算结果保留小数点后2位,单位为比特/符号。 四、(9分)简述平均互信息量的物理意义,并写出应公式。 六、(10分)设有离散无记忆信源,其概率分布如下: 12345671111111()2 4 8 16 32 6464x x x x x x x X P X ??????=?? ???? ??? 对其进行费诺编码,写出编码过程,求出信源熵、平均码长和编码效率。 七、信道编码(21分) 现有生成矩阵1 0001110 10011000100110 001101s G ????? ?=?? ?? ?? 1.求对应的系统校验矩阵H s。(2分) 2求该码字集合的最小码字距离d、最大检错能力 max l、最大纠错能力t max。(3分) 2. 4.现有接收序列为(1100100) r=,求纠错译码输出?c。(4分) 5. 画出该码的编码电路(4分) (四) 四、简答题(共20 分,每题10分 1.利用公式介绍无条件熵、条件熵、联合熵和平均互信息 量之间的关系。 2.简单介绍哈夫曼编码的步骤 五、计算题(共40 分) 1.某信源含有三个消息,概率分别为p(0)=0.2,p(1)=0.3, p(2)=0.5,失真矩阵为 421 032 201 D ?? ??=?? ?? ?? 。 求D max、D min和R (D max)。(10分) 2.设对称离散信道矩阵为 1111 3366 1111 6633 P ?? ?? =?? ?? ?? ?? ,求信道容 量C。(10分) 3.有一稳态马尔可夫信源,已知转移概率为p(S1/ S1)=2/3,p(S1/ S2)=1。求: (1)画出状态转移图和状态转移概率矩阵。 (2)求出各状态的稳态概率。 (3)求出信源的极限熵。 (20分) (五) 一、(11’)填空题 (1)1948年,美国数学家香农发表了题为 “通信的数学理论”的长篇论文,从而创立了信息论。(2)必然事件的自信息是0 。 (3)离散平稳无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍。 对于离散无记忆信源,当信源熵有最大值时,满足条 件为__信源符号等概分布_。 对于香农编码、费诺编码和霍夫曼编码,编码方法惟 一的是香农编码。 已知某线性分组码的最小汉明距离为3,那么这组码 最多能检测出_2_______个码元错误,最多能纠正 ___1__个码元错误。 设有一离散无记忆平稳信道,其信道容量为C,只要 待传送的信息传输率R__小于___C(大于、小于或者 等于), 则存在一种编码,当输入序列长度n足够大,使译码错误概率任意小。 (8)平均错误概率不仅与信道本身的统计特性有关,还与___译码规则____________和___编码方法___有关二、(9')判断题 (1)信息就是一种消息。 (?) (2)信息论研究的主要问题是在通信系统设计中如何实现信息传输、存储和处理的有效性和可靠性。 (√) (3)概率大的事件自信息量大。 (?) (4)互信息量可正、可负亦可为零。 (√) (5)信源剩余度用来衡量信源的相关性程度,信源剩余度大说明信源符号间的依赖关系较小。 (?) (6)对于固定的信源分布,平均互信息量是信道传递概率的下凸函数。(√) (7)非奇异码一定是唯一可译码,唯一可译码不一定是非奇异码。(?) (8)信源变长编码的核心问题是寻找紧致码(或最佳码),霍夫曼编码方法构造的是最佳码。 ( √ ) (9)信息率失真函数R(D)是关于平均失真度D 的上凸函数. ( ? ) 五、(18’).黑白气象传真图的消息只有黑色和白色两种, 求: 1) 黑色出现的概率为0.3,白色出现的概率为0.7。给出这个只有两个符号的信源X 的数学模型。假设图上黑白消息出现前后没有关联,求熵()X H ; 3)分别求上述两种信源的冗余度,比较它们的大小并说明其物理意义。 解:1)信源模型为 (1分) (2分) 2)由题意可知该信源为一阶马尔科夫信源。 (2分) 由 4分) 得极限状态概率 ( 2分) 3分) 119.0 2log ) (121=- =X H γ (1分) 447.02log ) (122=- =∞X H γ 12γγ>。说明:当信源的符号之间有依赖时,信源输出消息 的不确定性减弱。而信源冗余度正是反映信源符号依赖关系 的强弱,冗余度越大,依赖关系就越大。(2分) 六、(18’).信源空间为 1 234567()0.20.190.180.170.150.10.01 X x x x x x x x P X ???? =??????? ? ,试分别构造二元香农码和二元霍夫曼码,计算其平均码长 和编码效率(要求有编码过程)。 14 .3)(7 1 ==∑=i i i l a p L 831.014.361 .2)(=== L X H R 2)(3分)最大后验概率准则下,有, 八(10').二元对称信道如图。 1)若()430= p ,()4 1 1=p ,求()X H 、()Y X H |和()Y X I ;; 2)求该信道的信道容量。 解:1)共6分 2), (3分)此时输入概率分布为等概率分布。(1分) 九、(18')设一线性分组码具有一致监督矩阵 ?? ?? ? ?????=110101100110111000H 1)求此分组码n=?,k=?共有多少码字? 2)求此分组码的生成矩阵G 。 3)写出此分组码的所有码字。 4)若接收到码字(101001),求出伴随式并给出翻译结果。 解:1)n=6,k=3,共有8个码字。(3分) 2)设码字 ()012345C C C C C C C = 由T T HC 0=得 ??? ??=⊕⊕⊕=⊕⊕=⊕⊕0 000135 034012C C C C C C C C C C (3分) 令监督位为 ()012C C C ,则有 ??? ??⊕=⊕=⊕=3 404513 52C C C C C C C C C (3分) 生成矩阵为????? ???? ?101100110010011001 (2分) 3)所有码字为000000,001101,010011,011110,100110,101011,110101,111000。(4分) 4)由T T HR S =得 ()101=S ,(2分)该码字在第5位发生错误,(101001)纠正为(101011),即译码为(101001)(1分) (六) 一、概念简答题(每题5分,共40分) 1.什么是平均自信息量与平均互信息,比较一下这两个概念 的异同? 2.简述最大离散熵定理。对于一个有m 个符号的离散信源,其最大熵是多少? ()符号 /749.0|bit Y X H = 3.解释信息传输率、信道容量、最佳输入分布的概念,说明平均互信息与信源的概率分布、信道的传递概率间分别是什么关系? 4.对于一个一般的通信系统,试给出其系统模型框图,并结合此图,解释数据处理定理。 5.写出香农公式,并说明其物理意义。当信道带宽为5000Hz,信噪比为30dB时求信道容量。 6.解释无失真变长信源编码定理。 7.解释有噪信道编码定理。 8.什么是保真度准则?对二元信源 ,其失真矩阵,求a>0时率 失真函数的和? 二、综合题(每题10分,共60分) 1.黑白气象传真图的消息只有黑色和白色两种,求: 1)黑色出现的概率为0.3,白色出现的概率为0.7。给出这个只有两个符号的信源X的数学模型。假设图上黑白消息出 现前后没有关联,求熵; 2)假设黑白消息出现前后有关联,其依赖关系为: ,,,,求其熵; 2.二元对称信道如图。;1)若,,求和; 2)求该信道的信道容量和最佳输入分布。3.信源空间为 ,试分别构造二元和三元霍夫曼码,计算其平均码长和编码效率。 5.已知一(8,5)线性分组码的生成矩阵为。 求:1)输入为全00011和10100时该码的码字;2)最小码距。 答案 一、概念简答题(每题5分,共40分) 二、1.答:平均自信息为 表示信源的平均不确定度,也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量,也表示发X前后Y的平均不确定性减少的量,还表示通信前后整个系统不确定性减少的量。 2.答:最大离散熵定理为:离散无记忆信源,等概率分布时熵最大。最大熵值为。 平均互信息是信源概率分布的∩型凸函数,是信道传递概率的U 型凸函数。 5.答:香农公式为,它是高斯加性白噪声信道在单位时间内的信道容量,其值取决于信噪比和带宽。 由得 ,则 6.答:只要,当N足够长时,一定存在一种无失真编码。 7.答:当R<C时,只要码长足够长,一定能找到一种编码方法和译码规则,使译码错误概率无穷小。 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。 平均码长,编码效率 *