线性分组码-习题

1. 已知一个(5, 3)线性码C的生成矩阵为：

⎡1G=⎢⎢0

⎢⎣0

110

011

01⎤

01⎥⎥ 11⎥⎦

（1）求系统生成矩阵；

（2）列出C的信息位与系统码字的映射关系；

（3）求其最小Hamming距离，并说明其检错、纠错能力； （4）求校验矩阵H；

（5）列出译码表，求收到r=11101时的译码步骤与译码结果。 解：

（1）线性码C的生成矩阵经如下行变换：

⎡⎢11001⎤⎡1

0011⎤

⎢01101⎥将第2、加到第31行

⎢01101⎥⎢⎣00111⎥−−−−−−→⎥⎢

⎦⎢⎣0

0111⎥⎥⎦

⎡⎢10011⎤⎡0011⎤

⎢01101⎥将第3加到第2行

⎢1

01010⎥⎢⎣00111⎥−−−−−−→⎥⎢

⎦⎢⎣00111⎥⎥⎦

得到线性码C的系统生成矩阵为

⎡10011⎤GS=⎢⎢01010⎥ ⎢00111⎥

⎣⎥⎦

（2）码字c=(c0,c1, ,cn-1)的编码函数为

c=f(m)=m0[10011]+m1[01010]+m2[00111]生成了的8个码字如下

(3) 最小汉明距离d=2，所以可检1个错，但不能纠错。

1

(4) 由G=[In-k,Ak⨯(n-k)],H=[Ak⨯(n-k),In-k]，得校验矩阵

T

⎡11110⎤H=⎢⎥

10101⎣⎦

(5) 消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列

c0=00000, c1=00111,c2=01010, c3=01101, c4=10011, c5=10100,c6=11001, c7=11110

则译码表如下：

当接收到r =(11101)时，查找码表发现它所在的列的子集头为(01101)，所以将它译为c=01101。

2．设（7, 3）线性码的生成矩阵如下

⎡0101010⎤

⎥

G=⎢0010111⎢⎥

⎢⎣1001101⎥⎦

（1）求系统生成矩阵；

（2）求校验矩阵； （3）求最小汉明距离； （4）列出伴随式表。 解：

（1）生成矩阵G经如下行变换

⎡0⎢0⎢⎢⎣1⎡1⎢0⎢⎢⎣0101010⎤⎡1

⎢0交换第1、行3

010111⎥−−−−→⎥⎢

⎢001101⎥⎦⎣0

001101⎤⎡1

⎢0交换第2、行3

010111⎥−−−−−→⎥⎢

⎢101010⎥⎦⎣0001101⎤

010111⎥⎥101010⎥⎦

001101⎤101010⎥⎥010111⎥⎦

得到系统生成矩阵：

⎡1001101⎤

⎥

GS=⎢0101010⎢⎥

⎢⎣0010111⎥⎦

（2）由G=[In-k,Ak⨯(n-k)],H=[Ak⨯(n-k),In-k]，得校验矩阵为

T

2

⎡1⎢1H=⎢

⎢0⎢⎣1101000⎤010100⎥⎥ 110010⎥

⎥

010001⎦

（3）由于校验矩阵H的任意两列线性无关，3列则线性相关，所以最小汉明距离d=3。 （4）（7, 3）线性码的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列：c0=0000000，c1=0010111，c2=0101010，c3=0111101，c4=1001101，c5=1011010，

⎛7⎫c6=1100111，c7=1110000。又因伴随式有2=16种组合，差错图样为1的有 ⎪=7种，

⎝1⎭

4

⎛7⎫TT

差错图样为2的有 ⎪=21种，而由Hr=He，则计算陪集首的伴随式，构造伴

⎝2⎭

随表如下：

3．已知一个(6, 3)线性码C的生成矩阵为：

⎡1 0 0 1 0 1⎤

⎥.G=⎢0 1 0 0 1 1⎢⎥

⎢⎣0 0 1 1 1 0⎥⎦

（1） 写出它所对应的监督矩阵H；

（2） 求消息M=(101)的码字；

（3） 若收到码字为101010，计算伴随式，并求最有可能的发送码字。 解：

（1）线性码C的生成矩阵G就是其系统生成矩阵GS，所以其监督矩阵H直接得出：

⎡101100⎤

⎢⎥H=011010 ⎢⎥⎢⎣110001⎥⎦

3

（2）消息M=(m0,m1,m2)=(101)，则码字c为：

c=f(m)=[100101]+[001110]=[101011]

（3）收到码字r=(101010)，则伴随式

⎡1⎢0⎢⎢1T

rH=(101010) ⎢

⎢1⎢0⎢⎣001⎤11⎥⎥10⎥

⎥=(001) 00⎥10⎥

⎥01⎦

又（6, 3）线性码的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得码字序列：c0=000000，c1=001110，c2=010011，c3=011101，c4=100101，c5=101011，c6=110110，c7=111000。伴随式有23=8种情况，则计算伴随式得到伴随表如下：

伴随式（001）对应陪集首为（000001），而c=r+e，则由收到的码字r=(101010)，最有可能发送的码字c为：c=（101011）。

4．设(6, 3)线性码的信息元序列为x1x2x3，它满足如下监督方程组

⎧x1+x2+x4=0

⎪

⎨x2+x3+x5=0 ⎪x+x+x=0

36⎩1

（1）求校验矩阵，并校验10110是否为一个码字； （2）求生成矩阵，并由信息码元序列101生成一个码字。 解：

（1）由监督方程直接得监督矩阵即校验矩阵为：

4

⎡110100⎤⎢⎥H=011010 ⎢⎥⎢⎣101001⎥⎦

因为收到的序列10110为5位，而由（6, 3）线性码生成的码字为6位，所以10110不是码字。

（2）由G=[IT

n-k,Ak⨯(n-k)],H=[Ak⨯(n-k),In-k]，则生成矩阵为：

⎡100101G=⎢⎤⎢010110⎥=GS ⎢011⎥⎣001⎥⎦

信息码元序列M=（101），由c=mGs 得码字为c：

c=m0(100101)+m1(010110)+m2(001011)=(101110)

5