信息论与编码理论1(A卷答案)

第1页共5页2011-2012信息论与编码理论1A卷答案一、单项选择题（每题3分，总计15分）1．当底为10时，熵的单位为（D）。A比特B哈特C比特/符号D哈特/符号2．下列哪些量当YX,交换位置时（C）没有对称性。A);(YXIB),(YXHC)|(YXHD)|,(ZYXI3．下列（B）陈述是正确的。A算术编码不需要知道信源的分布BLZ编码不需要知道信源的分布C典型序列出现的概率比非典型的大D典型序列的数目比非典型的多4．下列数组中（C）不满足二个字母上的Kraft不等式。A(2，2，1)B(2,2)C(1,2,3)D（3，3，3）5．下列（D）是准对称信道的状态转移概率矩阵。A613121216131B5.05.05.05.05.05.05.05.05.0C323132313231D2.02.08.02.08.02.0二、填空题（每空2分，总计20分）1．若二元离散无记忆中25.0)0(p，75.0)1(p，则当给出100比特的信源序列，其中有10个1，其自信息为3log102002比特，整个序列的熵为)3log432(1002比特/符号。2．若某离散信道信道转移概率矩阵为125.0125.05.025.0125.0125.025.05.0，则其信道容量为43log352比特/符号；转移概率矩阵为5.05.04.06.06.04.0，则其信道容量为1比特/符号。3.两个相同的BSC做级联信道，其信道转移矩阵分别为pppp11，则级联信道的信道转移矩阵为22222212222221pppppppp，无穷多个级联后的矩阵为5.05.05.05.0。4．若一个信道的输入熵为6.1)(XH，输出熵为3.2)(YH，7.0);(YXI，则),(YXH__3.2比特/符号__，疑义度为0.9比特/符号_。第2页共5页5．在二元LZ编码中，若信源有K个，某段信源序列共有M个字典，则码长为KM22loglog。6．任一个唯一可译码的平均码长必大于等于DUHlog)(。三、判断题（每题2分，总计10分）1.概率大的事件自信息大（）2.若一个码字集合中的码字长度满足Kraft不等式，则其必为异字头码。（）3.若码字都被配置在树的叶子节点处，则这种码一定是唯一可译码。（√）4.平均互信息是上凸函数。（）5.对于离散无记忆信道，达到信道容量时的输入概率分布是唯一的（）四、计算题（55分）1）（15分）设随机变量YX,的联合概率分布如下：YXZ，为模2加。分别求);(),|(),(),(ZXIYXHYHXH。解:X的分布率为X01p2121则1)(XH比特/符号.Y的分布率为Y01p4143则3log432)(2YH比特/符号.YX01041411021ZX01041411210第3页共5页)0()0,0()0|0(YPYXpYXp=1,)1()1,0()1|0(YPYXpYXp=31)0()0,1()0|1(YPYXpYXp=0,)1()1,1()1|1(YPYXpYXp=32)1|0(log)1,0()0|0(log)0,0()|(22ppppYXH)1|1(log)1,1()0|1(log)0,1(22pppp=32log210log031log411log412222=213log432比特/符号.Z01p4341)0()0,0()0|0(ZPZXpZXp=31,)1()1,0()1|0(ZPZXpZXp=1)0()0,1()0|1(ZPZXpZXp=32,)1()1,1()1|1(ZPZXpZXp=0则)1()1|1(log)1,1()1()0|1(log)0,1()0()1|0(log)1,0()0()0|0(log)0,0();(2222XpppXpppXpppXpppZXI=210log02132log41211log412131log412222=9log4112比特/符号.2）（20分）若离散无记忆信源的概率分布为3.01.04.005.005.01.0654321aaaaaaU①分别构造二元，三元Huffman编码（要求码长方差最小，但不需求出），Shannon编码，Fano编码，Shannon-Fano-Elias编码。②并求①中二元Huffman编码的编码效率。（只列出式子即可）解:对信源按概率从大到小排序,05.005.01.01.03.04.0321564aaaaaaU,建立码树则有二第4页共5页元Huffman编码:,00111a,00012a,00003a,14a,00105a,016a要进行三元Huffman编码,则需要添加一个空信源,成为005.005.01.01.03.04.07321564aaaaaaaU,建立码树则有三元Huffman编码:,011a,0002a,0013a24a,,025a,16aShannon编码如下:信源码长累加概率码字4a20006a20.4015a40.710111a40.811002a50.9111003a50.9511110Fano编码如下:信源概率第1次分组第2次分组第3次分组第4次分组第5次分组码字4a0.4006a0.310105a0.1101101a0.11011102a0.0510111103a0.05111111Shannon-Fano-Elias编码信源概率)(xF)(xF)(xl二元)(xF码字1a0.10.10.0550.00001000012a0.050.150.12560.0010000010003a0.050.20.17560.0010110010114a0.40.60.430.0110115a0.10.70.6550.101001101001第5页共5页6a0.31.00.8530.110110二元Huffman编码的平均码长为l=3.021.044.0105.0405.041.04=2.2,编码效率为2.2)3.0,1.0,4.0,05.0,05.0,1.0(2log)()(HlUHRUH3）．设二元对称信道的信道转移矩阵为21214341。（1）若P(0)=41,P(1)=43，求信息熵H(X)，条件熵H(X/Y)，H(Y/X)，自信息量I(X；Y)（2）求信道容量及最佳输入分布。解：811.041log4143log43)(log)()(xiixPxPXHbit16721*4341*41)/0()()0(xxyPxPyP169)/1()()1(xxyPxPyP7116741*41)0()0/0()0()0/0(yPxyPxPyxP76)0/1(yxP3116943*41)1()0/1()0()1/0(yPxyPxPyxP32)1/1(yxPyxxypxypxpXYH)/(log)/()()/(21log2121log214143log4341log4141比特/符号。yxyxpyxpypYXH)/(log)/()()/(32log3276log7616931log3171log71167比特/符号。第6页共5页)/()();(YXHXHYXI2)解：非对称信道。1811281.021log2121log2143log4341log412121434121，解得622562.0377438.121求信道容量C)22log(21C=)22log(6225.03775.1=0.049求P(yj)327.022)(049.03775.111CyP628.022)(049.06225.022CyP求P(xj))(43)(21628.0)(41)(21372.02121xPxPxPxP解得512.0)(488.0)(12xPxP622562.0377438.11811281.012321811281.05.05.075.025.0110