信息论与编码理论-第7章线性分组码-习题解答-20071206

信息论与编码理论

第7章 线性分组码

习 题

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

??11001?G??01101???0011? 1??（1）求系统生成矩阵；

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

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

（5）列出译码表，求收到r=11101时的译码步骤与译码结果。 2．设（7, 3）线性码的生成矩阵如下

?0101010?G???0010111?

?01101??10??（1）求系统生成矩阵；

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

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，计算伴随式，并求最有可能的发送码字。4．设(6, 3)线性码的信息元序列为x1x2x3，它满足如下监督方程组

??x1?x2?x4?0?x2?x3?x5?0 ??x1?x3?x6?0（1）求校验矩阵，并校验10110是否为一个码字；

（2）求生成矩阵，并由信息码元序列101生成一个码字。

1

信息论与编码理论

习题答案

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

?1G???0??011001101?01?? 11??（1）求系统生成矩阵；

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

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

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

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

?1?0???0?1?0???01001??1?0将第2、加到第31行1101???????????0111???00011??1?0将第3加到第2行 1101???????????0111???00011?1101??0111??

0011?1010??0111??得到线性码C的系统生成矩阵为

?10011?? GS??01010????00111??（2）码字c?(c0,c1,?,cn?1)的编码函数为

生成了的8个码字如下

c?f(m)?m0?10011??m1?01010??m2?00111?

信息元 系统码字 000 001 010 011 100 101 110 111 00000 00111 01010 01101 10011 10100 11001 11110 2

信息论与编码理论

(3) 最小汉明距离d=2，所以可检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

则译码表如下：

00000 00111 01010 01101 10011 10100 11001 11110 10000 10111 11010 11101 00011 00100 01001 01110 01000 01111 00010 00101 11011 11100 10001 10110 00001 00110 01011 01100 10010 10101 11000 11111 当接收到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、行3010111?????????001101???0001101??1?0交换第2、行3010111??????????101010???0001101?010111??101010??

001101?101010??010111??得到系统生成矩阵：

?1001101??

GS??0101010????0010111??3

信息论与编码理论

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

T?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。又因伴随式有24=16种组合，差错图样为1的有???7种，

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

?2?随表如下：

伴随式 0000 1101 1010 0111 1000 0100 0010 0001

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

陪集首 0000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001 伴随式 0101 1001 1111 1100 1110 1011 0011 0110 陪集首 1001000 1000100 0011000 0001100 0100100 0100001 0010100 0000110 ?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直接得出：

4

信息论与编码理论

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

c?f(m)??100101???001110???101011?

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

?1?0??1rHT??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种情况，则计算伴随式得到伴随表如下：

伴随式 陪集首 000 101 011 110 100 010 001 111 000000 100000 010000 001000 000100 000010 000001 100010 伴随式（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?036?1（1）求校验矩阵，并校验10110是否为一个码字； （2）求生成矩阵，并由信息码元序列101生成一个码字。 解：

5

信息论与编码理论

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

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

（2）由G?[In?k,Ak?(n?k)],H?[Ak?(n?k),In?k]，则生成矩阵为：

T?100101???G?010110?GS ????001011??信息码元序列M=（101），由c=mGs 得码字为c：

c?m0?100101??m1?010110??m2?001011???101110?

6

本文来源：https://www.bwwdw.com/article/38zf.html