信息与编码理论 第2版 习题及答案汇 张长森 第1-7章 绪论、信源与信源熵-卷积码

习题1答案【解】用文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式，对客观物质运动和主观思维活动状态的一种表述，就称为消息。把消息变换成适合在信道中传输的物理量，这种物理量称为信号。信息是对事物运动状态或存在方式不确定性的描述。这就是香农信息的定义。信号携带着消息，它是消息的运载工具。消息中携带者信息。【解】一个消息之所以会包含信息，正是因为它具有不确定性，一个不具有不确定性的消息是不会包含任何信息的。一切有通信意义的消息的发生都是随机的，是事先无法预料的，具有不确定性。通信的目的就是为了消除这种不确定性。比如，在得知硬币的抛掷结果之前，人们对于结果出现正面还是反面是不确定的。通过通信，人们得知了硬币抛掷的结果，消除了不确定性，从而获得了信息。因此，信息是对事物运动状态或存在方式不确定性的描述。【解】信息量与消息发生的不确定性的大小有关。调制器（写入设备）信道编码器【解】调制器（写入设备）信道编码器信源信源编码器噪声源信道（存储媒质）信宿信源信源编码器噪声源信道（存储媒质）信宿信源译码器解调器（读取设备）信道译码器数字通信系统模型解调器（读取设备）信道译码器信源编码器把信源发出的语言、图像或文字等消息转换成二进制（或多进制）形式的信息序列。有时为了提高传输有效性，还会去除一些与信息传输无关的冗余度来实现数据压缩。信道编码器则为了抵抗传输过程中的各种干扰，改善误码率性能，往往会在传输的信息序列中人为的增加一些冗余度，使其具有自动检错或纠错的功能。调制器的功能是把信源编码器输出的信息序列变换成适合于信道传输的电信号，然后送入信道传输。解调器则是执行与调制器相反的功能，将接收到的电信号还原为信息序列。由于信号在信道传输过程中会受到信道特性、噪声和干扰信号的不利影响，因此在解调器输出的序列中会出现误码的情况。接下来，解调器的输出序列会送入信道译码器，其会在自己检错或纠错能力之内对接收到的序列进行检错或纠错。然后再通过信源译码器恢复成消息送给信宿。【解】信息论的研究对象正是这种统一的通信系统模型。人们通过系统中消息的传输和处理来研究信息传输和处理的共同规律。研究通信系统，其目的是要找到信息传输的共同规律，提高信息传输的可靠性、有效性、保密性和认证性，从而使信息传输系统达到最优化。20世4019591961习题2答案（5213【解】5252!Iig21t5241313413Cp(xi) 13C52此时能够获得的信息量为

413CI(xi)logp(xi)log1313.208bitC5248AA【解】A

px132

，自信息量为Ixlog2pxlog21/325bit【解】(1)1pX

21IX1log2pX1log21/214.39bit2pX2

21IX2log2pX2log22/213.39bit3pX3

21IX3log2pX3log23/212.81bit4pX4

21IX4log2pX4log24/212.39bit5pX5

21IX5log2pX5log25/212.07bit6pX6

21IX6log2pX6log26/211.81bit设掷一次骰子平均所获得的信息量为IX，则IXpX1IX1+pX2IX2+pX3IX3+pX4IX4+pX5IX5+pX6IX614.39+23.39+32.81+42.39+52.07+61.8121 21 21 21 21 212.399bita7（b12【解】设得到总点数为7的事件记为X7，X发生的概率pX71，6IX7log2pX7log21/62.58bit设得到总点数为12为事件记为X12，X发生的概率pX121，36IX=12log2pX12log21/365.17bit【解】四进制脉冲可以表示4个不同的消息，例如：{0,1,2,3}；八进制脉冲可以表示8个不1,2,3,4,5,6,21}。HX1g2n2l；HX2g2n3l；HX0g2n1l。所以可知，四进制、八进制脉冲所含信息量分别是二进制脉冲信息量的2倍和3倍。

Xx112 34Px 3/8 1/4 1/4 1/8 （20120130230012031010020321223210【解】12、101、25312p8

1214

158 此消息的信息量是

Ilogp73.98bit38I73.981.95bit38 38{0，1}P01P3。求：4 4【解】(1)

HX1log13log30.811bit/symbol4 4 4 4(2)平均每个符号携带的信息量0.811bit。每帧电视图像可以认为是由3105又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？100001000（【解】每一像素所含有的信息量为log

1

7bit，每帧图像含有的信息量为31057bit2.1106bit广播员描此图像广播的息量是1 恰当描述此图像，广播员在口述中需用汉字的数目为：2.11061 个 xxpx3px11 2 1 4 2 4该信源的最大熵以及与最大熵有关的冗余度。【解】可知信源的最大熵为H0log21，此信源的极限熵为HH1

1log13log30.8114 4 4 4由冗余度的计算公式可得11H1H0 1XHX。【解】抛掷n次硬币就使其正面朝上的概率为121121n2pXn2则有11n1 1n nHX22 log222n2bitn1 n1X

0 1 2 3 3 1 1 1PX

8 4 4 8该信源产生一个由100个符号组成的消息序列，求该消息序列的平均自信息量。【解】首先计算该信源的信源熵HX3log31log11log11log18 8 4 4 4 4 8 81.9056由100个符号组成的消息序列的平均自信息量为：HX100100HX190.56bit单符号离散无记忆信源，消息符号有四种取值，出现的概率为：p0，p10.25，p20.25，p30.125，试用MATLAB建模此信源。【解】clearall;clc;p0=0.375;p1=0.25;p2=0.25;p3=0.125N=50000;x=randsrc(1,N,[0123;p0p1p2p3]); %%3N0=length(find(x==0));P0x=N0/N %%0N1=length(find(x==1));P1x=N1/N %%1N2=length(find(x==2));P2x=N2/N %%2N3=length(find(x==3));P3x=N3/N %%3习题3答案“36”“5”（2，3121【解】根据题意，同时扔两个正常的骰子可能呈现的状态数有36种，因为两骰子是独立的，又各面呈现的概率都是1/6，所以36种中的任一状态出现的概率相等，为1/36。3636363、6和6、3，所以IAlog2PAlog25B5以IBlog2PB（XXA（有36A1,26HXlog2365.17比特/符号(比特/状态)Z＝X+Y（z=2x=1y=1x=1y=2x=2y=1x=1y=3、x=2y=2、x=3Z

2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 5 4 3 2 1Pz所得

36 36 36 36 36 36 36 36 36 36 36HZPzg2Pz4t3611/361C则所以得

PC1136IClog

PClog111.71bit2 2已知信源间[XP]:x1 x2信道特性如图所示求在该道上输的平均信息 量。x1x2

0.98010.80【解】该信源的平均熵为HXH0.5,0.51bitsymbol信道转移概率为YX01x10.980.02x20.200.80信源和信宿符号之间的联合分布为YX01x1491001100x2110410故接收符号的概率为可得后验概率为

0

59100

，

41100p x

0pY1,09，p

xpY1,1XY 1

0

XY 1

41p x

0pY2,00，p

xpY2,XY

0

XY 2

41于是HXYpXY

pXY10pXY101

11pXY11

1,og pXY

2,0og

pXY

2,og

0.4552 pXYpXY20pXY2

IX;YHXHX|Y0.5448bitsymbol已知信源发出aapapa11 2 1 2 2p11p221p12p21I1;1和I1;2。【解】由题可得

pabpbapa1111 11 1 2pabpbapa112 21 1 2pabpbapa121 12 2 2pabpbapa1122 22 2 22pbpab121i1

i1 22pbpab122所以I1;1og

i1

i2 2pp11

p1p111

p1p1log211pp12

1log1bitI1;2og

p11

log

p2p1p2pXY11log2 1pXY112

bit判断题（1）HX0；（2）若X与Y独立，则HXHXY；（3）若X与Y独立，则HYXHXY；（4）如果HXYZ0，则要么HXY0，要么HXZ0；（5）IX;YIX;YZ；（6）HXX0；（7）IX;YHY；（8）HXYHX【解】XHX0。对。若XY相互独立,则

pxpx|y,因此对于任意y值均有HX|YyHX，所以HXHX|Y。X和YIX;Y0，IX;Y|ZHX|ZHX|YZ101，故IX;YIX;Y|Z。XY表示棋盘的横格，Z表示棋X|0HX|Y0HX|Z0。IX;YIX;YZIX;YZ0IX;YIX;YZ。(7)IX;YHYHY|ZHYHY|X0。(8)对。增加条件可以减少不确定性，HX|YHX|YZIX;Z|Y0。X,YYX0101/31/3101/3求：(1)(2)(3)(4)(5)

HX，HYHXY，HYXHXYHYHYXIX;Y【解】(1)由X，Y的联合概率分布函数，可以求得X和Y的概率分布为X01PX2/31/3Y01PY1/32/3于是可得(2)

HXHY23

2123 3

10.918bitsymbol23(3)

HXY1HX|Y02HX|Y10.667HYX3 3HXY31log31.585bitsymbol3 2(4)HYHYX0.251bitsymbol(5)IX;YHYHY|X0.251bitsymbol1 1 1 1 4 4 4 4 (1)

P0 1 0 01 0 0 1 0 1 0 1 0(2)

2 2 100 010 P2 001 00100100010100000010100【解】(1)参考例2-8的计算方法。可以求得12，46，230，故2 2Cg2006g569l2 2Clog23。Clog242。EE求信道容量C。【解】信道转移矩阵为

p001p00pE0

p010p111pE10 E 101 010 1 这是一个准对称信道，信道容量为Clog2H1log1log211100P0P110002【解】由题意可知该二元信道的转移概率矩阵为0.010.99P0.010.99 为一个BSC信道。所以由BSC信道的信道容量计算公式可得Clog2mHPlog22H0.99,0.0110.99log20.990.01log20.010.92bit/symbolC1C1000C0.92bit/st t1/21/31/6 P 1/31/61/2如果Px1，PxPx1，求最佳译码时的平均错误概率。1 2 2 3 4【解】假设输入符号集和输出符号集分别为x1,x2,x3和y1,y2,y3。按照最大似然译码规则，选择如下:Fy1x1、Fy2x2、Fy3x3平均错误概率为:

P11+1+11+1=1E 2362362 如果需要按照最小错误概率译码，需要首先求出其联合概率矩阵：1 1 14 6 12 1 1 1 24 8 121 1 1 1 1 112 24 8最小错误概率译码规则应如下：Fy1x1、Fy2x1、Fy3x3此时错误概率为：

++P1+1 1 1+1+111++E 12248121224 24一个饭店只提供馒头和包子，当顾客点菜时只需说“M”或者“B”就表示所需要的是馒头8%10%。请问：【解】0.08C10.08log

12

0.92log

12

0.5978bitsymbolHX

10.9log10.469bitsymbol20.1 2 HXC，因此在这个信道可以正确的传递Xx0x1P01/4和P13/4Y的符号集为{0,1}Py

|x9

，Py|x1

，Py

|x1和Py|x4。求：(1)(2)(3)【解】

HY；IX;Y；HY|X。

0 0

1 0

0 1 5

1 1 5(1)容易计算由于

11HXPiPi1i0

(比特/符号)P0,0P0P0|0P0,1P0P1|0P1,0P1P0|15P1,1P1P1|15P0P0,0P0,15P1P0,1P1,15因此1(2)可计算

HYPlogPi0

(比特/符号)HY|XPi,iPyj|i8（比特/）j因此IX;YHYHY

|X

0.297(比特/符号)(3)由(1)和(2)得

HX,YHXHY|X

(比特/符号)HX

|YHXIX;Y

(比特/符号)HY|XPi,iPyj|i8i,j

(比特/符号)x 1/2 Y1/21/21/21/21/21/2【解】信道传输矩阵如下

1 1 0 02 2 00 1 1 00 2 2 PY|X=0

1 12 21 1 0 0 2 2可以看出这是一个对称信道，m4，那么信道容量为11C H(,,0,0)22mlogmPyj|xilogPyj|ximj1log24

1 12?2log22log4log12 221bit 【解】由信道转移概率矩阵P12 2 1 1 2 1 2 1可知，此信道为准对称信道。因此，当pp1时达到信道容量输出端分布为0 1 2q111110 2 1 2 22 2 1q1

11

111 22

2q1

1 2 2 12所以CmaxIX;YxHYHY|X

21 10g01g1g112g1121g12g2log1log1 2 1 2 2 1 2 1 2P1p

p

2p 1p 2 试求信道容量值C。【解】由信道转移概率矩阵P1p

p

2p 1p 2 可知此信道为准对称信道，当心到输入为等概率分布时达到信道容量，所以CxIX;YxHYHY|X=21log12log2 2 2 2121plog1pplogp2log22=21log11plog1pplogp2 （1达到信道容量C时输入概率分布Px；（2）信道容量值C。x0 1-ɛ y0ɛx1 1 y1ɛx2

1-ɛ y2 00 1 0 0 1则信道输出端分布为

q0p01p0q21由信道容量定义知CxIX;YxHYHY|XxH0,1,20H,1101H,1xpxH0,1,211H,1令C0，则有p01g01g10110所以2p01p1令C0，则有p11logp11p1log1p0p11H0所以log

p11p11

H,11由联立方程组解得p10 H 221

Hp1

21

2Hp2

2211 H 221 令H221A则 1Aq0 1A（2）信道容量为

A2qA1qA 12 ACH0,1,211H,12log1A2logA2A A A A

2A

H,1习题4答案4-1设有一个离散无记忆信源Uu2 u3 u4 u5， P(U) 试分别求其二元霍夫曼编码和费诺编码，并求其编码效率。【解】霍夫曼编码：符号 0.4u2 0.2u3 0.2u4 0.1u5 0.1

0.4010.2010.20.2

编码过程01001010.40.2

00.610.4

码字001011010011霍夫曼编码的信源熵：5平均码长：编码效率：

H(U)p(ui)log2p(ui)2.12biti=1 5K p(ui)Ki2.2biti=1H(U)96.3%K费诺编码：其费诺编码如下图所示。信源符号ui符号概率p(ui)第1次分组第2次分组第3次分组次 码字分组码长u10.4001u20.20102u3u4u50.20.10.1110110310 111041 11114信源熵为平均码长为编码效率为

55H(U)p(ui)log2p(ui)2.12biti=1 5K p(ui2.2biti1H(U)96.3%Ku2 u3 u4 u5 u6 u7，P(U) 0.200.190.150.140.120.100.10 试求：H)；7【解】信源熵：7H(U)p(ui)log2p(ui)=2.76biti=1符号 u2 u3 u4 u5 u6 u7

0.20010.20010.190.1501

编码过程01001010.260.200.20

0010.40101

码字10000001010011110111平均码长：编码效率：

7K= p(ui=2.8biti=1H(U)98.57%K01201012012u1u2 1u3 2u4u6u7平均码长：编码效率：

7K= p(uii=1 H)Klog23

97.05%u2 u3 u4

u5 u6

u8，P(U) 0.30.20.150.150.050.050.050.05 8【解】两种霍夫曼编码的信源熵：8H(U)p(ui)log2p(ui)2.67biti=1平均码长：编码效率：

8K p(uii=1 H)Klog23

93.9%8 p(u)(KK)20.36（方法(a)）i ii18 2p(u)(KK)20.96

（方法(b)方差）i ii1符号 概率u2 u3 u4 0.05u6 u7 u8 u9

0.30.20.150.15010120.050.05

0.3010.2010.20.150.15

0.500120.30120.22

码字10001022122200201202(a)符号 概率u2 u3 u4 u5 u6 u7 u8 u9

0.30.20.150.15010120.050.05

0.30.2010120.150.15

0.5010.3110.22

码字120102001002000000010002(b)方法(a)(b)(a)(b)(a)u2 u3 u4 u5 u6 u7，P(U) 0.200.190.180.170.150.10 对其进行二进制香农编码。【解】信源符号ui符概率累概率-logp(u)码长 码字p(u) P 2 ii iu2u3u4u5u6u70.20 0 2.34 3 0000.19 0.2 2.41 3 0010.18 0.39 2.48 3 0110.17 0.57 2.56 3 1000.15 0.74 2.74 3 1010.10 0.89 3.34 4 11100.01 0.99 6.66 7 11111104-4【解】费诺编码如下：信源符号ui符号概率p(ui)第1次分组第2次分组第3次分组第4次分组码字 码长u10.2000 2u20.1900010 3u60.101100110 4u70.0110111 4u30.18010 2u40.17110110 31111 3u50.15200W，10B，10W，84B，1424W【解】应用表3-6，可以得到该扫描行MH码为192W 8W 10B 10W 64B 20B 1408W 16W EOL0000100 00001101000101010000000000001原一行为1728个像素，用“0”表示白，用“1”表示黑，需1728位二元码元。现MH码这行只需用71位二元码元。可见，这一行数据压缩比为1728:71=24，压缩效率很高。

UA B C， P(U) 试应用算术编码方法对序列CABA进行编码，并对结果进行译码。【解】编码过程：步骤输入符号 编码间隔 编码判决1 C 0.8,1

符号的间隔范围0.8,12 A 3 B 0.85,0.88

0.8,10.8,0.9

间隔的前五个1/10间隔的六七八个1/104 A 0.85,0.865

0.85,0.88

间隔的前五个1/10从 中选择一个数作为输出：0.85译码过程：步骤 间隔

译码符号

译码判决1 0.8,12 0.8,0.93 0.85,0.884 0.85,0.8655 CABA

0.85在间隔[0.8,1)0.85在间隔[0.8,1)前5个1/100.85在间隔[0.8,0.9)第6、7、8个1/100.85在间隔[0.85,0.88)前5个1/10

U0 1， P(U) 已知信源序列为1101110011…。0、10.5，15【解】(1)

F(S)

P(S) K(2)序列 F(S)

P(S)

K码字01010.25(0.01)0.7511110.4375(0.0111)0.5625111100.4375(0.0111)0.14063100(3)

10H) p(ui)log2p(ui) 1Kp(ui)Kii=1H(U)K4-9用Lempel-Ziv算法对输入数据流000010110011100001001101111进行编码。【解】整个字符串分拆如下：0，00，01，011，001，1，10，000，100，11，0111，1用短语可描述为：(000，0)，(001，0)，(001，1)，(011，1)，(010，1)，(000，1)，(110，0)，(010，0)，(111，0)，(110，1)，(100，1)，(000，1)因此，上述字符串编码之后变成了：000000100011011101010001110001001110110110010001字典如图所示：字典位置字典内容定长码字00100000010000010011010011100011011110100101011101000111110110010000000100100110011101010111101101101111001...10001已知一基带信号m(tcost2cost(t)m(t)择？0.2s【解】(1)m(t)的最高频率fH2Hz，由抽样定理知抽样频率为fs2fH4Hz，故抽样间隔Ts1/fs0.25s。(2)基带信号频谱为M(f)1[(f1)(f1)][(f2)(f2)]s 2当抽样间隔Ts0.2s时，抽样频率为fs5Hz，故理想抽样信号的频谱为 Ms(f)fs M(fnfs)5 M(f5n) MMs(f)52.52 0

f/Hz已知信号m(t)fm、1【解】已采样信号ms(t)为m(t)和矩形脉冲序列p(t)的乘积ms(t)m(t)p(t)其中p(t)g2ttn其频谱表达式为

Pf2Sa2ffsfnfs2fsSa2nfsfnfsn n 式中fs1Ts2fm MsfMf2fsSan2fsfnfs2fsSan2fsMfnfsn n设信号m(t)9AcostA10V。若m(t)40N和量化间隔v。【解】因254026，所以所需的二进制码组的位数N6，量化间隔v2A0.5V40习题5答案1357个错误的nknkp0.01【解】根据题目要求，可以选用8,7偶校验码或8,7奇校验码。设码字结构为,m7p,,m7其中p为校验符号,, ,为7消息符对偶检码它们之间关系为m7m1m7对于奇校验码，它们之间的关系为m7m1m7

p0p1p0.01PC2p21p6C4p41p4C6p61p2C8p8603nd 8 8 8 8如果某2412122位以上的错误。如果该码通过符号错误概率为103的信道传输，求该码的译码错误概率。【解】该码的译码错误概率为P4Ckpk1pkM 24k324 24 1C01p4C1p1p3C2p21p29024 24 103923位错误的92组错误概率又是多少？【解】1P2Ckpk1pk1C01p928.79102M 92 92k13位错误的92127P Ck

pk1p7-kM 127k41C0

1p7

p1p6C2

p21p5C3

p31p4706127 127 127 127某线性分组码的最小码距是【解】由题意可知dmin11。如果该码只用于纠错，则确保能够纠正的错误位数最多（即最大纠错能力）为tdmin152 如果该码只用于检错，则确保能够检测出的错误位数最多（即最大检错能力）为edmin110个错误、检测个错误（dmin1

10故可以采用下表中方案2~方案5之一来进行同时检错和纠错。方案1（用于纠错）55方案246方案337方案428方案519方案6（用于检错）010请分析5【解】该码的两个合法码字分别是00000和dmin5，故可以采纠错位数检错位数方案1（用于纠错）22方案2（同时用于纠错和检错）13方案3（用于检错）04讨论n5【解】以5,4偶校验码为例，显然该码有2416个码字，分别为00000，10001，，，，，01010，01100，00110，，，，，，可知该码的最小码距为dmin2dmine11个错误，355-7如果一个5-7如果一个7,4线性分组码的生成矩阵为111100010G1010001100101100001(1)求该码的所有码字； 确定该码的监督矩阵H；如果接收向量为r【解】(1)消息向量与其对应的码字向量如下表：序号消息向量m1,2,3,4码字向量c1,2,3,4,5,6,71000000000002000111000013001001100104001110100115010010101006010101101017011011001108011100001119100011110001010010011001111010100101012101101010111311000101100141101100110115111000111101611111111111(2)因为该系统码的生成矩阵为(2)因为该系统码的生成矩阵为1111000GPI4101010001100101100001故可知该码的监督矩阵为HI3

1001101 PT 0011110对于接收向量r100 001 srHT1101101111 101 011110因为伴随式不是零向量，故可知该接收向量不是一个合法码字。dmin3，所以可知dmin3tdmin112 因为dmin3edmin12，，p4式中mi表示消息符号，pi表示校验符号。向量向量【解】,cn,cn,p2,,nk,1,2, ,k1,2, ,kG校验比特消息比特c1,2,故结合题目中给出的校验关系，可得生成矩阵为于是监督矩阵为

11101000 1011010 01011100101101000110001101010010110010111000010111 H因为dminH距为dmin4。因此，该码可以确保能够纠正的错误位数最多为tdmin112 可以确保检测出的错误位数最多为edmin13对于接收向量110000100001000011110101101111101srHT10101010 00111 1该伴随式不是全0向量，表明该接收向量不是一个合法码字。对于接收向量1000 010 00100001srHT01011100 00002 2 1110 1011 1101该伴随式是全0向量，表明该接收向量是一个合法码字。1245,1345,1235,1234,1,2,3,4,5确定该码的n、kdmin。【解】111111100000110100011100100101000101100000111G011 1

01010010111001011101000111110Hn9，消息符合个数k5。因为dminH中dmin4。设计一个nk2dmin5【解】0（最小码距dmin消息向量m1,2码字向量c1,2,3,4,50000000010101110101101111101所以该码的最小码距为dmin3。注：其他满足条件的码字集合还有，，00000,01110,10011,11101，00000,01110,10101,11011。监督矩阵为

G10110010110101110100 H 010010000001011101101110100001010101011111100000100100110100111110010001111100101100101000000111111010101100001101100110011011000111010001110110010010110010010001111因为最小码距为dmin3tdmin112 可以确保检测出的错误位数最多为edmin12错误图样e1110011100010001seHTe 所以可得该码可纠正错误模式的伴随式查询表如下：错误图样伴随式0000000000001001000100100010010001000011100001101000111110010100给出5【解】该码只有两个码字，即00000和11111dmin5，故纠错能力为2。其标准阵列如下：000001111100001111100001011101001001101101000101111000001111000111110000101110100100110110100010111000110110010101010101100100110101100100111010001011110000011112【解】该码的消息向量和码字向量的对应关系如下表：消息向量m码字向量1,2,300001111标准阵列为0001110011100101011000115-13分别判断73、74和是不是完美码。7【解】对于码长为n7的码，错1位的错误图样个数为C11，错2位的错误图样个77数为C221。7先来考虑7,3码，该码的标准阵列中共有238列，2416行，故可以纠正的错误图1822再来考虑7,4码，该码的标准阵列中共有2416列，238行，故可以纠正的错误图样包括所有的错1位的图样，并且不能再包括其他图样，所以该码是一个完美码。对于码长为n15的码，错1位的错误图样个数为C115，错2位的错误图样个数为C152105。15,11码的标准阵列中共有2112048列，2416行，故可以纠正的错误图C15样包括所有的错1位的图样，并且不能再包括其他图样，所以该码是一个完美码。某0011 1001 1010 P1100 1110 1011 如果接收向量为r【解】0000000010110111110001010111101010100110110110011110001011100HInkPT000该码的标准阵列中包含共有204824161(3)接收向量r011111001011011对应的伴随式为srHT0110此外，容易验证对于陪集首e有eHT0110，所以e是可能cre011111011011011n7的循环码，并给出所有可能的nk值。(1) X4X31；(2) X4X21；(3)X4X3X1；(4)X4X2X1；(5)X5X31。【解】nk45、62或7,3码。对于n5，X51X4X31X1X3X，故不会是5,1码。对于n6，X61X4X31X2X1X3X2X，故不会是6,2码。对于n7，X71X4X31X3X2X1X2X，故不会是7,3码。综上可知，该式不能生成一个n7的循环码。nk45、62或7,3码。对于n5，X51X4X21XX3X1，故不会是5,1码。对于n6，X61X4X21X21，故可以生成6,2码。对于n7，X71X4X21X3XX1，故不会是7,3码。综上可知，该式可以生成一个6,2循环码。nk45、62或7,3码。对于n5，X51X4X3X1X1X3X2，故不会是5,1码。对于n6，X61X4X3X1X2X1，故可以生成6,2码。对于n7，X71X4X3X1X3X2XX1，故不会是7,3码。综上可知，该式可以生成一个6,2循环码。nk45、62或7,3码。对于n5，X51X4X2X1XX3X2X1，故不会是5,1码。对于n6，X61X4X2X1X21X3X，故不会是6,2码。对于n7，X71X4X2X1X3X1，故可以生成7,3码。综上可知，该式可以生成一个7,3循环码。nk56或72码。对于n6，X61X5X31XX4X1，故不会是6,2码。对于n7，X71X5X31X21X3X2，故不会是7,3码。综上可知，该式不能生成一个n7的循环码。gXX4X2X1的循环码，请使用多项式除法运算将消息向量m【解】由题意可知k3，n7。消息向量m对应的多项式为mXX21于是有gX，可得

XnkmXX4X21X6X4XnkmXX2gXX3X2于是pXXnkmXmodgXX3X2所以码字多项式为

cXXnkmXpXX6X4X3X2对应的码字向量为c1011100。gXX3X2X1的5m开关1开关1mX该编码电路在输入m10101下的状态变化如下表：

开关2时钟顺序输入序列寄存器内容输出010101000--1101011112101100031010114110105--0101在k5个移位时钟之后，寄存器中的内容便为nk3位的校验比特，接下来的3个移位时钟内，寄存器中的校验比特依次输出。所以最后可得码字向量为 c10101010消息比特校验比特接下来对上面的结果进行验证。消息向量m对应的多项式为mXX4X21于是有

XnkmXX3X4X21X7X5X3将上式除以gX，可得XnkmXX4X3X2XgXX于是pXXnkmXmodgXX所以码字多项式为

cXXnkmXpXX7X5X3X对应的码字向量为c10101010，与编码器输出一致。如果某5gXX10X8X5X2X1确定消息多项式mXX4X21（；判断多项式vXX14X8X6X41【解】开关1开关1mX对于消息多项式mXX4X21，有XnkmXX10X4X21X14X12X10XnkmXX41gXX9X8X6X4X2X1pXXnkmXmodgXX9X8X6X4X2X1cXXnkmXpXX14X12X10X9X8X6X4X2X1对应的码字向量为c101011101010111。对于多项式vXX14X8X6X41vXX4X21gXX9X7X4X3X显然余式不为0，所以可知该多项式不是一个码字多项式。gXX4X1的循环码。结合消息向量m【解】开关1开关1mX译码器结构如下图：11伴随式输出该编码电路在输入m时钟顺序输入序列寄存器内容输出0110101100110000--1110101100111001211010110010101311010110010104110101111100511010110111611010010117110111100811010111911100101010100111--11101k11nk44个移位时钟内，寄存器中的校验比特依次输出。所以最后可得码字向量为 c110011010110111

校验比特将上面得到的码字向量c时钟顺序输入序列寄存器内容0111011010110011000011110110101100110002111011010110011003111011010110011041110110101100115111011010101016111011010011071110110100118111011001019111011111010111011111111110001112111110113110010141100115--0000习题6答案gXX5X21来构造GF32，如果gXGF32的所有元素，要求同时给出幂、多项式和向量三种形式。幂形式多项式形式向量形式/00000003110000111000102200100330100044幂形式多项式形式向量形式/0000000311000011100010220010033010004410000521001016301010742101008321011019431101010411000111210011112320111013432111001443211110115432111111164311101117411001118100011192001102032011002143110002242110101233210111124432111102543111001264211011127310101128421011029310100130410010设计一个码长为n31且可以纠t2BCH【解】选取GF32上的一个本原元素，则该BCH码的生成多项式为gXMX,3X式中

X和

X分别是和3的最小多项式。先来求

X，因为是一个本原元素，所以满足2的最小整数为l5，于是该元素的共轭类为,2,4,8,16，对应的最小多项式为44Xi0

X2XX2X4X8X16再来求

X219X3X214X12X16X41419X312333X23117X15X16X416X3X230X15X16X516X4X330X215X16X4X317X215X31X5X21X，令3，可求得满足2的最小等式为l5，于是该元素的共轭类为,2,4,8,63,6,2,4,74XXXXXXX42i 3 6 12 24 17i0X2X9X24X5X17X44X3595X2613X14X17X430X39X228X14X17X530X49X328X214X17X416X326X214X31X5X4X3X21因此，该BCH码的生成多项式为gXX3XX5X21X5X4X3X21X10X9X8X7X5X7X6X5X4X2X5X4X3X21X10X9X8X6X5X31于是nk10，kn1021，因此该码是31,21BCH码。clc;closeall;clc;closeall;p=2;g=[101001];%GF(32)生成多项式a=[01];%alpha^1[quot,a_remd]=gfdeconv(a,g,p); a_dec=bi2de(a_remd);a2=[001];%alpha^2[quot,a2_remd]=gfdeconv(a2,g,p); a2_dec=bi2de(a2_remd);a4=[00001];%alpha^4[quot,a4_remd]=gfdeconv(a4,g,p); a4_dec=bi2de(a4_remd);a8=[000000001];%alpha^8[quot,a8_remd]=gfdeconv(a8,g,p); a8_dec=bi2de(a8_remd);a16=[00000000000000001];%alpha^16[quot,a16_remd]=gfdeconv(a16,g,p);a16_dec=bi2de(a16_remd);m=5;apoly=gf([1a_dec],m);%x+alpha bpoly=gf([1a2_dec],m);%x+alpha^2 cpoly=gf([1a4_dec],m);%x+alpha^4dpoly=gf([1a8_dec],m);%x+alpha^8 epoly=gf([1a16_dec],m);%x+alpha^16AA=conv(apoly,bpoly);BB=conv(AA,cpoly);CC=conv(BB,dpoly);DD=conv(CC,epoly)6-3对于题5-2中的BCH码，如果接收向量为r0000000000000000000011001001001，请使用Berlekamp-Massey算法来确定错误位置。【解】显然对应于接收向量r的接收多项式为rXX10X9X6X31于是可得伴随式为

1Sr109631310时，

Sr220181261623Sr3078911234Sr44036241211240X1d0S10

d

1,X11X0Xdd1XX13X1时，

01131dS1S

63301 2 1 1当2时，11 22311 2

2X1X13Xd2S3

2S

1619160

0,d

3,X13X2Xdd1XX213X1628X213X13X22当3时，1 233,3131 2d3S4

3S

3S

123136013 224X3X13X13X213 22所以，可得错误定位多项式为

X13X13X222F51个根为23和26。这两个根的逆便是错误位置数，分别为1

8

5，于是可知2错误比特的位置分别为j5和j8，错误多项式为eXX8X5，所以译码后恢复21 2的码字多项式为cXrXeXX10X9X8X6X5X31对应的码字向量是

c00000000000000000000111011010016-45-2BCHr，Berlekamp-Massey【解】显然对应于接收向量r的接收多项式为rXX30X29X28X10X9X8X6X5X31于是可得伴随式为1Sr0980986531132122118S2r20860862061975086206143+1424211163Sr390878430272418159132825223027241815913028272524221815913028272524221815913214214394Sr412011611240363224201214272319952420121272423201912951432432clc;clearall;p=2;m=5;ii=4;clc;clearall;p=2;m=5;ii=4;%allprimpolys=primpoly(m,'all');%AllprimitivepolysforGF(256)prim_poly=[101001];%AprimitivepolynomialforGF(256)fieldgftuple([-1:p^m-2]',prim_poly,p);%field中是\alpha的指数，‐1对应alpha^{‐inf}=0，0对应alpha^0=1.A=gfadd(mod(30*ii,31),mod(29*ii,31),field);B=gfadd(A,mod(28*ii,31),field);C=gfadd(B,mod(10*ii,31),field);Dgfadd(C,mod(9*ii31field);Egfadd(D,mod(8*ii31field);Fgfadd(E,mod(6*ii31field);G=gfadd(F,mod(5*ii,31),field);H=gfadd(G,mod(3*ii,31),field);I=gfadd(H,0,field)0时，

0X1d0S10

d

1,X11X0Xdd1XX18X1时，

01181dS1S168802时，1281

1 2 1 12X1X18Xd2S3

2S

981692420

0,d

8,X11 23X2Xdd1XX218X223X218X25X21 22当3时，1 238,31 2dS3S3S

9616

3 4 1 3 2 2

d14,

X18X172224X3Xdd1XX318X25X221718XX318X25X21918XX1819X2527X2127X30X2所以，可得错误定位多项式为

X127X30X2222F521个根为2和30。这两个根的逆便是错误位置数，分别为1

29和

，于是可知错误比特的位置分别为j1和j29，错误多项式为eXXX29，所以译码后恢1 2复的码字多项式为cXrXeXX30X28X10X9X8X6X5X3X1clc;clearall;p=2;m=5;%allprimpolys=primpoly(m,'all');%AllprimitivepolysforGF(256)prim_poly=[101001];%AprimitivepolynomialforGF(256)field=gftuple([-1:p^m-2]',prim_poly,p);%field中是\alpha的指数，‐1对应alpha^{‐inf}=0，0对应alpha^0=1.forii=-1:p^m-2G=gfadd(mod(ii+27,31),mod(2*ii+30,31),field);ifG==0fprintf('%d\n',ii);endend对应的码字向量是clc;clearall;p=2;m=5;%allprimpolys=primpoly(m,'all');%AllprimitivepolysforGF(256)prim_poly=[101001];%AprimitivepolynomialforGF(256)field=gftuple([-1:p^m-2]',prim_poly,p);%field中是\alpha的指数，‐1对应alpha^{‐inf}=0，0对应alpha^0=1.forii=-1:p^m-2G=gfadd(mod(ii+27,31),mod(2*ii+30,31),field);ifG==0fprintf('%d\n',ii);endend通过一个7BCH码来构造一个4【解】根据例5-8的结果可知，15,7BCH码的生成多项式为gXX3XX8X7X6X41该码的生成矩阵对应于下列多项式向量的系数：Xn1Xn1modgX Xn2Xn2modgX XnkXnkmodgX通过移除15,7BCH码生成矩阵的前三行可以便可得到12,4缩短码的生成矩阵，所以需要计算下面的多项式向量：Xn4Xn4modgX X11X11modgXGX Xn5Xn5modgX XGX Xn6Xn6modgX X9X9modgXXn7Xn7modgX X8X8modgX计算结果如下：

X11X3X21gXX4X3X21X10X2XgXX7X6X5X2XX9XgXX6X5X4X1X8gXX7X6X41故 X11X4X3X21 X10X7X6X5X2 GX1000010000001110010011100110010011100100011101000G

X9X6X5X4X1X8X7X6X41 10011136BCH59个7499个74563【解】36BCH5639个7,4码字分组最多纠正9个错误，但是只有当每个码字中出现1个错误比特536BCH9个7,4码字分组可以纠正5位随机错误的概率仅为87650.2561。94N72个错误（t2）RSN2m17可得m3K2mt13。选取F3元素gXXX2X3X4X24X3X26X1X43X3X2X3clc;clc;closeall;p=2;g=[1101];%GF(8)生成多项式a1=[01];%alpha^1[quot,a1_remd]=gfdeconv(a1,g,p); a1_dec=bi2de(a1_remd);a2=[001];%alpha^2[quot,a2_remd]=gfdeconv(a2,g,p); a2_dec=bi2de(a2_remd);a3=[0001];%alpha^3[quot,a3_remd]=gfdeconv(a3,g,p); a3_dec=bi2de(a3_remd);a4=[00001];%alpha^4[quot,a4_remd]=gfdeconv(a4,g,p); a4_dec=bi2de(a4_remd);m=3;apoly=gf([1a1_dec],m);%x+alpha^1bpoly=gf([1a2_dec],m);%x+alpha^2cpoly=gf([1a3_dec],m);%x+alpha^3dpoly=gf([1a4_dec],m);%x+alpha^4AA=conv(apoly,bpoly)BB=conv(cpoly,dpoly)CC=conv(AA,BB)N633（t3RSN2m163可得m6K2mt157。选取F26原元素，则生成多项式为gXXX2X3X4X5X6X27X3X29X7X211X11X419X341X224X10X211X11X659X548X443X355X210X21故可知NK6，于是K57，所以该码共有码字数量为6457，大约8.95910102。clc;closeall;p=2;clc;closeall;p=2;g=[1100001];%GF(64)生成多项式a1=[01];%alpha^1[quot,a1_remd]=gfdeconv(a1,g,p); a1_dec=bi2de(a1_remd);a2=[001];%alpha^2[quot,a2_remd]=gfdeconv(a2,g,p); a2_dec=bi2de(a2_remd);a3=[0001];%alpha^3[quot,a3_remd]=gfdeconv(a3,g,p); a3_dec=bi2de(a3_remd);a4=[00001];%alpha^4[quot