南京工程学院信息论参考试卷iJ

一填空题（本题15空，每空1分，共15分）1设在一8行×8列共64个方格的正方形棋盘上，甲随意将一粒棋子放在棋盘的某个方格，让乙猜测棋子所在的位置。如将方格按顺序编号64;......,3;2;188332211yxyxyxyx，则令乙猜测棋子所在方格顺序号的信息量为（log264=6）bit；如方格按行和列编号，甲将棋子所在方格的行编号告诉乙后，在令乙猜测棋子所在列所需的信息量为（3）bit。2信源的平均自信息量指的是（平均每个符号所能提供的信息量）；信源熵用来表征信源的（平均不确定度）；平均互信息量I(X;Y)的物理含义是（Y已知后所获得的关于X的信息），I(Y;X)的物理含义是（X已知后所获得的关于Y的信息）。3传输信道中常见的错误有（随机错误）、（突发错误）和混合错误三种；差错控制方式主要有（检错重发）、（前向纠错）和混合方式三种。4设C={11100,01001,10010,00111}是一个二元码，该码的最小距离dmin=（3），则该码最多能检测出（2）个随机错，最多能纠正（1）个随机错。5设有一个二元等概信源：u={0，1}，P0=P1=1/2，通过一个二进制对称信道BSC，其失真函数dij与信道转移概率Pji=p(vj/ui)分别定义为jijidij01，jijiPji1，则失真矩阵[dij]=（1001），平均失真D=（）。二判断题（本题10小题,每小题1分,共10分）1．√2．×3．√4．√5．×6．×7．√8．√9．√10．×（1）对于独立信源，不可能进行预测编码。（）（2）信息率失真函数的意义是：对于给定的信源，在满足保真度准则*DD的前提下，信息率失真函数R(D)是信息率允许压缩到的最大值。（）（3）一般情况下，互信息满足：0≤I(X;Y)≤min(H(X),H(Y))。（）（4）码字集合{100，101，0，11}是唯一可译码。（）（5）互信息量);(jiyxI≥0，即具有非负性。（）（6）若要求发现n个独立随机错误，则要求最小码距1nmind。（）（7）对于强对称信道，只有当信源等概分布时，才能使其达到信道容量C。（）（8）二维离散平稳有记忆信源的熵满足：H(X1,X2)≤H(X1)+H(X2)。（）（9）线性分组码中任意两个码字的模2加仍为一个有用码字。（）（10）马尔可夫序列的联合概率具有时间推移不变性。（）四计算题（本题3小题,共25分）1设有离散无记忆信源X，其概率分布为P（X）={0.37，0.25，0.18，0.12，0.05，0.03}，求：1）信源符号熵H（X）；2）用哈夫曼编码编成二元变长码，并计算其编码效率；3）如要求译码错误小于10-3，采用定长编码达到2）中的编码效率，需要多少个信源符号一起编码？（3+4+4=11分）解：1）2()logiiiHXpp=2.22bit/符号2）两个小概率相加后，得到的概率重新排序，上分支编码为0，下分支编码为1。得到整个信源编码如上所述。平均码长0.3720.2520.1820.1230.0540.034K=2.58编码效率3）设采用定长二元码有：22222275.0)]([)()]([])([bitXHXIpXHXIEiiii编码效率为86.1%即()86.1%0.36()HXHX按译码错误10-3有，2325.7910ePLL个，所以，需要35.7910个信源符号一起编码，才可以达到86.1%的编码效率。2设C={00000000,00001111,00110011,00111100}是一个二元码。试：1）计算码C中所有码字之间的距离及最小距离；2）在一个二元码中，如果把某一个码字中的0和1互换，即0换为1，1换为0，所得的字称为此码字的补。所有码字的补构成的集合称为此码的补码。求码C的补码以及补码中所有码字之间的距离和最小距离，它们与1）中的结果有什么关系？3）试将2）中的结果推广到一般的二元码。（2+2+2=6分）解：1）d(00000000,00001111)=4d(00000000,00110011)=4d(00000000,00111100)=4d(00001111,00110011)=4d(00001111,00111100)=4d(00110011,00111100)=4故码C的最小距离d=4（2分）2）码C的补码是{11111111,11110000,11001100,11000011}d(11111111,11110000)=4d(11111111,11001100)=4d(11111111,11000011)=4d(11110000,11001100)=4d(11110000,11000011)=4d(11001100,11000011)=4故C补码的最小距离d=4（2分）3）推广到一般的二元码也有以上的结论：设码C中任意两码字的距离为d，即两码字有d位不同，n-d位相同。变补后，仍有d位不同，n-d位相同，所以任意两码字的距离不变，最小距离当然不变。（2分）3一个（8，4）系统线性分组码，其一致校验方程为：0123101220133023cmmmcmmmcmmmcmmm，其中m0~m3是信息位，C0~C3是校验位。1)求出此分组码的生成矩阵G和校验矩阵H。2)求此码的最小距离dmin。3)若输入信息m=(1010)，试求对应的输出码字。4)若接收序列R=（10111010），如何判断接收是否有错？（2+2+2+2=8分）：1）由一致校验方程，易得出生成矩阵11011000101101000111001011100001G校验矩阵10001101010010110010011100011110H2）16组码字为00000000、00011011、00101101、00110110、01001110、01010101、01100011、01111000、10000111、10011100、10101010、10110001、11001001、11010010、11100100、111111111∴4mind3）输入信息m=(1010)，对应的输出码字为10101010。4）1011的正确码字应该是10110011，所以有错，判断是否有错，只需计算RHT是否为零，如为零则无错，不为零则有错。五综合题（本题3小题,共30分）1一离散无记忆信源X的概率空间为83,41,83,,)(321xxxXPX，求：1）该信源的熵H（X）；2）对该信源进行二次扩展的概率空间)(2XPX，并求)(2XH；3）由此确定)(2XH与)(XH之间的关系。（2+3+3=8分）解:1）2()logiiiHXpp=1.565bit/符号2）X1X1X1X2X1X3X2X1X2X2X2X3X3X1X3X2X3X39/643/329/643/321/163/329/643/329/64221()log2iiiHXpp=1.563）有上述计算可知，)()(2XHXH离散无记忆信源的平均符号熵=离散单个符号熵2设某卷积码的转移函数矩阵为G（D）=（1+D，1+D2），试：1）画出该卷积码的编码器结构图；2）求该卷积码的状态图；3）求该码的自由距离df。（3+4+3=10分）解：1）编码器结果如下所示：2）状态图：3)假设初始状态为00，可以由上述的状态图看出：经路径00—10—01—00又回到初始状态，并容易验证这是一条最短路径，由此得自由距离df=4。3一个二进制二阶马尔可夫信源的原始信源为X：{0，1}，m=2，这时的状态空间为：S：{S1=00，S2=01，S3=10，S4=11}，共有nm=22=4个不同的状态。已知其一步转移概率为：求：1）该马尔可夫信源的状态图；2）各状态的极限概率；3）该信源的极限熵H∞。（4+4+4=12分）解：1）（4分）由状态图可以判断，这是一个非周期不可闭集，具有各态历经性，存在状态极限概率Wi。有：2）约束条件为：141iiWWPW，解得其极限概率分别为：W1=W4=5/14;W2=W3=2/14（4分）3）由极限概率和状态转移概率就可以计算马尔柯夫信源的极限熵：fuhaobitSiSjpSiSjpWHiji/8.0)/(log)/(414112（4分