信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子，试求： (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%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量平均每个回答中各含有多少信息量如果你问一位女士，则她的答案中含有多少平均信息量 解：
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.信息论研究内容：信源熵，信道容量，信息率失真函数，信源编码，信道编码，密码体制的安全性测度等等 第二章 １.自信息量：一个随机事件发生某一结果所带的信息量。 ２.平均互信息量：两个离散随机事件集合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
第一章信息论与基础 1.1信息与消息的概念有何区别？ 信息存在于任何事物之中,有物质的地方就有信息，信息本身是看不见、摸不着的，它必须依附于一定的物质形式。一切物质都有可能成为信息的载体，信息充满着整个物质世界。信息是物质和能量在空间和时间中分布的不均匀程度。信息是表征事物的状态和运动形式。 在通信系统中其传输的形式是消息。但消息传递过程的一个最基本、最普遍却又十分引人注意的特点是：收信者在收到消息以前是不知道具体内容的；在收到消息之前，收信者无法判断发送者将发来描述何种事物运动状态的具体消息；再者，即使收到消息，由于信道干扰的存在，也不能断定得到的消息是否正确和可靠。 在通信系统中形式上传输的是消息,但实质上传输的是信息。消息只是表达信息的工具，载荷信息的载体。显然在通信中被利用的（亦即携带信息的）实际客体是不重要的，而重要的是信息。 信息载荷在消息之中，同一信息可以由不同形式的消息来载荷；同一个消息可能包含非常丰富的信息，也可能只包含很少的信息。可见，信息与消息既有区别又有联系的。 1.2 简述信息传输系统五个组成部分的作用。 信源：产生消息和消息序列的源。消息是随机发生的，也就是说在未收到这些消息之前不可能确切地知道它们的内容。信源研究主要内容是消息的统计特性和信源产生信息的速率。 信宿：信息传送过程中的接受者，亦即接受消息的人和物。 编码器：将信源发出的消息变换成适于信道传送的信号的设备。它包含下述三个部分：(1)信源编码器：在一定的准则下，信源编码器对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。(2)纠错编码器：纠错编码器是对信源编码器的输出进行变换，用以提高对于信道干扰的抗击能力，也就是说提高信息传输的可靠性。(3)调制器：调制器是将纠错编码器的输出变换适合于信道传输要求的信号形式。纠错编码器和调制器的组合又称为信道编码器。 信道：把载荷消息的信号从发射端传到接受端的媒质或通道，包括收发设备在内的物理设施。信道除了传送信号外，还存储信号的作用。 译码器：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。 1.3 同时掷一对骰子，要得知面朝上点数之和，描述这一信源的数学 模型。 解：设该信源符号集合为X
设信源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
一填空题（本题20分，每小题2分） 1、平均自信息为 表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。 3、最大熵值为。 4、通信系统模型如下： 5、香农公式为为保证足够大的信道容量，可采用（1）用频带换信噪比；（2）用信噪比换频带。
6、只要，当N足够长时，一定存在一种无失真编码。 7、当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8、在认识论层次上研究信息的时候，必须同时考虑到形式、含义和效用三个方面的因素。 9、1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。 按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。 按照信息的地位，可以把信息分成客观信息和主观信息。 人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。 信息的可度量性是建立信息论的基础。 统计度量是信息度量最常用的方法。 熵是香农信息论最基本最重要的概念。 事物的不确定度是用时间统计发生概率的对数来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对
数的负值 。 12、自信息量的单位一般有 比特、奈特和哈特 。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ∞ 。 15、两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 。 16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量 趋于变小 。 17、离散平稳无记忆信源X 的N 次扩展信源的熵等于离散信源X 的熵的 N 倍 。 18、离散平稳有记忆信源的极限熵，=∞H )/(lim 121-∞→N N N X X X X H 。 19、对于n 元m 阶马尔可夫信源，其状态空间共有 nm 个不同的状态。 20、一维连续随即变量X 在[a ，b]区间内均匀分布时，其信源熵为 log2（b-a ） 。 21、平均功率为P 的高斯分布的连续信源，其信源熵，Hc （X ）=eP π2log 21 2。 22、对于限峰值功率的N 维连续信源，当概率密度 均匀分布 时连续信源熵具有最大值。 23、对于限平均功率的一维连续信源，当概率密度 高斯分布 时，信源熵有最大值。 24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P 和信源的熵功率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 )(361 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： (3)信源空间：
bit x H 32.436log 36 16236log 36215)(=??+?? =∴ (4)信源空间： 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 ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知Θ
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 -+--=-?? ????--+??????-+
信息论与编码 第四章 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 解:
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
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 平均码长为
第五章 --习题答案 (2) 哪些码是非延长码？ (3) 对所有唯一可译码求出其平均码长和编译效率。 解：首先，根据克劳夫特不等式，找出非唯一可译码 31123456231244135236:621 63:222222164 63: 164 :22421:2521:2521 C C C C C C --------------?<+++++=<<++?=+?>+?< 5C ∴不是唯一可译码，而4C ： 又根据码树构造码字的方法 1C ，3C ，6C 的码字均处于终端节点 ∴他们是即时码
(1) 因为A,B,C,D四个字母,每个字母用两个码,每个码为0.5ms, 所以每个字母用10ms 当信源等概率分布时,信源熵为H(X)=log(4)=2 平均信息传递速率为bit/ms=200bit/s (2) 信源熵为 H(X)= =0.198bit/ms=198bit/s 5-5 (1) 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1 128 H(U)= 1 2Log2() 1 4 Log4() + 1 8 Log8() + 1 16 Log16 () + 1 32 Log32 () + 1 64 Log64 () + 1 128 Log128 () + 1 128 Log128 () + 1.984 = (2) 每个信源使用3个二进制符号,出现0的次数为 出现1的次数为 P(0)= P(1)= (3) 相应的费诺码
（5）香农码和费诺码相同平均码长为 编码效率为： 5-11 （1）信源熵 （2）香农编码： 平均码长： 编码效率为 （3）
第5章有噪信道编码 5.1 基本要求 通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。 5.2 学习要点 5.2.1 信道译码函数与平均差错率 5.2.1.1 信道译码模型 从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F 。信道译码模型如图5.1所示。 5.2.1.2 信道译码函数 信道译码函数F 是从输出符号集合B 到输入符号集合A 的映射： *()j j F b a A =∈，1,2,...j s = 其含义是：将接收符号j b B ∈译为某个输入符号* j a A ∈。译码函数又称译码规则。 5.2.1.3 平均差错率 在信道输出端接收到符号j b 时，按译码规则* ()j j F b a A =∈将j b 译为*j a ，若此时信道输入刚好是 *j a ，则称为译码正确，否则称为译码错误。 j b 的译码正确概率是后验概率： *(|)()|j j j j P X a Y b P F b b ??===?? （5.1） j b 的译码错误概率： (|)()|1()|j j j j j P e b P X F b Y b P F b b ????=≠==-???? （5.2） 平均差错率是译码错误概率的统计平均，记为e P ： {} 1 1 1 1 ()(|)()1()|1(),1()|()s s e j j j j j j j s s j j j j j j j P P b P e b P b P F b b P F b b P F b P b F b ====??==-?? ??????=-=-?????? ∑∑∑∑ （5.3） 5.2.2 两种典型的译码规则 两种典型的译码规则是最佳译码规则和极大似然译码规则。 图5.1 信道译码模型 }r a
第五章课后习题 【5.1】某信源按43)0(= P ，4 1 )1(=P 的概率产生统计独立的二元序列。 （1）试求0N ，使当0N N >时有 01.005.0)()(≤ ≥?S H N I P i α 式中，)(S H 是信源的熵。 （2）试求当0N N =时典型序列集N G ε中含有的信源序列个数。 解： （1）该信源的信源熵为 811.0)(log )()(=?=∑i i s p s p S H 比特/符号 自信息的方差为 4715 .0811.04log 41 34log 43) ()]([)]([22222=?+=?=S H s I E s I D i i 根据等长码编码定理，我们知道 δεα?≤ ≥?1)()(S H N I P i 根据给定条件可知，05.0=ε，99.0=δ。而 []2 )(εδN s I D i = 因此 []5.19099 .0*05.04715 .0)(2 20==≥ δεi s I D N 取1910=N 。
（2）ε典型序列中信源序列个数取值范围为： ])([])([22)1(εεεδ+?<
《信息论与编码》-曹雪虹-课后习题答案 第二章 错误！未定义书签。2.1一个马尔可夫信源有3个符号{}1, 23,u u u ，转 移概率为：()1 1 |1/2p u u =，()2 1|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 =，画出状态图并求出 各符号稳态概率。 W 2、W 3 12310259 25625W W W ?=???=? ? ?=?? 2.2(0|p (0|01)p =0.5，(0|10)p 解：(0|00)(00|00)0.8p p ==(0|01)(10|01)0.5p p == 于是可以列出转移概率矩阵：0.80.20 0000.50.50.50.5000 00.20.8p ?? ? ?= ? ? ?? 状态图为：
设各状态00，01，10，11的稳态分布概率为W1,W2,W3,W4有 4 1 1 i i WP W W = = ? ? ? = ? ? ∑ 得 131 132 243 244 1234 0.80.5 0.20.5 0.50.2 0.50.8 1 W W W W W W W W W W W W W W W W += ? ?+= ?? += ? ?+= ? +++= ?? 计算得到 1 2 3 4 5 14 1 7 1 7 5 14 W W W W ? = ? ? ?= ? ? ?= ? ? ?= ? 2.31/6， 求： (1)“3和5 (2)“两个1 (3) 1的自信息量。 11 12 13 14 15 16 21 22 23 24 25 26 31 32 33 34 35 36 41 42 43 44 45 46 51 52 53 54 55 56
5.1某离散无记忆信源的概率空间为 采用香农码和费诺码对该信源进行二进制变长编码，写出编码输出码字，并且求出平均码长和编码效率。 解：计算相应的自信息量 1)()(11=-=a lbp a I 比特 2)()(22=-=a lbp a I 比特 3)()(313=-=a lbp a I 比特 4)()(44=-=a lbp a I 比特 5)()(55=-=a lbp a I 比特 6)()(66=-=a lbp a I 比特 7)()(77=-= a lbp a I 比特 7)()(77=-=a lbp a I 比特 根据香农码编码方法确定码长 1)()(+<≤i i i a I l a I 平均码长 984375 .164/6317128/17128/1664/1532/1416/138/124/112/1L 1=+=?+?+?+?+?+?+?+?=由于每个符号的码长等于自信息量，所以编码效率为1。 费罗马编码过程
5.2某离散无记忆信源的概率空间为 使用费罗码对该信源的扩展信源进行二进制变长编码， (1) 扩展信源长度，写出编码码字，计算平均码长和编码效率。 (2) 扩展信源长度，写出编码码字，计算平均码长和编码效率。 (3) 扩展信源长度，写出编码码字，计算平均码长和编码效率，并且与(1)的结果 进行比较。 解：信息熵811.025.025.075.075.0)(=--=lb lb X H 比特/符号 （1） 平均码长11=L 比特/符号 编码效率为 %1.81X) （H 1 1== L η （2） 平均码长为 84375.0）316 1316321631169（ 212=?+?+?+?=L 比特/符号 编码效率% 9684375 .0811 .0X) （H 2 2== = L η
第4章无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l。 4-2 设信源 6 126 1 126 ()1 ()()() ()i i s s s X p s p s p s p s P X = ?? ?? == ?? ?? ???? ∑。对此次能源进行m元唯一 可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）
4-3设信源为1 234567 811111111()2 4 8 16 3264128128s s s s s s s s X p X ?? ????=???? ??? ??? ，编成这样的码：（000，001，010，011，100，101，110，111）。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4求概率分布为11122 (,,, ,)3551515 信源的二元霍夫曼编码。讨论此码对于概率分布为 11111 (,,,,)55555 的信源也是最佳二元码。 4-5有两个信源X 和Y 如下： 1 234567()0.200.190.180.170.150.100.01X s s s s s s s p X ????=???????? 1 23456789()0.490.140.140.070.070.040.020.020.01Y s s s s s s s s s p Y ????=???????? （1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X 和Y 进行编码，并计算其平均码长和编码效率； （2）从X ，Y 两种不同信源来比较三种编码方法的优缺点。 4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码的信源的所有概率分布。 4-7设信源为1234 5678()0.40.20.10.10.050.050.050.05X s s s s s s s s p X ????=???????? ，求其三元霍夫曼编 码。 4-8若某一信源有N 个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当 N =2i 和N =2i +1（i 是正整数）时，每个码值的长度是多少？平均码长是多少？ 4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像
|= r = 2fc/X^) = 2x0_2 + 3x0_19+3x0_lg+2x0_17+3x0_15+ 4x01+4x001 = 274 R X 2_74 019 01g 017 015 01编二进制和三进制哈夫 曼码，计算各自的平均码长和编码效率. 解： X6 0110 4 X ： 1 0111 4 r = 2fc /X^) = 2xO_2 + 2xO_19+3xO_18+3xOJ7+3xO_15+ 4x01+4x001 = 2_72 就 K 2_72 Xi p(xj 编码 码字 ki S3 1 St S1 1 Xi 2 2 1 -Yr ( 00 2 Xs 1 01 2 Xi 2 02 2 i Xs ■ 10 2 X6 1 11 2 X ： 2 12 2 - 1_8- - 7 ;_128 21m ; 一 64 132 耳 116 A-1 - 8 比 1-4 - 源 言 信息论与编码复习题目公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08] 信息论复习提纲 第一章绪论 1．通信系统模型； 2．香浓信息的概念； 3．信源、信道、信源编码和信道编码研究的核心问题。 第二章离散信源及信源熵 1．离散信息量、联合信息量、条件信息量、互信息量定义； 2．信源熵、条件熵、联合熵定义； 3．平均互信息量定义、性质、三种表达式及物理意义，与其它熵的关系（不证明）； 4．最大信源熵定理及证明； 5．本章所有讲过的例题； 第三章离散信源的信源编码 1．信息传输速率、编码效率定义； 2．最佳编码定理（即节定理：概率越大，码长越小；概率越小，码长越大）及证明； 3．码组为即时码的充要条件； 4．单义可译定理（Kraft不等式）及应用； 5．费诺编码方法、霍夫曼编码方法应用（二进制，三进制，四进制）；6．本章所有讲过的例题； 第四章离散信道容量 1．利用信道矩阵计算信道容量（离散无噪信道、强对称离散信道、对称离散信道、准对称离散信道）； 2．本章讲过的例题； 第五章连续消息和连续信道 1．相对熵的定义； 2．均匀分布、高斯分布、指数分布的相对熵及证明； 3．峰值功率受限条件下的最大熵定理及证明，平均功率受限条件下的最大熵定理及证明，均值受限条件下的最大熵定理及证明； 4．香农公式及意义； 5．本章所有讲过的例题； 第六章差错控制 1．重量、最小重量、汉明距离、最小汉明距离、编码效率的定义；2．最小距离与检错、纠错的关系（即节定理）； 3．本章所有讲过的例题； 第七章线性分组码 1．线性分组码定义； 2．线性分组码的最小距离与最小重量的关系及证明； 3．生成矩阵、一致校验矩阵定义，给出线性方程组求出生成矩阵和一致校验矩阵的标准形式，生成矩阵与一致校验矩阵的关系； 4．制作标准阵列并利用标准阵列译码； 5．本章所有讲过的例题； 第八章循环码 《信息论与编码》 第四章 信息率失真函数 习题答案 4.1 解： 依题意可知：失真矩阵：??????=0110d ，转移概率??????--=εε εε11)|(i j a b p 平均失真： ε εεεε=?-?+??+??+?-?==∑∑==0)1(2/112/112/10)1(2/1) ,()|()(2121j i i j i j i b a d a b p a p D 4.2 解： 依题意可知：失真矩阵：?? ????=0210d ， 002/102/1),(min )(min =?+?==∑j i i j i y x d x p D ∑=?+?=?+?===i j i i j j y x d x p D D )102/122/1(2/112/102/1),()(min min max 舍去当0min =D ，bit X H R D R 12log )()0()(min ==== 因为没有失真，此时的转移概率为?? ????=1001P 当2/1max =D ，0)(max =D R 因为取的是第二列的max D 值，所以输出符号概率:,1)(,0)(21==b p b p ,,2221b a b a →→因此编码器的转移概率为?? ????=1010P 4.3 解： 0041041041041),(min )(43041141141141),()(min min min max =?+?+?+?===?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 当0min =D ，bit X H R D R 24log )()0()(min ==== 因为没有失真，此时的转移概率为????? ???????=1000010000100001P 当4/3max =D ，0 )(max =D R信息论与编码复习题目
《信息论与编码》答案-第四章
相关主题
文本预览