信息论第二次作业

信息论作业答案第二章1 ■一阶齐次马尔柯夫信源消息集X ∈{321,,a a a }，状态集S ∈{321,,S S S }。

且令3,2,1,==i a S i i , 符号条件转移概率为[]=21414141214113131)/(i j S a P(1) 画出该信源的状态转移图；(2)解：（1）[]111333111424111442(|)jip SS =??（2）1111231344111123232411112333421231w w w w w w w w w w w w w w w ++=??++=??++=??++=?311142114311w w w =??=??=?H(X|S 1)=H (1/3,1/3,1/3)=1.58bit/符号H(X|S 2)=H (1/4,1/2,1/4)=1.5bit/符号= H(X|S 3)33411111()(|) 1.58 1.52 1.52i i i H X w H X S ∞===?+??=∑bit/符号2 如果你确定你的朋友是6月的生日，但是不知道具体是哪一天。

那么你问你的朋友“你的生日是6月哪一天?”，则答案中含有的信息量为4.91bit ；3p42 2-12 4 p42 2-13 5 p43 2-19 6 p44 2-29第三章1. ■设信道的转移概率矩阵为P ＝0.90.10.10.9??（1）若p(x 0)=0.4，p(x 1)=0.6，求H(X ），H(Y ），H(Y|X ）和I(X ；Y ）；（2）求该信道的信道容量及其达到信道容量时输入符号的概率分布。

（3）设该信道以1800个二元符号/秒的速度传输输入符号。

现有一消息序列共有10000个二元符号，在p(x 0)=1/2，p(x 1)=1/2情况下，从信息传输的角度来考虑，10秒内能否将这消息序列无失真地传送完？解：(1)[]0.360.04(,)0.060.54p x y ??=?, [p(y)]=[0.42 0.58] H(X)(0.4,0.6)0.97H ==bit/符号H(Y)(0.42,0.58)0.98H ==bit/符号 H(Y|X)(0.9,0.1)0.47H ==bit/符号I(X;Y)= H(Y)－H(Y|X)=0.51bit/符号(2)C=1－H(ε)=1－H(Y|X)=0.53bit/符号 p 0=p 1=0.5（3）H(X)×104＝104 bit1800×C ×10＝9540 bit < 104 所以不能无失真传送完。

第一次课后作业：老三论：控制论、信息论和系统论，新三论：突变理论、耗散结构理论和协同论美国数学家维纳的控制论”美国数学家申农的信息论”美籍奥地利理论生物学家和哲学家贝塔朗菲的系统论”比利时化学家普里高津的耗散结构理论”德国物理学家哈肯的协同论:法国数学家托姆的突变理论”第二次课后作业：3工1 + 2 j 2 + -£'1 —*0-Tt —+ 3工3 -- J 1 1 52-i'i + = Z：* 十 1 O首先标准化：Max z=--3x1-2x2-x3+x4s.t x1-2x2+3x3-x4 < 152x1+x2-x3+2x4 < 10X1 ,x 2 ,X2 ,x 3 ,x 4> 0添加2个松弛变量x5 x6x1-2x2+3x2-x4+x5=15 2x1+x2-x3+2x4+x6=10用对偶单纯形法：0 X5 20 2 -1.5 2.5 0 1 0.5 51 X4 5 1 0.5 -0.5 1 0 0.5 --z -5 -4 -2.5 -0.5 0 0 -0.5在最优单纯性表中, 最小值为：-5 x5,x6的检验数均为负数，于是得到最优解X*=(0,0,0,5,20) T，所以可以C 1 > minSf t -S- t ” L- -Ta-Tf + 2J ；4 一 3 J 1 + gHu + 2-a-』一 5.rO >= 1 -6此题和上题类似：变成标准化Max -x1-x2-x3s.t.X5于是得到最优解由此得出min X*=(0,0,0,5,3,3)的值为0,。

—1 O J "I — 5% — 2口 + 5工I + 3^2 +心9—吕4十6工卫+ 15帀总］52Hi + >rj + 才1 —工* = 13工1t 工*耳。

添加松弛变量x5, x6, x7s.t. 5x1+3x2+x3 <9-5x1+6x2+15x2=15X6-z-1 -1(1)-1*-5化为标准化为:max 10x1+5x2+2x3-6x4 -+x1 -x4 -2x6=5 x2+2x4-3x5+x6=3 x3+2x4-5x5+6x6=5Cb XbX4 X5 X6-zX4 xj X),j=1 ….6;-1 X1-1 X2-1 X3X4 -1 2-1 X5 0 -3 -5X6 -2 1-2-313> min2x1+x2+x3-x4=13X1 ... x4》0令 Z1=3x1+2x2+x3-x415x1+3x2+x1+x5=9 -5x1+6x2+15x3+x6=15 2x1+x2+x3-x4+x7=133+ 才J 一hl + —工冃十工*工3丢2于是变为标准形为： max -3x1-2x2-x2+x41X1-2x2+x3-x41+x5=17 2x1+x2-x3+2x41+x6+x7= 14 x41 二0 X1 …x3>0CbXbb 10 5 2 -6 0 0 0X1X2 X3 X4 X5 X6 X7 0 X5 9 5 3 1 0 1 0 0 0 X6 15 -5 6 15 0 0 1 0 0X713 2 1 1 -1 0 0 1 -z-10-5-260 X1 1.8 1 0.6 0.2 0 0.2 0 0 0 X6 24 0 9 16 0 1 1 0 0X79.4 0 -0.2 0.6 -1 -0.4 0 1 -z-18-1-6-2T于是得到最优解 X*=(1.8,0,0,0,0,24,9.4) 于是最小值为: -18<15对第二个约束条件左右同时乘上X1-2x2+x3-x41-2+x5=15 2x1+x2-x3+2(x41-2)+x6+x7= 10 -1 ,再添加松弛变量 即 X1-2x2+x3-x41+x5=17 即 2x1+x2-x3+2x41+x6+x7= 14x5，x6，x7。

2.4 设离散无记忆信源⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X ，其发出的信息为(202120130213001203210110321010021032011223210)，求 (1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？解：(1) 此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是：62514814183⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=p此消息的信息量是：bit p I811.87log =-=(2) 此消息中平均每符号携带的信息量是：bitn I 951.145/811.87/==41()()log () 2.010i i i H X p x p x ==-=∑2.6 设信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡17.016.017.018.019.02.0)(654321x x x x x x X P X ，求这个信源的熵，并解释为什么H(X) > log6不满足信源熵的极值性。

解：585.26log )(/ 657.2 )17.0log 17.016.0log 16.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0( )(log )()(26=>=+++++-=-=∑X H symbol bit x p x p X H ii i 不满足极值性的原因是107.1)(6>=∑iix p 。

2.7 同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求： (1) “3和5同时出现”这事件的自信息； (2) “两个1同时出现”这事件的自信息；(3) 两个点数的各种组合（无序）对的熵和平均信息量； (4) 两个点数之和（即2, 3, … , 12构成的子集）的熵； (5) 两个点数中至少有一个是1的自信息量。

解：(1)用随机事件i x 表示“3和5同时出现”，则bitx p x I x p i i i 170.4181log )(log )(18161616161)(=-=-==⨯+⨯=(2) 用随机事件i x 表示“两个1同时出现”，则bitx p x I x p i i i 170.5361log )(log )(3616161)(=-=-==⨯=(3)两个点数的排列如下： 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 61 6263646566共有21种组合：其中11，22，33，44，55，66的概率是3616161=⨯ 其他15个组合的概率是18161612=⨯⨯symbol bit x p x p X H ii i / 337.4181log 18115361log 3616)(log )()(=⎪⎭⎫ ⎝⎛⨯+⨯-=-=∑(4)参考上面的两个点数的排列，可以得出两个点数求和的概率分布如下：sym bolbit x p x p X H X P X ii i / 274.3 61log 61365log 365291log 912121log 1212181log 1812361log 3612 )(log )()(36112181111211091936586173656915121418133612)(=⎪⎭⎫ ⎝⎛+⨯+⨯+⨯+⨯+⨯-=-=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡∑(5)bitx p x I x p i i i 710.13611log )(log )(3611116161)(=-=-==⨯⨯=2.10 对某城市进行交通忙闲的调查，并把天气分成晴雨两种状态，气温分成冷暖两个状态，调查结果得联合出现的相对频度如下：忙晴雨冷 12暖 8暖 16冷 27闲晴雨冷 8暖 15暖 12冷 5若把这些频度看作概率测度，求： (1) 忙闲的无条件熵；(2) 天气状态和气温状态已知时忙闲的条件熵；(3) 从天气状态和气温状态获得的关于忙闲的信息。

第二、三章 习题4.1 同时掷两个正常的骰子，也就是各面呈现的概率是61，求：（1）“3和5同时出现”这一事件的自信息量。

（2）“两个1同时出现”这一事件的自信息量。

（3）两个点数的各种组合（无序对）的熵或平均信息量。

（4）两个点数之和（即2，3…12构成的子集）的熵。

（5）两个点数中至少有一个是1的自信息。

4.2 消息符号集的概率分布和二进制代码如下表（1）求消息的符号熵。

（2）每个消息符号所需要的平均二进制码的个数或平均代码长度。

进而用这个结果求码序列中的一个二进制码的熵。

（3）当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ，求相邻码间的条件概率10110100,,,P P P P 。

4.3 某一无记忆信源的符号集为{0，1}，已知0p =14，1p =34（1）求符号的平均信息熵。

（2）由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（m -100）个“1”）的自信息量的表达式。

（3）计算（2）中的序列的熵4.6 有两个离散随机变量X 和Y ，其和为Y X Z +=（一般加法），若X 和Y 相互独立， 求证：（1）)()(Z H X H ≤)()(Z H Y H ≤（2）)()(Z H XY H ≥4.7 对于任意的三个离散随机变量X ，Y ，Z ，求证：（1） (;)(;)(;)(;)(;)(;)I X Y Z I X Y I Y Z X I Y Z I Z X Y I Z X -=-=- （2） ()()()(;)I XYZ H XZ H Y X I Z Y X =+- （3） )()()()(X H ZX H XY H XYZ I -≤-4.9 一个等概率的信源符号有八种字母，分别是10000x =，20011x =，30101x =，40110x = ，51001x = ，61010x = ，71100x = ，81111x =，用实验测定上述码字中的每个二进制符号，可得二元输出y ，已知条件概率为00P =11P =1-ε10P =01P =ε。

2．居住在某地区的女孩中有25%是大学生,在大学生中有75%是身高1.6以上的，而女孩中身高1.6米以上的占总数一半.假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？
解：
信息量：比特
有一信源输出X∈{0,1,2}，其概率为p0=1/4，p1=1/4，p2=1/2。

设计两个独立实验去观察它，其结果为Y1∈{0,1}和Y2∈{0,1}。

已知条件概率为
P(Y1|X) 0 1 P(Y2|X) 0 1
0 1 0 0 1 0
1 0 1 1 1 0
2 1/2 1/2 2 0 1 求：
1)I(X;Y1)和I(X;Y2)，并判断哪一个实验好些。

2)I(X;Y1,Y2)，并计算做Y1和Y2两个实验比做Y1或Y2中的一个实验各可多得多少关
于X的信息。

3)I(X;Y1/Y2)和I(X;Y2/Y1)，并解释它们的含义。

H(X)=
．若有二个串接的离散信道，它们的信道矩阵都是
00
10001⎡⎤⎢⎥
11．有一个一阶平稳马尔可夫链X1，X2,……X r……，各X r取值于集合A={a1,a2,a3}。

已知起始概率p(X r)为p1=1/2，p2=p3=1/4，转移概率如下。

j
1 2 3
21.0585
.1251
.11100=-=-
=∞H H R。

第二章习题参考答案2-1解：同时掷两个正常的骰子，这两个事件是相互独立的，所以两骰子面朝上点数的状态共有6×6＝36种，其中任一状态的分布都是等概的，出现的概率为1/36。

(1)设“3和5同时出现”为事件A ，则A 的发生有两种情况：甲3乙5，甲5乙3。

因此事件A 发生的概率为p(A)=(1/36)*2=1/18 故事件A 的自信息量为I(A)=－log 2p(A)=log 218=4.17 bit(2)设“两个1同时出现”为事件B ，则B 的发生只有一种情况：甲1乙1。

因此事件B 发生的概率为p(B)=1/36 故事件B 的自信息量为I(B)=－log 2p(B)=log 236=5.17 bit (3) 两个点数的排列如下：因为各种组合无序，所以共有21种组合： 其中11，22，33，44，55，66的概率是3616161=⨯ 其他15个组合的概率是18161612=⨯⨯symbol bit x p x p X H ii i / 337.4181log 18115361log 3616)(log )()(=⎪⎭⎫ ⎝⎛⨯+⨯-=-=∑(4) 参考上面的两个点数的排列，可以得出两个点数求和的概率分布：sym bolbit x p x p X H X P X ii i / 274.3 61log 61365log 365291log 912121log 1212181log 1812361log 3612 )(log )()(36112181111211091936586173656915121418133612)(=⎪⎭⎫ ⎝⎛+⨯+⨯+⨯+⨯+⨯-=-=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡∑(5)“两个点数中至少有一个是1”的组合数共有11种。

bitx p x I x p i i i 710.13611log )(log )(3611116161)(=-=-==⨯⨯=2-2解：(1)红色球x 1和白色球x 2的概率分布为⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡2121)(21x x x p X i 比特 12log *21*2)(log )()(2212==-=∑=i i i x p x p X H(2)红色球x 1和白色球x 2的概率分布为⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡100110099)(21x x x p X i 比特 08.0100log *100199100log *10099)(log )()(22212=+=-=∑=i i i x p x p X H (3)四种球的概率分布为⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡41414141)(4321x x x x x p X i ，42211()()log ()4**log 4 2 4i i i H X p x p x ==-==∑比特2-5解：骰子一共有六面，某一骰子扔得某一点数面朝上的概率是相等的，均为1/6。

2.2 居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高160厘米以上的，而女孩子中身高160厘米以上的占总数的一半。

假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？ 解：设随机变量X 代表女孩子学历 X x 1（是大学生） x 2（不是大学）P(X) 0.250.75设随机变量Y 代表女孩子身高Y y 1（身高>160cm ） y 2（身高<160cm ） P(Y) 0.50.5已知：在女大学生中有75%是身高160厘米以上的 即：bit x y p 75.0)/(11=求：身高160厘米以上的某女孩是大学生的信息量即：b i ty p x y p x p y x p y x I 415.15.075.025.0log )()/()(log )/(log )/(11111111=⨯-=-=-= 2.4 设离散无记忆信源⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X ，其发出的信息为( 02120130213001203210110321010021032011223210)，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？ 解：(1) 此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是：62514814183⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=p 此消息的信息量是：bit p I 811.87log =-=(2) 此消息中平均每符号携带的信息量是：b i t n I 951.145/811.87/==2.9 设有一个信源，它产生0，1序列的信息。

它在任意时间而且不论以前发生过什么符号，均按P(0) = 0.4，P(1) = 0.6的概率发出符号。

(1) 试问这个信源是否是平稳的？ (2) 试计算H(X 2), H(X 3/X 1X 2)及H ∞；(3) 试计算H(X 4)并写出X 4信源中可能有的所有符号。

一、实验目的1、通过实验进一步理解霍夫曼编码、算术编码和LZ编码原理和方法2、熟悉matlab编程和GUI界面的设计二、实验原理1、赫夫曼（Huffman ）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman 算法而产生。

Huffman 编码是一种基于统计的无损编码。

设信源X 的信源空间为：⎩⎨⎧∙)()()()(:)(::][32121N N x P x P x P x P X P x x x X P X 其中，1)(1=∑=Ni i x P ，现用二进制对信源X 中的每一个符号i x (i=1,2,…N)进行编码。

根据变长最佳编码定理，Huffman 编码步骤如下：（1）将信源符号xi 按其出现的概率，由大到小顺序排列。

（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；（3）对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）；（4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0；（5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的Huffman 码。

Huffman 编码的特点是：（1）Huffman 编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“1”是任意选择的（大概率为“0”，小概率为“1”，或者反之）。

第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。

这样编出的码字就不是唯一的。

（2）Huffman 编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。

（3）Huffman 编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman 编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。

第1讲2、信息论创始人是谁？香农。

3、信息和消息、信号有什么联系与区别？从信息理论角度上看，信号是消息的载体，信息含藏在消息之中，有信号有消息不一定有信息。

4、通信系统的主要性能指标是什么？ 有效性、可靠性和安全性。

5、举例说明信息论有哪些应用？为信息传送和处理系统提供数学模型和评估方法，在通信和信息处理领域是一门基础理论，在其它领域如语言学、生物学、医学、神经网络、经济学方面的应用也很成功。

具体应用实例有：语音、图像和数据信息的压缩，通信信道有效性和可靠性的提高，或信道传输功率指标要求的降低，通信或计算机系统可靠性和安全性的提高，信息处理领域的信号重建和模式识别等。

2.4 （求车牌自信息量）某车牌号的概率是(1/26)3×(1/10)3，24bit/牌，后一种概率为(1/36)6，31bit/牌， 第2讲设二元对称信道的传递矩阵(条件概率矩阵)为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡32313132若P(0) = 3/4, P(1) = 1/4，求H(X), H(Y), H(X/Y), H(Y/X)和I(X;Y)；先求P(Y)=∑X P(XY)和P(XY)=P(X)P(Y|X)，再得各种熵和互信息。

H(X)=H(3/4,1/4), H(Y)=H(7/12,5/12);H(XY)=H(1/2,1/4,1/12,1/6); H(X/Y)=H(XY)-H(Y)H(Y/X)=H(XY)-H(X)；或H(Y/X)=∑P(X=a)H(Y/a)=H(3/4,1/4) I(X;Y)=H(X)-H(X/Y)=H(X)+H(Y)-H(XY)； 2.2（求条件信息量）1.6米以上女孩是条件，某个1.6米以上的女大学生是概率事件，得条件概率为：P=0.25×0.75/0.5=0.375=3/8，信息量为I= -log0.375=1.42比特。

2.52.10(1)(2)（由联合概率分布求熵、联合熵和条件熵）（1）思路：先求出X 、Y 、Z 、XZ 、YZ 、XYZ 的概率或联合分布，再求其熵。

信息论习题一二答案参考信息论习题一二答案参考信息论习题一、二答案参考1.一个随即变量x的概率密度函数P(x)= x /2，0≤x≤2V，则信源的相对熵为（）。

A. 1.44bit/符号B. 1bit/符号正确C. 0.5bit/符号D. 0.72bit/符号2.下列不属于消息的是（）A. 文字B. 图像C. 语言D. 信号3.下列哪一项不属于最简单的通信系统模型（）A. 信宿B. 加密C. 信道D. 信源4.下列离散信源，熵最大的是（）。

A. H（1/2,1/2）B. H（1/2,1/4,1/8,1/8)C. H（1/3,1/3,1/3）D. H（0.9,0.1）5.下面哪一项不属于熵的性质（）A. 对称性B. 确定性C. 完备性D. 非负性6.同时扔两个正常的骰子，即各面呈现的概率都是1/6，若点数之和为12，则得到的自信息为（）。

A. －log36bitB. log36bitC. －log (11/36)bitD. log (11/36)bit7.对连续信源的熵的描述不正确的是（）。

A. 连续信源的熵和离散集的熵形式一致，只是用概率密度代替概率，用积分代替求和B. 连续信源的熵由相对熵和无穷大项构成C. 连续信源的熵值无限大D. 连续信源的熵可以是任意整数9.相对熵（）。

A. 总非负B. 总为正C. 总为负D. 都不对9.英文字母有26个，加上空格共27个符号，由此H0（X）=4.76bit/符号，根据有关研究H∞（X）=1.4 bit/符号，则冗余度为（）。

A. 0.71B. 0.51C. 0.11D. 0.3110.设信源S，若P（s1）=1/2、P（s2）=1/4、P（s3）=1/4，则其信源剩余度为（）。

A. 3/4B. 0C. 1/4D. 1/211.设有一个无记忆信源发出符号A和B，已知p（A）＝1/4，p （B）=3/4，发出二重符号序列消息的信源，则二次扩展信源熵为（）。

A. 0.81bit/二重符号B. 1.86 bit/二重符号C. 0.93 bit/二重符号D. 1.62bit/二重符号12.H（X/X）=0。