信息论与编码考试必备

注11表示二选一中的第一题,12表示二选一里第二题,以此类推.改正的地方，加上*号一.选择题（是从我笔记上得到的信息）11.输入输出，无噪信道（结果应该是D,内容不记得了）12无用信道容量为021任何一个[n,k,d]具备的性质：①给定一个[n,k,d]线性分组码，其生成矩阵可有多个②封闭性。任意两个码字的和还是它的码字③码的最小距离等于非零码的最小码重。④全0总是一个码字题目是选不具备的性质，其中有个选项，最大似然距离等于最小汉明距离，（错误）22其中有个选项,校验矩阵不等于生成矩阵(错误)（21,22）都是关于[n,k,d]线性分组码性质的考察*31失真函数R(D)不正确0minD*32.失真函数R(D).不正确的是,)()(maxminDRDR(错误,R(D)函数是减函数)41.下列离散信源计算中熵最大的是（选择等概率输入的就是最大的）42.下列关于信源熵不正确的是（H(XY)=H(X)+H(Y)错）51（题目关于信源信道有效性，可能不是这个题，看一下）为提高通信系统传输消息有效性，信源编码采用的方法是（A）。A.压缩信源的冗余度B.在信息比特中适当加入冗余比特C.研究码的生成矩阵D.对多组信息进行交织处理52.ML最大似然译码等价于AMP最大后验概率译码的条件是（D）A.离散无记忆信道B.采取Huffman编码C.对称信道D.输入等概率（以下的题都是从李佳捷录音得到的信息）二.判断题11.哈夫曼编码中最长的码子是唯一的(错)12.对相同概率分布的信源符号得到的哈夫曼编码是唯一的(错)21马氏信源序列hm是递减的（对）22.（对）31唯一可译码的充分必要条件是所有后缀集中不含有码子（对）32异字头码的码长必定满足Kraft不等式（对）41信源输出序列中，非典型序列出现概率很小，其数目少（错）42两个典型序列组成的联合序列必定是典型序列（错）51两个子信道的容量分别为c1,c2,串联后所得到新信道容量比c1,c2都小（对）52两个子信道的容量分别为c1,c2,并联后所得到新信道容量是c1,c2的和（对）61功率相同的高斯噪声信道，容量最小（对）62为了抵抗高斯噪声的干扰，信源输出要满足高斯分布（对）71连续信源在一一变换下，熵是不变的（错）72连续信源熵有最大值（错）81设信源编码码率为R，信源的熵为H，R=H的等价条件是存在着无失真编码（对）82信源编码码率为R，信道容量C，R=C的充分必要条件是存在着译码长度任意小的信道编码（对）三填空题11均值为0，方差为2的高斯分布在平方误差失真下，【mind0，maxd2】12均值为0，方差为2的高斯分布【R(D)=D2log21,0=D=2】*21.fanno不等式为:两个在相同字符表{0,1,2…，k-1}中取值的随机变量XX和满足如下不等式【1log|kPPHXXHEE】(考虑在两个相同字符表中取值的随机变量XX和,它们的联合)分布为1,....3,2,1,0,j,kjkXkXP在和取值。如果把X看成为对X的估计，定义错误概率为)(,1k010jkjXkXPPkjjE）（按老师给的符号给出相应不等式）*22.Kraft不等式:存在长度为n1,n2,……nk的D元异字头码的充要条件为【11n-kkkD】（按老师给的符号给出相应不等式）31.(n,k)循环码,生成多项式的次数为【n-k】32.G(X)是二元循环码的生成多项式，常数项为【1】41。Hamming码最多能检测【2】个错误42一个（n,k）线性码，生成矩阵为kkrkIPG，则其校验矩阵为TrkrrPIH)(,r=n-k例子：二元(7,3)hamming码的生成矩阵为G=100111001011010011011，则校验矩阵为H=【1111000110010010100100110001】51.n为高斯信源，其协方差矩阵为，那么它的熵为【Hne2log21】52.功率为2的受限连续信源的熵最大为【H2e2log21】61错误率为的BSC信道n次级联后容量为【C=22-1-1H-1n】62错误率为，n个BSC信道组成的和信道为C=nii1c2log【=Hn12log】ci为每个bsc信道容量，有C1=c2=c3=….cn=1-H()71两个长为n的码子，u和v，则w(t)(u+v)=w(t)(u)+w(t)(v)-2w(t)(u.v)（注u.v即为对应位置相乘）72.参数为（n,k,m）卷积码的编码速率为R=K/n四.大题(5*11’=55)11.A村有一半人说真话，3/10人总说假话，2/10人拒绝回答；B村有3/10人诚实，一半人说谎，2/10人拒绝回答。现随机地从A村和B村抽取人，p为抽到A村人的概率，1–p为抽到B村人的概率，问通过测试某人说话的状态平均能获得多少关于该人属于哪个村的信息？通过改变p，求出该信息的最大值。[解]用X表示随机抽取人所属的村别，Y表示说话的状态，则X和Y之间的关系图如下所示。12.（注意这个题，想应的代称改变了，过程结果不变）在某中学有3/4学生通过了考试，1/4学生没有通过。在通过考试的同学中10%有电脑，而没有通过的学生中50%有电脑，所有有电脑的同学都加入了通宵CS联盟，无电脑的同学中仅有40%加入通宵CS联盟。a.通过询问是否有电脑，能获得多少关于学生考试成绩的信息？b.通过询问是否参加通宵CS联盟，能获得多少关于学生成绩的信息？c.如果把学生成绩情况，电脑拥有情况和是否参加通宵CS联盟用三位二进数字传输，问每位数字携带多少信息？X表示学生有无通过考试，Y表示学生有无电脑，Z表示学生有无参加通宵CS联盟，X，Y，Z之间的关系图（a）I(X;Y)H(Y)H(Y|X)H(0.2,0.8)0.75H(0.1,0.9)0.25H(0.5,0.5)0.12bit（b）I(X;Z)H(Z)H(Z|X)H(0.52,0.48)0.75H(0.46,0.54)0.25H(0.7,0.3)0.03bit（c）第一位数字携带信息为H(X)H(0.75,0.25)0.811bit在已知第一位数字下，第二位数字携带信息为H(Y|X)0.75H(0.1,0.9)0.25H(0.5,0.5)=0.602bit在已知前二位数字下，第三位数字携带信息为：H(Z|X,Y)H(Z|Y)（因为X→Y→Z）0.2H(1)0.8H(0.4,0.6)0.8H(0.6,0.4)=0.777bit21.22.因为S7中元素在S1和S4中都出现过，所以S7以后的后缀分解集中不会出现S1−S7中没有出现过的元素，所以从S1−S7可见后缀分解集中不含有码字，所以编码是唯一可译的。3132.410),(min)(minxxxxdxpD1),()(minmaxxxxxdxpD存在着与失真度量矩阵具有同样对称性的转移概率分布达到率失真R（D），这个转移概率函数可以写为Q，1由于0110,,dxxdxx，所以对于任何有限平均失真，必须β=0，于是转移概率矩阵为-10-10Q在失真限制下、1,|,xxxxdxxqxpD检验信道如下)(1;DHXXIDR）（0=D=142补充过程:转移概率矩阵设为,且1,所以矩阵为-1-1,DxxdxxqxpDx-1-1,|,x，)()()1,()21,21()|()(;DHPHHHXXHXHXXIDR）（5152.解：五.综合题6162.解：