信息论第二次作业
1. 一个不合格的骰子，6 个面的出现概率111111,,,,
,36661212?????? (1) 求此骰子的熵；
(2) 令()n A 是长度为n 的精确典型序列集合，也就是:
{}()()11(,,):(,,)2n nH X n n A x x p x x ?==""
求当n ＝6 时上述骰子对应的()n A
中元素的个数。
2. 一个离散无记忆稳恒信源产生0,1 序列消息， P (1) = 0.001 ， P (0) = 0.999 。对该信源进行定长分组编码，分组长度为N = 100 。为分组中每一个包含不超过3 个“1”的序列分配一个二进制码字。
（1） 为了能够对所有包含不超过3 个“1”的序列进行编码，需要的二进制码字个数至少 是多少？
（2） 计算没有码字与观察到源序列对应的概率。
（3） 试用切比雪夫不等式求源序列没有码字的概率。将该结果与（2）中结果对比。
3. 设12,,,n X X X "为取自分布为010.250.75??????
的独立同分布的离散随机序列，试求下列两种情况下序列取典型序列的概率：100N =
（1）0ε→
（2）0.05ε=
4. 令12,,,n X X X "为独立同分布的随机变量，其概率分布为()p x ，{1,2,,}x m ∈"。所以，121
(,,,)()n
n i i p x x x p x ==∏"，我们知道121log (,,,)()n p X X X H X n ?→"依概率收敛。令121(,,,)()n n i i q x x x q x ==∏"，()q x 为另外一个概率分布函数，其概率空间也是{1,2,,}x m ∈"。
（1） 计算121lim log (,,,)n n q X X X n
→∞?"，其中12,,X X "为i.i.d 且服从p(x)分布。 （2） 计算对数似然比：1212(,,,)1lim
log (,,,)n n n q X X X n p X X X →∞""，其中12,,X X "为i.i.d 且服从p(x)分布。
5. 一幅普通的牌友26张红牌26张黑牌，每次从中取出一张牌，取出的牌不放回，令i X 表示第i 次取出的牌的颜色
（1） 计算1()H X
（2） 计算2()H X
（3） 121(|,,,)k k H X X X X ?"递增还是递减？
（4） 计算1252(,,,)H X X X "
6. 令101,,,,X X X ?""为一个平稳过程（不一定是Markov 的），下面的陈述哪些是对的哪些是错的？如果是对的请给出证明，如果是错的请举出反例。
（1） 00(|)(|)n n H X X H X X ?=
（2） 010(|)(|)n n H X X H X X ?≥
7. 信源编码指出：一个随机变量X 的最优码子长度的期望小于()1H X +，给出一个随机变量的例子，使得最优编码的长度的期望值逼近()1H X +。即：任给0ε>，设计一个分布使得最优编码的长度()1L H X ε>+?。
8. 国际象棋中国王横、直、斜都可以走，但每着限走一步，现给定一个33×的棋盘，计算国王行走产生的Markov 过程的熵率。 1 2 3
4 5 6
7 8 9
9. 设随机变量X 的概率分布如下：
123456(
,,,,,212121212121
p = （1） 找出二进制Huffman 编码
（2） 找出三进制Huffman 编码 （3） 计算上述两个编码方案的平均长度i i L p l =
∑。
10. 已知二元信源{0，1}，其中01/8p =，17/8p =，试对下列序列编算术码，并计算此序列的平均码长和编码效率
11111110111110
11. 考虑一个随机变量X 具有如下概率分布：1111(,,,
)33412 （1） 设计一个Huffman 编码
（2） 证明存在两种不同的码长分布都能达到最优，即：码长分布(1,2,3,3)和(2,2,2,2)都是最优的。
（3） 证明在最优的编码方案中，存在某些特定的符号所对应的码长超过香农码码长log ()p x ?????。
12. 考虑如下对于一个随机变量X 的编码方案，设随机变量X 的概率空间为{1,2,3,…,m},对应的概率分布分别为12,,,m p p p "，对这一随机变量进行香农编码。
（1） 证明：()()1H X L H X ≤<+
（2） 构造如下概率分布的一个香农码，（0.5，0.25，0.125，0.125）。