信息论基础试卷及详细答案

信息论基础模拟试题命题者:08级命题委员会小组高级顾问：韩海清一．填空题1.某随机变量集合有n个符号，其最大熵为logn（26面）2.一个线性分组码C={000000,111111}，该分组码的纠错个数为2（136面）(提示：观察两个字符串不同数字的个数，设为n，则纠错个数为[21－n]，在本题中n=6，所以答案为2)3.I(X;Y),H(Y),H(Y|X)之间的关系为I(X;Y)=H(Y)-H(Y|X)，H(X),H(X|Y)之间的关系为H(X|Y)≤H(X)（26，27面）4.若信源符号数为q，码符号数为r，对信源符号进行编码，相应码长度为qll.....1，则异前置码存在的充要条件是：11≤∑=−qilir(课本88面，Kraft定理)5.加性高斯白噪声（AWGN）信道实现可靠通信的信噪比的下界为-1.59db（课本173面）6.一维高斯随机变量集的熵为)2log(212σπe（注意σ是平均方差，而2σ是方差，69面）7.一个加性高斯白噪声（AWGN）信道的噪声的功率谱密度为20N，输入信号平均功率限制为P，信道的带宽为W，那么信道每单位时间的容量为C=)1log(0WNPW+(169面)8在BSC（二元对称信道）中，错误率为p，则其信道容量C=1-H(p)（121面）9差熵为h（X）的连续随机变量集合X的熵功率为2σ=)(221Xheeπ（72面）10.一个最小距离为d的二元分组码能纠错能力为]21[−d（参考第二题）二．判断题1.对称信道达到容量时，输入概率和输出概率唯一。（√）（123面）2.设试验信道输入符号{321,,aaa}，概率分别为1/3，1/3，1/3，失真矩阵为⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛123312321，则3/5,1maxmin==DD。（√）（186面）3.若（X,Y,Z）为马氏链，则（Z,Y,X）也是马氏链。（√）（60面）4.分组码的最小距离就是其最小重量的非零码字的重量。（×）（135面，应该是线性分组码）5.为有效抵抗加性高斯噪声干扰，信道输入应该是高斯分布。（√）（164面）6.信道疑义度始终为正。（×）（138面，应该是非负，可以为0）7.信道输入和输出之间的平均互信息是下凸函数。（×）（29面，应该是上凸函数）8.信息处理过程中熵是不会增加的。（√）（26面）9.典型序列信源符号出现的概率近似等于其频率。（√）（86面）10.若信道的输入与输出分别为X,Y，输入符号的数目为r，那么信道疑义度满足H(X|Y)rppHEElog)(+≤。（×）（138面，应该是r-1）11.一个离散平稳无记忆信道的极限熵等于最小平均熵。（√）（119面）12.对于离散无记忆信道，达到容量时输入概率分布是唯一的。（×）（123面，不唯一）13.噪声功率相同的加性信道中以高斯噪声信道容量最大。（×）（应该是最小）14.R(D)函数是平均失真函数的下凸函数。（√）（187面）15.MAP准则是使译码平均错误率最小的准则。（√）（132面）16.任意两个典型序列的联合序列是典型序列。（×）17.与离散信源一样，连续信源的平均互信息也具有对称性和非负性。（√）（73面）18.通过一一变换后，连续信源的差熵一定会变化。（×）（67面，应该是可能会变化）19.转移概率矩阵不随时间变化的马氏链是平稳马氏链。（×）（47面，那是齐次马氏链）20.R≥H⇔存在无失真信源编码。（√）（7面，还有几个类似的，如R≤C⇔存在译码差错任意小的信道编码；R⇔≥)(DR存在平均失真）三．计算题1.给定离散无记忆信源的数学模型为⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛4/14/12/1321aaaPX，求其二次扩展源的熵)(2XH。（40面）解：)(2XH=2H(X)=2[2)41log41(21log21×−−]=3比特/扩展符号2.设直流平衡序列的滑动数字为n，当n=3时写出其连接矩阵并计算其容量。(219面)解：当n=3时，连接矩阵为⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=0101010103D设3D的最大特征值为maxλ，则其容量为C(3)=max2logλ=])13([coslog2+π=2log2=0.5比特/符号3.一个二维独立高斯信源（21XX），其中21,XX均值都为零，方差分别为2和4，采用均方失真测度，求该信源的R(D)函数。（201面）解：如果21,XX都使用，有B=2D/2和B≤2，得D≤2R(D)=DDD22log214log412log41=+如果仅使用2X，有B=2D-2和2B≤4，得2D≤3R(D)=224log41−D=12log21−D由max2D=2+4，得maxD=3所求R(D)函数：⎪⎩⎪⎨⎧≥≤−≤=3,032,)1/(2log)2/1(20,22log)2/1()(DDDDDDR4.已知信道的转移概率矩阵为⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛2/16/13/13/12/16/16/13/12/1，现有两种判决规则：规则A：⎪⎩⎪⎨⎧======332211)()()(abygabygabyg，规则B：⎪⎩⎪⎨⎧======233211)()()(abygabygabyg设输入等概率，求信道的疑义度和两种译码规则下信道疑义度的上界。（139面）解：由于信道为强对称信道，所以当信道输入等概率时，输出也等概率，H(X)=H(Y)。又因为H(X)-H(X|Y)=H(Y)-H(Y|X)，所以信道疑义度：H(X|Y)=H(Y|X)=H(1/2,1/3,1/6)=61log6131log3121log21−−−=3log21322+(bit)（1）对于规则A，由于∑∑====−3131)|(31)|()(1iiiiiiiEabPabPaPP=21331××=1/2，所以EP=1/2，信道疑义度上界为：H(1/2)+(1/2)×log2=1.5bit（2）对于规则B，由于∑∑====−3131)|(31)|()(1iiiiiiiEabPabPaPP=)316121(31++×=1/3，所以EP=2/3，信道疑义度上界为：H(2/3)+2/3×log2=3log2（bit）5.设X和Y时分别具有均值yxmm,，方差22,yxσσ的两个独立的高斯随机变量集合，且U=2/)(YX+，V=2/)(YX−，试求h(UV)。（70面）解：依据题意有⎟⎟⎠⎞⎜⎜⎝⎛⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛−=⎟⎟⎠⎞⎜⎜⎝⎛yxvu22222222所以h(UV)=h(XY)+log⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛−22222222det=log(yxeσσπ2)+log1=log(yxeσσπ2)6.设有一个二维独立并联高斯信道，两个子信道的噪声的方差分别为10,12221==σσ，输入信号的总能量为E=6，求信道容量C和达到容量时的能量分配21,EE；若其他条件不变，将输入信号的总能量改为E=15，结果又是多少呢？（165面）解：依题意得：⎪⎩⎪⎨⎧=+=+=[phone]EEBEBE，该方程组无非负数解，为此，应有方差大的子信道分配的能量为0所以⎩⎨⎧==+0121EBE⇒7,61==BEC=)161log(21+=7log21总能量改为E=15时有：⎩⎨⎧=+=−1592121EEEE有正数解1E=12,2E=3C=)1031log(21)121log(21+++=10169log217.写出错误率为p的二元对称信道的转移概率矩阵，并计算其二次扩展信道的转移概率矩阵和容量。（121面）解：该信道的转移概率矩阵为⎟⎟⎠⎞⎜⎜⎝⎛−−pppp11二次扩展信道的转移概率矩阵为⎟⎟⎠⎞⎜⎜⎝⎛−−⊗⎟⎟⎠⎞⎜⎜⎝⎛−−=∏pppppppp1111=⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−−−−−−−−−−−22222222)1()1()1()1()1()1()1()1()1()1()1()1(pppppppppppppppppppppppp由于错误率为p的二元对称信道的容量C=1-H(p)，所以信道的二次扩展信道容量为)(2222pHCC−==比特/符号8.一信道的转移概率矩阵为⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛3161316161613131，求信道容量和达到容量时的输出概率(112面)解：设输出概率分别为4321,,,qqqq。该信道为准对称信道，当输入等概率时达到信道容量可计算输出概率为1q=41)3161(21=+，31)3131(212=+=q，)6161(213+=q，414=q所以信道容量为C=)61,61,31,31()41,61,31,41(HH−=]2)61log61(2)31log31[()41log4161log6131log3141log41(×+×++++−=3log21652−（比特/符号）四．解答题1.一个二阶马氏链，符号集A={0，1}，转移概率为p(0|00)=p(1|11)=0.8,p(1|00)=p(0|11)=0.2,p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5(1)确定所对应的马氏源的状态，写出状态转移矩阵；(2)若信源初始状态分布为平稳分布，求8次扩展源的熵；(3)求信源的符号熵；(4)求信源效率；(5)求信源剩余度。（49，52，54面）解：(1)马氏源状态为2A={11,10,01,003210====}状态转移矩阵为P=⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛8.02.000005.05.05.05.000002.08.0(2)根据[P]可计算[h]=[4321,,,hhhh]，得：722.02.0log2.08.0log8.041=−−==hh15.0log5.05.0log5.032=−−==hh由（4321ππππ）⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛8.02.000005.05.05.05.000002.08.0=（4321ππππ）及14321=+++ππππ得状态平稳分布为：[4321ππππ]=[5/141/71/75/14]对应状态平稳分布的熵为H([π])=)7/1log()7/1(2)14/5log()14/5(2××−××−=1.863bit所以8次扩展源的熵为H(821.....XXX)=H([π])+(8-2)][][hTπ=1.863+]2)5.0log5.05.0log5.0(712)2.0log2.08.0log8.0(145[6×−−+×−−=6.669比特/符号(3)根据前面，得马氏信源熵为][][)(hXHTπ=∞=2)54.0log5.05.0log5.0(712)21.0log2.08.0log8.0(145×−−+×−−=0.801比特/符号(4)信源效率0HH∞=η=0.801/2log2=0.801(5)信源剩余度γ=1-η=0.1992.设一个等时长有约束系统的标号如图所示，其中0，1符号等时长，(1)求该约束信道的容量；(2)是否存在编码率为0.75的二元有限编码器。（212面）解：(1)该信道的连接矩阵为D=⎟⎟⎠⎞⎜⎜⎝⎛1110令,0=−zID得012=−−zz12解得)51(max+=λ所以信道容量为C=]2/)51[(log2+=0.694比特/符号(2)由于0.6940.75，故不存在这样的编码器3.某地区的女孩中25%是大学生，在大学生中有75%是身高1.6m以上的，而女孩中身高1.6m以上的占总数的一半。假如已得知“身高1.6m以上的某女孩是大学生”的消息，问获得了多少信息量？(34面)解：设A为“女孩是大学生”的事件；B为“女孩身高1.6m以上”的事件，则P(A)=0.25，p(B)=0.5，p(B|A)=0.75身高1.6m以上的某女孩是大学生的概率为p(A|B)，由已知条件可得p(A|B)=)()(BpABp=)()|().(BpABpAp=5.075.025.0×=0.375因此所获得信息量为：I(A|B)=-logp(A|B)=375.0log2−=1.42bit4.一信源S的符号集A={54321,,,,aaaaa}，概率分别为0.5，0.25，0.125，0.0625，0.0625(1)对该信源进行二元哈夫曼编码；(2)计算平均码