《信息论、编码与密码学》课后习题答案.doc 48页

'《信息论、编码与密码学》课后习题答案第1章信源编码1.1考虑一个信源概率为{0.30，0.25，0.20，0.15，0.10}的DMS。求信源熵H（X）。解：信源熵H(X)=-[0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322)]=[0.521+0.5+0.464+0.411+0.332]=2.228(bit)故得其信源熵H(X)为2.228bit1.2证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。解：若二元离散信源的统计特性为P+Q=1H(X)=-[P*log(P)+(1-P)*log(1-P)]对H(X)求导求极值，由dH(X)/d(P)=0可得可知当概率P=Q=1/2时，有信源熵对于三元离散信源，当概率时，信源熵，此结论可以推广到N元的离散信源。1.3证明不等式。画出曲线和 的平面图以表明上述不等式的正确性。证明：Y=lnxY=x-1yx1绘制图形说明如下可以很明确说明上述不等式的正确性。1.4证明1.5有一个信源X，它有无穷多个可能的输出，它们出现的概率为P（Xi）=2i-1,i=1,2,3,….,这个信源的平均自信息H（X）是什么？解：因为P（Xi）=2i-1,i=1,2,3,…所以H（X）=- =-log2(2+2.22+3.23+…..+n.2n)=2-（1-n）2n+11.6考虑另一个几何分布的随机变量X，满足P（Xi）=P（1-P）i-1i=1,2,3,…..,这个信源的平均自信息H（X）是什么？解：因为P（Xi）=P（1-P）i-1,i=1,2,3,所以H（X）=-=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+…….+np(1-p)n]=(1-n)(1-p)n+1-1.7考虑一个只取整数值的随机变量，满足，其中，。求熵。解：为了方便计算，设，则，；根据公式计算自信息量为：；则熵为：=？1.8计算概率分布函数为的均匀分布随机变量的微分熵。画出相对于参数的平面图，并对结果进行评论。 解：根据公式（1-21）可知，微分熵为：当时，，则当或时，，则根据得到的结果可以画出相应的平面图，由图可以看到随着的增加，即的减小，微分熵相应的增加。00.1101.9考虑一个信源的概率为的DMS。（1）给出此信源的霍夫曼码。（2）计算出这些码子的平均码长。（3）这个码的效率是多少？解：1）依题意，由霍夫曼编码的规则，得：1.00 0.650.400.200.350.250.200.150.05表格如下：符号概率自信息码字0.351.51510.252.000010.202.3220000.152.73800100.054.32200112）由平均码长公式,代入数据，得：3）首先，该信源的熵为： 该码的效率为：1.10考虑一个信源概率为{0.35，0.20，0.15，0.15，0.10，0.10，0.05，0.05}的DMS。(1)给出此信源的一种有效定长码。(2)给出此信源的霍夫曼码。(3)比较这两种码并给出评论。解：1）空2）依题意，由霍夫曼编码的规则，得: 符号概率自信息码字0.202.322010.202.3220000.152.7380010.152.7381000.101.0001010.101.0001100.054.32211100.054.32211112）空1.11一个DMS只有三个输出符号，它们的概率为{0.5，0.4，0.1}。(1)给出此信源的霍夫曼码并确定编码效率。(2)每次考虑两个符号时，给出此信源的霍夫曼码并确定编码效率。 (3)每次考虑三个符号时，给出此信源的霍夫曼码并确定编码效率。解：(1)本题的霍夫曼编码如下图所示：0.50.40.1010.5101.0图1.11霍夫曼编码则霍夫曼码如下表：符号概率码字x10.51x20.400x30.101该信源的熵为：平均每个符号的比特数为：该码的效率为：（2）把符号每两个分一组，重新应用霍夫曼编码算法，如下表所示： 符号对概率码字x1x10.2500x1x20.20010x2x10.20011x2x20.161010x1x30.05100x3x10.05110x2x30.041011x3x20.041110x3x30.011111该信源的熵为：每个组的平均比特数为:故该码的效率为：(3)依题意，把符合每三个分成一组，再重新应用霍夫曼编码算法，得: 编码表格如下：符号对概率自信息码字0.12502.70901000.10003.322300000.10003.322300010.10003.32231100.08003.6443011 0.08003.644301000.08003.644301010.06403.966200110.02505.3223101100.02505.3223101110.02505.3223111000.02005.6444111010.02005.6444111100.02005.6444111110.02005.64440010000.02005.64440010010.02005.64440010100.01605.96640010110.01605.96641010000.01605.96641010010.00507.664610101010.00507.6646101010000.00507.6646101010010.00407.9666101011000.00407.9666101011010.00407.966610101110 0.00109.9668101011111.14确定下列比特流的Lempel-Ziv码：01001111100101000001010101100110000从码字流恢复原来的序列。解：根据Lempel-Ziv算法列出下表：字典位置字典内容定长码字00010000000010100001001100000100100110010101011110100101100010011101110100011100000000110100100100110010101000100101110110101110110010100111011001000111100010000 第2章信道容量和编码2.1考虑图2-10所示的二元信道，设发送二元符号的先验概率为P0和P1，其中P0+P1=1，求后验概率和。01P00P111-qpq1-p解： 2.5（1）一个电话信道具有带宽3000Hz,且SNR=20dB.求信道容量。（2）若SNR增加到25dB,求信道容量。解：(1)SNR=20dB=100信道容量=Wlog2(1+SNR/W)(b/s)=3000*log2(1+100/3000)=142(b/s)(2)SNR=25dB=316信道容量=Wlog2(1+SNR/W)(b/s)=3000*log2(1+316/3000)=413(b/s)2.7假定一个电视每秒钟显示30个画面，每个画面大约有个像素，每个像素需要16比特的彩色显示。假定SNR为25dB，计算支持电视信号传输所需要的带宽（利用信息容量定理）解：根据题意，该电视信号所需的信息容量为：根据信息容量定理：，其中为信噪比，据题意据上式解得带宽2.8考虑图2-15所示的Z型信道。（1）求获得信道容量所需要的输入概率。（2）若将N个这样的信道相级联，证明联合信道可以用一个信道转移概率为的等价Z信道表示。（3）当时联合信道的容量是什么？ 图2-15解：(1)w为带宽信道容量(b/s)(2)由图可知信道转移概率为P那么N级级联的信道转移概率(3)当时级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在所有可能的输入概率上求得的即：2.10(1)证明对有限方差，高斯随机变量具有所有随机变量可能获得的最大微分熵。(2)证明该熵由公式给出。 证明：(1)由题意可知，高斯随机变量获得的微分熵为：则有：即其平均功率为：对于有限方差的高斯随机变量，即当平均功率受限时，有：即有：综上可得，对于平均功率受限的连续随机变量，当服从高斯分布时具有最大微分熵。(2)随机变量的微分熵为：(1)对于高斯分布，我们有：(2)其中，m为数学期望。将(2)式代入(1)可得：(3)由(3)式可以推出：(4)故(4)式即为本题所证。2.11 第3章纠错控制编码3.1证明是一个线性码。它的最小距离是什么？证明：由书中的定义3.8可知，线性码应该满足一下条件：（1）两个属于该码的码字的和仍然是一个属于该码的码字，（2）全零字总是一个码字，（3）两个码字之间的最小距离等于任何非零码字的最小重量，即设，即，，，，首先证明条件（1）：，，，，，，很明显，条件（1）是满足的。条件（2）也是显然成立的。最后证明条件（3）：不难看出最小距离，并且最小重量，即综上，三个条件都满足，那么就是一个线性码，它的最小距离是2。3.3考虑GF（2）上的下列生成矩阵2）用此矩阵生成所有可能的码字。3）求奇偶校验矩阵H。4）求与其等价的一个系统码的生成矩阵。5）构造该码的标准阵列。6）这个码的最小距离是多少。7）这个码能检测多少错误。8）写出这个码能检测的所有错误模式。 2）这个码能纠多少个错误。3）如果我们用此编码方案，那么符号错误概率是多少？将它与末尾的错误概率进行比较。4）这是一个线性码？解：（1）========此矩阵生成的码为：{00000，01010，10011，11001，10100，11110，00111，01101} （2）又在二元情况下，奇偶校验矩阵可写为：(4该码的标准阵列（5）奇偶校验矩阵H的第1、3列的和为零向量，因此，这个码的最小距离为：d*=2。（6）一个码至少可以检测所有重量小于或等于（d*-1）的非零错误模式。这个码的最小距离为：d*=2，所以重量为1的错误模式可以检测得到。（7）这个码能检测的所有错误模式{00001，00010，00100，01000，10000}（8）能纠正不多于t个错误应满足又d*=2所以即这个码能纠0个错误（9）才vv（10）{00000，01010，10011，11001，10100，11110，00111，01101}线性码的性质： 1、两个属于该码的码字的和仍是属于该码的码字00000+01010=0101000000+11001=1100100000+10011=1001100000+10100=1010000000+11110=1111000000+00111=0011100000+01101=0110101010+10011=1100101010+11001=1001101010+10100=1111001010+11110=1010001010+00111=0110101010+01101=0011110011+11001=0101010011+10100=0011110011+11110=0110110011+00111=1010010011+01101=1111011001+10100=0110111001+11110=0011111001+00111=1111011001+01101=1010010100+11110=0101010100+00111=1001110100+01101=1100111110+00111=1100111110+01101=1001100111+01101=01010满足第一条性质2、全零码字总是一个码字{00000，01010，10011，11001，10100，11110，00111，01101}满足第二条性质 1、一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量，即d*=w*D(00000，01010)=2D(00000，10011)=3D(00000，11001)=3D(00000，10100)=2D(00000，11110)=4D(00000，00111)=3D(00000，01101)=3D(01010，10011)=3D(01010，11001)=2D(01010，10100)=4D(01010，11110)=2D(01010，00111)=3D(01010，01101)=3{00000，01010，10011，11001，10100，11110，00111，01101}D(10011，11001)=2D(10011，10100)=3D(10011，11110)=3D(10011，00111)=2D(10011，01101)=4D(11001，10100)=3D(11001，11110)=3D(11001，00111)=4D(11001，01101)=2D(10100，11110)=2D(10100，00111)=3D(10100，01101)=3D(11110，00111)=3D(11110，01101)=3D(00111，01101)=2这个码的最小距离为2等于该码的最小重量满足第三条性质所以，这个码是线性码。3.4 构造C={00000，10101，01010，11111}的生成矩阵。因为这个G不是唯一的，给出另一个能生成这个码字集合的生成矩阵。解：设生成矩阵是G=，由题知，m=2,n=5,c=iGi=(0,0)(0,1),(1,0),(1,1)生成矩阵G=3.7对下列每一个集合S，列出扩张码:（1）S={0101，1010，1100}（2）S={1000，0100，0010，0001}（3）S={11000，01111，11110，01010}解:(1)0101+1010=1111，0101+1100=10011010+1100=0110，0101+1010+1100=0011再补上0000及原先3个公共组成第二，三问步骤省略为{1111，1001，0110，0011，0000，0101，1010，1100}(2)为{1100，1010，1001，0110，0101，0011，1110，1011，0111，1101，1111，0000，1000，0100，0010，0001}(3)为{10111，00110，10010，10001，00101，10100，01001，11000，01111，11110，01010，00000，11011，01100，11101} 3.8考虑（23，12，7）二元码。证明若它被用在一个比特错误概率为p=0.01的二元对称信道（BSC）中，字错误概率将约为0.00008解：由题可得其转移概率p=0.01，在(23.12.7)二元码中其可以纠出2t+1>=7t=3位错误即在码元中出现4个错才会使得其出现误码率，出现3个以上错误的概率为则出现的误字率为0.00008所以得证。3.9假设是一个二元码，它的奇偶校验矩阵为。证明由通过添加整体奇偶校验比特得到的扩展码的奇偶校验矩阵为.证明：根据题意，扩展码为:,又得奇偶校验矩阵为，。 ，即扩展码的奇偶校验矩阵为。证毕。3.11设C是长度为n,最小距离为7的二元完备码。证明n=7或n=23。证明：由完备码的定义可知，一个完备码必须满足下列条件：(1)由题意可知：，其中即有：当n=7时，由（1）式可得，右式展开得：同理，可证得n=23时，同样满足（1）式。故可证明当n=7或n=23时，C是二元完备码。 3.12用来表示二元汉明码的码率，求。解：根据二元汉明码的性质可知：其中m是任意正整数。则由码率的定义可知：则有： 第4章循环码4.1下面的哪个码是（a）循环码，（b）与一个循环码等价？（1）上的。（2）上的。（3）上的。（4）上的。（5）长度为的-元重复码。解：由书中定义4.1可知，循环码需要满足两个条件，（1）首先它必须是一个线性码，（2）其次它的一个码字的任意循环移位的结果还是一个码字，即若为其中的一个码字，则也是其中一个码字。下面一一证明：（1）首先证明是一个线性码：设，则，，，，，，，，，，，，，，显然不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。（2）首先证明是一个线性码：设，则，，，，，，，，， 满足线性码的第一个条件，显然第二个条件也满足。中的最小距离，最小重量，即，也满足第三个条件，可知是一个线性码。下面证明是循环的，，经过循环移位之后得到的码字是，这个码字不是中的码字，即不满足循环码的第二个条件。综上可知，不是一个循环码，但是它与一个循环码等价。（3）首先证明是一个线性码：设，则，，，，，，，，，显然不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。（4）首先证明是一个线性码：设，则，，，，，满足线性码的第一个条件，显然第二个条件也满足。中的最小距离，最小重量，即，也满足第三个条件，可知是一个线性码。下面证明是循环的，，经过循环移位之后得到的码字是，这个码字不是中的码字，即不满足循环码的第二个条件。综上可知，不是一个循环码，但是它与一个循环码等价。（5）长度为的-元重复码，假设，，则，可知其不为线性码，也定不为循环码。4.2为下列定义的多项式环构造加法和乘法表 +01xX+1001xX+11101+xxxxX+101X+1X+1x10乘法表如下：.01xX+100000101xX+1x0x1X+1X+10X+1X+10(2)加法表如下：+012xX+1X+22x2x+12x+20012xX+1X+22x2x+12x+211201+x2+xx2x+12x+22x2201X+2xX+12x+22x2x+1xxX+1X+22x2x+12x+2012X+1X+1X+2x2x+12x+22x120X+2X+2xX+12x+22x2x+12012x2x2x+12x+2012xX+1X+2 2x+12x+12x+22x120X+1X+2x2x+22x+22x2x+1201X+2xX+1乘法表如下：.012xX+1X+22x2x+12x+200000000001012xX+1X+22x2x+12x+220212x2x+22x+1xX+2x+1x0x2x2X+22x+21X+12x+1X+10X+12x+2X+22x12x+12xX+20X+22x+12x+21xX+12x22x02xx12x+1X+122x+2x+22x+12x+2002x+12x+2X+2X+1X+12x+12x2x22x+2X+2X112x4.4找出所有分组长度为5的二元循环码，求出每个码的最小距离。解：要找到分组长度为5的所有2元循环码，首先要分解=在GF（2）中，是既约的，所求的循环码为：定义在R5中的多项式=24=16个，信息多6yj多项式在下表中列出：000000，00000000011，00011，111010010，00110，111110011，00110，10001 010001010010101111011001010011101001100011000100111011101011110101110101110010100110110111111011000111110001故不同的码字有：码字最小码距000000000112001102111014111110100012101012011114010012110002110114111014101002101114 1111044.7设多项式为GF(2)上分组长度为15的一个循环码的生成多项式。(1)求生成矩阵G.。(2)求奇偶校验矩阵H。(3)这个码能检测多少个错误？(4)这个码能纠多少个错误？(5)将生成矩阵写成系统型。解：(1)由生成多项式可知：生成矩阵为：(2)由于已知分组长度为15，设奇偶校验多项式为h(x),则有：即：其中，上式为取模运算。故，对应的奇偶校验矩阵为： (3)建立如下表格：ii(x)c(x)=i(x)g(x)c00o0000000000000000011g(x)00001010011011110xxg(x)00010100110111011x+1(x+1)g(x)000111110100101由该表格可以看出，该码的最小距离为7。即：故可知，该码可以检测个错误。(4)由于，则有：即：故该码可以纠3个错误。(5)该生成矩阵的系统型为：4.11生成多项式为的码在中作检错和纠错标准。（1）这个码能纠多少个随机错误？（2）这个码能纠多少个突发错误？解：又经过尝试我们得到分组长度是满足且能整除的最小整数, 可以纠的突发错误最多为t=12个；能纠的随机错误为x=5个。第5章BCH码5.1用一个合适的本原多项式由构造。解：考虑由子域构造扩域，已知，，现在对 进行分解，即在上分解，下面考虑扩域上的元素，这些元素可以表示为：通过观察上的元素，我们可以选择作为本原多项式来构造。考虑上的元素，并不是上的本原元，则我们可以假设上的本原元为，则可以通过的幂模得到上的所有元素。经过多项式的运算可以得到中的元素：5.2找出分组长度为26的纠三个错误的三元BCH码的生成多项式g(x) Z的幂GF(27)的元素Z1zZ2Z2Z3Z+2Z4Z2+2zZ52z2+2z+1Z6Z2+z+1Z72Z82z2+2Z91Z10Z2+zZ11Z2+z+2Z122z2+z+2Z132Z142zZ152z2+1Z16Z+2Z17Z2+1Z18Z2Z19Z+2Z202z2+z+1Z21Z+1Z22Z2Z23Z24Z25 5.4求下列码的生成多项式和最小距离：(1)RS(15,11)码。(2)RS(15,7)码。(3)RS(31,21)码。解：(1)由RS(15,11)码可知，n=15,k=11。则根据RS码的性质可知，n-k=2t即：2t=15-11=4一个RS码的生成多项式可以写成：故该RS(15,11)码的生成多项式为：我们这里用到扩域GF(16)上的元素，该扩域是由GF(2)以本原多项式构造的(书上例5.7)。则有：该RS(15,11)码的最小距离为：(2)由RS(15,7)码可知，n=15,k=7。根据RS码的性质：n-k=2t即：2t=15-7=8根据(1)题所涉及的性质可知，RS(15,7)码的生成多项式为： 该RS(15,7)码的最小距离为：(3)RS（31，21）码中，t=5，115.6考虑上具有下列奇偶校验矩阵的码(1)证明该码纠三个错误的码。（2）求该码的生成多项式证明：又因为在中，矩阵中元素所以经过计算，中满足和为零的行向量的最小个数为7，，所以这个码能纠个错。证毕。第6章卷积码 6.2设计一个（12，4）系统卷积编码器使其约束长度且。（1）构造该编码器的网格图。（2）该码的是什么？解：（1）由题意可知，，，且约束长度为可以得到，，通过这些参量我们可以设计出编码器，如下图所示：编码输出输入移位寄存器这个编码器每次把1比特输入编码成3比特的输出。信息帧的长度为，码字帧的长度为，分组长度为12，该编码器的约束长度为，码率为。编码器的状态图：（只有四种状态） 0000111101111000卷积编码器输入和输出的比特如下表所示输入比特编码器当前状态编码器之后状态输出比特0000000000100010010101000100101100110111001000111010101010110110011100111011100100010001011001100000010101011111011100100011001011101110111001110110011111111100编码器的网格图为： 0010011100000000000010110110110101001001011111111111011001101110010000100100002121，，，因为，6.3考虑下图所示的二元编码器（1）构造该编码器的网格图（2）记下该编码器的（1）输入当前状态下一个状态输出000000000000100001000001010000100001110001100000001000010011101001010111011000110111111001110110000100001010100101001011010100101011110101101010001100011100101101011101011100111101111101111100 （1）由图可得（2）6.4考虑图6-36所示的二元编码器。i3i2i1++++++c1c2c3c4图6-36(1)写出该编码器的k,n,v,m及R的值。(2)给出该编码器的生成多项式矩阵G(D)。(3)给出该编码器的生成矩阵G。(4)给出该编码器的奇偶校验矩阵H。(5)该编码的d*、dfree和nfree的值各是多少？(6)该编码器在dfree的Heller界上是最优的吗？(7)用该编码器将下列比特序列进行编码：101001001010000。解：(1)由题意可知：m=4 由图6-36可知：k0=3,n0=4。则有：k=(m+1)k0=15,n=(m+1)n0=20由约束长度公式可得：v=mk0=12由码率公式可得：R=k0/n0=0.85(2)该编码器的生成多项式矩阵为：(3)由图可知：故该编码器的生成矩阵G为;将5个矩阵代入矩阵G中既可。(4)将5个矩阵进行变换得： 其中，I为k0*k0阶单位矩阵，即3*3阶单位矩阵。P1,P2,P3,P4为k0*(n0-k0)阶矩阵，即3*(4-3),也就是3*1阶矩阵。于是，该编码器的奇偶校验矩阵可写为：其中分别为P1,P2,P3,P4的转置。0为k0*k0阶矩阵，即3*3阶矩阵。 第7章网格编码调制7.1考虑由下列定义的码率为的卷积码：这个码用到格雷编码（每个符号被赋值3比特，这样一来两个相连符号的码只在一个比特位不同）的8-PSK信号集。该TCM方案的吞吐量为2bit/s/Hz。（1）在该编码器的网格图中有多少状态？（2）求自由欧几里得距离（3）关于吞吐量为2bit/s/Hz的无编码的QPSK，求渐近编码增益。解：由此多项式矩阵，可以构造编码器，TCM方案如下：自然映射：，，，，，，，输入比特编码器当前状态编码器之后的状态输出000000000010001110100010111 110011010000100100010101111100110011110111000001000000011001000101010100111011111001100100011101111101110100111111011（1）在该编码器的网格图中有4个状态。（2）自由欧几里得距离：（3）渐近编码增益：由书中P158（7-2）式得到， 第8章密码学8.1我们想要测试加密技术字符+x的安全性，其中每个明文字符移动x个位置来产生密文。（1）假设用强力攻击，需要试验多少次才能破译这个码？（2）假设一个计算机需要1ms来测试一个移位，那么要破译这个码需要多长时间？解：（1）每个字符最多需要25次就能破译，若明文有个字符，则需要试验次才能破译这个码。（2）每个字符最多需要来破译这个码，若明文有个字符，则需要测试才能破译这个码。8.2假设N个人及组想用保密密钥密码。组中的每两个人应该能够秘密通信。需要多少不同的密钥？答：共需要个不同的密钥。8.6(1)用素数29和61生成RSA算法的密钥。(2)将字母“RSA”用ASCⅡ码表示，然后用上述生成的密钥将它们加密。(3)接下来用素数对37和67生成密钥。步骤(1)还是步骤(3)中的密钥更安全？为什么?解：(1)第一个素数(A)=29第二个素数(B)=61则：N=29*61=1769T=(29-1)*(61-1)=1680 E与1680必须除1之外没有其他公共因子。E(公钥)可以为9。D(私钥)=9-1mod1680=373(2)字母“RSA”用ASCⅡ码表示为：82，83，65“R”用82表示：则有M=82C(密文)=829mod1769=1472“S”用83表示：则有M=83C(密文)=839mod1769=1120“A”用65表示：则有M=65C(密文)=659mod1769=1064(3)第一个素数(A)=37第二个素数(B)=67则：N=37*67=2479T=(37-1)*(67-1)=2376E与2376必须除1之外没有其他公共因子。E(公钥)可以为5。D(私钥)=5-1mod2376=950综上可以看出：步骤(1)与步骤(3)的密钥相比，步骤(3)更安全。因为密钥越大，就越难被破解，安全性也就越高。'