信息论与编码_第五、六章习题

1

第五章习题

张亚飞信息工程教研室

2011-2012学年第1学期

5-1 将下表所列的某六进制信源进行二进制编码，试问：

01001100101110111

1000001010110110

0101101110010011111

010110111011110111110

001011011101111011111

000001010011100101

1/21/41/161/161/161/16

u 1u 2u 3u 4u 5u 6

C6C5C4C3C2C1概率消息

C5是奇异码，所以，一定不是唯一可译码

3

11

2

3

4

5

6

23124

413

523

6:621

63

:2222221

64

63:1

64:22421

:2521:2521

C C C C C C ??????????????×<+++++=<<++×=+×>+×<

C1是定长的非奇异码，所以，一定是唯一可译码

C1、C3、C6是即时码，所以，一定是唯一可译码

C2和C4的判断需利用萨得纳斯-彼得森准则

111 011

1111 0111

01111111111

0111111

011

0S1

C2

C2是唯一可译码

111

0011001010S31

S20

110111001111

10011100101

0S4S1C2C4不是唯一可译码

C1、C2、C3、C6是唯一可译码

C1、C3、C6是非延长码

222111

()log 2log 44*log 162/2416H X bit =++=符号

6

1()

i i i K K p a ==∑()

log H X K m

η=

13/

K=码元符号

10.667

η=

23

111

1*2*(3456)* 2.125/ 2416

K K

==+++++=码元符号

230.941

ηη

==

6

11

2*3* 2.5/ 22

K=+=码元符号60.8

η=

第五章习题5-11

11110

5

4.644

0.96

0.04

x6

111043.6440.880.08x510132.6440.720.16x410032.4740.540.18x301032.1840.320.22x20021.64400.32x1码字码长Ki -logp(xi)

累加概率Pi 符号概率pi 信源符号xi （2）香农编码

()(0.32,0.22,0.18,0.16,0.08,0.04) 2.35/H X H bit ==符号

6

1

() 2.84/i i i K K p a ===∑码元符号

()0.827

log H X K m

η==

4

1111

1

0.04

x6

4111001

0.08x531100

1

0.16x42100

1

0.18x320110.22x220000

0.32

x1码长编码4

3

21

符号概率pi 信源符号xi （3）费诺编码

6

1() 2.4/i i i K K p a ===∑码元符号

()0.979

log H X K m

η==

（4）哈夫曼二进制编码

K

i

6

1() 2.4/i i i K K p a ===∑码元符号

()0.979

log H X K m

η==

（5）哈夫曼三进制编码

这里：m=3，n=6

令θ=2，m+θ(m－1)=7，则t=7－n=7－6=1

所以,需要增加一个虚假符号，或第一次取m-t=2个符号进行编码

哈夫曼三进制编码

K

i

6

1() 1.58/i i i K K p a ===∑码元符号

2() 2.350.938

log 1.58*log 3

H X K m η===

（6）若逐个符号进行二进制定长编码，要求不出差错

log /log 3K n m ≥=3/K =码元符号

'

log 3bit/R K m ==符号()0.783

log H X K m

η==

（7）若δ≤10-3，η=0.979，求定长编码L

()0.979,0.05

()H X H X ηεε

==≈+信息序列的自信息方差为

[]6

2

2

2

1

()(log )()0.523

i i i X p p H X σ==?=∑2

5

2

() 2.110X L σεδ

≥≈×

1、若有一信源

120.80.2X a a P ????

=????????

每秒钟发出2.66个信源符号，将此信源的输出符号

送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只传递2个二元符号，试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失真传输？若能，试说明如何编码并说明原因。

信息论与编码理论习题答案

信息论与编码理论习题 答案 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 。

信息论与编码课后习题答案

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

信息论与编码习题参考答案

bit/s 104.98310661.130)/)(()/(R bit/frame 10661.1322.3105)(H 105)(H bit/pels 322.310log )(log )()(H 76650510 10?=??=?=∴?=??=??====∑=frame bit X H s frame r x X a p a p x i i i 所需信息速率为：每帧图像的熵是：每个像素的熵是：，由熵的极值性： 由于亮度电平等概出现 . 5.2,,5.25.2477.210 log 300log )(H )(H pels /bit 300log )(log )()(H bit 3001030,10,,3001300 11倍左右比黑白电视系统高彩色电视系统信息率要图形所以传输相同的倍作用大信息量比黑白电视系统彩色电视系统每个像素每个像素的熵是：量化 所以每个像素需要用个亮度每个色彩度需要求下在满足黑白电视系统要个不同色彩度增加∴≈====∴=?∑=x x b p b p x i i i 个汉字 最少需要数描述一帧图像需要汉字每个汉字所包含信息量每个汉字所出现概率每帧图象所含信息量556 6 5 5 10322.6/10322.61 .0log 101.2)()()()(,log H(c):1.010000 1000 symble /bit 101.2128log 103)(103)(: ?∴?=-?=≥ ≤-=∴== ?=??=??=frame c H X H n c nH X H n p p x H X H ),...,,(21n p p p n m ≤≤0∑=-=m i i m p q 1 1)log(),,...,,(),...,,(2121m n q q p p p H p p p H m m m n -+≤ ∑∑+==- -=>-=<-=''-=''∴>- =''-=''>-=n m i i i m i i i n p p p p p p p H x x x x f x e x x x f x x e x x x f x x x x f 1 121log log ),...,,( )0(log )( 0log )log ()(0 log )log ()()0(log )( 又为凸函数。即又为凸函数，如下：先证明 时等式成立。 当且仅当时等式成立。当且仅当即可得： 的算术平均值的函数，函数的平均值小于变量由凸函数的性质，变量n m m m m m n m m m i i i m m m m m m i i i n m i i i m i i i n n m m m m m n m i i i m m n m i i n m i i n m i i n m i i n m i i i p p p m n q q p p p H p p p H q q p p q p p p H m n q q q p p p p p p p p p H p p p m n q q q p p m n q q m n p m n p m n m n p f m n m n p f m n p p ===-+≤--=-+--≤- -=∴===-+-≤- --=----=---≤---=- ++==+==+++=+=+=+=+=+=∑∑∑∑∑∑∑∑∑ ∑...)log(),,...,,(),...,,(log log ),,...,,() log(log log log log ),...,,(...) log(log log log log )()()() ()(log 2121211 211 1 1 21211 1111 1 X n

信息论与编码习题与答案第四章

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

信息论与编码理论课后习题答案高等教育出版社

信息论与编码理论习题解 第二章-信息量和熵 解: 平均每个符号长为:154 4.0312.032= ?+?秒 每个符号的熵为9183.03log 3 1 23log 32=?+?比特/符号 所以信息速率为444.34 15 9183.0=?比特/秒 解: 同步信号均相同不含信息,其余认为等概, 每个码字的信息量为 3*2=6 比特； 所以信息速率为600010006=?比特/秒 解:(a)一对骰子总点数为7的概率是 36 6 所以得到的信息量为 585.2)366(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以得到的信息量为 17.536 1 log 2= 比特 解: (a)任一特定排列的概率为 ! 521 ,所以给出的信息量为 58.225! 521 log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1352 13 13 521344!13C A =? 所以得到的信息量为 21.134 log 1313 52 2=C 比特. 解:易证每次出现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 解: 可能有的排列总数为 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-= 比特 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地； Z=0表示学过英语，Z=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/2 01/302/31/32/30p ?? ?= ? ??? 设状态u 1，u 2，u 3稳定后的概率分别为W 1，W 2、W 3 由1231WP W W W W =??++=?得1231132231231 112331223 231W 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 == (1|11)(11|11)0.8p p == (1|10)(01|10)0.5p p ==

信息论与编码第五章答案

设信源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

信息论与编码理论习题答案全解

信息论与编码理论习题答案全解

第二章 信息量和熵 2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的 信息速率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子，告诉你得到的总的点数为：(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 =2.585 bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？ 解：(a) )(a p =! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选 种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit

2.9 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的 点数之和，Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、 ),|(Y X Z H 、)|,(Y Z X H 、)|(X Z H 。 解：令第一第二第三颗骰子的结果分别为321,,x x x ，1x ，2x ，3x 相互独立， 则1x X =，21x x Y +=，321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6 log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ，所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ，所以)|(Y X H =2)(X H -)(Y H =1.8955 bit ),|(Y X Z H =)|(Y Z H =)(X H =2.585 bit )|,(Y Z X H =)|(Y X H +)|(XY Z H =1.8955+2.585=4.4805 bit 2.10 设一个系统传送10个数字，0，1，…，9。奇数在传送过程中以0.5的概 率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。 解： 信道 X Y 9,7,5,3,1=i 8,6,4,2,0=i √Χ );(Y X I =)(Y H -)|(X Y H 因为输入等概，由信道条件可知，

信息论与编码理论第二章习题答案

I (X ;Y=1)= P(x/Y 1)I(x;Y 1) x P(x/Y 1)log P(x/Y 1) P(x) = P(X 0/Y 1)log P(X 0/Y 1) P(X 0) P(X 1/Y 1)log P(X 1/Y 1) P(X 1) 部分答案，仅供参考。 信息速率是指平均每秒传输的信息量点和划出现的信息量分别为log3Jog3， 2’ 一秒钟点和划出现的次数平均为 1 15 2 1 ~4 0.20.4 - 3 3 一秒钟点和划分别出现的次数平均为巴5 4 4 那么根据两者出现的次数，可以计算一秒钟其信息量平均为10 log 3 5 竺 5 4 2 4 4 2 解： ⑻骰子A和B，掷出7点有以下6种可能： A=1,B=6; A=2,B=5; A=3,B=4; A=4,B=3; A=5,B=2; A=6,B=1 概率为6/36=1/6，所以信息量 -log(1/6)=1+log3 ~ bit (b)骰子A和B,掷出12点只有1种可能： A=6,B=6 概率为1/36，所以信息量 -log(1/36)=2+log9 ~ bit 解： 出现各点数的概率和信息量： 1 点：1/21 , log21 ?bit ; 2 点：2/21 , log21-1 ?bit ; 3 点：1/7 , log7 4 点：4/21 , log21-2 5 点：5/21 , log (21/5 )~; 6 点：2/ 7 , log(7/2)? 平均信息量： (1/21) X +(2/21) X +(1/7) X +(4/21) X +(5/21) X +(2/7) 解： X=1:考生被录取；X=0考生未被录取； Y=1：考生来自本市；Y=0考生来自外地； Z=1:考生学过英语；z=o：考生未学过英语 P(X=1)=1/4, P( X=q=3/4; P( Y=1/ X=1)=1/2 ；P( Y=1/ X=0)=1/10 ；P(Z=1/ Y=1 )=1, P( Z=1/ X=0, Y=0 )=, P( Z=1/ X=1, Y=0 )=, P(Z=1/Y=0)= (a)P(X=0,Y=1)=P(Y=1/X=0)P(X=0)=, P(X=1,Y=1)= P(Y=1/X=1)P(X=1)= P(Y=1)= P(X=0,Y=1)+ P(X=1,Y=1)= P(X=0/Y=1)=P(X=0,Y=1)/P(Y=1)=, P(X=1/Y=1)=P(X=1,Y=1)/P(Y=1)=

王育民信息论与编码理论第四章答案2

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.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它 的信息速率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子，告诉你得到的总的点数为：(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 =2.585 bit (2) 可能的唯一，为 {6，6} )( b p = 36 1 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克（52），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13牌，所给出的点数都不相同时得到多少信息量？

解：(a) )(a p = ! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选 种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit 2.9 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点 数之和，Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。 解：令第一第二第三颗骰子的结果分别为321,,x x x ，1x ，2x ，3x 相互独立， 则1x X =，21x x Y +=，321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ，所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ，所以)|(Y X H =2)(X H -)(Y H =1.8955 bit

信息论与编码 第四章 (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 解:

信息论与编码习题参考答案(全)

信息论与编码习题参考答案 第一章 单符号离散信源 1.1同时掷一对均匀的子，试求： (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 )(361 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： (3)信源空间： bit x H 32.436log 36 62log 3615)(=??+?? =∴ (4)信源空间： bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.11136 log log )(3611333==-=∴==

1.2如有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 =?=-=-=∴?=∑?=是同时落入某两格的概率 1.3从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为0.5%.如果你问一位男士：“你是否是红绿色盲？”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量？平均每个回答中各含有多少信息量？如果你问一位女士，则她的答案中含有多少平均信息量？ 解： bit w P w P w P w P m m P m I w P w I bit m P m P m P m P m bit m P m I bit m P m I n n y y n n y y n n y y n n y y 0454.0log99.5%99.5%-log0.5%-0.5% )(log )()(log )()(H % 5.99log )(log )(%5.0log )(log )(36 6.0log93%93%-log7%-7% )(log )()(log )()(H 105.0%93log )(log )(84.3%7log )(log )(: =??=?-?-=-=-=-=-==??=?-?-==-=-==-=-=平均每个回答信息量：：回答“不是”的信息量回答“是”的信息量：对于女： 平均每个回答信息量：：回答“不是”的信息量回答“是”的信息量：对于男士

信息论与编码课后习题答案

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=符号 2．设有一个无记忆信源发出符号A 和B ，已知4 3 41)(.)(= =B p A p 。求： ①计算该信源熵； ②设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率； ③又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。 解：①∑- =X i i x p x p X H )(log )()( = bit/符号 ②发出二重符号序列消息的信源,发出四种消息的概率分别为 1614141)(=?=AA p 1634341 )(=?=AB p 1634143)(=?=BA p 1694343)(=?=BB p 用费诺编码方法 代码组 b i BB 0 1 BA 10 2 AB 110 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

(完整版)信息论与编码习题参考答案

1.6为了使电视图象获得良好的清晰度和规定的对比度，需要用5×105个像素和10个不同的亮度电平，并设每秒要传送30帧图象，所有的像素是独立的，且所有亮度电平等概出现。求传输此图象所需要的信息率（bit/s ）。 解： bit/s 104.98310661.130)/)(()/(R bit/frame 10661.1322.3105)(H 105)(H bit/pels 322.310log )(log )()(H 76650510 10?=??=?=∴?=??=??====∑=frame bit X H s frame r x X a p a p x i i i 所需信息速率为：每帧图像的熵是：每个像素的熵是：，由熵的极值性： 由于亮度电平等概出现 1.7设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度。试证明传输这种彩电系统的信息率要比黑白系统的信息率大 2.5倍左右。 证: . 5.2,,5.25.2477.210 log 300log )(H )(H pels /bit 300log )(log )()(H bit 3001030,10,,3001300 11倍左右比黑白电视系统高彩色电视系统信息率要图形所以传输相同的倍作用大信息量比黑白电视系统彩色电视系统每个像素每个像素的熵是：量化 所以每个像素需要用个亮度每个色彩度需要求下在满足黑白电视系统要个不同色彩度增加∴≈====∴=?∑=x x b p b p x i i i Θ 1.8每帧电视图像可以认为是由3×105个像素组成，所以像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现。问每帧图像含有多少信息量？若现在有一个广播员，在约10000个汉字中选1000个字来口述这一电视图像，试问若要恰当地描述此图像，广播员在口述中至少需要多少汉字？ 解: 个汉字 最少需要数描述一帧图像需要汉字每个汉字所包含信息量每个汉字所出现概率每帧图象所含信息量556 6 5 5 10322.6/10322.61 .0log 101.2)()()()(,log H(c):1.010000 1000 symble /bit 101.2128log 103)(103)(: ?∴?=-?=≥ ≤-=∴== ?=??=??=frame c H X H n c nH X H n p p x H X H 1.9 给 定 一 个 概 率 分 布 ) ,...,,(21n p p p 和一个整数m ， n m ≤≤0。定义 ∑=-=m i i m p q 1 1，证明： )log(),,...,,(),...,,(2121m n q q p p p H p p p H m m m n -+≤。并说明等式何时成立？ 证： ∑∑+==- -=>-=<-=''-=''∴>- =''-=''>-=n m i i i m i i i n p p p p p p p H x x x x f x e x x x f x x e x x x f x x x x f 1 121log log ),...,,( )0(log )( 0log )log ()(0 log )log ()()0(log )(ΘΘ又为凸函数。即又为凸函数，如下：先证明 时等式成立。 当且仅当时等式成立。当且仅当即可得： 的算术平均值的函数，函数的平均值小于变量由凸函数的性质，变量n m m m m m n m m m i i i m m m m m m i i i n m i i i m i i i n n m m m m m n m i i i m m n m i i n m i i n m i i n m i i n m i i i p p p m n q q p p p H p p p H q q p p q p p p H m n q q q p p p p p p p p p H p p p m n q q q p p m n q q m n p m n p m n m n p f m n m n p f m n p p ===-+≤--=-+--≤- -=∴===-+-≤- --=----=---≤---=- ++==+==+++=+=+=+=+=+=∑∑∑∑∑∑∑∑∑ ∑...)log(),,...,,(),...,,(log log ),,...,,() log(log log log log ),...,,(...) log(log log log log )()()() ()(log 2121211 211 1 1 21211 1111 1 ΘΘ 2.13把n 个二进制对称信道串接起来，每个二进制对称信道的错误传输概率为p(0

信息论与编码习题与答案第五章

5-10 设有离散无记忆信源}03.0,07.0,10.0,18.0,25.0,37.0{)(=X P 。 （1）求该信源符号熵H(X)。 （2）用哈夫曼编码编成二元变长码，计算其编码效率。 （3）要求译码错误小于3 10-，采用定长二元码达到（2）中的哈夫曼编码效率，问需要多少个信源符号连在一起编？ 解：（1）信源符号熵为 symbol bit x p x p X H i i i /23.203.0log 03.007.0log 07.010.0log 10.018.0log 18.025.0log 25.037.0log 37.0) (log )()(222222=------=-=∑ （2） 1 x 3x 2x 6 x 5x 4x 0.370.250.180.100.070.03 01 1 1 1 1 0.10 0.20 0.38 0.62 1.00 000111 10110001001 符号概率 编码 该哈夫曼码的平均码长为 符号 码元/3.2403.0407.0310.0218.0225.0237.0)(=?+?+?+?+?+?==∑i i i K x p K 编码效率为9696.03.223 .2)(=== K X H η (3)信源序列的自信息方差为 2 2 22) (792.0)]([)]()[log ()(bit X H x p x p X i i i =-=∑σ 7.00696.90)() (==+= εε η得，由X H X H

5 3 22210 2.6110)7.00(92.70)(?=?=≥-δεσX L 由切比雪夫不等式可得 所以，至少需要1.62×105个信源符号一起编码才能满足要求。 5-12 已知一信源包含8个消息符号，其出现的概率 }04.0,07.0,1.0,06.0,05.0,4.0,18.0,1.0{)(=X P ，则求： （1）该信源在每秒内发出1个符号，求该信源的熵及信息传输速率。 （2）对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率。 （3）采用香农编码，写出相应码字，求出编码效率。 （4）进行费诺编码，写出相应码字，求出编码效率。 解：（1）信源熵 symbol bit x p x p X H i i i /55.204.0log 04.007.0log 07.01.0log 1.006.0log 06.005.0log 05.04.0log 4.018.0log 18.01.0log 1.0) (log )()(22222222=--------=-=∑ 信息传输速率为 s b i t R /55.2= （2）哈夫曼编码： 2 x 8 x 6 x 5x 4x 3x 1x 7x 0.40.180.10.10.070.060.05 0.04符号概率 码字 1 0.09 1 0.130.19 1 0.23 1 0.37 0 10.6 1 1.001 001 01100000100 0101 0001000011 信源各符号的对应哈夫曼曼码字如下： 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 011 001 1 00010 0101 0000 0100 00011 平均码长为