《信息论、编码与密码学》课后习题答案
第1章 信源编码
1.1
考虑一个信源概率为{0.30,0.25,0.20,0.15,0.10}的DMS。求信源熵H(X)。
解: 信源熵 H(X)
pklog2(pk)
k1
5
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.228bit
1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解: 若二元离散信源的统计特性为
P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值,由dH(X)/d(P)=0可得
p
log0
1pp
1
1p
1p
2
可知当概率P=Q=1/2时,有信源熵H(X)max
对于三元离散信源,当概率
1(bit)
时,信源熵
P1P2P31/3
H(X)m
a
5i),t x1.58(b
此结论可以推广到N元的离散信源。
1.3 证明不等式lnxx1。画出曲线y1lnx和y2x1的平面图以表明上述不
等式的正确性。 证明:
f(x)lnxx1(x0)
1
f(x)
x
令f(x)0,x1又有x00x1时f(x)0此时f(x)fmax0也即lnxx1
当x1时同理可得此时lnxx1综上可得lnxx1证毕
绘制图形说明如下 可以很明确说明上述 不等式的正确性。
1.4 证明I(X;Y)0。在什么条件下等号成立?
(IX;Y)=P(xi,yj)I(xi,yj)
i1j1n
m
P(xi,yj)log
i1j1
nm
P(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)
i1n
=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)
i1n
=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+„„.+np(1-p)n]
(p1)2
=(1-n)(1-p)- p
n+1
1.7 考虑一个只取整数值的随机变量X,满足PXn
1
,n2,3,...,。求熵HX。 2
n2nlogn
1
,其中2
Anlogn
A
解:为了方便计算,设Bnlogn,则A
2
11
,PXn;
ABBn2
1
根据公式计算自信息量为:IXlogPXlogAB;
1logB
B1logAB
则熵为:HXPXIXlogABn2=?
1ABn2n2ABn2n2
Bn2B
1.8 计算概率分布函数为
a10xa
px
否则0
的均匀分布随机变量X的微分熵HX。画出HX相对于参数a0.1a10的平面图,并对结果进行评论。
解:根据公式(1-21)可知,微分熵为:HXpxlogpxdx
当0xa时,pxa1,则
HXa1loga1dx
0a
1logaalogax0aloga aa
当x0或xa时,px0 ,则HX
根据得到的结果可以画出相应的平面图,由图可以看到随着a的增加,即px的减小,微分熵HX相应的增加。
HX
1.9考虑一个信源的概率为0.35,0.25,0.20,0.15,0.05的DMS。 (1)给出此信源的霍夫曼码。 (2)计算出这些码子的平均码长。 (3)这个码的效率是多少?
解:1)依题意,由霍夫曼编码的规则,得:
x1 0.35
x
2x3x4x5 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
5
n(x
k1
n
k
)p(xk),代入数据,得:
Rn(xk)p(xk)1(0.35)2(0.25)3(0.20)
k1
4(0.15)5(0.05)0.350.50.60.60.252.3(bit)
3)首先,该信源的熵为:
H(X)pklog2pk(0.35log20.350.25log20.25
k1
5
0.20log20.200.15log20.150.05log20.05)(0.351.5150.252.00.202.3220.152.7380.054.322)
(0.53030.50.46440.41070.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)依题意,由霍夫曼编码的规则,得:
概率 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
符号
x1 x2
x3 x4
x5 x6 x7 x8
3)空
1.11 一个DMS只有三个输出符号,它们的概率为{0.5,0.4,0.1}。 (1)给出此信源的霍夫曼码并确定编码效率。
(2)每次考虑两个符号时,给出此信源的霍夫曼码并确定编码效率。
(3)每次考虑三个符号时,给出此信源的霍夫曼码并确定编码效率。 解:
(1)本题的霍夫曼编码如下图所示:
1
1
1.0
0.5 0.4
图1.11 霍夫曼编码
则霍夫曼码如下表:
该信源的熵为:
H(X)pklog2pk
k1
3
(0.5log20.50.4log20.40.1log20.1) 0.50000.52880.33221.3610(bit)
平均每个符号的比特数为:
Rn(xk)p(xk)
k1
3
1(0.5)2(0.4)2(0.1) 0.50.80.21.5000(bit/符号)
该码的效率为:
1.3160/1.50000.9073
(2)把符号每两个分一组,重新应用霍夫曼编码算法,如下表所示:
该信源的熵为:
2H(X)pklog2pk2.7219(bit)
k1
9
H(X)1.3610(bit)
每个组的平均比特数为:
9
RBn(xk)P(xk)
k1
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/符号对)
R3.00/21.5000(bit/符号)
故该码的效率为:
1.3160/1.50000.9073
(3)依题意,把符合每三个分成一组,再重新应用霍夫曼编码算法,得:
编码表格如下:
符号对
概率 0.1250 0.1000 0.1000 0.1000 0.0800
自信息 2.7090 3.3223 3.3223 3.3223 3.6443
码字 100 0000 0001 110 011
x1x1x1 x1x1x2 x1x2x1 x2x1x1 x1x2x2
0.0800 0.0800 0.0640 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.6443 3.6443 3.9662 5.3223 5.3223 5.3223 5.6444 5.6444 5.6444 5.6444 5.6444 5.6444 5.9664 5.9664 5.9664 7.6646 7.6646 7.6646 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码:
[***********][**************]00从码字流恢复原来的序列。 解:根据Lempel-Ziv算法列出下表:
第2章 信道容量和编码
2.1 考虑图2-10所示的二元信道,设发送二元符号的先验概率为P0和P1,其中P0+ P1=1,求后验概率P(X0|Y1)和P(X1|Y1)。
解:PX0p0 PX1p1
PYX0p PY0X1q PY0X01p PYX11q
PX0,Y0PX0PY0X0PY0PX0Y0
PX0Y0
PX0PY0X0
PY0
p01p p01pp1q
PY0PX0PY0X0PX1PY0X1
p01pp1q
PX1,Y1PX1PYX1PY1PXY1
PXY1
PX1PY1X1
PY1
p11q p0pp11qPY1PX0PYX0PX1PYX1
p0pp11q
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个画面,每个画面大约有2105个像素,每个像素需要16比特的彩色显示。假定SNR为25dB, 计算支持电视信号传输所需要的带宽(利用信息容量定理)
解:根据题意,该电视信号所需的信息容量为:
C30210516bit/s9.6107bit/s
根据信息容量定理:CWlog2(1
P
25dB N0
PP
为信噪比,据题意),其中N0N0W
据上式解得带宽C1.1510Hz
7
2.8 考虑图2-15所示的Z型信道。
(1)求获得信道容量所需要的输入概率。
(2)若将N个这样的信道相级联,证明联合信道可以用一个信道转移概率
为p
N
的等价Z信道表示。
(3)当N时联合信道的容量是什么?
图2-15
解: (1) w为带宽
P
) (b/s) 信道容量 CWlog2(1N0W
CBlog2(1
S) N
(2) 由图可知信道转移概率为P
P(0|1)P(1|0)P
那么N级级联的信道转移概率
P(0|1)PW
(3)当N
N级级联
时 P(0|1)
级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在所有可能的输入概率上求得的即:
CmaxI(x;y)
p(xj)
CmaxP(xj)P(yi|xj)log
p(xj)
j0i0
q1r1
P(yi|xj)P(yi)
2.10 (1)证明对有限方差2,高斯随机变量具有所有随机变量可能获得的最大
微分熵。
(2)证明该熵由公式1/2log2(2e2)给出。 证明:
(1)由题意可知,高斯随机变量获得的微分熵为:
1
H(X)log2(2e2)
2
则有:
2
即其平均功率为:
12e12e
e2H(X)
2
2
e2H(X)
对于有限方差的高斯随机变量,即当平均功率受限时,有:
即有:
p(x)dx1,(xm)2p(x)dx2.
H(X)log2
综上可得,对于平均功率受限的连续随机变量,当服从高斯分布时具有最大微分熵。
(2)随机变量的微分熵为:
H(X)p(x)log2p(x)dx (1)
对于高斯分布,我们有:
p(x)
其中,m为数学期望。
1
2(xm)2} (2)
2 将(2)式代入(1)可得:
H(X)p(x
1
2(xm)2]dx (3) 2
由(3)式可以推出:
1
H(X)log2(2e2) (4)
2
故(4) 式即为本题所证。
2.11
写一个程序,它在输入信道转移矩阵后计算出信道容量?解:依据设定情况在一般的二元通信信道
输入前只有两种状态,0和1,假设传输发生错误概率为p,正确概率为1-p.这只是假定的一种情况,其实在程序中可看作这几个参量为个数组。CP[]及WP[]。再根据计算信道容量公式
q1r1
p(yi|xj)
maxp(xj)p(yi|xj)log,输出对应的信道容量值。
p(xj)j0i0
p(yi)
第3章 纠错控制编码
3.1 证明C0000是一个线性码。它的最小距离是什么? ,1100,0011,1111证明:由书中的定义3.8可知,线性码应该满足一下条件: (1) 两个属于该码的码字的和仍然是一个属于该码的码字, (2) 全零字总是一个码字,
(3) 两个码字之间的最小距离等于任何非零码字的最小重量,即dw 设Cc1,c2,c3,c4,即c10000,c21100,c30011,c41111, 首先证明条件(1):
c1c21100c2,c1c30011c3,c1c41111c4,c2c31111c4,
c2c40011c3,c3c41100c2,
很明显,条件(1)是满足的。条件(2)也是显然成立的。 最后证明条件(3):
不难看出最小距离d2,并且最小重量w2,即dw
综上,三个条件都满足,那么C就是一个线性码,它的最小距离是2。
3.3 考虑GF(2)上的下列生成矩阵
10100
G10011
01010
3)用此矩阵生成所有可能的码字。 4)求奇偶校验矩阵H。
5)求与其等价的一个系统码的生成矩阵。 6)构造该码的标准阵列。 7)这个码的最小距离是多少。 8)这个码能检测多少错误。
9)写出这个码能检测的所有错误模式。
10)这个码能纠多少个错误。
11)如果我们用此编码方案,那么符号错误概率是多少?将它与末尾的错误概率进行比较。
12)这是一个线性码?
10100
解:(1)c100010011=00000
0101010100
c200110011=01010
0101010100
c301010011=10011
0101010100
c401110011=11001
0101010100
c510010011=10100
0101010100
c610110011=11110
0101010100
c711010011=00111
0101010100
c811110011=01101
01010
此矩阵生成的码为:{00000,01010,10011,11001,10100,11110,00111,01101}
1010010011
(2)G1001101010
01010001-1-1
11111T
P10 P101又在二元情况下,11
11
111
PT101
奇偶校验矩阵可写为:HPTI
11110
10101
(4该码的标准阵列
10011
G01010
001-1-1
(5)奇偶校验矩阵H的第1、3列的和为零向量, 因此,这个码的最小距离为:d*=2。
(6)一个码至少可以检测所有重量小于或等于(d*-1)的非零错误模式。 这个码的最小距离为:d*=2 ,所以重量为1的错误模式可以检测得到。 (7)这个码能检测的所有错误模式 {00001,00010,00100,01000,10000} (8)能纠正不多于t个错误应满足d*2t1 又d*=2 所以22t1 即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, 满足第二条性质
,10100,11110,00111,01101} 11001
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
的,给出另一个能生成这个码字集合的生成矩阵。
a11
解:设生成矩阵是G=
a1n
,由题知,m=2,n=5,
am1amn
c=iG 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个以上错误的概率为
nn23nnnCp(1p)C2323pn4
n4
[**************]01C23pqC23pqC23pqC23pq23
23
0.00008
则出现的误字率为0.00008 所以得证。
3.9 假设C是一个二元码,它的奇偶校验矩阵为H。证明由C通过添加整体奇偶校验比特得到的扩展码C1的奇偶校验矩阵为
H1H
11|0|0|. |01|1
证明:根据题意,扩展码C1为:
C1C
11|0|0|,又|01|0
C得奇偶校验矩阵为H,CHT0。
TT
H1H
00|1|1|, |10|1
T
C1H1C
11
|0
|0
|HT|0
1|000
|1
|1
|CHT|1
00|10
0
0
0 000
即扩展码C1的奇偶校验矩阵为H1。 证毕。
3.11设C是长度为n,最小距离为7的二元完备码。证明n=7或n=23。 证明:由完备码的定义可知,一个完备码必须满足下列条件:
2
nk
i
Cn (1) i0
t
由题意可知:d*2t1,其中d*7 即有:t3
当n=7时,由(1)式可得,
2
71
C
i0
3
i
7
右式展开得:
i0123CCCCC77777i03
17213564左式
同理,可证得n=23时,同样满足(1)式。 故可证明当n=7或n=23时,C是二元完备码。
3.12 用rH来表示二元汉明码的码率,求limrH。
k
解:根据二元汉明码的性质可知:
其中m是任意正整数。 则由码率的定义可知:
则有:
(n,k)=(2m-1,2m-1-m)
rk2m-1-mHn2m-1
limkr2m-1-m
Hlimk2m-1
1
第4章 循环码
4.1 下面的哪个码是(a)循环码,(b)与一个循环码等价? (1)GF2上的0000。 ,0110,1100,0011,1001(2)GF2上的00000。 ,10110,01101,11011(3)GF3上的00000。 ,10110,01101,11011
。 (4)GF3上的0000,1122,2211
(5)长度为n的q-元重复码。
解:由书中定义4.1可知,循环码需要满足两个条件, (1) 首先它必须是一个线性码,
(2) 其次它的一个码字的任意循环移位的结果还是一个码字,即若
a0,a1,...,an1为其中的一个码字,则an1,a0,...,an2也是其中一个码字。
下面一一证明:
(1)首先证明C1是一个线性码:设C1c1,c2,c3,c4,c5,则
c10000,c20110,c31100,c40011,c51001,
c1c20110c2,c1c31100c3,c1c40011c4,c1c51001c5,
c2c31010? ,c2c40101?,c2c51111?,c3c41111?,c3c50101?,c4c51010?
显然C1不满足线性码的第一个条件,则它不是一个线性码,就不可能是一个循环码。
(2)首先证明C2是一个线性码:设C2c1,c2,c3,c4,则 ,c411011, c100000,c210110,c301101
c1c210110c2,c1c301101c3,c1c411011c4,c2c311011c4,
c2c401101c3,c3c410110c2
C2满足线性码的第一个条件,显然第二个条件也满足。C2中的最小距离d3,最小重量w3,即dw3,C2也满足第三个条件,可知C2是一个线性码。
01011,下面证明C2是循环的,c210110,经过循环移位之后得到的码字是c2这个码字不是C2中的码字,即C2不满足循环码的第二个条件。 综上可知,C2不是一个循环码,但是它与一个循环码等价。 (3)首先证明C3是一个线性码:设C3c1,c2,c3,c4,则 ,c411011, c100000,c210110,c301101
c1c210110c2,c1c301101c3,c1c411011c4,c2c311211?,c2c421121?,c3c412112?
显然C3不满足线性码的第一个条件,则它不是一个线性码,就不可能是一个循环码。
(4)首先证明C4是一个线性码:设C4c1,c2,c3,则
c10000,c21122,c32211,
c1c21122c2,c1c32211c3,c2c30000c1
C4满足线性码的第一个条件,显然第二个条件也满足。C4中的最小距离d4,最小重量w4,即dw4,C4也满足第三个条件,可知C4是一个线性码。
2112,下面证明C4是循环的,c21122,经过循环移位之后得到的码字是c2这个码字不是C4中的码字,即C4不满足循环码的第二个条件。 综上可知,C4不是一个循环码,但是它与一个循环码等价。 (5)长度为n的q-元重复码,
,可知其不为线性码,也定不为循环码。 111111111假设n3,q2,则
4.2 为下列定义的多项式环构造加法和乘法表
F(x)x21F(x)
(2)定义在GF(3)上的2
x1
解:(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
x X+1 0 0 x X+1 1 X+1 X+1
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
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元循环码,首先要分解x51
x51=(x1)(x4x3x2x1)
在GF(2)中,是(x4x3x2x1)既约的,所求的循环码为:c(x)i(x)g(x) 定义在R45中的多项式i(x)=2=16个,信息多6yj多项式在下表中列出:
故不同的码字有:
4.7 设多项式
g(x)x10x8x5x4x2x1
为GF(2)上分组长度为15的一个循环码的生成多项式。 (1)求生成矩阵G.。 (2)求奇偶校验矩阵H。 (3)这个码能检测多少个错误? (4)这个码能纠多少个错误?
(5)将生成矩阵写成系统型。 解:
(1)由生成多项式g(x)x10x8x5x4x2x1可知: 生成矩阵为:
[***********]0110010100G0
[1**********]10[1**********]1010
[1**********]10(2)由于已知分组长度为15,设奇偶校验多项式为h(x),则有:x151g(x)h(x)
即:
h(x)x151/(x10x8x5x4x2x1)
x5
x3
x
其中,上式为取模运算。 故,对应的奇偶校验矩阵为:
[***********]10000000H[1**********]00…………………………………[1**********]100
00
0
1
00
0000…101015
…
(3)建立如下表格:
由该表格可以看出,该码的最小距离为7。 即:d*7
故可知,该码可以检测d*16个错误。 (4)由于d*7,则有:72t1 即:t3
故该码可以纠3个错误。 (5)该生成矩阵的系统型为:
10
G[I|P]0
00
[1**********]110
[1**********]100[1**********]110
[1**********]111[1**********]101
4.11 生成多项式为g(x)(x231)(x17x31)的码在GSM中作检错和纠错标准。
(1)这个码能纠多少个随机错误? (2)这个码能纠多少个突发错误?
解:g(x)(x12211)(x17x31)x40x26x21x17x31 t12,nk40
又经过尝试我们得到分组长度是满足g(x)且能整除x231的最小整数
n75,
k754035 2xk35,x5
可以纠的突发错误最多为t=12个;能纠的随机错误为x=5个。
第5章BCH码
5.1 用一个合适的本原多项式由GF3构造GF9。解:考虑由子域构GF3造扩域GF9,已知q3,m2,现在对xqm
1进行
分解,即在GF3上分解,
xq1x81x1x1x21x41
m
下面考虑扩域GF9上的元素,这些元素可以表示为:
0z2z1z12z1 2z22z2
通过观察GF9上的元素,我们可以选择pxx21作为本原多项式来构造
GF9。
考虑GF9上的元素,z并不是GF9上的本原元,则我们可以假设GF9上的本原元为z1,则可以通过的幂模p得到GF9上的所有元素。 经过多项式的运算可以得到GF9中的元素:
的幂
GF9上的元素
z1 2z 2z1 2 2z2
1z1
2z22z1 3z31
4z4z3z1
5z52z4z32z1 6z62z31
z
z2
7z7z62z42z3z1
8z82z7z62z5z42z3z22z1
1
5.2 找出分组长度为26的纠三个错误的三元BCH码的生成多项式g(x)
依据确定可纠t个错误的BCH码的生成多项式的步骤nqm1即3m126,m3.
选取一个次数为3的素多项式并构造GF(27),令p(x)=x32x1
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)(xi)(xi1)...(x2ti1)(x2ti)
故该RS(15,11)码的生成多项式为:
g(x)(x1)(x2)(x3)(x4)
我们这里用到扩域GF(16)上的元素,该扩域是由GF(2)以本原多项式
p(z)z4z1构造的(书上例5.7)。 则有:
g(x)(x1)(x2)(x3)(x4)
x4(z3z21)x3(z3z2)x2z3x(z2z1) x4(13)x3(6)x2(3)x10
该RS(15,11)码的最小距离为:
d*2t1415
(2)
由RS(15,7)码可知,n=15,k=7。 根据RS码的性质:n-k=2t 即:2t=15-7=8
根据(1)题所涉及的性质可知,RS(15,7)码的生成多项式为:
g(x)(x1)(x2)(x3)(x4)(x5)(x6)(x7)(x8)
[x4(13)x3(6)x2(3)x10][x4(2)x3(14)x2x11]x8(8)x7(10)x6(2)x5(7)x4(14)x3(14)x2(9)x6
该RS(15,7)码的最小距离为:
d*2t1819
(3) RS(31,21)码中,t=5,d*11
111123
5.6 考虑GF(11)上具有下列奇偶校验矩阵的码H
1223233123
(1)证明该码纠三个错误的码。 (2)求该码的生成多项式
1112T
证明:H
122312
133233
1111T
1122223
10133233
102103231101010
1
10 210103
又因为在GF(11)中,矩阵中元素
3327(mod11)5,4364(mod11)9,53125(mod11)4,63216(mod11)773343(mod11)2,83512(mod11)6,93729(mod11)3,1031000(mod11)104216(mod11)5,5225(mod11)3,6236(mod11)3,7249(mod11)58264(mod11)9,9281(mod11)4,102100(mod11)1
所以经过计算,HT中满足和为零的行向量的最小个数为7,d2t1,所以这个码能纠t
d1
3个错。证毕。 2
第6章 卷积码
6.2 设计一个(12,4)系统卷积编码器使其约束长度v3且d8。 (1)构造该编码器的网格图。 (2)该码的dfree是什么?
解:(1)由题意可知,n12,k4,且约束长度为vmk03 可以得到m3,k01,n03
通过这些参量我们可以设计出编码器,如下图所示:
这个编码器每次把1比特输入编码成3比特的输出。信息帧的长度为k01,码字帧的长度为n03,分组长度为12,该编码器的约束长度为vmk03,码率为。
编码器的状态图:(只有四种状态)
卷积编码器输入和输出的比特如下表所示
输入比特
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
d2,d123,d35,d4
6 d因为m3,4d6dfree
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)由图可得
k01,n03,v4,vmk0,得m4,R
k01n03
该码的d*和dfree的值是多少?
(3)解:由状态表m3则m1级d*d1*d2*d3*d4*123410
dfreemax[dj*]8
j
6.4 考虑图6-36所示的二元编码器。
图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)g24(D)g(D)g
31(D)g32(D)g3334(D)
DD2D2DD20D2DDD2
00D4D
(3) 由图可知:
0
000G000,G101011100000
10110,G1001,G0000020000300001000000G40
000010,0
故该编码器的生成矩阵G为;
G0
G1G2G3G4
0000…0G0G1G2G3G400
0…G0
0G0G1G2G3G4
0…
……………………… …
…
…………………
…
将G0G1G2G3G45个矩阵代入矩阵G中既可。 (4)
将G0G1G2G3G45个矩阵进行变换得:
00
00,00
G0I|P0,G1I|P1,G2I|P2,G3I|P3,G4I|P4。其中,I为k0*k0阶单位矩阵,即3*3阶单位矩阵。
P1,P2,P3,P4为k0*(n0-k0)阶矩阵,即3*(4-3),也就是3*1阶矩阵。 于是,该编码器的奇偶校验矩阵可写为:
P0T-I
TTP0P-I10
P2T0P1T0P0T-IT
P30P2T0P1T0 …HT
P0PT0PT0
32
4
P4T0P3T0
P4T0………
…
其中P0TP1TP2TP3TP4T分别为P1,P2,P3,P4的转置。0为 k0*k0阶矩阵,即3*3阶矩阵。
第7章 网格编码调制
7.1 考虑由下列定义的码率为23的卷积码:
1DDD2
GD2
2
D1D1DD
这个码用到格雷编码(每个符号被赋值3比特,这样一来两个相连符号的码只在一个比特位不同)的8-PSK信号集。该TCM方案的吞吐量为2bit/s/Hz。 (1) 在该编码器的网格图中有多少状态? (2) 求自由欧几里得距离
(3) 关于吞吐量为2bit/s/Hz的无编码的QPSK,求渐近编码增益。
g11Dg12Dg13D1DDD2解:GD 22gDgDgD222321D1D1DD23
由此多项式矩阵,可以构造编码器,TCM方案如下:
自然映射:
001s1,010s2,100s4,000s0,011s3,101s5,110s6,111s7
输入比特
编码器当前状态
编码器之后的状
态
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,s3
(1) 在该编码器的网格图中有4个状态。 (2) 自由欧几里得距离:
222d2freedEs0,s7dEs0,s7dEs2,s3
330.586Es1.758E2
0202020
(3) 渐近编码增益:由书中P158(7-2)式得到,
gg
SNR
d
10log
d
2free2free
Es
E有编码
10log
s无编码
1.758
1.86dB 2
第8章 密码学
8.1 我们想要测试加密技术字符+x的安全性,其中每个明文字符移动x个位置来产生密文。
(1)假设用强力攻击,需要试验多少次才能破译这个码?
(2)假设一个计算机需要1ms来测试一个移位,那么要破译这个码需要多长时间?
解:(1)每个字符最多需要25次就能破译,若明文有n个字符,则需要试验n25次才能破译这个码。
(2)每个字符最多需要251ms25ms来破译这个码,若明文有n个字符,则需要测试n251msn25ms才能破译这个码。
8.2 假设N个人及组想用保密密钥密码。组中的每两个人应该能够秘密通信。需要多少不同的密钥?
2
答:共需要CN
N(N1)
个不同的密钥。 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=1064 (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)更安全。 因为密钥越大,就越难被破解,安全性也就越高。
《信息论、编码与密码学》课后习题答案
第1章 信源编码
1.1
考虑一个信源概率为{0.30,0.25,0.20,0.15,0.10}的DMS。求信源熵H(X)。
解: 信源熵 H(X)
pklog2(pk)
k1
5
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.228bit
1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解: 若二元离散信源的统计特性为
P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值,由dH(X)/d(P)=0可得
p
log0
1pp
1
1p
1p
2
可知当概率P=Q=1/2时,有信源熵H(X)max
对于三元离散信源,当概率
1(bit)
时,信源熵
P1P2P31/3
H(X)m
a
5i),t x1.58(b
此结论可以推广到N元的离散信源。
1.3 证明不等式lnxx1。画出曲线y1lnx和y2x1的平面图以表明上述不
等式的正确性。 证明:
f(x)lnxx1(x0)
1
f(x)
x
令f(x)0,x1又有x00x1时f(x)0此时f(x)fmax0也即lnxx1
当x1时同理可得此时lnxx1综上可得lnxx1证毕
绘制图形说明如下 可以很明确说明上述 不等式的正确性。
1.4 证明I(X;Y)0。在什么条件下等号成立?
(IX;Y)=P(xi,yj)I(xi,yj)
i1j1n
m
P(xi,yj)log
i1j1
nm
P(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)
i1n
=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)
i1n
=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+„„.+np(1-p)n]
(p1)2
=(1-n)(1-p)- p
n+1
1.7 考虑一个只取整数值的随机变量X,满足PXn
1
,n2,3,...,。求熵HX。 2
n2nlogn
1
,其中2
Anlogn
A
解:为了方便计算,设Bnlogn,则A
2
11
,PXn;
ABBn2
1
根据公式计算自信息量为:IXlogPXlogAB;
1logB
B1logAB
则熵为:HXPXIXlogABn2=?
1ABn2n2ABn2n2
Bn2B
1.8 计算概率分布函数为
a10xa
px
否则0
的均匀分布随机变量X的微分熵HX。画出HX相对于参数a0.1a10的平面图,并对结果进行评论。
解:根据公式(1-21)可知,微分熵为:HXpxlogpxdx
当0xa时,pxa1,则
HXa1loga1dx
0a
1logaalogax0aloga aa
当x0或xa时,px0 ,则HX
根据得到的结果可以画出相应的平面图,由图可以看到随着a的增加,即px的减小,微分熵HX相应的增加。
HX
1.9考虑一个信源的概率为0.35,0.25,0.20,0.15,0.05的DMS。 (1)给出此信源的霍夫曼码。 (2)计算出这些码子的平均码长。 (3)这个码的效率是多少?
解:1)依题意,由霍夫曼编码的规则,得:
x1 0.35
x
2x3x4x5 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
5
n(x
k1
n
k
)p(xk),代入数据,得:
Rn(xk)p(xk)1(0.35)2(0.25)3(0.20)
k1
4(0.15)5(0.05)0.350.50.60.60.252.3(bit)
3)首先,该信源的熵为:
H(X)pklog2pk(0.35log20.350.25log20.25
k1
5
0.20log20.200.15log20.150.05log20.05)(0.351.5150.252.00.202.3220.152.7380.054.322)
(0.53030.50.46440.41070.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)依题意,由霍夫曼编码的规则,得:
概率 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
符号
x1 x2
x3 x4
x5 x6 x7 x8
3)空
1.11 一个DMS只有三个输出符号,它们的概率为{0.5,0.4,0.1}。 (1)给出此信源的霍夫曼码并确定编码效率。
(2)每次考虑两个符号时,给出此信源的霍夫曼码并确定编码效率。
(3)每次考虑三个符号时,给出此信源的霍夫曼码并确定编码效率。 解:
(1)本题的霍夫曼编码如下图所示:
1
1
1.0
0.5 0.4
图1.11 霍夫曼编码
则霍夫曼码如下表:
该信源的熵为:
H(X)pklog2pk
k1
3
(0.5log20.50.4log20.40.1log20.1) 0.50000.52880.33221.3610(bit)
平均每个符号的比特数为:
Rn(xk)p(xk)
k1
3
1(0.5)2(0.4)2(0.1) 0.50.80.21.5000(bit/符号)
该码的效率为:
1.3160/1.50000.9073
(2)把符号每两个分一组,重新应用霍夫曼编码算法,如下表所示:
该信源的熵为:
2H(X)pklog2pk2.7219(bit)
k1
9
H(X)1.3610(bit)
每个组的平均比特数为:
9
RBn(xk)P(xk)
k1
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/符号对)
R3.00/21.5000(bit/符号)
故该码的效率为:
1.3160/1.50000.9073
(3)依题意,把符合每三个分成一组,再重新应用霍夫曼编码算法,得:
编码表格如下:
符号对
概率 0.1250 0.1000 0.1000 0.1000 0.0800
自信息 2.7090 3.3223 3.3223 3.3223 3.6443
码字 100 0000 0001 110 011
x1x1x1 x1x1x2 x1x2x1 x2x1x1 x1x2x2
0.0800 0.0800 0.0640 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.6443 3.6443 3.9662 5.3223 5.3223 5.3223 5.6444 5.6444 5.6444 5.6444 5.6444 5.6444 5.9664 5.9664 5.9664 7.6646 7.6646 7.6646 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码:
[***********][**************]00从码字流恢复原来的序列。 解:根据Lempel-Ziv算法列出下表:
第2章 信道容量和编码
2.1 考虑图2-10所示的二元信道,设发送二元符号的先验概率为P0和P1,其中P0+ P1=1,求后验概率P(X0|Y1)和P(X1|Y1)。
解:PX0p0 PX1p1
PYX0p PY0X1q PY0X01p PYX11q
PX0,Y0PX0PY0X0PY0PX0Y0
PX0Y0
PX0PY0X0
PY0
p01p p01pp1q
PY0PX0PY0X0PX1PY0X1
p01pp1q
PX1,Y1PX1PYX1PY1PXY1
PXY1
PX1PY1X1
PY1
p11q p0pp11qPY1PX0PYX0PX1PYX1
p0pp11q
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个画面,每个画面大约有2105个像素,每个像素需要16比特的彩色显示。假定SNR为25dB, 计算支持电视信号传输所需要的带宽(利用信息容量定理)
解:根据题意,该电视信号所需的信息容量为:
C30210516bit/s9.6107bit/s
根据信息容量定理:CWlog2(1
P
25dB N0
PP
为信噪比,据题意),其中N0N0W
据上式解得带宽C1.1510Hz
7
2.8 考虑图2-15所示的Z型信道。
(1)求获得信道容量所需要的输入概率。
(2)若将N个这样的信道相级联,证明联合信道可以用一个信道转移概率
为p
N
的等价Z信道表示。
(3)当N时联合信道的容量是什么?
图2-15
解: (1) w为带宽
P
) (b/s) 信道容量 CWlog2(1N0W
CBlog2(1
S) N
(2) 由图可知信道转移概率为P
P(0|1)P(1|0)P
那么N级级联的信道转移概率
P(0|1)PW
(3)当N
N级级联
时 P(0|1)
级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在所有可能的输入概率上求得的即:
CmaxI(x;y)
p(xj)
CmaxP(xj)P(yi|xj)log
p(xj)
j0i0
q1r1
P(yi|xj)P(yi)
2.10 (1)证明对有限方差2,高斯随机变量具有所有随机变量可能获得的最大
微分熵。
(2)证明该熵由公式1/2log2(2e2)给出。 证明:
(1)由题意可知,高斯随机变量获得的微分熵为:
1
H(X)log2(2e2)
2
则有:
2
即其平均功率为:
12e12e
e2H(X)
2
2
e2H(X)
对于有限方差的高斯随机变量,即当平均功率受限时,有:
即有:
p(x)dx1,(xm)2p(x)dx2.
H(X)log2
综上可得,对于平均功率受限的连续随机变量,当服从高斯分布时具有最大微分熵。
(2)随机变量的微分熵为:
H(X)p(x)log2p(x)dx (1)
对于高斯分布,我们有:
p(x)
其中,m为数学期望。
1
2(xm)2} (2)
2 将(2)式代入(1)可得:
H(X)p(x
1
2(xm)2]dx (3) 2
由(3)式可以推出:
1
H(X)log2(2e2) (4)
2
故(4) 式即为本题所证。
2.11
写一个程序,它在输入信道转移矩阵后计算出信道容量?解:依据设定情况在一般的二元通信信道
输入前只有两种状态,0和1,假设传输发生错误概率为p,正确概率为1-p.这只是假定的一种情况,其实在程序中可看作这几个参量为个数组。CP[]及WP[]。再根据计算信道容量公式
q1r1
p(yi|xj)
maxp(xj)p(yi|xj)log,输出对应的信道容量值。
p(xj)j0i0
p(yi)
第3章 纠错控制编码
3.1 证明C0000是一个线性码。它的最小距离是什么? ,1100,0011,1111证明:由书中的定义3.8可知,线性码应该满足一下条件: (1) 两个属于该码的码字的和仍然是一个属于该码的码字, (2) 全零字总是一个码字,
(3) 两个码字之间的最小距离等于任何非零码字的最小重量,即dw 设Cc1,c2,c3,c4,即c10000,c21100,c30011,c41111, 首先证明条件(1):
c1c21100c2,c1c30011c3,c1c41111c4,c2c31111c4,
c2c40011c3,c3c41100c2,
很明显,条件(1)是满足的。条件(2)也是显然成立的。 最后证明条件(3):
不难看出最小距离d2,并且最小重量w2,即dw
综上,三个条件都满足,那么C就是一个线性码,它的最小距离是2。
3.3 考虑GF(2)上的下列生成矩阵
10100
G10011
01010
3)用此矩阵生成所有可能的码字。 4)求奇偶校验矩阵H。
5)求与其等价的一个系统码的生成矩阵。 6)构造该码的标准阵列。 7)这个码的最小距离是多少。 8)这个码能检测多少错误。
9)写出这个码能检测的所有错误模式。
10)这个码能纠多少个错误。
11)如果我们用此编码方案,那么符号错误概率是多少?将它与末尾的错误概率进行比较。
12)这是一个线性码?
10100
解:(1)c100010011=00000
0101010100
c200110011=01010
0101010100
c301010011=10011
0101010100
c401110011=11001
0101010100
c510010011=10100
0101010100
c610110011=11110
0101010100
c711010011=00111
0101010100
c811110011=01101
01010
此矩阵生成的码为:{00000,01010,10011,11001,10100,11110,00111,01101}
1010010011
(2)G1001101010
01010001-1-1
11111T
P10 P101又在二元情况下,11
11
111
PT101
奇偶校验矩阵可写为:HPTI
11110
10101
(4该码的标准阵列
10011
G01010
001-1-1
(5)奇偶校验矩阵H的第1、3列的和为零向量, 因此,这个码的最小距离为:d*=2。
(6)一个码至少可以检测所有重量小于或等于(d*-1)的非零错误模式。 这个码的最小距离为:d*=2 ,所以重量为1的错误模式可以检测得到。 (7)这个码能检测的所有错误模式 {00001,00010,00100,01000,10000} (8)能纠正不多于t个错误应满足d*2t1 又d*=2 所以22t1 即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, 满足第二条性质
,10100,11110,00111,01101} 11001
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
的,给出另一个能生成这个码字集合的生成矩阵。
a11
解:设生成矩阵是G=
a1n
,由题知,m=2,n=5,
am1amn
c=iG 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个以上错误的概率为
nn23nnnCp(1p)C2323pn4
n4
[**************]01C23pqC23pqC23pqC23pq23
23
0.00008
则出现的误字率为0.00008 所以得证。
3.9 假设C是一个二元码,它的奇偶校验矩阵为H。证明由C通过添加整体奇偶校验比特得到的扩展码C1的奇偶校验矩阵为
H1H
11|0|0|. |01|1
证明:根据题意,扩展码C1为:
C1C
11|0|0|,又|01|0
C得奇偶校验矩阵为H,CHT0。
TT
H1H
00|1|1|, |10|1
T
C1H1C
11
|0
|0
|HT|0
1|000
|1
|1
|CHT|1
00|10
0
0
0 000
即扩展码C1的奇偶校验矩阵为H1。 证毕。
3.11设C是长度为n,最小距离为7的二元完备码。证明n=7或n=23。 证明:由完备码的定义可知,一个完备码必须满足下列条件:
2
nk
i
Cn (1) i0
t
由题意可知:d*2t1,其中d*7 即有:t3
当n=7时,由(1)式可得,
2
71
C
i0
3
i
7
右式展开得:
i0123CCCCC77777i03
17213564左式
同理,可证得n=23时,同样满足(1)式。 故可证明当n=7或n=23时,C是二元完备码。
3.12 用rH来表示二元汉明码的码率,求limrH。
k
解:根据二元汉明码的性质可知:
其中m是任意正整数。 则由码率的定义可知:
则有:
(n,k)=(2m-1,2m-1-m)
rk2m-1-mHn2m-1
limkr2m-1-m
Hlimk2m-1
1
第4章 循环码
4.1 下面的哪个码是(a)循环码,(b)与一个循环码等价? (1)GF2上的0000。 ,0110,1100,0011,1001(2)GF2上的00000。 ,10110,01101,11011(3)GF3上的00000。 ,10110,01101,11011
。 (4)GF3上的0000,1122,2211
(5)长度为n的q-元重复码。
解:由书中定义4.1可知,循环码需要满足两个条件, (1) 首先它必须是一个线性码,
(2) 其次它的一个码字的任意循环移位的结果还是一个码字,即若
a0,a1,...,an1为其中的一个码字,则an1,a0,...,an2也是其中一个码字。
下面一一证明:
(1)首先证明C1是一个线性码:设C1c1,c2,c3,c4,c5,则
c10000,c20110,c31100,c40011,c51001,
c1c20110c2,c1c31100c3,c1c40011c4,c1c51001c5,
c2c31010? ,c2c40101?,c2c51111?,c3c41111?,c3c50101?,c4c51010?
显然C1不满足线性码的第一个条件,则它不是一个线性码,就不可能是一个循环码。
(2)首先证明C2是一个线性码:设C2c1,c2,c3,c4,则 ,c411011, c100000,c210110,c301101
c1c210110c2,c1c301101c3,c1c411011c4,c2c311011c4,
c2c401101c3,c3c410110c2
C2满足线性码的第一个条件,显然第二个条件也满足。C2中的最小距离d3,最小重量w3,即dw3,C2也满足第三个条件,可知C2是一个线性码。
01011,下面证明C2是循环的,c210110,经过循环移位之后得到的码字是c2这个码字不是C2中的码字,即C2不满足循环码的第二个条件。 综上可知,C2不是一个循环码,但是它与一个循环码等价。 (3)首先证明C3是一个线性码:设C3c1,c2,c3,c4,则 ,c411011, c100000,c210110,c301101
c1c210110c2,c1c301101c3,c1c411011c4,c2c311211?,c2c421121?,c3c412112?
显然C3不满足线性码的第一个条件,则它不是一个线性码,就不可能是一个循环码。
(4)首先证明C4是一个线性码:设C4c1,c2,c3,则
c10000,c21122,c32211,
c1c21122c2,c1c32211c3,c2c30000c1
C4满足线性码的第一个条件,显然第二个条件也满足。C4中的最小距离d4,最小重量w4,即dw4,C4也满足第三个条件,可知C4是一个线性码。
2112,下面证明C4是循环的,c21122,经过循环移位之后得到的码字是c2这个码字不是C4中的码字,即C4不满足循环码的第二个条件。 综上可知,C4不是一个循环码,但是它与一个循环码等价。 (5)长度为n的q-元重复码,
,可知其不为线性码,也定不为循环码。 111111111假设n3,q2,则
4.2 为下列定义的多项式环构造加法和乘法表
F(x)x21F(x)
(2)定义在GF(3)上的2
x1
解:(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
x X+1 0 0 x X+1 1 X+1 X+1
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
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元循环码,首先要分解x51
x51=(x1)(x4x3x2x1)
在GF(2)中,是(x4x3x2x1)既约的,所求的循环码为:c(x)i(x)g(x) 定义在R45中的多项式i(x)=2=16个,信息多6yj多项式在下表中列出:
故不同的码字有:
4.7 设多项式
g(x)x10x8x5x4x2x1
为GF(2)上分组长度为15的一个循环码的生成多项式。 (1)求生成矩阵G.。 (2)求奇偶校验矩阵H。 (3)这个码能检测多少个错误? (4)这个码能纠多少个错误?
(5)将生成矩阵写成系统型。 解:
(1)由生成多项式g(x)x10x8x5x4x2x1可知: 生成矩阵为:
[***********]0110010100G0
[1**********]10[1**********]1010
[1**********]10(2)由于已知分组长度为15,设奇偶校验多项式为h(x),则有:x151g(x)h(x)
即:
h(x)x151/(x10x8x5x4x2x1)
x5
x3
x
其中,上式为取模运算。 故,对应的奇偶校验矩阵为:
[***********]10000000H[1**********]00…………………………………[1**********]100
00
0
1
00
0000…101015
…
(3)建立如下表格:
由该表格可以看出,该码的最小距离为7。 即:d*7
故可知,该码可以检测d*16个错误。 (4)由于d*7,则有:72t1 即:t3
故该码可以纠3个错误。 (5)该生成矩阵的系统型为:
10
G[I|P]0
00
[1**********]110
[1**********]100[1**********]110
[1**********]111[1**********]101
4.11 生成多项式为g(x)(x231)(x17x31)的码在GSM中作检错和纠错标准。
(1)这个码能纠多少个随机错误? (2)这个码能纠多少个突发错误?
解:g(x)(x12211)(x17x31)x40x26x21x17x31 t12,nk40
又经过尝试我们得到分组长度是满足g(x)且能整除x231的最小整数
n75,
k754035 2xk35,x5
可以纠的突发错误最多为t=12个;能纠的随机错误为x=5个。
第5章BCH码
5.1 用一个合适的本原多项式由GF3构造GF9。解:考虑由子域构GF3造扩域GF9,已知q3,m2,现在对xqm
1进行
分解,即在GF3上分解,
xq1x81x1x1x21x41
m
下面考虑扩域GF9上的元素,这些元素可以表示为:
0z2z1z12z1 2z22z2
通过观察GF9上的元素,我们可以选择pxx21作为本原多项式来构造
GF9。
考虑GF9上的元素,z并不是GF9上的本原元,则我们可以假设GF9上的本原元为z1,则可以通过的幂模p得到GF9上的所有元素。 经过多项式的运算可以得到GF9中的元素:
的幂
GF9上的元素
z1 2z 2z1 2 2z2
1z1
2z22z1 3z31
4z4z3z1
5z52z4z32z1 6z62z31
z
z2
7z7z62z42z3z1
8z82z7z62z5z42z3z22z1
1
5.2 找出分组长度为26的纠三个错误的三元BCH码的生成多项式g(x)
依据确定可纠t个错误的BCH码的生成多项式的步骤nqm1即3m126,m3.
选取一个次数为3的素多项式并构造GF(27),令p(x)=x32x1
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)(xi)(xi1)...(x2ti1)(x2ti)
故该RS(15,11)码的生成多项式为:
g(x)(x1)(x2)(x3)(x4)
我们这里用到扩域GF(16)上的元素,该扩域是由GF(2)以本原多项式
p(z)z4z1构造的(书上例5.7)。 则有:
g(x)(x1)(x2)(x3)(x4)
x4(z3z21)x3(z3z2)x2z3x(z2z1) x4(13)x3(6)x2(3)x10
该RS(15,11)码的最小距离为:
d*2t1415
(2)
由RS(15,7)码可知,n=15,k=7。 根据RS码的性质:n-k=2t 即:2t=15-7=8
根据(1)题所涉及的性质可知,RS(15,7)码的生成多项式为:
g(x)(x1)(x2)(x3)(x4)(x5)(x6)(x7)(x8)
[x4(13)x3(6)x2(3)x10][x4(2)x3(14)x2x11]x8(8)x7(10)x6(2)x5(7)x4(14)x3(14)x2(9)x6
该RS(15,7)码的最小距离为:
d*2t1819
(3) RS(31,21)码中,t=5,d*11
111123
5.6 考虑GF(11)上具有下列奇偶校验矩阵的码H
1223233123
(1)证明该码纠三个错误的码。 (2)求该码的生成多项式
1112T
证明:H
122312
133233
1111T
1122223
10133233
102103231101010
1
10 210103
又因为在GF(11)中,矩阵中元素
3327(mod11)5,4364(mod11)9,53125(mod11)4,63216(mod11)773343(mod11)2,83512(mod11)6,93729(mod11)3,1031000(mod11)104216(mod11)5,5225(mod11)3,6236(mod11)3,7249(mod11)58264(mod11)9,9281(mod11)4,102100(mod11)1
所以经过计算,HT中满足和为零的行向量的最小个数为7,d2t1,所以这个码能纠t
d1
3个错。证毕。 2
第6章 卷积码
6.2 设计一个(12,4)系统卷积编码器使其约束长度v3且d8。 (1)构造该编码器的网格图。 (2)该码的dfree是什么?
解:(1)由题意可知,n12,k4,且约束长度为vmk03 可以得到m3,k01,n03
通过这些参量我们可以设计出编码器,如下图所示:
这个编码器每次把1比特输入编码成3比特的输出。信息帧的长度为k01,码字帧的长度为n03,分组长度为12,该编码器的约束长度为vmk03,码率为。
编码器的状态图:(只有四种状态)
卷积编码器输入和输出的比特如下表所示
输入比特
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
d2,d123,d35,d4
6 d因为m3,4d6dfree
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)由图可得
k01,n03,v4,vmk0,得m4,R
k01n03
该码的d*和dfree的值是多少?
(3)解:由状态表m3则m1级d*d1*d2*d3*d4*123410
dfreemax[dj*]8
j
6.4 考虑图6-36所示的二元编码器。
图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)g24(D)g(D)g
31(D)g32(D)g3334(D)
DD2D2DD20D2DDD2
00D4D
(3) 由图可知:
0
000G000,G101011100000
10110,G1001,G0000020000300001000000G40
000010,0
故该编码器的生成矩阵G为;
G0
G1G2G3G4
0000…0G0G1G2G3G400
0…G0
0G0G1G2G3G4
0…
……………………… …
…
…………………
…
将G0G1G2G3G45个矩阵代入矩阵G中既可。 (4)
将G0G1G2G3G45个矩阵进行变换得:
00
00,00
G0I|P0,G1I|P1,G2I|P2,G3I|P3,G4I|P4。其中,I为k0*k0阶单位矩阵,即3*3阶单位矩阵。
P1,P2,P3,P4为k0*(n0-k0)阶矩阵,即3*(4-3),也就是3*1阶矩阵。 于是,该编码器的奇偶校验矩阵可写为:
P0T-I
TTP0P-I10
P2T0P1T0P0T-IT
P30P2T0P1T0 …HT
P0PT0PT0
32
4
P4T0P3T0
P4T0………
…
其中P0TP1TP2TP3TP4T分别为P1,P2,P3,P4的转置。0为 k0*k0阶矩阵,即3*3阶矩阵。
第7章 网格编码调制
7.1 考虑由下列定义的码率为23的卷积码:
1DDD2
GD2
2
D1D1DD
这个码用到格雷编码(每个符号被赋值3比特,这样一来两个相连符号的码只在一个比特位不同)的8-PSK信号集。该TCM方案的吞吐量为2bit/s/Hz。 (1) 在该编码器的网格图中有多少状态? (2) 求自由欧几里得距离
(3) 关于吞吐量为2bit/s/Hz的无编码的QPSK,求渐近编码增益。
g11Dg12Dg13D1DDD2解:GD 22gDgDgD222321D1D1DD23
由此多项式矩阵,可以构造编码器,TCM方案如下:
自然映射:
001s1,010s2,100s4,000s0,011s3,101s5,110s6,111s7
输入比特
编码器当前状态
编码器之后的状
态
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,s3
(1) 在该编码器的网格图中有4个状态。 (2) 自由欧几里得距离:
222d2freedEs0,s7dEs0,s7dEs2,s3
330.586Es1.758E2
0202020
(3) 渐近编码增益:由书中P158(7-2)式得到,
gg
SNR
d
10log
d
2free2free
Es
E有编码
10log
s无编码
1.758
1.86dB 2
第8章 密码学
8.1 我们想要测试加密技术字符+x的安全性,其中每个明文字符移动x个位置来产生密文。
(1)假设用强力攻击,需要试验多少次才能破译这个码?
(2)假设一个计算机需要1ms来测试一个移位,那么要破译这个码需要多长时间?
解:(1)每个字符最多需要25次就能破译,若明文有n个字符,则需要试验n25次才能破译这个码。
(2)每个字符最多需要251ms25ms来破译这个码,若明文有n个字符,则需要测试n251msn25ms才能破译这个码。
8.2 假设N个人及组想用保密密钥密码。组中的每两个人应该能够秘密通信。需要多少不同的密钥?
2
答:共需要CN
N(N1)
个不同的密钥。 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=1064 (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)更安全。 因为密钥越大,就越难被破解,安全性也就越高。