大学课件《信息处理与编码》习题答案集57章.doc

51设有一离散无记忆信源如下：试求其哈夫曼编码，并求其编码效率。52 设有一离散无记忆信源如下：试求：1） 信源符号熵H(U)2） 求相应二元哈夫曼编码及其编码效率3） 求相应三元哈夫曼编码及其编码效率4） 若要求Pe=10-3,采用定长二元码要求达到（2）中哈夫曼编码效率时，估计要多少信源符号一起编才能实现。（1）编码 CU11.010U211U3000U4001U5010U60110U70111平均码长编码效率(3)平均码长编码效率(4)按编码效率，即，有按差错概率，有约需个信源符号一起编码。53 设有一离散无记忆信源：,试对下列三种情况将信源输出进行二进制哈夫曼编码，并求每个信源符号平均码长和编码效率。（1） 对每个信源符号进行编码；（2） 对每两个信源（二维扩展）符号进行编码；（3） 对每三个信源（三维扩展）符号进行编码； 解：（1）每个信源符号进行编码； 平均码长：信源消息熵：编码效率：(2)对每两个信源（二维扩展）符号进行编码；平均码长：编码效率：(3) 对每三个信源（三维扩展）符号进行编码；U1 U1 U1 0.729 0.729 0.729 0.729 0.729 0.729 0.729 0 1 0 U1 U1 U2 0.081 0.081 0.081 0.081 0.109 0.162 0 0.271 1 100 U1 U2 U1 0.081 0.081 0.081 0.081 0.081 0 0.109 1 101U2 U1 U1 0.081 0.081 0.081 0.081 0 0.081 1 110 U1 U2 U2 0.009 0.01 0.018 0 0.028 1 11100U2 U1 U20.009 0.009 0 0.01 1 11101U2 U2 U10.009 0 0.009 1 11110U2 U2 U2 0.001 1 11111平均码长：编码效率：5.4若已知一离散无记忆信源如下：试利用二元编码符号编成哈夫曼码，用两种方法使得他们有相同的最小平均码长但方差不相同，并说明哪种编码实用性更好。解： 方法一：平均码长： 方法二：平均码长：比较上述两种方法的编码结果，平均码长相等，第二种方法的方差要比第一种方法小，所以，第二种方法更有实用性。5.5若已知一离散信源符号集为：（a） 若：，试求对其进行哈夫曼编码及其编码效率？（b） 若用习题5-1所示马氏链状态图来描述：求稳态时符号出现概率并求信源熵；（c） 试设计一个哈夫曼编码，使每次对两个信源符号编码并求每个信源符号平均比特数以及编码效率。(a)(b)其状态转移矩阵为 设平稳分布为计算信息熵为s信源消息率概率编码u1 u110u1 u2001u2 u1010u2 u2111u1 u30000u3 u1 0001u2 u31100u3 u21101u1 u401110u4 u101111u3 u3011000u2 u4011010u4 u2 011011u3 u40110011u4 u301100100u4 u4011001015.6设两集合 (1)由题意知:对S，其状态转移概率矩阵为 由状态转移图可知 所以(2)(3)信息效率平均编码长度逼近。5.7一离散无记忆信源0 1，其出现概率分别为：p0=0.3,p1=0.7,已知信源序列为1101110011试求：（1） 对此序列进行算术编码；（2） 若将0，1符号概率近似取为p0=0.25, p1=0.75,进行算术编码；（3） 计算编码效率。解：（1）将概率化为二进制：p1=0.101, p0=0.011。则累计概率为：P1=0.000, P0=0.101。设定起始状态为空序列，令A()=1,C()=0。由公式（5-1-29）得：C(1)=C()+A()P1=0+1*0=0A(1)=A()p1=1*0.101=0.101C(11)=C(1)+A(1)P1=0+0.101*0=0A(11)= A(1)p1=0.101*0.101=0.011001C(110)=C(11)+A(11)P0=0+0.011001*0.101=0.001111101A(110)=A(11)p0=0.011001*0.011=0.001001011C(1101)=C(110)+A(110)*P1=0.001111101+0.001001011*0=0.001111101A(1101)=A(110)p1=0.001001011*0.101=0.000101110111C(11011)=C(1101)+A(1101)*P1=0.001111101+0.000101110111*0=0.001111101A(11011)=A(1101)*p1=0.000101110111*0.101=0.000011101010011C(110111)=C(11011)+A(11011)*P1=0.001111101+0.000011101010011*0=0.001111101A(110111)=A(11011)*p1=0.000011101010011*0.101=0.000010010010011111后面的几位可以依此推算出来。（2）将概率化为二进制：p1=0.11, p0=0.01。则累计概率为：P1=0.00, P0=0.11。 设定起始状态为空序列，令A()=1,C()=0。由公式（5-1-29）得：C(1)=C()+A()P1=0+1*0=0A(1)=A()p1=1*0.11=0.11C(11)=C(1)+A(1)P1=0+0.11*0=0A(11)= A(1)p1=0.11*0.11=0.1001C(110)=C(11)+A(11)P0=0+0.1001*0.11=0.011011A(110)=A(11)p0=0.1001*0.01=0.001001C(1101)=C(110)+A(110)*P1=0.011011+0.001001*0=0.011011A(1101)=A(110)p1=0.001001*0.11=0.00011011C(11011)=C(1101)+A(1101)*P1=0.011011+0.00011011*0=0.011011A(11011)=A(1101)*p1=0.00011011*0.11=0.0001010001C(110111)=C(11011)+A(11011)*P1=0.011011+0.0001010001*0=0.011011A(110111)=A(11011)*p1=0.0001010001*0.11=0.000011110011后面各位可以依此类推算出来5.8 对5.7题中的编码结果利用比较法写出译码过程。解：只对第二种编码进行译码：C(110111)=0.00110110.11,所以译出第一个符号为1；去掉被乘概率因子（加权）：0.0011011*10=0.0110110.11,译出第二个符号为1；再出掉被乘概率因子（加权）：0.0011011*100=0.110110.11,1,所以译出第三个符号是0；去掉累计概率：即0.11011-0.11=0.00011,再去掉被乘概率因子（加权）：0.00011*8=0.00011*1000=0.110.11,1,所以译出第四个符号为0；去掉累计概率：即0.11-0.11=0.0,0.0*8=0.00.11,所以译出第五个符号为1；同理，译得第六、七个符号为11；则译出的序列为S*=110111=S。5.9 对离散、无记忆信源符号A、B、C其概率分别为5/9、1/3、1/9，试应用算术编码方法对序列CABA进行编码，并对结果进行译码。解：符号符号概率pi符号累计概率Pi=piA(5/9) 0.10B(1/3) 0.010.1C(1/9) 0.010.11假设起始状态为空虚列，令A()=1,C()=0.由公式得：C(C)=C()+A()PC=0+1*0.11=0.11;A(C)=A()pC=1*0.01=0.01;C(CA)=C(C)+A(C)PA=0.11+0.01*0=0.11;A(CA)=A(C)pA=0.01*0.1=0.001;C(CAB)=C(CA)+A(CA)PB=0.11+0.1*0.001=0.1101;A(CAB)=A(CA)pB=0.001*0.01=0.00001;C(CABA)=C(CAB)+A(CAB)PA=0.1101+0.00001*0=0.1101;解码过程如下： A B CA B C A B C A0.1101位于0.11，1，所以第一个码子是C,0.1101-0.11=0.0001,乘上加权 0.0001*10=0.001，位于0，0.1，所以第二个码子是A,0.001*100=0.1,位于0.1，0.11，所以第三个码子是B,0.1-0.1=0,位于0，0.1，所以第四个码子是A,所以码序列是CABA。510已知二维矢量（x,y）在正三角形内均匀分布，求N=4的码书，此三角形的三个顶点是。解：将此三角形分成等面积的16份，如图所示：根据上图将此三角形内分成16个等面积的小正三角形，各部分的码书分别如下： 100002 00013 00104 00115 01006 01017 01108 01119 100010 100111 101012 101113 110014 110115 111016 11115.12 应用修正哈夫曼码对下面2047黑白像素的单行序列进行编码并计算压缩比：1W1B2W4W4B8W8B16W16B32W32B64W64B128W128B256W256B512W512B1W.解：其哈夫曼码为：000111010011111101101110011000101101010000001011100011011000001101010110110011010100000011110000110111100100011010100001100100000001101110110111001101010000010110110000110111011001010011010100000011011000000110111000111编码前总码长为：L总=（1+2+4+8+16+32+64+128+256+512）*2+1=2047；编码后总码长为：L总=6+3+4+2+4+3+5+6+6+10+8+12+5+8+10+10+5+8+12+10+7+8+12+10+8+5+13+10+6=216压缩比为：L总/ L总=2047/216= 9.47685.13设输出矩阵为,已知5.14可得变换后的设5.15 设信源协方差矩阵为：试求：用DFT计算解：由公式得： 5.16 若仍应用上题中的协方差矩阵值，采用沃尔什哈达码变换，试求，并于上题结果相比较。解：由公式得： 与上题结果作比较，形式上都是对角阵，只是对角线上的元素不同。517若用DCT对5.15中的信源进行变换，试求变换后的协方差矩阵。若变为：，试求变换后的协方差矩阵，其中，。将，代入得（2）将，代入得518 若已知信源的协方差矩阵为：，试求：1） 由K-L变换所得输出协方差矩阵用哈尔变换求输出的协方差矩阵（1）取变换矩阵为，因为A是正交的，所以有，所以有（2） 第六章习题6.1 c = 5m + 12 mod 26 明文 information 密文 AZLETUMDAEZ6.2 （1） g18+135f a13n r51+1312m t70s e25z （2） w20u a16q L10k 所以：相应密文为：fmznsuqkk 6.3 设已知下列分组加密方程为: 试求当明文为”data security”时,加密后的密文.(加密时,可不计字间空隙)解: 上方程可表示为: ,mod26解此方程有:时; 时; 时; 时; 时; 时; 所以加密后的密文为”gpmr uscoctub”6.4 已知下列分组加密方程为：试求当明文为“data security“（不计单字间空隙）时，加密后的密文。解：明文为：datasecurity301901842201781924 所以密文为： iwkw kypcpoli6.5 已知序列加密体制如习题图6-1。而密码产生器为一简单的4节m序列产生器如习题图6-2。当明文序列为101010101010101时，试求：(1) 密钥序列K(写一个周期)；(2) 密文序列C以及还原后的明文序列m(写一个周期)；(3) 若将上述抽头位置从（4，1）改为（4，2），试问能否仍能产生m序列伪随机密钥？(4) 试问窃听者在已知密钥抽头位置（4，1）时，需窃得几位明文（或密钥）后可破译，若未知抽头位置信息时，又需要窃得多少位才能破译？解：（1） 密钥序列k（一个周期）：000111101011001；（2） 密文序列c（一个周期）：101101000001100；还原后的铭文序列m（一个周期）：101010101010101；（3） 若抽头位置从（4，1）改为（4，2），则不能产生m序列伪随机密钥；（4） 在已知密钥抽头位置时，n位可破；未知时，相继的2n位可破。6.6 若已知一个分组加密方式如习题图6-3。01234567 0 1234567 试求：（1）制订对照真值表；（2）列出模二加加密方程组；（3）列出 的模二加解密方程组；（4）若任意改变明文和密文间的连线方式，试问可以组成多少种密钥？解：（1） 真值表输 入输 出 0000011310011117201000003011110641000102510110046110101571110011（2） 加密方程（3） 解密方程（4） 任意改变连线方式，可以组成(23)!=8!种。6.7若已知DES体制中8个S盒之一的S1盒选择压缩函数如下：列号行号01234567891011121314150144131215118310612590710157414213110612119538241148136211151297310503512824917511214100613 假设输入S1盒的矢量为X=（x0 x1x2x3x4x5）=（010011）。而S1表格行号是由输入的头尾所组成的矢量表示，即行号=（x0x5）。剩下四位表示列号，即列号=（x1x2x3x4）；试求通过选择压缩函数S1变换后的输出矢量。解：根据题意：行号=（x0x5）=（01）=1；列号=（x1x2x3x4）=（1001）=9， 所以压缩后的输出数为6，输出矢量为（y0y1y2y3）=（0110）。6.8 在对具有1000个保密用户的中小型通信网进行保密通信，若采用对称的单钥制，且每个用户仅具有一个加密密钥，试问每个用户应需要保留多少种密钥？若改用不对称双钥即公开密钥，这时每个用户又需保管多少种密钥？ 解：（1）采用对称的单钥制，每个用户需保留个。 （2）采用不对称的双钥制，每个用户需保留1000个。6.9 若采用一种指数的方式加密的简单RSA体制，设，明文为a，b，c，d四个字母。试求：（1） 素数积n=？相应的欧拉常数；（2） 若令a=0，b=1，c=2，d=3，且选用加密指数e为：，取e=5；选用解密指数d为：（e，d）=1mod，即，取，则d=5。这时求四个加密后的密文。（3） 求解密后还原的明文。解：（1） 素数积，欧拉常数；（2） 加密后的密文： （3） 解密后的原文： 6.10 试比较数字签证与通常采用的手写书签以及消息认证三者之间的差异，并讨论数字签证的主要优点和特点。答：数字签证与手写书签字的主要区别在于前者是0与1的数字序列，而后者则是因人而异的各类文字。数字签证与消息认证之间的主要区别在于：消息认证能使收方验证消息的发送者以及所发送的消息内容是否被伪造和修改。当收者和发者之间没有利害冲突时，防止非法用户的第三者的破坏就足够了。但当收者与发者之间有利害冲突时，消息认证就显得无能为力了。这时只有借助于数字签字技术。数字签字的特点：收方能确认发方的签字，但不能伪造；当发方发出签字消息给收方后，就不能再否认所签发的消息；可以确认收、发双方的消息传送，但也不能伪造着一过程；可以进一步对所传送明文数字加以保密以防窃听，既可在发送端防止伪造和篡改，又能在接收端防止窃听。6.11 若将一单路模拟话音频谱分为四段,进行频域置乱加密,其各段之间的相关系数如下:uij 1 2 3 41 1 0.8 0.64 0.512 0.8 1 0.8 0.643 0.64 0.8 1 0.84 0.51 0.64 0.8 1试求:(1)若仅采用频域置乱问可以组成多少种置乱方式?(2)若要求0.6才可用，问有多少种可用方式?(3)若与倒频相结合,试问置乱又增加了多少种?解: (1)4!=24种(2)1种(3)4!*=384种6-12（1） 置乱矩阵T：T的逆矩阵：6.13 = 0.8 052 即 （0.8）3 0.52 相邻时隙的编号应差3以上 输出 c = 84736251 2置乱矩阵 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 T= 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 13解密矩阵 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 T-1 = 0 0 0 0 0 1 0 0 = TT 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1题7.1 解：对于（7，1）重复码有 (0 0 0 0 0 0 0) (1 1 1 1 1 1 1) 两种形式 可以看出它的生成矩阵是 G=(1 1 1 1 1 1 1) 又由于 C1=C0 C2=C0 C3=C0 C4=C0 C5=C0 C6=C0 可知其监督矩阵为 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 H= 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 d min = ( 1 1 1 1 1 1 1 ) = 7 ( 0 0 0 0 0 0 0 ) 题7.2 解： ;经过基本矩阵变化为；所以 P=;=；。由生成矩阵可知，最小距离d=3.题7.3 解 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 G = 0 0 1 0 0 0 1 1 1 N = 9, K = 5 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 H= 1 1 1 0 1 0 0 1 0 dmin= 3 1 1 1 1 0 0 0 0 1 c0 = 0 0 0 0 0 0 0 0 0 c 1= 1 0 0 0 0 1 1 1 1 c 2= 0 1 0 0 0 1 0 1 1 c 3= 1 1 0 0 0 0 1 0 0 c4 = 0 0 1 0 0 0 1 1 1 c5 = 1 0 1 0 0 1 0 0 0c7 = 0 1 1 0 0 1 1 0 0题7.4 解 1s1=y1y2y3y5s2=y2y3y4y6s3=y1y2y4y7s4=y1y3y4y8y1y2y3y4y5y6y7y8 s1 s2 s3 s4 1 0 1 1 1 1 1 0 S = YHT = (0 1 1 1 1 0 0 1)HT = (0 1 1 1 1 0 0 1) 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 =(1 1 0 1) 没出的码字 c=0111100100100000=010110017-5(1) 循环码(15,4) (2) a非系统码的生成矩阵: b系统码的生成矩阵: (3)监督矩阵：7-6 解：码矢量码多项式生成元幂 0 0 0 0000 0 0 110 0 1 0X0 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1题7.9已知某汉明码的监督矩阵如下,试求起生成矩阵。当输入序列为110101101010时,求编码器的输出序列。解：其生成矩阵为如下：当输入序列为1101,0110,1010输出序列为1101001,0110001,1010011。题7.10已知一个（6,3）线性分组码的全部码字为001011,110011,010110,101110,100101,111000,011101,000000,求该码的输出矩阵与监督矩阵,并讨论起纠错能力.解：其生成矩阵为:其监督矩阵为：因为n-k=6-3=3=2r+1所以r=1.即能纠1位错误。7.11设一个(7,4)循环码的生成多项式g(x)=x3+x+1,当接收矢量为r=(1100100)时,问接收是否有错?如果有错,至少有几个错?该码能否纠正这些错?并求译码器的码字c.解：接收是有错误的。1+x2=1+x+x4mod(x3+x+1)错误至少有一位。该码能纠正这个错误。因为x6=1+x2mod(x3+x+1)所以译码器的输出为1100101。 7.12一个(15,7)的循环码,生成多项式为g(x)=x9+x6+x5+x4+x+1,a. 设计编码器电路.b. 设信息位为u=(101001)确定监督位并编成系统码的码字.解：编码电路如下：监督位为01100001，系统码字为011000010101001。 D3D2D1D0 D4D5D6D7 3. 输入 反馈 输出 状态（） 00000000000 00000000000 00000000000 10010000000 00001000000 00000100000 10010010000 00001001000 10010100100 00001010010 10010101001 01010111100 10011011110 10011101111 11000011111 1011