北邮信息论200806级期中考试试题及答案

北京邮电大学

06级《信息论》期中考试试题答案

（2008.11.15）

姓名 班级 学号 分数

注意：要求将试卷和答题纸一起上交

一、(25分)已知基于字符表{“blank”, B, I, M, O, P, S, T}的一段文本如下：

OTTOS MOPS TOBT MIT OTTOS MOP BIS OTTO MOPPOT （其中的blank表示空格）

(1) 统计文本中出现各字符的频度，并近似看作各字符的概率进行二元Huffman

编码，给出每个字符对应的码字（要求：码长方差最小）；(9分) (2) 求平均码长及码长方差；(4+4=8分) (3) 求编码速率和编码效率。(4+4=8分) 解：

（1）首先计算字母表中的字符在文本中出现的频度：（2分） I M O P S T 字符 “blank” B ? 2 2 4 11 4 4 10 45 频度 8 Huffman编码： 码字O11T10“blank”8M4PSBI44220101418181S0111B1110I1111

001160002745“blank”010118M110P0110O00T10（3+4=7分，每错一个码字扣0.5分）

(2) 平均码长及码长方差为：

l?2?(11?10)/45?3?(8?4)/45?4?(4?4?2?2)/45?2.8码元/信源符号(4分)

?2??pili2?l?11?22/45?10?22/45?8?32/45?4?32/45?2?4?42/45?2?2?42/45?2.82?0.693i2?（4分）

3）编码速率R'?llog2?2.8比特/信源符号（4分） 编码效率??

二、（25分）一马氏源具有状态集合?1,2,...,N?，状态转移图如下图所示

pq123… …H(X)??2.75322.8?98.32%（4分）

Llog2ppppNqqqq

其中p?0,q?0,p?q?1。

（1）当N=3时，写出状态转移概率矩阵，并求平稳分布。（3+6=9分） （2）对任意N值，写出状态转移概率矩阵，并求平稳分布。（3+6=9分） （3）对任意N值，求马氏源的符号熵。（7分） 答：

（1） N=3,状态转移概率矩阵为：

?q??q?0?p0q0??p? （3分） p???qq??1?2?3???由?0??1??2??3?1p0q0??p????1?2?3? （3分）

p??

q2(1?p)2?1?2?2p?pq?q1?p?p2pqp(1?p)?得平稳分布为：?2?2（各1分共3分） 22p?pq?q1?p?pp2p2?3?2?p?pq?q21?p?p2

（2） 对任意N，状态转移概率概率矩阵如下：

?q??q?0??0?.??0?0?p0q0.000p0q.000...00p0....0...0...0....0??0?0??0? （3分） .??p?p??p0q0.000p0q.000...00...0p...00...0.....0...00...q0??0?0?? 0????1?2?3...?N?1?N?.??p?p??0...00...q该马氏源处于平稳分布时，有：

?q??q?0??N??0?.??0?0???1?2?3...?N?1以及

??i?1Ni?1（2+1=3分）

得：

?ip??i-1q （i?2，N）， 从而有：N?p??i????1， ??i?1i?1?q?p1??令?=，得：?1?q1??N因此，平稳分布为：

i-1

?i?1(1??)（3分） ?i?，（i?1，N）1??N（3）由于马氏源状态转移概率矩阵的每行都相等，所以有：

（4分） h1?h2?...?hN?H(p)，

从而对任意N，有H??H(p)（3分）

三、（25分）x和z为独立同分布的连续随机变量，且都在区间[-1/2, 1/2]上服从

均匀分布，随机变量y=x+z。

（1） 求连续随机变量集合Z的差熵h(Z);（5分）

?x??10??x?（2） 证明：h(Y|X) = h(Z);（提示：????）（7分） ????y??11??z?（3） 求连续随机变量Y的概率密度函数；（提示：两个独立随机变量之和的概

率密度为这两个随机变量概率密度的卷积）（3分） （4） 求连续随机变量集合Y的差熵h(Y); （5分） （5） 求I(X;Y)。（5分） 解：

（1） h(Z) = 0bit; (5分) （2） 由提示：

?x??10??x??y???11??z? ??????有：

?10?h(XY)=h(XZ)+logdet???h(XZ)11??(3分)

又由Z与X独立，

从而：h(XY)=h(X)+h(Y|X)=h(XZ)= h(X)+h(Z|X)= h(X)+h(Z) (3分) 可得：h(Y|X)= h(Z) (1分)

?y?1?1?y?0f(y)????y?10?y?1(3分) （3）

(用图形卷积或分区域积分的方法均给分)

（4）

h(Y)=-?(y+1)ln(y+1)dy -?(-y+1)ln(-y+1)dy -101?12111???2?tlntdt ??2?tlnt??t2dt ?002t??0?2?1?nat2101(5分)

或1/2loge=0.722bit

（5） I(X;Y) = h(Y) - h(Y|X) = h(Y) - h(Z) = 1/2nat 或1/2loge=0.722bit(5分)

四、（25分）在某地区篮球联赛的每个赛季，最终只有A、B两球队进入决赛争夺冠军。决赛采用7场4胜制，首先赢得4场胜利的球队获得冠军，并结束比赛。把产生冠军的事件x用A、B两队各场次的比赛结果表示，作为信源X产生的随机事件，例如：AAAA表示事件“A队胜前4场获得冠军”；ABBAAA，表示事件“A队在第1、4、5、6场取胜获得冠军(而B队在第2、3场取胜)”，…。假设两球队在每场比赛中的取胜机会均等，每场比赛只有“A胜”或“B胜”两种结果，并且各场比赛的结果是彼此独立的。

（1）写出信源X的所有事件及其相应的概率；（5分） （2）求信源的熵H（X）；（5分）

（3）求事件“两队打满7场”所提供的信息量；（5分）

（4）列出A队前三场都失利的所有情况，求“A队前三场都失利”所提供的信

息量；（5分）

（5）求事件“A队在前三场都失利的条件下又取得冠军”所提供的信息量？

（5分）

解

（1）A队获冠军的事件数和相应的概率如下表：（4分）

事件 数目 单事件的概率 概率的和

赛4场获冠军 1 1/16 1/16 （AAAA）

赛5场获冠军（前4 4 1/32 1/8 场B胜1场）

赛6场获冠军（前5 10 1/64 5/32 场B胜2场）

赛7场获冠军（前6 20 1/128 5/32 场B胜3场）

总概率 1/2 同理得到相同的B队获冠军的事件数和相应的概率分布。（1分） （2）信源X的熵：

1111H(X)?2?[()log216?4?()log232?10?()log264?20?()log(128)]163264128（3分）

?186/32?5.8125比特（1+1=2分） （3） “两队打满7场”事件数为40，（1分）

所求概率为40?(1/128)?5/16，（1分） 事件“两队打满7场”所提供的信息量：

I1??log2(5/16)?1.6781比特（3分）

（4）A队在前三场都失利情况下的所有事件与概率：（每概率0.5分共2分）

事件 概率 结果 BBBB 1/16 B取得冠军 BBBAB 1/32 B取得冠军 1/64 B取得冠BBBAAB 军 1/128 B取得冠BBBAAAB 军 1/128 A取得冠BBBAAAA 军 I2?log28?3比特（3分）

（5）A队在前三场都失利的条件下又取得冠军的条件概率：

1/128?1/16（2分）

(1/16)?(1/32)?(1/64)?2?(1/128)“A队在前三场都失利的条件下又取得冠军的”的信息量：

I3?log216?4比特（3分）

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