信息论与编码
（第五讲）
第一篇信息论第1章概论（2）
第2章信源及其信息量（12）第3章信道及其容量（4）第4章信息率失真函数（4）第二篇编码理论
第5章信源编码（4）
第6章信道编码的基本概念（2）第7章线性分组码（6）第8章循环码（4）第9章卷积码（4）
目录
第二章信息熵
本章重点：信源的统计特性和数学模型、各类信源的信息测度—熵及其性质。
2.1 单符号离散信源
2.2 扩展信源
2.3 连续信源
2.4 离散无失真信源编码定理
2.5 小结
2.2 扩展信源
2.2.1 扩展信源
2.2.2 离散平稳无记忆信源2.2.3 离散平稳有记忆信源2.2.4 马尔可夫信源
2.2.5 信源冗余度及信息变差
(1) 马尔可夫信源的定义(2) m 阶马尔可夫信源(3) 举例
2.2扩展信源
(1) 马尔可夫信源的定义
①信源的状态和符号集②马尔可夫链③时齐的马尔可夫链④马尔可夫信源定义⑤举例⑥结论
2.2扩展信源
(1) 马尔可夫信源的定义
①信源的状态和符号集
á有一类信源，输出的符号序列中符号之间的依赖关系是有限的，即任何
时刻信源符号发生的概率只与前面已经发出的若干个符号有关，而与更前面发出的符号无关。
á设符号集为X ，状态为S 。信源输出的信息符号还与信源所处的状态有
关。
状态S ∈{e 1,e 2,…,e J }符号X ∈{x 1,x 2, …,x n }
每一时刻信源发出一个符号后，所处的状态将发生转移。
2.2扩展信源
(1) 马尔可夫信源的定义
①信源的状态和符号集
返回目录
2.2扩展信源
(1) 马尔可夫信源的定义
②马尔可夫链
á信源输出的随机符号序列为X 1,X 2, …,X l －1,X l , …á信源所处的随机状态序列为S 1,S 2, …,S l －1,S l , …á在第l 时刻，信源状态为e i 时，输出符号x k 的概率为：
p l (x k /e i )=P (X l =x k /S l =e i )
á在第l －1 时刻，信源状态e i 时，下一时刻转移到e j 的状态转移概率为：
p l (e j /e i )=P (S l =e j /S l -1=e i )
á称信源的随机状态序列服从马尔可夫链。
返回目录
2.2扩展信源
(1) 马尔可夫信源的定义
③时齐马尔可夫链
á一步转移概率：状态转移概率p l (e j /e i )=P (S l =e j /S l -1=e i )称为马尔可夫链在
时刻l 的状态一步转移概率。
á时齐/齐次马尔可夫链：一般情况下，状态转移概率和已知状态下符号发
生的概率均与时刻l 有关。若这些概率与时刻l 无关，即：
p l (x k /e i )= p (x k /e i )p l (e j /e i )= p (e j /e i )
则称为时齐的或齐次的。此时的信源状态服从时齐马尔可夫链。
返回目录
2.2扩展信源
(1) 马尔可夫信源的定义
④马尔可夫信源定义
á马尔可夫信源：信源输出的符号和所处的状态满足下列两个条件。
??
?====??1
),/()1(1i l m l j l e S x X e S P l l 即：
信源的状态惟一确定。的输出符号和前一时刻时刻所处的状态由当前信源某一时刻信源符号的输出只与此刻信源所处的状态有关，与以前的状态和以前的输出符号都无关。即：P (X l =x k /S l =e i ,X l －1=x k 1,S l －1=e j ,…) =p l (x k /e i )当具有时齐性时有：p l (x k /e i )= p (x k /e i )
2.2扩展信源
信源l 时刻所处的状态由当前的输出符号和前一时刻(l-1)信源的状态唯一确定。即：
(1) 马尔可夫信源的定义
④马尔可夫信源定义
á说明：
若信源处于某一状态e i ，当它发出一个符号后，所处的状态就变了； 任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定; 因为条件概率p (x k /e i ) 已给定，状态的转移满足一定的概率分布，据此
可求出状态的一步转移概率p (e j /e i )。
á马尔可夫链的状态转移图：每个圆圈代表一种状态，状态之间的有向线
代表某一状态向另一状态的转移。有向线一侧的符号和数字分别代表发出的符号和条件概率。
返回目录
2.2扩展信源
(1) 马尔可夫信源的定义
⑤举例
[例2.2.3] ：设信源符号X ∈{x 1, x 2, x 3}，信源所处的状态S ∈{e 1, e 2, e 3, e 4, e 5}。各状态之间的转移情况由图2.2.1
给出。
2.2扩展信源
????
?????================????L
),/(1),/(1
),/(0),/(1121112211111112e S x X e S
P e S x X e S P e S x X e S
P e S x X e S P l l l
l l l l l l l l l (1) 马尔可夫信源的定义
⑤举例
[例2.2.3] ：
á由矩阵看出：
5
,4,3,2,1,1)/(3
1
==∑=i e x
p k i k
á由图中看出：
2.2扩展信源
(1) 马尔可夫信源的定义
⑤举例
[例2.2.3] ：
á由图中可得状态的一步转移概率：
á
该信源满足马尔可夫信源定义。
2.2扩展信源
(1) 马尔可夫信源的定义
⑤举例
[例2.2.4] ：有一个二元二阶马尔可夫信源，其信源符号集为[0,1]，条件概率为：p (0/00)=p (1/11)=0.8p (1/00)=p (0/11)=0.2
p (0/01)=p (0/10)=p(1/01)=p(1/10)=0.5
D 信源任何时刻发出什么符号只与前二个符号有关，与更前面的符号无关.D 信源有n m =22=4种可能的状态，即00,01,10,11，分别用e 1, e 2, e 3, e 4表示。D 如果原来状态为00，则此时刻只可能发出符号0或1，下一时刻只可能转
移到00和01状态，不会转移到10或11
状态。
2.2扩展信源
(1) 马尔可夫信源的定义
⑤举例
[例2.2.4] ：
D 处在00状态时发符号0的概率为0.8，所以处在00状态转回到00状态的概
率为0.8。
D 处在00状态时发符号1的概率为0.2，所以00状态转移到01状态的概率为
0.2。
D 根据给定的条件概率，可以求得状态之间的转移概率(一步转移概率)为:
p (e 1/e 1)= p (e 4/e 4)= 0.8p (e 2/e 1)= p (e 3/e 4)= 0.2
p (e 3/e 2)= p (e 2/e 3)=p (e 4/e 2)= p (e 1/e 3)= 0.5其它的状态转移概率都为零。
2.2扩展信源
(1) 马尔可夫信源的定义
⑤举例
[例2.2.4]
：
D 二元信源发出的一串二元序列可变
换成状态序列。
D 例如：二元序列为…01011100…，
状态序列为…e 2 e 3e 2e 4e 4e 3e 1…。
D 这串状态序列是时齐的马尔可夫链
，它在任何时刻l ，状态之间的转移可由一步转移概率确定。
返回目录
2.2扩展信源
(1) 马尔可夫信源的定义
⑥结论：
á一般有记忆信源发出的是有关联性的各符号构成的整体消息
，即发出的是符号序列，并用符号间的联合概率描述这种关联性；
á马尔可夫信源的不同之处在于它用符号之间的转移概率（条
件概率）来描述这种关联关系。即马尔可夫信源是以转移概率发出每个信源符号；
á转移概率的大小取决于它与前面符号之间的关联性。
返回目录
2.2扩展信源
(2) m 阶马尔可夫信源
①m 阶马尔可夫信源②m 阶马尔可夫信源的极限熵③有限齐次马尔可夫链各态历经定理④有关问题的说明
2.2扩展信源
第二章课后习题 【2.1】设有12 枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪一枚是假币，试问至少必须称多少次？ 解：从信息论的角度看， “12 枚硬币中，某一枚为假币”该事件发生的概率为P = 1 12 ； “假币的重量比真的轻，或重”该事件发生的概率为P = 1 2 ； 为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因此有 I = log12 + log 2 = log 24 比特 而用天平称时，有三种可能性：重、轻、相等，三者是等概率的，均为P = 平每一次消除的不确定性为I = log 3 比特 因此，必须称的次数为1 3 ，因此天 I 1 I 2 log 24 log 3 H 2.9 次 因此，至少需称3 次。 【延伸】如何测量？分 3 堆，每堆4 枚，经过 3 次测量能否测出哪一枚为假币。【2.2】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是 3 和4”时，试问这三种情况分别获得多少信息量？解： “两骰子总点数之和为2”有一种可能，即两骰子的点数各为1，由于二者是独立的， 因此该种情况发生的概率为P = 1 1 6 6 1 36 ，该事件的信息量为： ?
? ? 5 = ? ? 2 = I = log 36 H 5.17 比特 “两骰子总点数之和为 8”共有如下可能：2 和 6、3 和 5、4 和 4、5 和 3、6 和 2，概 率为 P = 1 1 6 6 5 36 ，因此该事件的信息量为： 36 I = log H 2.85 比特 5 “两骰子面朝上点数是 3 和 4”的可能性有两种：3 和 4、4 和 3，概率为 P = 1 1 6 6 1 18 ， 因此该事件的信息量为： I = log18 H 4.17 比特 【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几？”则答案中含有 多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多 少信息量（假设已知星期一至星期日的顺序）？ 解： 如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为 P = 1 7 ，因此此时从答案中获得的信息量为 I = log 7 = 2.807 比特 而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为 1，此时获得 的信息量为 0 比特。 【2.4】居住某地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6 米以上的， 而女孩中身高 1.6 米以上的占总数一半。假如我们得知“身高 1.6 米以上的某女孩是大学 生”的消息，问获得多少信息量？ 解： 设 A 表示女孩是大学生， P ( A ) = 0.25 ； B 表示女孩身高 1.6 米以上， P ( B | A ) = 0.75 ， P ( B ) = 0.5 “身高 1.6 米以上的某女孩是大学生”的发生概率为
信息论与编码理论习题 答案 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】
第二章 信息量和熵 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速 率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息 量。 解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log = bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log = bit 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？ 解：(a) )(a p =! 521 信息量=) (1 log a p =!52log = bit (b) ? ??????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C = bit 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和， Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。
《信息论与编码（第二版）》雪虹答案 第二章 2.1一个马尔可夫信源有3个符号{}1,23,u u u ，转移概率为：()11|1/2p u u =，()21|1/2p u u =，()31|0p u u =，()12|1/3p u u =，()22|0p u u =，()32|2/3p u u =，()13|1/3p u u =，()23|2/3p u u =，()33|0p u u =，画出状态图并求出各符号稳态概率。 解：状态图如下 状态转移矩阵为： 1/21/201/302/31/32/30p ?? ?= ? ??? 设状态u 1，u 2，u 3稳定后的概率分别为W 1，W 2、W 3 由1231WP W W W W =??++=?得1231132231231112331223231W W W W W W W W W W W W ?++=???+=???=???++=?计算可得1231025925625W W W ?=???=???=?? 2.2 由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：(0|00)p =0.8，(0|11)p =0.2，(1|00)p =0.2，(1|11)p =0.8，(0|01)p =0.5，(0|10)p =0.5，(1|01)p =0.5，(1|10)p =0.5。画出状态图，并计算各状态的稳态概率。 解：(0|00)(00|00)0.8p p == (0|01)(10|01)0.5p p == (0|11)(10|11)0.2p p == (0|10)(00|10)0.5p p == (1|00)(01|00)0.2p p == (1|01)(11|01)0.5p p == (1|11)(11|11)0.8p p == (1|10)(01|10)0.5p p ==
第三章 3.1 设二元对称信道的传递矩阵为?????? ????32313132 (1) 若P(0) = 3/4, P(1) = 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)； (2) 求该信道的信道容量及其达到信道容量时的输入概率分布； 解： 1) symbol bit Y X H X H Y X I symbol bit X Y H Y H X H Y X H X Y H Y H Y X H X H Y X I symbol bit y p Y H x y p x p x y p x p y x p y x p y p x y p x p x y p x p y x p y x p y p symbol bit x y p x y p x p X Y H symbol bit x p X H j j i j i j i j i i i / 062.0749.0811.0)/()();(/ 749.0918.0980.0811.0)/()()()/() /()()/()();(/ 980.0)4167.0log 4167.05833.0log 5833.0()()(4167 .03 2 413143)/()()/()()()()(5833.031 413243)/()()/()()()()(/ 918.0 10 log )3 2 lg 324131lg 314131lg 314332lg 3243( ) /(log )/()()/(/ 811.0)41 log 4143log 43()()(222221212221221211112111222=-==-==+-=+-=-=-==?+?-=-==?+?=+=+==?+?= +=+==??+?+?+?-=-==?+?-=-=∑∑∑∑ 2) 2221122 max (;)log log 2(lg lg )log 100.082 /3333 mi C I X Y m H bit symbol ==-=++?=其最佳输入分布为1 ()2 i p x = 3-2某信源发送端有2个符号，i x ，i ＝1，2；()i p x a =，每秒发出一个符号。接受端有3
4-1 设有一个二元等该率信源{}1,0∈X ,2/110==p p ，通过一个二进制对称信道（BSC ）。其失真函数ij d 与信道转移概率ij p 分别定义为 j i j i d ij =≠???=,0,1 ，j i j i p ij =≠? ??-=,1,εε 试求失真矩阵d 和平均失真D 。 解：由题意得， 失真矩阵为d ??????=0110d ，信道转移概率矩阵为P ?? ????--=εεεε11)(i j 平均失真为ε εεεε=?-+?+?+?-= =∑0)1(211211210)1(21),()()(,j i d i j p i p D j i 4-3 设输入符号与输出符号X 和Y 均取值于{0,1,2,3}，且输入符号的概率分布为P(X=i)=1/4,i=0,1,2,3,设失真矩阵为 ????? ???????=0111101111011110d 求)(),(,,max min max min D R D R D D 以及相应的编码器转移概率矩阵。 解：由题意，得 0min =D 则symbol bit X H R D R /24log )()0()(2min ==== 这时信源无失真，0→0,1→1,2→2,3→3，相应的编码器转移概率矩阵为
????? ???????=1000 010*********)j (i P ∑===30 3,2,1,0max ),()(min i j j i d i p D ，，14 1141041141141141141041min{?+?+?+??+?+?+?= }04 1141141141141041141141?+?+?+??+?+?+?， 43}43,43,43,43min{== 则0)(max =D R 此时输出概率分布可有多种，其中一种为：p(0)=1,p(1)=p(2)=p(3)=0 则相应的编码器转移概率矩阵为????? ???????=0001000100010001)(i j P
信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子，试求： (1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵； (5)“两个点数中至少有一个是1”的自信息量。 解： bit P a I N n P bit P a I N n P c c N 17.536log log )(36 1 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： * (3)信源空间： bit x H 32.436log 36 16236log 36215)(=??+?? =∴
bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.111 36 log log )(3611333==-=∴== ? 如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格内，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格内。 （1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。 解： ！ bit a P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481 )(:)1(48 1 i i i i i ==-=∴=-=∴= ∑=落入任一格的概率 bit b P b P b b P b I b P A i 55.547log )(log )()(H 47 log )(log )(47 1 )(:B ,)2(48 1i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知 bit AB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()() (log )(47 1 481)()3(47481 =?=-=-=∴?=∑?=是同时落入某两格的概率 从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量平均每个回答中各含有多少信息量如果你问一位女士，则她的答案中含有多少平均信息量 解：
第三章 信道容量-习题答案 3.1 设二元对称信道的传递矩阵为? ? ? ???3/23/13/13/2 (1) 若P(0) = 3/4, P(1) = 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)； (2) 求该信道的信道容量及其达到信道容量时的输入概率分布； 解： 1) symbol bit Y X H X H Y X I symbol bit X Y H Y H X H Y X H X Y H Y H Y X H X H Y X I symbol bit y p Y H x y p x p x y p x p y x p y x p y p x y p x p x y p x p y x p y x p y p symbol bit x y p x y p x p X Y H symbol bit x p X H j j i j i j i j i i i / 062.0749.0811.0)/()();(/ 749.0918.0980.0811.0)/()()()/() /()()/()();(/ 980.0)4167.0log 4167.05833.0log 5833.0()()(4167 .03 2 413143)/()()/()()()()(5833.031 413243)/()()/()()()()(/ 918.0 10 log )3 2 lg 324131lg 314131lg 314332lg 3243( ) /(log )/()()/(/ 811.0)41 log 4143log 43()()(222221212221221211112111222=-==-==+-=+-=-=-==?+?-=-==?+?=+=+==?+?= +=+==??+?+?+?-=-==?+?-=-=∑∑∑∑ 2) 2 1 )(/ 082.010log )3 2 lg 3231lg 31(2log log );(max 222= =?++=-==i mi x p symbol bit H m Y X I C 3.2 解： (1)αα-==1)(,)(21x p x p ??????=4/14/12/102/12/1P ，?? ? ???---=4/)1(4/)1(2/)1(02/12/1)(αααααj i y x P 4/)1()(,4/14/)(,2/1)(321αα-=+==y p y p y p 接收端的不确定度： ))1(41 log()1(41)4141log()4141()2log(21)(αααα---++-=Y H )1log(41)1log(4123αααα---++-= (2)
设信源1 234567()0.20.190.180.170.150.10.01X a a a a a a a p X ????=???? ???? (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率. 解： (1) 7 21222222()()log () 0.2log 0.20.19log 0.19 0.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.012.609/i i i H X p a p a bit symbol ==-=-?-?-?-?-?-?-?=∑ (2) (3) 7 1 ()0.230.1930.1830.1730.153 0.140.0173.141 ()()/ 2.609 3.14183.1% i i i K k p x H X H X K R η===?+?+?+?+?+?+?====÷=∑ 对习题的信源编二进制费诺码，计算编码效率. 解：
a i p(a i )编码码字k i a1 0002 a2 1 00103 a310113 a4 1 0102 a5 1 01103 a6 1 011104 a7111114 对信源编二进制和三进制哈夫 曼码，计算各自的平均码长和编码效率. 解： 二进制哈夫曼码： x i p(x i)编码码字k i s61 s50 s41 s30 s21 x10102 x21112 x300003
x410013 x500103 s11 x6001104 x7101114 三进制哈夫曼码： x i p(x i)编码码字k i s31 s20 s11 x1221 x20002 x31012 x42022 x50102 x61112 x72122
1． 有一个马尔可夫信源，已知p(x 1|x 1)=2/3，p(x 2|x 1)=1/3，p(x 1|x 2)=1，p(x 2|x 2)=0，试画出该信源的香农线图，并求出信源熵。 解：该信源的香农线图为： 1/3 ○ ○ 2/3 (x 1) 1 (x 2) 在计算信源熵之前，先用转移概率求稳定状态下二个状态x 1和 x 2 的概率)(1x p 和)(2x p 立方程：)()()(1111x p x x p x p =+)()(221x p x x p =)()(2132x p x p + )()()(1122x p x x p x p =+)()(222x p x x p =)(0)(2131x p x p + )()(21x p x p +=1 得4 3 1)(=x p 4 12)(=x p 马尔可夫信源熵H = ∑∑- I J i j i j i x x p x x p x p )(log )()( 得 H=0.689bit/符号 2．设有一个无记忆信源发出符号A 和B ，已知4 341)(.)(= =B p A p 。求： ①计算该信源熵； ②设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率； ③又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。 解：①∑- =X i i x p x p X H )(log )()( =0.812 bit/符号 ②发出二重符号序列消息的信源,发出四种消息的概率分别为 用费诺编码方法 代码组 b i BB 0 1 BA 10 2 AB 110 3 AA 111 3 无记忆信源 624.1)(2)(2 ==X H X H bit/双符号 平均代码组长度 2B =1.687 bit/双符号 B X H R )(22==0.963 bit/码元时间 ③三重符号序列消息有8个,它们的概率分别为 用霍夫曼编码方法 代码组 b i BBB 64 27 0 0 1 BBA 64 9 0 )(6419 1 110 3
2-1.解：该一阶马尔可夫信源，由转移概率构成的转移矩阵为： 对应的状态图如右图所示。设各符号稳定概率为：1p ，2p ，3p 则可得方程组： 1p = 211p +312p +313p 2p =211p +323p 3p =3 22p 1p +2p +3p =1 解得各符号稳态概率为： 1p = 2510，2p =259，3p =25 6 2-2.解：该马尔可夫信源的符号条件概率矩阵为： 状态转移概率矩阵为： 对应的状态图如右图所示。
设各状态的稳态分布概率为1W ,2W ,3W ,4W ,则可得方程组为： 1W =0.81W +0.53W 2W =0.21W +0.53W 3W =0.52W +0.24W 4W =0.52W +0.84W 1W +2W +3W +4W =1 解得稳定分布的概率为: 1W = 145，2W =142，3W =142，4W =14 5 2-3.解：（1）“3和5同时出现”事件的概率为： p(3,5)= 18 1 故其自信息量为： I(3,5)=-㏒2 18 1 =4.17bit （2）“两个1同时出现”事件的概率为： p(1,1)= 36 1 故其自信息量为： I(1,1)=- ㏒2 36 1 =5.17bit （3）两个点数的各种组合构成的信源，其概率空间为： 则该信源熵为： H(x 1)=6× 36 1 lb36+15×181lb18=4.337bit/事件 （4）两个点数之和构成的信源，其概率空间为：
则该信源的熵为： H(x 2)=2× 361 lb36+2×181lb18+2×121lb12+2×91lb9+2×365lb 536+6 1lb6 =3.274bit/事件 （5）两个点数中至少有一个是1的概率为： p(1)= 36 11 故其自信息量为： I(1)= -㏒2 36 11 =1.7105bit 2-7.解：（1）离散无记忆信源的每个符号的自信息量为 I(x 1)= -㏒2 83 =1.415bit I(x 2)= -㏒241 =2bit I(x 3)= -㏒241 =2bit I(x 4)= -㏒28 1 =3bit （2）由于信源发出消息符号序列有12个2，14个0，13个1，6个3，故该消息符 号序列的自信息量为： I(x)= -㏒2( 8 3)14 (41)25 (81)6 =87.81bit 平均每个符号携带的信息量为： L H (x)= 45 ) (x I =1.95bit/符号 2-10 解：用1x 表示第一次摸出的球为黑色，用2x 表示第一次摸出的球为白色，用1y 表示第二次摸出的球为黑色，用2y 表示第二次摸出的球为白色，则 (1)一次实验包含的不确定度为： H(X)=-p(1x )lbp(1x )-p(2x )lbp(2x )=- 13lb 13-23lb 2 3 =0.92 bit (2)第一次实验X 摸出的球是黑色，第二次实验Y 给出的不确定度: H(Y|1x )=-p(1y |1x )lb p(1y |1x )-p(2y |1x )lb p(2y |1x ) = - 27lb 27-57lb 57 = 0.86 bit (3)第一次实验X 摸出的球是白色，第二次实验Y 给出的不确定度:
第一章 1.通信系统的基本模型: 2.信息论研究内容：信源熵，信道容量，信息率失真函数，信源编码，信道编码，密码体制的安全性测度等等 第二章 １.自信息量：一个随机事件发生某一结果所带的信息量。 ２.平均互信息量：两个离散随机事件集合X 和Y ，若其任意两件的互信息量为 I （Xi;Yj ），则其联合概率加权的统计平均值，称为两集合的平均互信息量，用I （X;Y ）表示 ３.熵功率：与一个连续信源具有相同熵的高斯信源的平均功率定义为熵功率。如果熵功率等于信源平均功率，表示信源没有剩余；熵功率和信源的平均功率相差越大，说明信源的剩余越大。所以信源平均功率和熵功率之差称为连续信源的剩余度。信源熵的相对率(信源效率)：实际熵与最大熵的比值 信源冗余度： 0H H ∞=ηη ζ-=1
意义：针对最大熵而言，无用信息在其中所占的比例。 ３.极限熵： 平均符号熵的N 取极限值，即原始信源不断发符号，符号间的统计关系延伸到无穷。 ４. ５.离散信源和连续信源的最大熵定理。 离散无记忆信源，等概率分布时熵最大。 连续信源，峰值功率受限时，均匀分布的熵最大。 平均功率受限时，高斯分布的熵最大。 均值受限时，指数分布的熵最大 ６.限平均功率的连续信源的最大熵功率： 称为平均符号熵。 定义：即无记忆有记忆N X H H X H N X H X NH X H X H X H N N N N N N )() ()()()()()(=≤∴≤≤
若一个连续信源输出信号的平均功率被限定为p ，则其输出信号幅度的概率密度分布是高斯分布时，信源有最大的熵，其值为 1log 22 ep π.对于N 维连续平稳信源来说，若其输出的N 维随机序列的协方差矩阵C 被限定，则N 维随机矢量为正态分布时信源 的熵最大，也就是N 维高斯信源的熵最大，其值为1log ||log 222N C e π+ 7.离散信源的无失真定长编码定理： 离散信源无失真编码的基本原理 原理图 说明： （1） 信源发出的消息：是多符号离散信源消息，长度为L,可以用L 次扩展信 源表示为： X L =(X 1X 2……X L ) 其中，每一位X i 都取自同一个原始信源符号集合（n 种符号）： X={x 1，x 2，…x n } 则最多可以对应n L 条消息。 （2）信源编码后，编成的码序列长度为k,可以用k 次扩展信宿符号表示为： Y k =(Y 1Y 2……Y k ) 称为码字/码组 其中，每一位Y i 都取自同一个原始信宿符号集合： Y={y 1，y 2，…y m } 又叫信道基本符号集合（称为码元，且是m 进制的） 则最多可编成m k 个码序列，对应m k 条消息 定长编码：信源消息编成的码字长度k 是固定的。对应的编码定理称为定长信源编码定理。 变长编码：信源消息编成的码字长度k 是可变的。 8.离散信源的最佳变长编码定理 最佳变长编码定理：若信源有n 条消息，第i 条消息出现的概率为p i ，且 p 1>=p 2>=…>=p n ，且第i 条消息对应的码长为k i ，并有k 1<=k 2<=…<=k n
没文化，真可怕！！！ 第三章 3.1 设二元对称信道的传递矩阵为? ?????????32313132 (1) 若P(0) = 3/4, P(1) = 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)； (2) 求该信道的信道容量及其达到信道容量时的输入概率分布； 解： 1) symbol bit Y X H X H Y X I symbol bit X Y H Y H X H Y X H X Y H Y H Y X H X H Y X I symbol bit y p Y H x y p x p x y p x p y x p y x p y p x y p x p x y p x p y x p y x p y p symbol bit x y p x y p x p X Y H symbol bit x p X H j j i j i j i j i i i / 062.0749.0811.0)/()();(/ 749.0918.0980.0811.0)/()()()/() /()()/()();(/ 980.0)4167.0log 4167.05833.0log 5833.0()()(4167 .03 2 413143)/()()/()()()()(5833.031 413243)/()()/()()()()(/ 918.0 10 log )3 2 lg 324131lg 314131lg 314332lg 3243( ) /(log )/()()/(/ 811.0)41 log 4143log 43()()(222221212221221211112111222=-==-==+-=+-=-=-==?+?-=-==?+?=+=+==?+?= +=+==??+?+?+?-=-==?+?-=-=∑∑∑∑ 2) 2221122 max (;)log log 2(lg lg )log 100.082 /3333 mi C I X Y m H bit symbol ==-=++?=其最佳输入分布为1 ()2 i p x = 3-2某信源发送端有2个符号，i x ，i ＝1，2；()i p x a =，每秒发出一个符号。接受端有3 种符号i y ，j ＝1，2，3，转移概率矩阵为1/21/201/21/41/4P ?? =???? 。 （1） 计算接受端的平均不确定度；
第一章信息论与基础 1.1信息与消息的概念有何区别？ 信息存在于任何事物之中,有物质的地方就有信息，信息本身是看不见、摸不着的，它必须依附于一定的物质形式。一切物质都有可能成为信息的载体，信息充满着整个物质世界。信息是物质和能量在空间和时间中分布的不均匀程度。信息是表征事物的状态和运动形式。 在通信系统中其传输的形式是消息。但消息传递过程的一个最基本、最普遍却又十分引人注意的特点是：收信者在收到消息以前是不知道具体内容的；在收到消息之前，收信者无法判断发送者将发来描述何种事物运动状态的具体消息；再者，即使收到消息，由于信道干扰的存在，也不能断定得到的消息是否正确和可靠。 在通信系统中形式上传输的是消息,但实质上传输的是信息。消息只是表达信息的工具，载荷信息的载体。显然在通信中被利用的（亦即携带信息的）实际客体是不重要的，而重要的是信息。 信息载荷在消息之中，同一信息可以由不同形式的消息来载荷；同一个消息可能包含非常丰富的信息，也可能只包含很少的信息。可见，信息与消息既有区别又有联系的。 1.2 简述信息传输系统五个组成部分的作用。 信源：产生消息和消息序列的源。消息是随机发生的，也就是说在未收到这些消息之前不可能确切地知道它们的内容。信源研究主要内容是消息的统计特性和信源产生信息的速率。 信宿：信息传送过程中的接受者，亦即接受消息的人和物。 编码器：将信源发出的消息变换成适于信道传送的信号的设备。它包含下述三个部分：(1)信源编码器：在一定的准则下，信源编码器对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。(2)纠错编码器：纠错编码器是对信源编码器的输出进行变换，用以提高对于信道干扰的抗击能力，也就是说提高信息传输的可靠性。(3)调制器：调制器是将纠错编码器的输出变换适合于信道传输要求的信号形式。纠错编码器和调制器的组合又称为信道编码器。 信道：把载荷消息的信号从发射端传到接受端的媒质或通道，包括收发设备在内的物理设施。信道除了传送信号外，还存储信号的作用。 译码器：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。 1.3 同时掷一对骰子，要得知面朝上点数之和，描述这一信源的数学 模型。 解：设该信源符号集合为X
第3章 信道容量 习题解答 3-1 设二进制对称信道的转移概率矩阵为2/31/31/32/3?? ?? ?? 解: (1) 若12()3/4,()1/4P a P a ==，求(),(),(|),(|)H X H Y H X Y H Y X 和 (;)I X Y 。 i i 2 i=1 3311 H(X)=p(a )log p(a )log()log()0.8113(/)4444bit -=-?-=∑符号 111121********* j j j=1 32117 p(b )=p(a )p(b |a )+p(a )p(b |a )=43431231125 p(b )=p(a )p(b |a )+p(a )p(b |a )=434312 7755 H(Y)=p(b )log(b )=log()log()0.9799(/) 12121212bit ?+?= ?+?= ---=∑符号 22 i j j i j i j i ,H(Y|X)=p(a ,b )logp(b |a )p(b |a )logp(b |a ) 2211 log()log()0.9183(/) 3333 i j j bit -=-=-?-?=∑∑符号 I(X;Y)=H(Y)H(Y|X)=0.97990.91830.0616(/)bit --=符号 H(X|Y)=H(X)I(X;Y)=0.81130.06160.7497(/bit --=符号) (2)求该信道的信道容量及其达到信道容量时的输入概率分布。 二进制对称信息的信道容量 H(P)=-plog(p)-(1-p)log(1-p) 1122 C =1-H(P)=1+log()+log()=0.0817(bit/) 3333 符
4.5若将N 个相同的BSC 级联如题图4.5所示，各信道的转移概率矩阵为??????--p p p p 11。令Q t =P{X t =0}，t=0,1,…,N,且Q 0为已知。 题图 4.5 (a)求Q t 的表达式。 (b)证明N →∞时有Q N →1/2，且与Q 0取值无关，从而证明N →∞级联信道的信道容量C N →0，P>0。 解： (a)对于满足X N 为马氏链的串联信道，他们总的信道转移概率矩阵为各个串联信道矩阵的乘积，即P(X N |X 0)= P(X 1|X 0) P(X 2|X 1)……P(X N |X N-1) 由已知得，但各信道的转移概率矩阵为?? ?? ??--p p p p 11 则两个信道级联的转移概率矩阵为： P 2=??????--p p p p 11????? ?--p p p p 11=()()()()??????-+---+2222112p 12p 1p p p p p p 三个信道级联的转移概率矩阵为： P 3=()()()()???? ??????-+----+33331221211221211221211-2p 2121p p p 四个信道级联的转移概率矩阵为： P 4=()()()()???? ??????-+----+44441221211221211221211-2p 2121p p p 以此类推：可得N 个信道级联的转移概率矩阵为： P N =()()()()??????????-+----+N N N N p p p 122121122 1211221211-2p 2121 则 Q t =P{X t =0}=()()()()()000121221211122121122121Q p p Q p Q p t t t t -+--=-?? ????--+??????-+
信息论与编码理论习题解 第二章-信息量和熵 2.1解: 平均每个符号长为:15 4 4.03 12.03 2= ?+?秒 每个符号的熵为9183.03log 3123log 3 2=?+?比特/符号 所以信息速率为444.34 15 9183.0=?比特/秒 2.2 解: 同步信号均相同不含信息,其余认为等概, 每个码字的信息量为 3*2=6 比特； 所以信息速率为600010006=?比特/秒 2.3 解:(a)一对骰子总点数为7的概率是 36 6 所以得到的信息量为 585.2)36 6(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以得到的信息量为 17.536 1 log 2 = 比特 2.4 解: (a)任一特定排列的概率为 ! 521 ,所以给出的信息量为 58.225! 521 log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1352 13 13521344!13C A =? 所以得到的信息量为 21.134 log 1313 52 2=C 比特. 2.5 解:易证每次出现i 点的概率为 21 i ,所以
比特比特比特比特比特比特比特398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(26 12=-==============-==∑ =i i X H x I x I x I x I x I x I i i i x I i 2.6 解: 可能有的排列总数为 27720! 5!4!3! 12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有???? ??37种排法，Y 表示梧桐树可以栽 种的位置，它有???? ??58种排法，所以共有???? ??58*???? ??37=1960种排法保证没有 两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地； Z=0表示学过英语，Z=1表示未学过英语，由此得
信息论与编码 第四章 4.5判断以下几种信道是不是准对称信道 （1）?? ????3.02.05.05.03.02.0不是 （2）???? ??????7.03.06.04.03.07.0不是 （3）?? ????7.01.02.02.01.07.0是 （4）?? ????6/13/13/16/16/16/13/13/1 是 4.7计算以下离散无记忆信道DMC 的容量及最佳分布 （1）P=???? ??????---p p p p p p 101001 解： 此为对称信道，达到C 需要等概，则该信道的最佳分布为： X q （X ） = x1 x2 x313 13 13 所以该信道的容量为：C=log 3+（1-p ）log(1?p)+p log p =log3-H 2（p ） (2)P=??????----2/)1(2/)1(2/2 /2/2/2/)1(2/)1(p p p p p p p p
解: 易得该信道为一个准对称信道，假定最佳分布为： X q （X ） = x1 x2 13 13 s1= (1?p)/2p/2p/2(1?p)/2 s2= (1?p)/2p/2p/2(1?p)/2 C=log k - N s *log M s -H =log 2-(1/2*log 1/2+1/2*log 1/2)+(1-p)log(1?p)/2+p log p =log2+(1-p)log(1?p)/2+p log p =log2-H 2（p ） (5)P= 132323 13 解: C=log 2+13×log 13+23×log 23 =0.083 4.10给定离散信道的信道转移概率矩阵P=????? ???????----q q q q p p p p 100100001001,计算其信道容量C 解:
《信息论与编码（第二版）》曹雪虹答案 第二章 一个马尔可夫信源有3个符号{}1,23,u u u ，转移概率为：()11|1/2p u u =，()21|1/2p u u =， ()31|0p u u =，()12|1/3p u u =，()22|0p u u =，()32|2/3p u u =，()13|1/3p u u =，()23|2/3p u u =，()33|0p u u =，画出状态图并求出各符号稳态概率。 解：状态图如下 状态转移矩阵为： 1/21/2 01/302/31/32/30p ?? ?= ? ??? 设状态u 1，u 2，u 3稳定后的概率分别为W 1，W 2、W 3 由1231WP W W W W =??++=?得1231132 231231 112331223231W W W W W W W W W W W W ?++=???+=???=???++=? 计算可得1231025925625W W W ?=???= ?? ?=?? 由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：(0|00)p =，(0|11)p =，(1|00)p =， (1|11)p =，(0|01)p =，(0|10)p =，(1|01)p =，(1|10)p =。画出状态图，并计算各状态的稳态概 率。 解：(0|00)(00|00)0.8p p == (0|01)(10|01)0.5p p == (0|11)(10|11)0.2p p == (0|10)(00|10)0.5p p == (1|00)(01|00)0.2p p == (1|01)(11|01)0.5p p == u 1 u 2 u 3 1/2 1/21/3 2/32/3 1/3
5.1 设信源1 234567()0.20.190.180.170.150.10.01X a a a a a a a p X ????=???? ???? (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率. 解： (1) 7 21222222()()log () 0.2log 0.20.19log 0.19 0.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.012.609/i i i H X p a p a bit symbol ==-=-?-?-?-?-?-?-?=∑ (3) 7 1 ()0.230.1930.1830.1730.153 0.140.0173.141 ()()/ 2.609 3.14183.1% i i i K k p x H X H X K R η===?+?+?+?+?+?+?====÷=∑ 5.2 对习题5.1的信源编二进制费诺码，计算编码效率. 解：
5.3对信源编二进制和三进制 哈夫曼码，计算各自的平均码长和编码效率. 解： 二进制哈夫曼码： x i p(x i)编码码字k i s61 s50.610 s40.391 s30.350 s20.261 x10.20102 x20.191112 x30.1800003 x40.1710013 x50.1500103 s10.111 x60.1001104 x70.01101114 三进制哈夫曼码： x i p(x i)编码码字k i s31 s20.540 s10.261 x10.2221 x20.190002 x30.181012 x40.172022