信息论、编码与密码学课后复习题答案

第1章 信源编码

1.1

考虑一个信源概率为{0.30，0.25，0.20，0.15，0.10}的DMS。求信源熵H（X）。

解： 信源熵 H(X)pklog2(pk)

k15

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.4+0.411+0.332] =2.228(bit)

故得其信源熵H(X)为2.228bit

1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解： 若二元离散信源的统计特性为

P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值，由dH(X)/d(P)=0可得

plog01pp11p1p2可知当概率P=Q=1/2时，有信源熵H(X)max

对于三元离散信源，当概率

1(bit)

时，信源熵

P1P2P31/3H(X)max1.585(bit)，

此结论可以推广到N元的离散信源。

1.3 证明不等式lnxx1。画出曲线y1lnx和y2x1的平面图以表明上述不

等式的正确性。 证明：

f(x)lnxx1(x0)1f(x)x令f(x)0，x1又有x00x1时f(x)0此时f(x)fmax0也即lnxx1当x1时同理可得此时lnxx1综上可得lnxx1证毕

绘制图形说明如下 可以很明确说明上述 不等式的正确性。

1.4 证明I(X;Y)0。在什么条件下等号成立？

Y=lnx 1 x y Y=x-1 （IX；Y）=P(xi,yj)I(xi,yj)i1j1nmP(xi,yj)logi1j1nmP(xi,yj)P(xi)P(yj)

当和相互时等号成立。

1.5 有一个信源X，它有无穷多个可能的输出，它们出现的概率为P（Xi）=2i-1,i=1,2,3,….,这个信源的平均自信息H（X）是什么？

解：因为 P（Xi）=2i-1,i=1,2,3,…

所以 H（X）= -p(xi)logp(xi)

i1n

=-log2(2+2.22+3.23+…..+n.2n) =2-（1-n）2n+1

i-1

1.6 考虑另一个几何分布的随机变量X，满足P（Xi）=P（1-P）i=1,2,3,…..,

这个信源的 平均自信息H（X）是什么？

解：因为 P（Xi）= P（1-P）i-1,i=1,2,3,

所以H（X）= -p(xi)logp(xi)

i1n

=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+…….+np(1-p)n]

(p1)2=(1-n)(1-p)- pn+1

1.7 考虑一个只取整数值的随机变量X，满足PXn1，n2,3,...,。求熵HX。 2n2nlogn1，其中

Anlog2nA

解：为了方便计算，设Bnlogn，则A211，PXn； BABn21根据公式计算自信息量为：IXlogPXlogAB；

1logBB1logAB则熵为：HXPXIXlogABn2=？

1ABn2n2ABn2n2Bn2B1.8 计算概率分布函数为

a10xapx

0否则的均匀分布随机变量X的微分熵HX。画出HX相对于参数a0.1a10的平面图，并对结果进行评论。

解：根据公式（1-21）可知，微分熵为：HXpxlogpxdx

当0xa时，pxa1，则

HXa1loga1dx0a1logaalogax0aloga aa当x0或xa时，px0 ，则HX

根据得到的结果可以画出相应的平面图，由图可以看到随着a的增加，即px的减小，微分熵HX相应的增加。

HX

0.1 0 10 a

1.9考虑一个信源的概率为0.35,0.25,0.20,0.15,0.05的DMS。 （1）给出此信源的霍夫曼码。 （2）计算出这些码子的平均码长R。 （3）这个码的效率是多少？

解：1）依题意，由霍夫曼编码的规则，得：

1 1.00 x1 0.35 x3 0.20 1 0.65 0.40 0

0 x2 0.25 0 0.20 1 1 0 x4 0.15 x5 0.05

表格如下：

符号

概率 0.35 0.25 0.20 0.15 0.05

自信息 1.515 2.000 2.322 2.738 4.322

码字 1 01 000 0010 0011

x1 x2

x3 x4

x5

2）由平均码长公式 Rn(xk1nk)p(xk),代入数据，得：

Rn(xk15k)p(xk)1(0.35)2(0.25)3(0.20)4(0.15)5(0.05)0.350.50.60.60.252.3(bit)3）首先，该信源的熵为：

H(X)pklog2pk(0.35log20.350.25log20.25k150.20log20.200.15log20.150.05log20.05)(0.351.5150.252.00.202.3220.152.7380.054.322)(0.53030.50.440.41070.2161)(2.1215)2.1215 (bit) 该码的效率为：

H(X)(2.1215/2.300)0.9224

R

1.10考虑一个信源概率为{0.35，0.20，0.15，0.15，0.10，0.10，0.05，0.05}的DMS。

(1)给出此信源的一种有效定长码。 (2)给出此信源的霍夫曼码。 (3)比较这两种码并给出评论。 解：1）空

2）依题意，由霍夫曼编码的规则，得:

x1 0.20x2 0.2010.55x3 0.15x4 0.15x5 0.10x6 0.10x7 0.05010.35 01.00 00.25010001概率 0.20 0.20 0.15 0.15 0.10 0.10 0.05 0.05

自信息 2.322 2.322 2.738 2.738 1.000 1.000 4.322 4.322

码字 01 000 001 100 101 110 1110 1111

0.45 10.20 1x8 0.05符号

0.10 1 x1 x2

x3

x4

x5 x6 x7 x8

3）空

1.11 一个DMS只有三个输出符号，它们的概率为{0.5，0.4，0.1}。 (1)给出此信源的霍夫曼码并确定编码效率。

(2)每次考虑两个符号时，给出此信源的霍夫曼码并确定编码效率。

(3)每次考虑三个符号时，给出此信源的霍夫曼码并确定编码效率。 解：

(1)本题的霍夫曼编码如下图所示：

0.5 0.4 0.1

0 1

1

1.0

0.5 0

图1.11 霍夫曼编码

则霍夫曼码如下表：

符号 x1 x2 x3

该信源的熵为：

概率 0.5 0.4 0.1 码字 1 00 01 H(X)pklog2pkk13(0.5log20.50.4log20.40.1log20.1) 0.50000.52880.33221.3610(bit)平均每个符号的比特数为：

Rn(xk)p(xk)k131(0.5)2(0.4)2(0.1) 0.50.80.21.5000(bit/符号)该码的效率为：

1.3160/1.50000.9073

（2）把符号每两个分一组，重新应用霍夫曼编码算法，如下表所示：

符号对 x1x1 x1x2 x2x1 x2x2 x1x3 x3x1 x2x3 x3x2 x3x3 该信源的熵为：

概率 0.25 0.20 0.20 0.16 0.05 0.05 0.04 0.04 0.01 码字 00 010 011 1010 100 110 1011 1110 1111 2H(X)pklog2pk2.7219(bit)k19

H(X)1.3610(bit)每个组的平均比特数为:

9RBn(xk)P(xk)k12(0.25)3(0.2)3(0.2)4(0.16)3(0.05)3(0.05)4(0.04)4(0.04)4(0.01)3.00(bit/符号对)

R3.00/21.5000(bit/符号)

故该码的效率为：

1.3160/1.50000.9073

(3)依题意，把符合每三个分成一组，再重新应用霍夫曼编码算法，得:

x1x1x1 0.1250x1x1x2 0.10000010.2000 0x1x2x1 0.1000x2x1x1 0.1000x1x2x2 0.0800x2x1x2 0.0800x2x2x1 0.0800x2x2x2 0.00x1x1x3 0.0250010.2400 1010.1600 00.1850 010.0500 110.5800 0x1x3x1 0.0250x3x1x1 0.02500.3400 101.0000 010.0450 00.1400 0.0850 1x1x2x3 0.0200x1x3x2 0.02000.4200 100.0400 1x2x1x3 0.0200x2x3x1 0.0200x3x1x2 0.0200x3x2x1 0.0200x2x2x3 0.0160x2x3x2 0.0160xxx 0.0160100.2350 00.0400 0100.0760 0.1100 0.0360 1110.0320 010

编码表格如下：

符号对

概率 0.1250 0.1000 0.1000 0.1000 0.0800

自信息 2.7090 3.3223 3.3223 3.3223 3.43

码字 100 0000 0001 110 011

x1x1x1 x1x1x2 x1x2x1 x2x1x1 x1x2x2

符号对 概率 0.0800 0.0800 0.00 0.0250 0.0250 0.0250 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0160 0.0160 0.0160 0.0050 0.0050 0.0050 0.0040 0.0040 0.0040

自信息 3.43 3.43 3.9662 5.3223 5.3223 5.3223 5.44 5.44 5.44 5.44 5.44 5.44 5.96 5.96 5.96 7.66 7.66 7.66 7.9666 7.9666 7.9666

码字 0100 0101 0011 10110 10111 11100 11101 11110 11111 001000 001001 001010 001011 101000 101001 1010101 10101000 10101001 10101100 10101101 10101110

x2x1x2 x2x2x1 x2x2x2 x1x1x3 x1x3x1 x3x1x1 x1x2x3 x1x3x2 x2x1x3 x2x3x1 x3x1x2 x3x2x1 x2x2x3 x2x3x2 x3x2x2 x1x3x3 x3x1x3 x3x3x1 x2x3x3 x3x2x3 x3x3x2

符号对 概率 0.0010

自信息 9.9668

码字 10101111

x3x3x3

1.14

确

定

下

列比特流的Lempel-Ziv码：

01001111100101000001010101100110000从码字流恢复原来的序列。 解：根据Lempel-Ziv算法列出下表：

字典位置 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1101 1110 1111 字典内容 0 1 00 11 111 001 01 000 0010 10 101 100 110 000 定长码字 00000 00001 00010 00101 01001 00111 00011 00110 01100 00100 10101 10100 01000 10000

第2章 信道容量和编码

2.1 考虑图2-10所示的二元信道，设发送二元符号的先验概率为P0和P1，其中P0+ P1=1，求后验概率P(X0|Y1)和P(X1|Y1)。

1-p P0 0 0 q P1 1 1-q p 1

解：PX0p0 PX1p1

PY1X0p PY0X1q PY0X01p PY1X11q

PX0,Y0PX0PY0X0PY0PX0Y0

PX0Y0PX0PY0X0PY0p01p p01pp1qPY0PX0PY0X0PX1PY0X1

p01pp1q

PX1,Y1PX1PY1X1PY1PX1Y1

PX1Y1PX1PY1X1PY1p11q

p0pp11qPY1PX0PY1X0PX1PY1X1

p0pp11q

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个画面，每个画面大约有2105个像素，每个像素需要16比特的彩色显示。假定SNR为25dB， 计算支持电视信号传输所需要的带宽（利用信息容量定理）

解：根据题意，该电视信号所需的信息容量为：

C30210516bit/s9.6107bit/s

根据信息容量定理：CWlog2(1P25dB N0PP)，其中为信噪比，据题意

N0N0W

 据上式解得带宽C1.1510Hz

72.8 考虑图2-15所示的Z型信道。

（1）求获得信道容量所需要的输入概率。

（2）若将N个这样的信道相级联，证明联合信道可以用一个信道转移概率

为p

N的等价Z信道表示。

（3）当N时联合信道的容量是什么？

图2-15

解： (1) w为带宽

P) (b/s) 信道容量 CWlog2(1N0W

SCBlog2(1)

NP(0|1)P(1|0)P

(2) 由图可知信道转移概率为P

那么N级级联的信道转移概率

PP(0|1)(3)当NN级级联W

时 P(0|1)

级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在所有可能的输入概率上求得的即：

CmaxI(x;y)

p(xj)CmaxP(xj)P(yi|xj)logp(xj)j0i0q1r1P(yi|xj)P(yi)

2.10 (1)证明对有限方差2，高斯随机变量具有所有随机变量可能获得的最大

微分熵。

(2)证明该熵由公式1/2log2(2e2)给出。 证明：

(1)由题意可知，高斯随机变量获得的微分熵为：

1H(X)log2(2e2)

2则有：

2即其平均功率为：

12e12ee2H(X)

22

e2H(X)

对于有限方差的高斯随机变量，即当平均功率受限时，有：

即有：

p(x)dx1,(xm)2p(x)dx2.

H(X)log22e

综上可得，对于平均功率受限的连续随机变量，当服从高斯分布时具有最大微分熵。

(2)随机变量的微分熵为：

H(X)p(x)log2p(x)dx (1)

对于高斯分布，我们有：

p(x)其中，m为数学期望。

11exp{2(xm)2} (2)

22 将(2)式代入(1)可得：

H(X)p(x)[ln112(xm)2]dx (3) 22由(3)式可以推出：

1H(X)log2(2e2) (4)

2故(4) 式即为本题所证。

2.11

写一个程序，它在输入信道转移矩阵后计算出信道容量？解：依据设定情况在一般的二元通信信道输入前只有两种状态，0和1，假设传输发生错误概率为p,正确概率为1-p.这只是假定的一种情况，其实在程序中可看作这几个参量为个数组。CP[]及WP[]。再根据计算信道容量公式q1r1p(yi|xj)maxp(xj)p(yi|xj)log,输出对应的信道容量值。

p(xj)j0i0

p(yi)第3章 纠错控制编码

3.1 证明C0000,1100,0011,1111是一个线性码。它的最小距离是什么？ 证明：由书中的定义3.8可知，线性码应该满足一下条件： （1） 两个属于该码的码字的和仍然是一个属于该码的码字， （2） 全零字总是一个码字，

（3） 两个码字之间的最小距离等于任何非零码字的最小重量，即dw 设Cc1,c2,c3,c4，即c10000，c21100，c30011，c41111， 首先证明条件（1）：

c1c21100c2，c1c30011c3，c1c41111c4，c2c31111c4，c2c40011c3，c3c41100c2，

很明显，条件（1）是满足的。条件（2）也是显然成立的。 最后证明条件（3）：

不难看出最小距离d2，并且最小重量w2，即dw

综上，三个条件都满足，那么C就是一个线性码，它的最小距离是2。

3.3 考虑GF（2）上的下列生成矩阵

10100G10011

010103）用此矩阵生成所有可能的码字。 4）求奇偶校验矩阵H。

5）求与其等价的一个系统码的生成矩阵。 6）构造该码的标准阵列。 7）这个码的最小距离是多少。 8）这个码能检测多少错误。

9）写出这个码能检测的所有错误模式。

10）这个码能纠多少个错误。

11）如果我们用此编码方案，那么符号错误概率是多少？将它与末尾的错误概率进行比较。

12）这是一个线性码？

10100解：（1）c100010011=00000

0101010100 c200110011=01010

0101010100 c301010011=10011

0101010100 c401110011=11001

0101010100 c510010011=10100

0101010100 c610110011=11110

0101010100 c711010011=00111

0101010100 c811110011=01101

01010 此矩阵生成的码为：{00000，01010，10011，11001，10100，11110，00111，01101}

1010010011（2）G1001101010

01010001-1-111111T P10 P101又在二元情况下，11

11111 PT101

奇偶校验矩阵可写为：HPTI

11110 10101

 (4该码的标准阵列

10011 G01010

001-1-1（5）奇偶校验矩阵H的第1、3列的和为零向量， 因此，这个码的最小距离为：d*=2。

（6）一个码至少可以检测所有重量小于或等于（d*-1）的非零错误模式。 这个码的最小距离为：d*=2 ，所以重量为1的错误模式可以检测得到。 （7）这个码能检测的所有错误模式

{00001，00010，00100，01000，10000} （8）能纠正不多于t个错误应满足d*2t1 又d*=2 所以22t1 即t1 2 这个码能纠0个错误 （9）才vv

（10）{00000，01010，10011，11001，10100，11110，00111，01101}

线性码的性质：

1、两个属于该码的码字的和仍是属于该码的码字

00000+01010=01010

00000+11001=11001

00000+10011=10011 00000+10100=10100 00000+11110=11110 00000+00111=00111 00000+01101=01101

01010+10011=11001 01010+11001=10011 01010+10100=11110 01010+11110=10100 01010+00111=01101 01010+01101=00111

10011+11001=01010 10011+10100=00111 10011+11110=01101 10011+00111=10100 10011+01101=11110

11001+10100=01101 11001+11110=00111 11001+00111=11110 11001+01101=10100

10100+11110=01010 10100+00111=10011 10100+01101=11001

11110+00111=11001 11110+01101=10011

00111+01101=01010 满足第一条性质

2、全零码字总是一个码字

{00000，01010，10011，11001，10100，11110，00111，01101} 满足第二条性质

3、一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量， 即d*=w*

D(00000，01010)=2 D(00000，10011)=3 D(00000，11001)=3

D(00000，11110)=4

D(00000，10100)=2 D(00000，00111)=3

D(00000，01101)=3

D(01010，10011)=3

D(01010，11001)=2

D(01010，10100)=4 D(01010，11110)=2 D(01010，00111)=3 D(01010，01101)=3

{00000，01010，10011，11001，10100，11110，00111，01101} D(10011，11001)=2 D(10011，10100)=3 D(10011，11110)=3 D(10011，01101)=4

D(11001，10100)=3

D(11001，11110)=3 D(10011，00111)=2

D(11001，00111)=4 D(11001，01101)=2

D(10100，11110)=2 D(10100，00111)=3 D(10100，01101)=3

D(11110，00111)=3

D(00111，01101)=2

这个码的最小距离为2等于该码的最小重量 满足第三条性质

所以，这个码是线性码。

3.4 构造C={00000，10101，01010，11111}的生成矩阵。因为这个G不是唯一

D(11110，01101)=3

的，给出另一个能生成这个码字集合的生成矩阵。

a11K解：设生成矩阵是G=MOa1nM，由题知，m=2,n=5, amnam1LQ c=i•G i=(0,0) (0,1),(1,0),(1,1)

01010生成矩阵G=

10101

3.7 对下列每一个集合S，列出扩张码: 解:

(1) 0101+1010=1111 ， 0101+1100=1001

1010+1100=0110 ， 0101+1010+1100=0011 （1）S={0101，1010，1100} （2）S={1000，0100，0010，0001} （3）S={11000，01111，11110，01010}

再补上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>=7 t=3位错误

即在码元中出现4个错才会使得其出现误码率，出现3个以上错误的概率为

nn23nnnCp(1p)C2323pn4n423231CpqCpqCpqCpq0.00008则出现的误字率为0.00008 所以得证。

023023112223223221323320

3.9 假设C是一个二元码，它的奇偶校验矩阵为H。证明由C通过添加整体奇偶校验比特得到的扩展码C1的奇偶校验矩阵为

H1H11K|0|0. |M|01|1证明：根据题意，扩展码C1为:

C1C11K|0|0,又QC得奇偶校验矩阵为H，CHT0。 |M|01|0QTTH1H00K|1|1， |M|10|1TC1H1C11K|0|0|MHT|01|000|1|1CHT|M|100|10000 M000KL即扩展码C1的奇偶校验矩阵为H1。 证毕。

3.11设C是长度为n,最小距离为7的二元完备码。证明n=7或n=23。 证明：由完备码的定义可知，一个完备码必须满足下列条件：

2nkiCn (1) i0t由题意可知：d*2t1，其中d*7 即有：t3

当n=7时，由（1）式可得，

271Ci03i7

右式展开得：

i0123CCCCC77777i03172135左式

同理，可证得n=23时，同样满足（1）式。 故可证明当n=7或n=23时，C是二元完备码。

3.12 用rH来表示二元汉明码的码率，求limrH。

k解：根据二元汉明码的性质可知：

其中m是任意正整数。 则由码率的定义可知：

则有：

(n,k)=(2m-1,2m-1-m)

rk2m-1-mHn2m-1 limkr2m-1-mHlimk2m-11 第4章 循环码

4.1 下面的哪个码是（a）循环码，（b）与一个循环码等价？ （1）GF2上的0000,0110,1100,0011,1001。 （2）GF2上的00000,10110,01101,11011。 （3）GF3上的00000,10110,01101,11011。 （4）GF3上的0000,1122,2211。 （5）长度为n的q-元重复码。

解：由书中定义4.1可知，循环码需要满足两个条件， （1） 首先它必须是一个线性码，

（2） 其次它的一个码字的任意循环移位的结果还是一个码字，即若

a0,a1,...,an1为其中的一个码字，则an1,a0,...,an2也是其中一个码字。

下面一一证明：

（1）首先证明C1是一个线性码：设C1c1,c2,c3,c4,c5，则

c10000，c20110，c31100，c40011，c51001，

c1c20110c2，c1c31100c3，c1c40011c4，c1c51001c5，c2c31010? ，c2c40101?，c2c51111?，c3c41111?，c3c50101?，c4c51010?

显然C1不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。

（2）首先证明C2是一个线性码：设C2c1,c2,c3,c4，则

c100000，c210110，c301101，c411011，

c1c210110c2，c1c301101c3，c1c411011c4，c2c311011c4，c2c401101c3，c3c410110c2

C2满足线性码的第一个条件，显然第二个条件也满足。C2中的最小距离d3，

最小重量w3，即dw3，C2也满足第三个条件，可知C2是一个线性码。

01011，下面证明C2是循环的，c210110，经过循环移位之后得到的码字是c2这个码字不是C2中的码字，即C2不满足循环码的第二个条件。 综上可知，C2不是一个循环码，但是它与一个循环码等价。 （3）首先证明C3是一个线性码：设C3c1,c2,c3,c4，则

c100000，c210110，c301101，c411011，

c1c210110c2，c1c301101c3，c1c411011c4，c2c311211?，

c2c421121?，c3c412112?

显然C3不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。

（4）首先证明C4是一个线性码：设C4c1,c2,c3，则

c10000，c21122，c32211，

c1c21122c2，c1c32211c3，c2c30000c1

C4满足线性码的第一个条件，显然第二个条件也满足。C4中的最小距离d4，

最小重量w4，即dw4，C4也满足第三个条件，可知C4是一个线性码。

2112，下面证明C4是循环的，c21122，经过循环移位之后得到的码字是c2这个码字不是C4中的码字，即C4不满足循环码的第二个条件。 综上可知，C4不是一个循环码，但是它与一个循环码等价。 （5）长度为n的q-元重复码，

111111111，可知其不为线性码，也定不为循环码。 假设n3，q2，则

4.2 为下列定义的多项式环构造加法和乘法表

F（x）x21F（x）(2)定义在GF（3）上的2x1

解：(1)首先判断得环的多项式的最高次数=1，环中有四个元素，(1)定义在GF（2）上的分别为0,1,x,x+1. 所得加法表如下：+ 0 0 0 1 1 x x X+1 X+1

乘法表如下：

. 0 0 0 1 0 x 0 X+1 0

(2)加法表如下：+ 0 0 0 1 1 2 2 x x X+1 X+1 X+2 X+2 2x

2x

1 1 0 X+1 x

1 0 1 x X+1

1 1 2 0 X+1 X+2 x 2x+1

x X+1 x X+1 1+x x 0 1 1

0

x X+1 0 0 x X+1 1 X+1 X+1

0

2 x X+1 2 x X+1 0 1+x 2+x 1 X+2 x X+2 2x 2x+1 x 2x+1 2x+2 X+1 2x+2 2x 2x+2

0

1

X+2 2x X+2 2x x 2x+1 X+1 2x+2 2x+2 0 2x 1 2x+1 2 2

x

2x+1 2x+2 2x+1 2x+2 2x+2 2x 2x 2x+1 1 2 2 0 0 1 X+1

X+2

2x+1 2x+2

2x+1 2x+2

2x+2 2x

2x 2x+1

1 2

2 0

0 1

X+1 X+2

X+2 x

x X+1

乘法表如下： . 0 1 2 x X+1 X+2 2x 2x+1 2x+2 0 0 0 0 0 0 0 0 0 0 1 0 1 2 x X+1 X+2 2x 2x+1 2x+2 2 0 2 1 2x 2x+2 2x+1 x X+2 x+1 x 0 x 2x 2 X+2 2x+2 1 X+1 2x+1 X+1 0 X+1 2x+2 X+2 2x 1 2x+1 2 x X+2 0 X+2 2x+1 2x+2 1 x X+1 2x 2 2x 0 2x x 1 2x+1 X+1 2 2x+2 x+2 2x+1 0 2x+1 X+2 X+1 2 2x 2x+2 X 1 2x+2 0

2x+2

X+1

2x+1

x

2

X+2

1 2x

4.4 找出所有分组长度为5的二元循环码，求出每个码的最小距离。

解：要找到分组长度为5的所有2元循环码，首先要分解x51

x51=(x1)(x4x3x2x1)

在GF（2）中，是(x4x3x2x1)既约的，所求的循环码为：c(x)i(x)gg(x) 定义在R5中的多项式i(x)=24=16个，信息多6yj多项式在下表中列出：

i i(x) c(x) c 0000 0 0，0 00000 0001 1 x1，x4x3x2x 00011，11101 0010 x x2x，x4x3x2x 00110，11111 0011 x1 x2x，x5x 00110，10001 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

故不同的码字有：

x2 x3x x3x2x1 x3x x31 x4x3 x4x3x1 x4x3x2x x4x3x21 x4x2 x4x2x1 x4x3 01010 01111 01010 01001 11000 11011 11110 10101 10100 10111 11000 10001 x21 x2x x2x1 x3 x31 x3x x3x1 x3x2 x3x21 x3x2x x4x3x21 x41 码字 00000 00011 00110 11101 11111 10001 10101 01111 01001 11000 11011 11101 10100 10111 最小码距 0 2 2 4 0 2 2 4 2 2 4 4 2 4 11110 4

4.7 设多项式

g(x)x10x8x5x4x2x1

为GF(2)上分组长度为15的一个循环码的生成多项式。 (1)求生成矩阵G.。 (2)求奇偶校验矩阵H。 (3)这个码能检测多少个错误？ (4)这个码能纠多少个错误？

(5)将生成矩阵写成系统型。 解：

(1)由生成多项式g(x)x10x8x5x4x2x1可知： 生成矩阵为：

111011001010001110110010100G0001110110010100001110110010100001110110010(2)由于已知分组长度为15，设奇偶校验多项式为h(x),则有：x151g(x)h(x)

即：

h(x)x151/(x10x8x5x4x2x1)x5x3x

其中，上式为取模运算。 故，对应的奇偶校验矩阵为：

10101000000000101010000000H0010101000000…………………………………0000000001010000

01000000……101015

(3)建立如下表格：

i 00 01 10 11 i(x) o 1 x x+1 c(x)=i(x)g(x) 0 g(x) x g(x) (x+1) g(x) c 000000000000000 000010100110111 000101001101110 000111110100101 由该表格可以看出，该码的最小距离为7。 即：d*7

故可知，该码可以检测d*16个错误。 (4)由于d*7，则有：72t1 即：t3

故该码可以纠3个错误。 (5)该生成矩阵的系统型为：

10G[I|P]000

000000110101101000101010110001001101001110

00100110101111000111011001014.11 生成多项式为g(x)(x231)(x17x31)的码在GSM中作检错和纠错标准。

（1）这个码能纠多少个随机错误？ （2）这个码能纠多少个突发错误？

解：g(x)(x12211)(x17x31)x40x26x21x17x31 t12,nk40

又经过尝试我们得到分组长度是满足g(x)且能整除x231的最小整数

n75,

k754035 2xk35,x5

可以纠的突发错误最多为t=12个；能纠的随机错误为x=5个。

第5章BCH码

5.1 用一个合适的本原多项式由GF3构造GF9。解：考虑由子域构GF3造扩域GF9，已知q3，m2，现在对xqm1进行

分解，即在GF3上分解，

xq1x81x1x1x21x41

m下面考虑扩域GF9上的元素，这些元素可以表示为：

0z2z1z12z1 2z22z2通过观察GF9上的元素，我们可以选择pxx21作为本原多项式来构造

GF9。

考虑GF9上的元素，z并不是GF9上的本原元，则我们可以假设GF9上的本原元为z1，则可以通过的幂模p得到GF9上的所有元素。 经过多项式的运算可以得到GF9中的元素：

的幂 1z1

GF9上的元素

z1 2z

2z22z1 3z31

2z1 2

4z4z3z1

5z52z4z32z1 6z62z31

2z2

z

7z7z62z42z3z1

z2 1

8z82z7z62z5z42z3z22z1

5.2 找出分组长度为26的纠三个错误的三元BCH码的生成多项式g(x)

依据确定可纠t个错误的BCH码的生成多项式的步骤nqm1即3m126,m3.选取一个次数为3的素多项式并构造GF（27），令p(x)=x32x1

Z的幂 Z1 Z2 Z3 Z4 Z Z6 Z7 Z8 Z9 Z10 Z11 Z12 Z13 Z14 Z15 Z16 Z17 Z18 Z19 Z Z21 Z22 Z23 Z24 Z25 205GF(27)的元素 z Z2 Z+2 Z2+2z 2z+2z+1 Z2+z+1 2 2z2+2 1 Z2+z Z2+z+2 2z2+z+2 2 2z 2z2+1 Z+2 Z2+1 Z2 Z+2 2z+z+1 Z+1 Z2 22

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码的生成多项式可以写成：

g(x)(xi)(xi1)...(x2ti1)(x2ti)

故该RS(15,11)码的生成多项式为：

g(x)(x1)(x2)(x3)(x4)

我们这里用到扩域GF(16)上的元素，该扩域是由GF(2)以本原多项式

p(z)z4z1构造的(书上例5.7)。

则有：

g(x)(x1)(x2)(x3)(x4)x4(z3z21)x3(z3z2)x2z3x(z2z1) x4(13)x3(6)x2(3)x10该RS(15,11)码的最小距离为：

d*2t1415

(2)

由RS(15,7)码可知，n=15,k=7。 根据RS码的性质：n-k=2t 即：2t=15-7=8

根据(1)题所涉及的性质可知，RS(15,7)码的生成多项式为：

g(x)(x1)(x2)(x3)(x4)(x5)(x6)(x7)(x8)[x4(13)x3(6)x2(3)x10][x4(2)x3(14)x2x11]x8(8)x7(10)x6(2)x5(7)x4(14)x3(14)x2(9)x6该RS(15,7)码的最小距离为：

d*2t1819

(3) RS（31，21）码中，t=5，d*11

11125.6 考虑GF(11)上具有下列奇偶校验矩阵的码H1223121L3L32L33L110 210103(1)证明该码纠三个错误的码。 （2）求该码的生成多项式

1112T证明：H12231213LL32L33L1111T112222310133233

102MMMM103231101010又因为在GF(11)中，矩阵中元素

3327(mod11)5,43(mod11)9,53125(mod11)4,63216(mod11)773343(mod11)2,83512(mod11)6,93729(mod11)3,1031000(mod11)104216(mod11)5,5225(mod11)3,6236(mod11)3,7249(mod11)582(mod11)9,9281(mod11)4,102100(mod11)1所以经过计算，HT中满足和为零的行向量的最小个数为7，d2t1，所以这个码能纠t

d13个错。证毕。 2第6章 卷积码

6.2 设计一个（12，4）系统卷积编码器使其约束长度v3且d8。 （1）构造该编码器的网格图。 （2）该码的dfree是什么？

解：（1）由题意可知，n12，k4，且约束长度为vmk03 可以得到m3，k01，n03

通过这些参量我们可以设计出编码器，如下图所示：

移位寄存器 输入 编码输出

这个编码器每次把1比特输入编码成3比特的输出。信息帧的长度为k01，码字帧的长度为n03，分组长度为12，该编码器的约束长度为vmk03，码率为13。

编码器的状态图：（只有四种状态）

01 0 0 0 00 1 0 11 1 1 1 10

卷积编码器输入和输出的比特如下表所示

输入比特

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

编码器的网格图为：

编码器当前状态

000 000 100 100 010 010 110 110 001 001 101 101 011 011 111 111

编码器之后状态

000 100 010 110 001 101 011 111 000 100 010 110 001 101 011 111

输出比特 000 101 010 111 110 011 100 001 101 000 111 010 011 110 001 100

00 10 01 11 0 2 000 101 0 000 101 010 2 111 0 1 000 0 110 101 1 011 010 100 111 001 000 110 101 011 010 100 111 001

5，d4d12，d23，d36

因为m3，

6.3 考虑下图所示的二元编码器

（1）构造该编码器的网格图 （2）记下该编码器的k0,n0,v,m,R

（1）输入 当前状态 下一个状态 输出 0 0000 0000 000 1 0000 1000 001 0 1000 0100 001 1 1000 1100 000 0 0100 0010 011 1 0100 1010 111 0 1100 0110 111 1 1100 1110 110 0 0010 0001 010 1 0010 1001 011 0 1010 0101 011 1 1010 1101 010 0 0110 0011 100 1 0110 1011 101 0 1110 0111 101 1 1110 1111 100

（2）由图可得

k01,n03,v4,vmk0，得m4,Rk01n03

该码的d*和dfree的值是多少?（3）解：由状态表m3则m1级d*d1*d2*d3*d4*123410

dfreemax[dj*]8j6.4 考虑图6-36所示的二元编码器。

+ i1 + + i2 + c3 c2 + c1 i3 + c4

图6-36

(1)写出该编码器的k,n,v,m及R的值。 (2)给出该编码器的生成多项式矩阵G(D)。 (3)给出该编码器的生成矩阵G。 (4)给出该编码器的奇偶校验矩阵H。 (5)该编码的d*、dfree和nfree的值各是多少？ (6)该编码器在dfree的Heller界上是最优的吗？

(7)用该编码器将下列比特序列进行编码：101 001 001 010 000。 解： (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)

该编码器的生成多项式矩阵为：

g11(D)g12(D)g13(D)g14(D)G(D)g21(D)g22(D)g23(D)g24(D)g(D)g31(D)g32(D)g3334(D)

DD2D2DD20D2DDD200D4D(3) 由图可知：

0000G000,G10101110000010110,G1001,G0000020000300001000000G40000010,0故该编码器的生成矩阵G为;

G0G1G2G3G40000…0G0G1G2G3G4000…G00G0G1G2G3G400…

…………………………………………………将G0G1G2G3G45个矩阵代入矩阵G中既可。 (4)

将G0G1G2G3G45个矩阵进行变换得：

0000,00

G0I|P0,G1I|P1,G2I|P2,G3I|P3,G4I|P4。其中，I为k0*k0阶单位矩阵，即3*3阶单位矩阵。

P1,P2,P3,P4为k0*(n0-k0)阶矩阵，即3*(4-3),也就是3*1阶矩阵。 于是，该编码器的奇偶校验矩阵可写为：

P0T-ITTP0P-I10P2T0P1T0P0T-ITTTP0P0P0?…21H3TP0PT0PT0324P4T0P3T0P4T0………?…? ??其中P0TP1TP2TP3TP4T分别为P1,P2,P3,P4的转置。0为 k0*k0阶矩阵，即3*3阶矩阵。

第7章 网格编码调制

7.1 考虑由下列定义的码率为23的卷积码：

1DDD2 GD22D1D1DD这个码用到格雷编码（每个符号被赋值3比特，这样一来两个相连符号的码只在一个比特位不同）的8-PSK信号集。该TCM方案的吞吐量为2bit/s/Hz。 （1） 在该编码器的网格图中有多少状态？ （2） 求自由欧几里得距离

（3） 关于吞吐量为2bit/s/Hz的无编码的QPSK，求渐近编码增益。

g11Dg12Dg13D1DDD2解：GD 22gDgDgD222321D1D1DD23由此多项式矩阵，可以构造编码器，TCM方案如下：

a1 c1 a2 D D2 c2 c3

自然映射：

000s0，011s3，101s5，110s6，111s7 001s1，010s2，100s4，

输入比特 编码器当前状态 编码器之后的状

态

输出

00 01 10 11

00 00 00 00

00 01 10 11

000 110 111 010

00 01 10 11 00 01 10 11 00 01 10 11

01 01 01 01 10 10 10 10 11 11 11 11

00 01 10 11 00 01 10 11 00 01 10 11

100 111 011 000 000 000 100 111 100 111 100 011

状态00：s7,s0,s6,s2状态01：s4,s7,s3,s0状态10：s0,s4,s7,s0 状态11：s4,s7,s4,s3s0 s7 s0 s7 s2 s3

（1） 在该编码器的网格图中有4个状态。 （2） 自由欧几里得距离：

222d2freedEs0,s7dEs0,s7dEs2,s3330.586Es1.758E20202020

（3） 渐近编码增益：由书中P158（7-2）式得到，

ggSNRd10logd2free2freeEsE有编码10logs无编码1.7581.86dB 2

第8章 密码学

8.1 我们想要测试加密技术字符+x的安全性，其中每个明文字符移动x个位置来产生密文。

（1）假设用强力攻击，需要试验多少次才能破译这个码？

（2）假设一个计算机需要1ms来测试一个移位，那么要破译这个码需要多长时间？

解：（1）每个字符最多需要25次就能破译，若明文有n个字符，则需要试验n25次才能破译这个码。

（2）每个字符最多需要251ms25ms来破译这个码，若明文有n个字符，则需要测试n251msn25ms才能破译这个码。

8.2 假设N个人及组想用保密密钥密码。组中的每两个人应该能够秘密通信。需要多少不同的密钥？

2答：共需要CNN(N1)个不同的密钥。 2

8.6 (1)用素数29和61生成RSA算法的密钥。

(2)将字母“RSA”用ASCⅡ码表示，然后用上述生成的密钥将它们加密。 (3)接下来用素数对37和67生成密钥。步骤(1)还是步骤(3)中的密钥更安全？为什么? 解： (1)

第一个素数(A)=29 第二个素数(B)=61 则：

N=29*61=1769 T=(29-1)*(61-1)=1680

E与1680必须除1之外没有其他公共因子。 E(公钥)可以为9。 D(私钥)=9-1mod1680=373 (2)

字母“RSA”用ASCⅡ码表示为：82，83，65 “R”用82表示：则有M=82 C(密文)=829mod1769=1472 “S”用83表示：则有M=83 C(密文)=839mod1769=1120 “A”用65表示：则有M=65 C(密文)=659mod1769=10 (3)

第一个素数(A)=37 第二个素数(B)=67 则：

N=37*67=2479 T=(37-1)*(67-1)=2376

E与2376必须除1之外没有其他公共因子。 E(公钥)可以为5。 D(私钥)=5-1mod2376=950 综上可以看出：

步骤(1)与步骤(3)的密钥相比，步骤(3)更安全。 因为密钥越大，就越难被破解，安全性也就越高。