信息论习题

[例2.1.4条件熵]已知X，Y}1,0{,XY构成的联合概率为：p(00)=p(11)=1/8,p(01)=p(10)=3/8,计算条件熵H(X/Y)。解：根据条件熵公式：mjnijijiyxpyxpYXH112)/(log)()/()()()/(jjijiypyxpyxp首先求21)()(ijijyxpyp，有)/(406.0243log8341log81)1/1(log)11()0/1(log)10()1/0(log)01()0/0(log)00()/(,43)1/0()0/1()1/1(412/18/1)0()00()0()00()0/0()0/0(21)1()1(8183)10()00()0()0(22222211111212111symbolbitppppppppYXHpppypyxpppyxppyppcyxpyxpypp从而有：同理可求得[例2.1.5]将已知信源5.05.0)(21xxXPX接到下图所示的信道上，求在该信道上传输的平均互信息量I(X;Y)、疑义度H(X/Y)、噪声熵H(Y/X)和联合熵H(XY)。1x0.981y0.020.22x0.82y解：（1）由),/()()(ijijixypxpyxP求出各联合概率：49.098.05.0)/()()(11111xypxpyxp01.002.05.0)/()()(12121xypxpyxp10.020.05.0)/()()(21212xypxpyxp40.080.05.0)/()()(22222xypxpyxp（2）由,)()(1nijijyxPyP得到Y集各消息概率：)(1yp59.010.049.0)()()(1211211yxpyxpyxPii41.059.01)(1)(12ypyp（3）由)()()/(jjijiypyxpyxp，得到X的各后验概率：831.059.049.0)()()/(11111ypyxpyxp169.0)/(1)/(1112yxpyxp同样可推出976.0)/(,024.0)/(2221yxpyxp（4）)/(1}5.0log5.05.0log5.0{)(log)()(22212符号比特iiixpxpXH}41.0log41.059.0log59.0{)(log)()(22212iiiypypYH=0.98(比特/符号))(log)()(211jinimjjiyxpyxpXYH}40.0log40.010.0log10.001.0log01.049.0log49.0{2222=1.43（比特/符号）（5）平均互信息符号）比特/(55.043.198.01)()()();(XYHYHXHYXI（6）疑义度21212)/(log)(/ijjijiyxpyxpYXH）（}976.0log40.0169.0log10.0024.0log01.0831.0log49.0{2222符号）比特/(45.0（7）噪声熵21212)/(log)(/ijijjixypyxpXYH）（}80.0log40.020.0log10.002.0log01.098.0log49.0{2222符号）比特/(43.0[例2.2.1]有一离散平稳无记忆信源313211)(41,41,21,,)(iixpxxxXPX，求此信源的二次扩展信源的熵。先求出此离散平稳无记忆信源的二次扩展信源。扩展信源的每个元素是信源X的输出长度为2的消息序列。由于扩展信源是无记忆的，故)9,,2,1;3,2,1,()()()(2121iiixpxpapiii2X信源的元素1a2a4a5a6a7a8a9a对应的消息序列11xx21xx31xx12xx22xx32xx13xx23xx33xx概率)(iap4181818116116181161161根据熵的定义，二次扩展信源的熵为)(2)/(3)(XHXHN符号比特结论：计算扩展信源的熵时，不必构造新的信源，可直接从原信源X的熵导出。即离散平稳无记忆信源X的N次扩展信源的熵为离散信源X的熵的N倍。3a[例2.2.2]设某二维离散信源X=21XX的原始信源X的信源模型为36119441)(321xxxXPX，X=21XX中前后两个符号的条件概率为2X)/(12XXP1X1x2x3x1x7/92/902x1/83/41/83x02/119/11原始信源的熵为：)/(542.1)(log)()(231symbolbitxpxpXHiii由条件概率确定的条件熵为：)/(870.0)/(log)/()()/(12121212313112symbolbitxxpxxpxpXXHiiiiiii条件熵比信源熵（无条件熵）减少了0.672bit/symbol,正是由于符号之间的依赖性所造成的。信源X=21XX平均每发一个消息所能提供的信息量，即联合熵)/(412.2)/()()(12121symbolbitXXHXHXXH则每一个信源符号所提供的平均信息量)/(206.1)(21)(21)(212symbolbitXXHXHXH小于信源X所提供的平均信息量H(X)，这同样是由于符号之间的统计相关性所引起的。[例2.2.3]设信源符号},,{321xxxX，信源所处的状态},,,,{54321eeeeeS。各状态之间的转移情况由下图给出。e1e5e4e3e2211x412x413x412x11x213x213x432x413x411x212x将图中信源在ie状态下发符号kx的条件概率)/(ikexp用矩阵表示为321xxx2141410014143021210414121由矩阵可明显看出，315,4,3,2,1,1)/(kikiexp。另从图中还可得0),/(1),/(1),/(0),/(1121112211111112eSxXeSPeSxXeSPeSxXeSPeSxXeSPllllllllllll所以信源满足式(4)由图还可得状态的进一步转移概率54321eeeee4143000000000041430002121004104121该信源满足式(2)-(4)，所以是马尔可夫信源，并且是时齐的马尔可夫信源。[例2.2.4]某二元2阶马尔可夫信源，原始信源X的符号集为1,021XX，其状态空间共有422mn个不同的状态4321,,,eeee，即，其状态转移概率图如下，000111100.80.80.20.20.50.50.50.5由上图可知，当信源处于状态100e时,其后发生符号0的概率是0.8,即8.0)|()00|0(11expp,状态仍停留在1e,即8.0)|()|(1111expeep。当信源仍处于状态1e，而发出的符号为1时，状态转移至201e，故一步转移概率2.0)|()|()00|1(1212eepexpp。当信源处于状态012e时，其一步转移概率为5.0)|()|()01|0(2321eepexpp，}11,10,01,00{:4321eeeeE5.0)|()|()01|1(2422eepexpp。同理，当信源处于状态103e时，5.0)|()|()10|0(3131eepexpp5.0)|()|()10|1(3232eepexpp当信源处于状态114e2.0)|()|()11|0(4341eepexpp8.0)|()|()11|1(4442eepexpp这样，由二元信源X}1,0{得到的状态空间4,321,,eeee和相应的一步转移概率构成的2阶马尔可夫信源模型为4,3,2,1,)/(4321jieepeeeeij且0)(,1)/(41ijijepeep由414,3,2,1)/()()(iijijjeepepep可求出稳定状态下的)(jep，称为状态极限概率。将一步转移概率代入上式得：)(8.0)(5.0)()(2.0)(5.0)()(5.0)(2.0)()(5.0)(8.0)(424423312311epepepepepepepepepepepep解此方程组得142)()(145)()(3241epepepep计算极限熵)/(8.0)/(log)/()(414112symbolbiteepeepepHHijijiji需要注意的是H并非在任何情况下都存在。首先应记住的是：我们讨论的是平稳信源。其次，对n元m阶马尔可夫信源来说，只有极限概率mjnjep,,2,1),(都存在时，方能计算出H。从理论上可以证明，如果m阶马尔可夫信源稳定后具有各态历经性，则状态极限概率)(jep可根据式（10）求出。必须强调的是，m阶马尔可夫信源和消息长度为m的有记忆信源，其所含符号的依赖关系不同，对相应关系的数学描述不同，平均信息量的计算公式也不同。m阶马尔可夫信源的记忆长度虽为有限值m，但符号之间的依赖关系延伸到无穷，通常用状态转移概率（条件概率）来描述这种依赖关系。可理解为马尔可夫信源以转移概率发出每个信源符号，所以平均每发一个符号提供的信息量应是极限熵1mH。而对于长度为m的有记忆信息源X，发出的则是一组组符号序列，每m个符号构成一个符号序列组，代表一个消息。组与组之间是相互统计独立的，因此符号之间的相互依赖关系仅限于符号之间的m个符号，一般用这m个符号的联合概率来描述符号间的依赖关系。对于这种有记忆信源，平均每发一个符号，（不是一个消息）提供的信息量，是m个符号的联合熵的m分之一，即平均符号熵)(1)(21mmXXXHmXH[例2.4.1]设某单符号信源模型为04.005.006.007.010.010.018.04.0)(87654321xxxxxxxxxpX计算得)/(55.2)(符号比特XH323.1)]([2ixI若要求编码效率为90%,即90.0)()(XHXH则=0.28设译码差错率为610，由式（3）可得7106875.1L由此可见，在差错率和效率的要求都不苛刻的情况下，就必须有1600多万个信源符号一起编码，技术实现非常困难。不仅如此，它的编码效率也不高。对8种可能的取值编定长码，要无差错地译码，每种取值需用3个比特，其编码效率%85355.2为了解决这一问题，就出现了不等长编码，也称变长编码。不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。另外，接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。这就是所谓的译码同步和译码延时问题。[思考题]已知12个球中有一个球的重量与其它球不同，其它球均等重。问用无砝码的天平至少须几次才能找出此球？解：天平有3种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12个球中的不等重球（可较轻，也可较重）的不确定性为：24log21121log因为3log3＞log24∴3次测量可以找出该球具体称法略。[例一]一副充分洗乱了的牌（含52张牌），试问：(1)任