信息论与编码习题解答

信息论与编码习题解答

第一章

1. 一位朋友很不赞成“通信的目的是传送信息”及“消息中未知的成分才算是信息”这些说法。他举例说：我多遍地欣赏梅兰芳大师的同一段表演，百看不厌，大师正在唱的正在表演的使我愉快，将要唱的和表演的我都知道，照你们的说法电视里没给我任何信息，怎么能让我接受呢？请从信息论的角度对此做出解释。（主要从狭义信息论与广义信息论研究的内容去理解和解释）

答：从狭义信息论角度，虽然将要表演的内容观众已知，但是每一次演出不可能完全相同。而观众在欣赏的同时也在接受着新的感官和视听享受。从这一角度来说，观众还是可以得到新的信息的。另一种解释可以从广义信息论的角度来分析，它涉及了信息的社会性、实用性等主观因素，同时受知识水平、文化素质的影响。京剧朋友们在欣赏京剧时也因为主观因素而获得了享受，因此属于广义信息论的范畴。

2．利用下图（图1.2）所示的通信系统分别传送同样时间（例如十分钟）的重大新闻公告和轻音乐，它们在接收端各方框的输入中所含的信息是否相同，为什么？

信源 加密 加密 密钥 信道 信宿 信源 译码 信源 编码 信道 干扰源 信道 编码 译码 解密 解密 密钥

图1.2 通信系统的一般框图

答：重大新闻是语言，频率为300~3400Hz，而轻音乐的频率为20~20000Hz。同样的时间内轻音乐的采样编码的数据要比语音的数据量大，按码元熵值，音乐的信息量要比新闻大。但是在信宿端，按信息的不确定度，信息量就应分别对待，对于新闻与音乐的信息量大小在广义上说，因人而异。

第二章

1．一珍珠养殖场收获240颗外观及重量完全相同的特大珍珠，但不幸被人用外观相同但重量仅有微小差异的假珠换掉1颗。（1）一人随手取出3颗，经测量恰好找出了假珠，问这一事件大约给出了多少比特的信息量；（2）不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多6次能找出，结果确是如此，问后一事件给出多少信息量；（3）对上述结果作出解释。 解：（1）从240颗珍珠中取3颗，其中恰好有1颗假珠的概率为：

239!P?CC22393240?2!?237!?240!3!?237!1240/3?1/80

所以，此事件给出的信息量为：I= – log2P = log280=6.32 (bit)

（2）240颗中含1颗假珠，用天平等分法最多6次即可找到假珠，这是一个必然事件，因此信息量为0。

（3）按照Shannon对信息量的定义，只在事件含有不确定成分，才有信息量，并且不确定成分越大，信息量也越大，必然事件则没有信息量。但是从广义信息论的角度，如果那个人不知道用天平二分法找假珠，另一个告诉他这个方法，使他由不知道到知道，也应该含有一定的信息量。

2．每帧电视图像可以认为是由3?105个象素组成，所有象素均独立变化，且每一象素又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？如果一个广播员在约10000个汉字的字汇中选取1000个字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，且彼此独立）？若要恰当地描述此图像，广播员在口述中至少需用多少汉字？

解：由于每一象素取128个不同的亮度电平，各个亮度电平等概率出现。因此每个亮度电平包含的信息量为

I(X) = – lb(1/128)=lb128=7 bit/像素

每帧图像中像素均是独立变化的，因此每帧图像信源就是离散亮度电平信源的无记忆N次扩展。由此，每帧图像包含的信息量为

I(XN) = NI(X)= 3?105?7 =2.1?106 bit/帧

广播员在约10000个汉字中选取字汇来口述此电视图像，各个汉字等概分布，因此每个汉字包含的信息量为

I(Y) = – lb(1/10000)=lb1000=13.29 bit/字

广播员述电视图像是从这个汉字字汇信源中独立地选取1000个字进行描述，因此广播员描述此图像所广播的信息量是

I(YN) = NI(Y)= 1000?13.29 =1.329 ?104 bit/字

由于口述一个汉字所包含的信息量为I(Y)，而一帧电视图像包含的信息量是I(XN)，因此广播员要恰当地描述此图像，需要的汉字数量为：

I(XN)I(Y)3．已知 X： 1, 0

P(X)： p, 1 – p （1）求证：H(X) = H(p)

?2.1?10613.29?1.58?105字

（2）求H(p)并作其曲线，解释其含义。

（1） 证明：H(X)= I(X1) +I(X2) = –plbp – (1–p)lb (1–p) =H(p) （2） 解：

H(p) 1 0 0.5 1 p

该H(p)曲线说明，当0与1等概出现时，即p=0.5时，熵最大。当p由0.5分别趋向于0和1时，熵逐渐减小至0。

4．证明H(X3|X1X2) ? H(X2|X1)，并说明等式成立的条件。

证明：设离散平稳信源输出的随机符号序列为…X1,X2,X3,…。又设

x1?X1,x2?X2,x3?X3,而且x1,x2,x3都取自于同一符号集A??a1,a2,?,ag?，并满足有

?P(xX2X12|x1)?1,?P(x3|x2)?1,?P(x3|x1x2)?1,X3X3?P(x)??P(x)??P(x)?1123X2X3

??P(xx)???P(xx)???P(xx)?1122313X1X2X2X3X1X3???P(xxx)?1123X1X2X3?P(xxx)?P(xx)12323X1

?P(xxx)?P(xx)12313X2?P(xxx)?P(xx)12312X3在区域[0，1]内设f(x)=－xlogx, f(x)在[0，1]内是?型凸函数，所以满足詹森不等式

?Pf(x)?f(?Px) 其中?P?1

iiiiii?1i?1i?1qqq现今xi?P(x3|x2x1),设其概率空间为P(x1|x2)，并满足

?P(x|x)?1

12X1所以根据詹森不等式得

?P(xX1X11|x2)[?xilogxi]??[?P(x1|x2)xi]log[?P(x1|x2)xi]X1X1??P(x1|x2)P(x3|x1x2)logP(x3|x1x2)???P(x1|x2)P(x3|x1x2)log?P(x1|x2)P(x3|x1x2)X1X1

所以

?P(xxx)?P(xx)12323X1?P(xxX113|x2)P(x2)?P(x3|x2)P(x2)

上式对所有x1,x2,x3的取值都成立，所以

?P(xxX113|x2)?P(x3|x2)

?P(xX11|x2)P(x3|x1x2)?P(x3|x2)所以??P(x1x3|x2)logP(x3|x1x2)??P(x3|x2)logP(x3|x2)X1因为0?P(x2)?1,x2?X2，所以上式两边相乘，等号不变。有

??P(x2)P(x1x3|x2)logP(x3|x1x2)??P(x2)P(x3|x2)logP(x3|x2)

X1上式对所有x2,x3都成立，所以对所有x2,x3求和下式也成立

????P(x1x2x3)logP(x3|x1x2)????P(x2x3)logP(x3|x2)

X1X2X3X2X3因为 H(X3|X1X2) ? H(X3|X2) 所以是平稳信源 H(X3|X2) = H(X2|X1) 得 H(X3|X1X2) ? H(X2|X1)

只有当P(x3|x1x2)?P(x3|x2)(对所有x1,x2,x3)时等式成立。

'?p1??， 5．设有一概率空间，其概率分布为{p1, p2, …, pq}，且p1>p2。若取p1'p2?p2??，其中0 <2? ? p1 – p2，而其它概率值不变。证明由此得到的新的概率空间的熵

是增加的，并用熵的物理意义加以解释。 证明：令a?得

?p1?p2?0的小数1?a?p1?p2??

p1?p2ap1?(1?a)p2?(1?a)p1?ap2??p1?p2p1?p1?p2??p2?p2??p1?p2p1?p2???p1??p2?p1??p1?p2p1?p2

因为f(x)=－xlogx是?型函数，根据?型凸函数的定义有

f[ap1?(1?a)p2]?af(p1)?(1?a)f(p2)

所以 f(p2??)?af(p1)?(1?a)f(p2) 即 ?(p2??)log(p2??)??[同理得

?p1?p2p1logp1?p1?p2??p2logp2]

p1?p2(1??)??[ ?(p1??)logpp1?p2???p1logp1?p2logp2]

p1?p2p1?p2以上两不等式两边相加，不等号不变。

所以得

?(p1??)log(p1??)?(p2??)log(p2??)??p1logp2?p2logp2

6．某办公室和其上级机关的自动传真机均兼有电话功能。根据多年来对双方相互通信次数的统计，该办公室给上级机关发传真和打电话占的比例约为3:7，但发传真时约有5%的次数对方按电话接续而振铃，拨电话时约有1%的次数对方按传真接续而不振铃。求：（1）上级机关值班员听到电话振铃而对此次通信的疑义度；（2）接续信道的噪声熵。 解：设发传真和打电话分别为事件X1与X2,对方按传真和按电话接续分别为事件Y1和Y2,则

P(X1)=30%,P(X2)=70%

P(Y1|X1)=95%, P(Y2|X1)=5%, P(Y1|X2)=1%, P(Y2|X2)=99% P(X1Y1)=0.285, P(X1Y2)=0.015 P(X2Y1)=0.007, P(X2Y2)=0.693

P(Y1)= P(X1Y1)+ P(X2Y1)= 0.292 P(Y2)=1－ P(Y1)= 0.708

H(X)=－ P(X1)lb P(X1) － P(X2)lb P(X2) =0.8814 bit/符号

H(Y)=－ P(Y1)lb P(Y1) － P(Y2)lb P(Y2) =0.8713 bit/符号 22lbP H(XY)= ? ? ? P (XiYj ) (XiYj ) =1.0239 bit/两个信符 i?1j?1 I(X;Y)=H(X)+H(Y) － H(XY)=0.7288 bit/信符 （1）听到电话振铃的疑义度

H(X|Y2)=－ P(X1Y2)lb P(X1Y2)－ P(X2Y2)lb P(X2Y2)= 0.4575 bit/信符 （2）接续信道的噪声熵

H(Y|X)=H(Y)－I(X;Y)=0.1425 bit/信符

7．四个等概分布的消息M1，M2，M3，M4被送入如图所示的信道进行传输，通过编码使M1 = 00，M2 = 01，M3 =10，M4 =11。求输入是M1和输出符号是0的互信息量是多少？如果知道第2个符号也是0，这时带来多少附加信息量？

X Y p 0 0 p p 1 1 p 图2.6

解：信源P(M1)= P(M2)= P(M3)= P(M4)=1/4, 信道为二元对称无记忆信道，消息Mi与码字一一对应，所以设Mi

?(xi1xi2)设接收序列为Y=(y1y2)

接收到第一个数字为0，即y1=0。那么，接收到第一个数字0与M1之间的互信息为

I(M1;y1?0)?logP(y1?0|M1)

P(y1?0)因为信道为无记忆信道，所以

P(y1?0|M1)?P(y1?0|x11x12?00)?P(y1?0|x11?0)?P(0|0)?p同理，得I(y1

?0|Mi)?P(y1?0|xi1xi2)?P(y1?0|xi1)

输出第一个符号是y1=0时，

有可能是四个消息中任意一个第一个数字传送来的。 所以

P(y1?0)??P(Mi)(y1?0|Mi)i?141?[P(y1?0|x11?0)?P(y1?0|x21?0)?P(y1?0|x31?1)?P(y1?0|x41?1)]41?2I(M1;y1?0)?1?lbp 比特

接收到第二个数字也是0时，得到关于M1的附加互信息为 I(M1;y2?0|y1?0)?I(M1;y1y2?00)?I(M1;y1?0)

其中

故得

I(M1;y1y2?00)?logP(y1y2?00|M1)

P(y1y2?00)同理，因为信道是无记忆信道，

所以

P(y1y2?00|Mi)?P(y1y2?00|xi1xi2)?P(y1?0|xi1)P(y2?0|xi2)

得

P(y1y2?00|M1)?P(y1?0|x11?0)P(y2?0|x12?0)?P(0|0)P(0|0)?p42

输出端出现第一个符号和第二个符号都为0的概率为

P(y1y2?00)??P(Mi)(y1y2?00|Mi)i?11?[P(y1?0|x11?0)P(y2?0|x12?0)?P(y1?0|x21?0)P(y2?0|x21?1) 4?P(y1?0|x31?1)P(y2?0|x31?0)?P(y1?0|x41?1)P(y2?0|x41?1)]?14p2?2(1?lbp) 比特 所以I(M1;y1y2?00)?log14得附加互信息为

I(M1;y2?0|y1?0)?1?lbp 比特

8．证明若随机变量X，Y，Z构成马氏链，即X→Y→Z，则有Z→Y→X。

证明：因为(X,Y, Z)是马氏链，有P(z|xy)=P(z|y),对所有x?X,y?Y,z?Z成立，而

P(x|yz)=P(xyz)/P(yz) = P(z|xy) P(xy)/ P(y) P(z|y)

= P(z|xy) P(y) P(x|y)/ P(y) P(z|y) 对所有x?X,y?Y,z?Z成立

故得P(x|yz)=P(x|y) 对所有x?X,y?Y,z?Z成立 所以(Z,Y, X)也是马氏链。

习题（第3章）

1．发出二重符号序列消息的信源熵为H(X2)，而一阶马尔可夫信源的信源熵为H(X/X)。试比较这两者的大小，并说明原因。 2． 设随机变量序列(XYZ)是马氏链，且X：{a1, a2, …, ar}，Y：{ b1, b2, …, bs}，Z：{ c1, c2, …, cL}。又设X与Y之间的转移概率为p(bj /ai) ( i =1, 2, …, r；j =1, 2, …, s)；Y与Z之间的转移概率为p(ck /bj) ( j =1, 2, …, s；k =1, 2, …, L)。试证明X与Y之间的转移概率为

p?ck/ai???p?bj/ai?p?ck/bj?

j?1s

3． 有一个马尔可夫信源，已知p(x1x1)?23，p(x2x1)?13，p(x1x2)?1，p(x2x2)?0，

试画出该信源的香农线图，并求出信源熵。

2一步转移矩阵为P，P?[3113] 02?Q(x)??13Q(x1)?Q(x2)?1?可得 ? Q(x2)?Q(x1)3??Q(x2)?Q(x1)?1??3Q(x1)?4 故 {1Q(x2)?4所以，信源熵为

H??H2????Q(Ei)P(ak|Ei)logP(ak|Ei)i?1k?12221??Q(Ei)H(ak|Ei)?Q(x1)H(,)?Q(x2)H(1,0)

33i?13231?[log?log3]?0.6887比特/符号4323

4．一个马尔科夫链的基本符号为0，1，2三种，他们以等概率出现，且具有相同的转移概率，没有任何固定约束，试（1）画出单纯马尔科夫链信源的香农线图，并求稳定状态下的信源熵H1。（2）画出二阶马尔科夫链信源的香农线图，并求稳定状态下的信源熵H2。 解：（1）由已知得P(j|i)?21 i,j?0,1,2则香农线图如下 3 1/3 1/3 1/3 0 1/3 1/3 1/3 1/3 1/3 2 1/3 1

稳定时 H(X)?3?log bit/符号 3?1.585

13（2）二阶马尔可夫信源，初始状态有3?9个，等概分布

2 P(m|ij)?2221 3 H2????P(m|ij)logP(m|ij)?1.585 bit/符号

i?0j?0m?001 00 02 10 22 21 20 12 11

图中每条路径概率均为1/3

5．某一阶马尔可夫信源的状态转移如图3.4所示，信源符号集为X：{0, 1, 2}，并定义p?1?p。试求：

（1） 信源的极限熵H?；

（2） p取何值时H?取最大值。

p p p/2 0 p/2 p/2 p/2 p/2 p/2 2 1 p 图3.4

解：（1）

?p?p一步转移矩阵为P，P???2?p??2p2pp2p?2?p? 2?p???pp?Q(0)?pQ(0)?Q(1)?Q(2)?22?pp?Q(1)?Q(0)?pQ(1)?Q(2)可得 ? 22?ppQ(2)?Q(0)?Q(1)?pQ(2)?22?Q(0)?Q(1)?Q(2)?1?计算得Q(0)?Q(1)?Q(2)?1 3则得P(0)?P(1)?P(2)?所以，信源熵为

1 3H??H2??Q(Ei)H(X|Ei)i?12?P(0)H(X|0)?P(1)H(X|1)?P(2)H(X|2)1pp1pp1pp?H(p,,)?H(,p,)?H(,,p)322322322??plogp?plogp?p比特/符号

（2）因为 H???(1?p)log(1?p)?plogp?p 求其对p的一阶导数

?H?11?log(1?p)??logp??1?pln2ln2

2(1?p)?log(1?p)?logp?log2?logp令

?H?2(1?p)?0,得log?0 ?pp所以当p=2/3时，信源的极限熵达到最大值。 6．设随机变量序列X=X1X2?XN通过某离散信道{X; P(Y/X); Y}，其输出序列为Y=Y1Y2?YN。试证明若

（1）p (bjN / ai1 ai1…aiN；bj1 bj2…bjN –1) = p (bjN / aiN)；

（2）p (bj1 bj2…bjN –1 / ai1 ai1…aiN) = p (bj1 bj2…bjN –1 / ai1 ai1…aiN–1) 则该信道的转移概率为

P(X/Y)?p?bj1bj2?bjN/ai1ai2?aiN???p?bjk/aik?

k?1N证明：

?p?bj1bj2?bjN?1/ai1ai2?aiN??p?bjN/ai1ai2?aiN;bi1bi2?biN?1??p?bj1bj2?bjN?1/ai1ai2?aiN?1??p?bjN/aiN??...??p?bjk/aik?k?1NP(X/Y)?p?bj1bj2?bjN/ai1ai2?aiN?

?p?bj1bj2?bjN?2/ai1ai2?aiN?2??p?bjN?1/aiN?1??p?bjN/aiN?7．设信源X的N次扩展信源X=X1X2?XN通过信道{X; P(Y/X); Y}，其输出序列为Y=Y1Y2?YN。试证明

（1） 当信源为无记忆信源，即X1X2?XN之间统计独立时，有

?I?Xk;Yk??I?X;Y?；

k?1N

PE?1?Pc?1?{P(x1)P(y1|x1)?P(x1)P(y2|x1)?P(x3)P(y3|x3)}?1?{1/2?1/2?1/2?1/3?1/4?1/2}?1?13/24?11/24LM

15．10 （1）PE?M1（2）PE?M1（3）PE?M??P(yj?1i?1i?*LMj|xi)?1/2(P(y1|x2)?P(y2|x1))?p

??P(yj?1i?1i?*LMj|xi)?1/2P(y1|x2)?p/2

??P(yj?1i?1i?*j|xi)?1/2(P(y2|x2)?P(y2|x1))?p

5．11 ？？

5．12 （1）对信源四个消息进行编码，选择码长n=4，这组码为 C : {(x1,x2,1/2,1/2)} xi?0或1 i=(1,2) 编码后的信息传输率 R?log41? 比特/符号 42 （2）设接收序列??(y1y2y3y4) yi?{0,1}(i?1,2,3,4)根据信道的传输特性，输入序列

?共有16个，正好分成4个互不相交的子集，每个码字只传输到其中对应的一个子集：

?1?(0 0 1/2 1/2)?(0 0 y3 y4) ?2?(0 1 1/2 1/2)?(0 1 y3 y4) ?3?(1 0 1/2 1/2)?(1 0 y3 y4) ?4?(1 1 1/2 1/2)?(1 1 y3 y4) 所以根据选择的译码规则

f(y1y2y3y4)=(y1y21/2 1/2)

正好将接收序列译成所发送的码字，可计算每个码字引起的错误概率 Pe(i)?[所以有PE??P(?|?) F(?)??]?0

iiY?P(?)PiCie?0。

513(1) P(x|y)?P(xy)，又P(xy)?P(x)P(y|x),P(y)??P(xy),根据题目所给的数据得 P(y)XP(y)=[7/12 5/12]

P(x|y)= 6/7 3/5

1/7 2/5 又H(X)???P(x)logP(x)?0.811 比特/符号

XH(X|Y)????P(x)P(x|y)logP(x|y)?XY [?3/4?2/3log2/3?1/4?1/3log1/3?3/4?1/3log1/3?1/4?2/3log2/3]

??2/3log2/3?1/3log1/3?0.39?0.528?0.918 所以 I(X;Y)?H(X)?H(X|Y)?0.062 比特/符号 (2) 此信道为二元对称信道，所以信道容量

C?1?H(p)?1?H(2/3)?0.082 比特/符号

根据二元对称信道的性质可知，输入符号为等概分布，即P(0)=P(1)=1/2时信道的信息传输率才能达到这个信道的容量值。 5．14 （1）由P(y)??P(xy),得

X3P(y)=[1/2 1/4+1/4a 1/4-1/4a]

所以

H(Y)???P(yi)logP(yi)?1/2?(1/4?1/4a)log(1/4?1/4a)?i?1

(1/4?1/4a)log(1/4?1/4a),H(Y|X)????P(x)P(y|x)logP(y|x)?a(1/2log2?1/2log2)XY（2）?(1?a)(1/2log2?1/4log4)?(1?a)1/4log4

?3/2?1/2a比特/符号(3) C?H(Y)?H(Y|X)??1?1/2a?1/4(1?a)log(1/4?1/4a)?1/4(1?a)log(1/4?1/4a)

6.1 (1) 收到传真的概率为8/(4+8+3+1)*2/(7+1+2)=1/10 I=-log1/10=3.3 比特

（2）可采取压缩编码，安最佳编码原则编码等措施

（3）编码时码长尽可能长，这样根据香浓第二定理，总存在一种编码，只要码长足够长，总存在一种编码，是错误概率任意小。最好结合实际分析如何克服随机，突发干扰。 （4）C=Blog(1+S/N)=2.048log(1+10率为8.34Mbps。

6.2 （1）h(x)??p(x)logp(x)dx?1/2log2(2?e?) 比特/样值

（2）对样值进行256级量化，当其服从均匀分布时，信源有最大熵，H=log256=8比特/符号 （3）fs?120KHz?12KHz?108KHz B?8fs/2?432KHz

所以 C?Blog2(1?S/N)?4.31M。

1.2)=8.34Mbps，不失真条件下，该信道允许最大信息传输速

?2（4）S/N=36dB, C=5.17Mbps

所以Sc?(5.17?4.31)/4.31?20%。 6.3 (1) h(x)?1/2log2(2?e?) 比特/样值 （2） 冗余度=

28?8K?8.55K?100%?86.6%

8?8K （3）C?Blog2(1?S/N) 其中C=9.6K B=1.2288*2Mbps, 得S/N=-25.7dB

(4) C?Blog2(1?S/N)=2.4576log2(1?106.4 由于P(x)=1/2=

0.3)?3.88Mbps

1,所以电压为1V~(-1)V上的均匀分布，

1?(?1) 又 n?2?0T',所以 10=2?0，?0=5

ht=2?0*（1/2）lb(4Ps)= ?0lb(4*1)=2?0=10 bit/s 6.5

hp(x)???p(x)lnp(x)dx?11???(1?|x|)ln(1?|x|)dx

?1??2?(1?x)ln(1?x)dx?11又n?2?0T',所以 10=2?0，?0=5

所以ht?2?0hp(x)??20(1?x)ln(1?x)dx

0?16.6

h(x)???p(x)lnp(x)dx02???kxlnkx()dx02

6.7 C?Blog2(1?S/N)?Blog2(1?10)?30?30?10?log210?B*9.97

所以 B=3?10Hz.

6.8 (1)C?log264?log216?5?10?25?6?10bit

(2)又C?Blog2(1?S/N) 而 10log10SN58367?30dB，

所以 S/N=10,

所以C?Blog2(1?10)=9.97B B=6?10Hz 6.9 C?Blog2(1?S/N)

所以 5.6?4log2(1??5733PP)?4(1?) Nn0B所以 P=3.2?10W. 6.10 C?Blog2(1?S/N)=

Sn0BSlog2(1?)

n0Sn0B所以limC?lim[B???B???n0BSSlog2(1?)]() （2） Sn0Bn0利用关系式 lim1/xlog2(1?x)?log2e?1.44，

x??0所以式（2）变为limC?B???SSlog2e?1.44，为一常量。 n0n06.11 H(X)?????/2?/2AcosxlnAcosxdx

=?AlnA???/2?/2cosxdx???/2??/2Acosxlncosxdx

再由逐步分布积分得 H(X)=-2AlnA-2Aln2+2A. 因为

???/2?/2p(x)dx?1，所以2A=1 A=1/2

a 所以 H(X)=1 奈特/自由度 6.12 （1）H(X)?? =??0ap(x)logp(x)dx

bxlogbxdx

22?0 =-logb

?a0p(x)dx-2b

?a0x2logxdx

2ba32ba3loge?loga?logb =93 因为

?a0p(x)dx=1，所以b=1/83。 a3 故H(X)=2/3loge+loga-log3

dX?1 , 所以 H(Y)=2/3loge+loga-log3 dYdX(3) 若Y=2X ，则?1/2，所以H(Y)=H(X)-log1/2=2/3loge+loga-log3/2。

dY(2) 若Y=X+A，则

6.13 C?Blog2(1?S/n0B)?6.5?10log2(1?45.5/6.5)?1.95?10bit/s 6.14 C?Blog2(1?S/N)

(1)C?10?log2(1?10)?3.46?10bit/s

(2)10?log2(1?10)?Blog2(1?5) 所以 B=1.34?10Hz (3) 10?log2(1?10)?0.5?10log2(1?S/N) 所以 S/N=120

66666676第七章 习题

1. 设某二址接入信道，输入X1, X2和输出Y的条件概率为P(Y/X1X2 )，其值是：

p (0/00) = 1– ? p (0/01) =1/2 p (0/10) =1/2 p (0/11) =? p (1/00) =? p (1/01) =1/2 p (1/10) =1/2 p (1/11)=1–? 其中? <1/2，试求其容量界限。

2. 设某广播信道，其输入X和输出Y1、Y2之间的条件概率P(Y1/X)和P(Y2/X)的具体值是：

p(Y1/X): p(0/0)?1??1p(Y2/X): p(0/0)?1??2p(1/0)??1p(1/0)??2p(0/1)??1p(0/1)??2p(1/1)?1??1p(1/1)?1??2其中?

1

<1/2, ? 2 <1/2，试求其容量界限。 3. 计算图7.12中二址接入信道的容量。

X1X200011Y0121101111图7.16

第8章 习题

1. 设输入符号表与输出符号表为X=Y={0, 1, 2, 3}，且输入信号的分布为

p(X = i) = 1/4, i = 0, 1, 2, 3

设失真矩阵为

?0?1d???1??1?求Dmax和Dmin及R(Dmax)。

101111011??1? 1??0??

?X??0?P(X)???1???4ri?111214Dmin??p(ai)?min d?ai,bj?

j?43? 1?4???r?Dmax?min??p(ai)? d?ai,bj??

j?i?1??0111??1011?? ?D????1101???1110??Dmin?0

?3333?3Dmax?min?,,,??

?4444?4R?Dmax??0

1??X???10??2. 设无记忆信源???p(X)??1/31/31/3??，接收符号AY ={1/2, 1/2}，失真矩阵?????12???D??11?。试求：Dmax和Dmin及达到Dmax和Dmin时的转移概率矩阵。

?21???1??X???10?P(X)???111? ???33??3??12??

?D???11????21???44?4Dmin?1, Dmax?min?,??

?33?3在Dmin时，

??p?bjai??1?由于?j?Ji，所以

??p?bjai?, j?Ji?10?11? ?P???22????01??在Dmax时，

由于pbjai?Pbj，所以

?????10??

?P???10????10??3. 三元信源的概率分别为p(0) = 0.4, p(1) = 0.4, p(2) = 0.2，失真函数dij为：当i = j时，dij =

0；当i ? j时，dij = 1 (i, j = 0, 1, 2)，求信息率失真函数R(D)。

12??X??0??P(X)??0.40.40.2?

?????011??

?D???101????110??5221lb5Dmin?0，R?0??H?X??52?5lb2?5lb5?lb5?0.8?1.52

R?Dmax??0

由定义知：R(D)?rsDmax?min?0.6, 0.6, 0.8??0.6

min?I(X;Y)?，I?X;Y??H?X??H?X|Y? ??平均失真度一定与试验信道的平均错误概率Pe有关，即

Pbj/ai?BDD???P(ai)P(bj/ai)d(ai,bj)i?1j?1s

??P(ai)P(bj/ai)?Pei?j根据保真度准则，应有Pe ? D 根据Fano不等式

H(X/Y) ? H (Pe) + Pe log (r–1)

?H?X|Y??H?Pe??Pelb2?H?X|Y??H?Pe??Pe?H?D??D?R?D??H?X??H?D??D

?lb5?0.8?H?D??D?lb5?0.8?D?H?D?0?D?0.6R?D???

0D?0.6?4. 设有一连续信源，其均值为0，方差为?X，熵为H(X)，定义失真函数为―平方误差‖

失真，即d(x,y)?(x?y)。证明其率失真函数满足下列关系式：

211?XH(X)?log2πeD?R(D)?log

22D22当输入信源为高斯分布时等号成立。

证明：

（1） 证明上界：

1R(D)?H(X)?log2πeD

2连续信源R(D)函数是在

??p?x|y??0?? ????p?x|y?dx?1???D?????p?x?p?x|y?d?x,y?dxdy?D?约束条件下，求平均互信息：

I?X;Y??????????p?x?p?x|y?lbp?x|y?dxdy

p?x?引入参量S和待定函数??x?。在失真不超过D时，I?X;Y?为下确界的试验信道满足

??p0?x|y??p0?y???x?eSd?x,y??????Sd?x,y?????x?p?x?edx?1 ???1???x????p?y?eSd?x,y???????0dy???D?s??????????p?x?p0?y???x?eSd?x,y?d?x,y?dxdy

R?S??SD?S??????p?x?lb??x?dx

由泛函分析中的变分法求I?X;Y?的条件极值 令x?y??, d?x,y??d?????2 由于以上规定了下确界，则

??????x?p?x?eSd?x,y?dx?1

设集合

?s????x?: ????x?p?x?eSd?x,y???dx?1,任意y?

则有R?D??sup?SD?S??s?0,??x???s??????p?x?lb??x?dx???

令??x??K?S?p?x? ?1其中K?S?????????eSd???d????

由（1）得K?S????x,y???eSd?dx?1

即K?S??????eSd???d??1

当d?????2时，且S?0， 得

??S?2?2???ed??2???eS?d???S??

由（2）（3）两式，有

R?D??SD???p?x?lbK?S???p?x?dx?SD?????p?x?lb1p?x?dx?????p?x?lb1K?S?dx?SD?H?X????p?x??lb??eSd???????d??????dx?SD?H?X??lb??eSd?????d?由对数得换底公式，有

ln2?R?D??SD?H?X??ln??eSd?????d??R 若要（1）式等号成立，则等效于（5）式等号成立。

1）2）4）5） （

（

（

（

R??D??令gS?????eSd??????????Sd???eSd???d?

d???d?

e?ed?则R??D??g???d???d?

???Sd?????S然后再求二阶导数，得

?R?????gS???d???d????gS???d???d??????????

??Ed2????E2?d????由于gS???是d???得概率密度函数

2?2????且

????gS???d??????????eSd???d?eSd???d??1

所以R???0，即（5）式右边为上凸函数，在R??0的S上确极大值，有

代入d?????得

2D??gS???d???d?

???gS?????S?eS?2

?D??由式（5）得

?S????e?2S?2d???1 2S （6）

S???ln2?R?D???1d?2?HX?ln?e2???H?X??12lne?ln?H?X??12ln2?eD??S1?H?X??12lne?2ln2D?

即R?D???H?X??12ln2?eD

21?X（2） 证明上界R(D)?log

2D设信道的传递函数的概率为：

?1?y??x?2?exp??? 2?D2??D??它是已知X?x时y的概率分布，即均值为?x，方差为?D的高斯分布，其中??1??D2。 p??y|x??1D?????????p?x?p??y|x?d?x,y?dxdy???p?x?dx????????p?x?dx??2?y?x?p??y|x?dy???2?????y??x??2xy?1????x?1????p??y|x?dy?22??y??x?2?p??y|x?dy?2xy?1????p??y|x?dy????????????p?x?dx?????22??x1???p??y|x?dy?????????????????D?2x?1????x?x?1????p?x?dx22

????D??1???x?p?x?dx2222??D??1???????x2p?x?dx2??D??1????X?D设BD??p?y|x?:D?D?，p??y|x??BD 由于R?D??Inf?I?X;Y??

所以R?D??I??X;Y?

p?x|y??BDI?X;Y??H?Y??H?Y|X?输出信号Y???X?Z?，

?H?Y??12lb2?e?D

??????于是Y时均值为零，方差为??2H?Y??12lb2?e?X?D

E?Y????E?X??E?Z???0

22EY2??2EX2?EZ2??2?X??D??X?D

2X???D的随即变量。

?当方差受限时，高斯随即变量的差熵最大，有

?2I?X;Y??1lb2?e??D?1X22lb2?e?D221?X?D1?X?lb?lb2?D2D?????

21?XR?D??I??X;Y??lb

2D当且仅当p?x?是高斯分布时，上式等号成立。

211?X综上所述，H(X)?log2πeD?R(D)?log

22Da?a|x|5. 随机变量X服从对称指数分布p(x)?e，失真函数为d (x, y) = | x – y |，求信源的

2R(D)。

pX?x??a?axe，d?x,y??x?y 2

令??x?y，得d????? 且gS????eSd???????eSd???d??eS?S?????ed?

????eS?d??2?e0?S?d??2 S得gS???????S2eS?

D??gS???d???d????S2S2S2?????eS?d??S??2??e0d?1S

?2?1S2?对gS???进行傅立叶变换

GS?????gS???e?j??d????S2?2S??2S2??2Q????P???2S

2??P????2P???S1??j?y??pY?y??Q?ed? ???2??pY?y??pX?x?y??D2p?X?x?y?

a?aya32?ay?pY?y??e?De22 a?ay??1?a2D2?e21由pY?y??0，得D?

aDmax?Infy

??????pX?x?d?x,y?dxx?ya?axedx 2且

?Infy???1a当0?D?Dmax?1时 aR?D??RL?D??H?X??H?gS??lb2ae?lb2eD??lbaD, 0?D?1a?A,?0,|f|?F1|f|?F1，失真度量取

6. 设有平稳高斯信源X (t)，其功率谱为G(f)??d(x,y)?(x?y)2，容许的样值失真为D。试求：

（1） 信息率失真函数R(D)；

（2） 用一独立加性高斯信道（带宽为F2，限功率为P，噪声的双边功率谱密

度为

N0）来传送上述信源时，最小可能方差与F2的关系。 2（1）对于时间 连续的平稳高斯信源，当功率谱密度已知时，

R?D??14?1R?D??2?12??????max?0,lb??2SG?????d?

?1???min?,G???d? ????2S??在本题中

?1???min?,G???d?????2S???1???min??,G?f??df???2S? F11???df?F12SF1????1 ?设A?-?S2S??F即S??1

D1?R?D??max?0,lb??2SG?????d????4?1???max?0,lb??2SG?f???df2??1F1??lb??2SA?df 2?F1?F1lb??2SA?R?D??2AF1 bit/sD0?D?2AF1?F1lb（2）信道容量为C?F2lb??1???由定理可知，当C?R?D?时，可以采用最佳编码，其硬气的错误小于等于D。 取R?D??C,求得最小均方误差D。

P??bit/s F2N0??F1lb?2AF1P?? ?F2lb?1??? DFN20???F2?P?F1 ?D?2F1A??1?FN??20??D令??F2F1，??

F1N0???D??1??得? 2F1A????D?1 ??0时，

2F1AD?1??1??? ??1时，

2F1A???1?????时，由于lim?????????D?e??如下图： 所以

2F1AD2F1A1?????e??

?1????1e??0??1??

7. 某工厂的产品合格率为99%，废品率为1%。若将一个合格产品作为废品处理，将损失

1元；若将一个废品当作合格产品出厂，将损失100元；若将合格品出厂，废品报废，不造成损失。试分析质量管理中各种情况造成的损失及付出的代价。 解 根据题意有

信源空间： 好（合格） 废（废品） P(好)=0.99 P(废)=0.01 选择失真函数为

d(好，好)=0 d(废，废)=0

d(好，废)=10 d(废，好)=100 失真矩阵为

F2F1 好 废好?0?D???废?1001? 0??可将产品检验分成如下4种情况：全部产品都当合格品，全部产品都当废品，完美的检验和允许出错的检验。下面分别进行讨论。

情况1 全部产品不经检验而出厂——都当合格品。 把这一过程看作是一个―信道‖，其―传递概率‖为

P(好/好)=1 P(废/好)=0 P(好/废)=1 P(废/废)=0

信道矩阵为

好废??这种情况的平均损失，即平均失真度，为

好?10?废?10???

D???P(ai)P(bj/ai)d(ai,bj)

ij =P(好)?P(好/好) ?d(好,好)+ P(好)?P(废/好) ?d(好,废)

+P(废)?P(好/废话) ?d(废,好)+ P(废)?P(废/废) ?d(废, 废) =0.01?1?100=1元/个

情况2 全部产品不经检验全部报废——都当废品

这时的信道传输概率为

P(好/好)=0 P(废/好)=1 P (好/废)=0 P (废/废)=1

信道矩阵为

好废好?0??1? ??废?01?

平均失真度为

D???P(ai)P(bj/ai)d(ai,bj)ij

=P(好)?P(好/好) ?d(好,好)+ P(好)?P(废/好) ?d(好,废)

+P(废)?P(好/废) ?d(废,好)+ P(废)?P(废/废) ?d(废, 废)

=0.99?1?1=0.99元/个

Dmax?0.99

R(Dmax)?0

全部报废造成损失小于全部出厂造成的损失。

情况3 经过检验能正确无误地判断合格品和废品——完美的检验 这相当于无噪信道的情况，信道矩阵为

好废??平均失真度为

好?10??? 废?01?D?0

即这种情况不会另外造成损失。

情况4 检测时允许有一定的错误——非完美的检验 设检验的正确率为p，则信道的传输概率为

P(好/好)=p P(废/好)=1-p P(好/废)=1-p P(废/废)=p

信道矩阵为

好 废1-p? ???废?1-pp??好?p平均失真度为

D???P(ai)P(bj/ai)d(ai,bj)

ij =P(好)?P(废/好) ?d(好, 废)+P(废)?P(好/废) ?d(废,好)

=0.99?(1-p)?1+0.01?p?100 = 1.99(1-p)元/个

8. 设输入符号表为X= {0, 1 }，输出符号表为Y={0, 1}。定义失真函数为：

d (0, 0) = d (1,1) = 0 d (0, 1) = d (1,0) = 1

试求失真矩阵[D]。 d?0,0??d?1,1??0

d?0,1??d?1,0??1

?01??D????

?10?9. 某二元信源X的信源空间为

?X?P????其中w < 1/2，其失真矩阵为

X: a1, a2?P(X):w, 1?w

?0d?D? ?????d0?（1） 试求Dmax和R(Dmax)；

（2） 试求Dmin及R(Dmin)； （3） 试求R(D)；

（4） 写出取得R(D)的试验信道的各传递概率；

（5） 当d = 1时，写出与试验信道相对应的反向试验信道的信道矩阵。

解： ??X??a1a2??? ???P(X)???1????D????0d?? d0??（1）Dmax?min?d?,d?1?????d?（因为??1/2）

R?Dmax??0

（2）Dmin?0

R?Dmin??H?X????lb???1???lb?1????H???

（3） 由于

令eSd??iP?xi?eiSdij?1

??，则

1???1,?1????2?????????1,1? ?1??1????1??1???? ??得到????1????2??1??1?????1????1?1????? ?1???2??1????1????1???Pb??11??????1?????? ?1?P?b????1???????2?1???D?S????P?ai?P?bj?d?ai,bj?eijSdij?d???1????????1??????1?????????d?1???

?1?????1????1???1??d?deSd??1??1?eSdR?S??Sd??H????lb?1??? 1??Sd得到??e?D d?DS?1D lndd?DR?D??DDdln?H????lndd?Dd?DD?D??H?????lnD?lnd?D?lnd?ln?d?D??d?d??D??D?D???D??H?????lnD??1??ln?d?D?????1???lnd?

?d??d?d???d??DD?D??D???H?????ln??1??ln?1???d?d??d???d?D??H????H???d?D=0时，R?0??H??? D=d?时，R?d???0

??D??H????H?? 0?D?d? 所以R?D??? ?d??0 D?d??（4）p?bj|ai??p?bj??ieSdij

p?b1|a1??p?b1??1e0?p?b1??11????1??????1

?1????1??????1??????1??2????p?b1|a2??p?b1??2eSd?p?b1??2?11????1????????

?1????1???1??????1????????1??2?1??????p?b2|a1??p?b2??1eSd?p?b2??1?1??1????????1??

?1????1????1??????????1??2????p?b2|a2??p?b2??2e0?p?b2??211??1????????

?1????1???1????1????????1??2?1??????（5）d=1时，??D 1?D1??1?D，?D 1??1??p?a1|b1??p?a1??p?b1|a1???1p?a1?p?b1?11?????1?D?1?????1???

p?a1|b2???p?a2|b1???p?a2|b2???p?a1??p?b2|a1???1?p?a1?p?b2?1?1??????????

?1????Dp?a2??p?b1|a2???2?p?a2?p?b1?1?????1?????D?1????1????1???p?a2??p?b2|a2???2p?a2?p?b2?11??1?????1?D?1????1????1???

第9章 习题

1. 对(2, 1), (3, 1), (4, 1), (5, 1)，讨论其纠检错能力，对用完备译码、不完备译码以及不完备

译码＋ARQ等方法译码，求译码错误概率。 解：

对(2, 1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错

对(3, 1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错

对(4, 1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错，若d=4,能检3个错，纠1个错

对(5, 1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错；若d=4,能检3个错，纠1个错；若d=5,能检4个错，纠2个错

2. 为什么d =2的(n, n–1)码能检测奇数个错误？ 解:

d=2，能检1个错，又因为(n, n–1)码是奇偶校验码，即对于

奇校验码：Cn?1?Cn?2????C0?0 偶校验码：Cn?1?Cn?2????C0?1 当出现一个错或者奇数个错时，在接收端 奇校验码：Cn?1?Cn?2????C0?1 偶校验码：Cn?1?Cn?2????C0?0

都能检测到错误，故d =2的(n, n–1)码能检测奇数个错误。

3. 设C = {11100, 01001, 10010, 00111}是一个二元码，求码C的最小距离d。 解：

d(11100, 01001)=3 d(11100, 10010)=3 d(11100, 00111)=4 d(01001, 10010)=4 d(01001, 00111)=3 d(10010, 00111)=3 故码C的最小距离d=3

4．设C = {00000000, 00001111, 00110011, 00111100}是一个二元码。 （1） 计算码C中所有码字之间的距离及最小距离；

（2） 在一个二元码中，如果把某一个码字中的0和1互换，即0换为1，1换为0，所得的字称为此码字的补。所有码字的补构成的集合称为此码的补码。求码C的补码以及补码中所有码字之间的距离和最小距离，它们与（1）中的结果有什么关系？ （3） 把（2）中的结果推广到一般的二元码。

解：

（1） d(00000000, 00001111)=4 d(00000000, 00110011)=4

d(00000000, 00111100)=4 d(00001111, 00110011)=4 d(00001111, 00111100)=4 d(00110011,00111100)=4 故码C的最小距离d=4

（2） 码C的补码是 {11111111, 11110000, 11001100, 11000011}

d(11111111, 11110000)=4 d(11111111, 11001100)=4 d(11111111, 11000011)=4 d(11110000, 11001100)=4 d(11110000, 11000011)=4 d(11001100, 11000011)=4 故C补码的最小距离d=4

（3）推广到一般的二元码也有以上的结论

设码C中任意两码字的距离为d, 即两码字有d位不同，n-d位相同。变补后，仍有d位不同，n-d位相同，所以任意两码字的距离不变，最小距离当然不变。

习题（第10章）

1. 已知11次本原多项式p (x) = x11 + x2 + 1，试求GF(211)中元素? =? 89及? 2, ? 3, ? 4, ? 5的最小多项式。 解：

?11??2?1

84???89???11??????4?1??????16?1????8??6?? ?2??7??5??3??2?? ?3??10??7??3??2

?4??10??6??5??4??3??2 ?5??8??7??6??5?1 ???89的共轭元为：

?2??7??5??3??2??

?4??10??6??5??4??3??2 ?8??10??9??8??6??5??2?1 ?16??8??6??5??4??3??2??

?1?x???x???x??2x??4x??8x??16?x11?x10?x6?x5?x4?x2?1????????

?2?x???4?x??x?x?x?x?x?11110642

?3?x??x11?x10?x6?x5?x4?x2?1 ?5?x??x11?x9?x7?x6?x5?x?1

2. 求码长为n的q元重复码的生成矩阵。 若n=2,q=2，则有22＝4个码字 生成矩阵

?10?G???

01??对于码长为n的q元重复码，生成矩阵是q?q维单位矩阵。

nn??1????1n??? G?q ????????1???

3. 一个二元(11, 24, 5)码是线性码吗？为什么？ 是线性码。

n?k?13,

2t?1?11

13>11

4. 证明对于一个二元线性码L一定满足下列条件之一： （1） 码L中所有码字具有偶数重量；

本文来源：https://www.bwwdw.com/article/wq1.html