信息论与纠错编码题库.doc

第八章 线性分组码

8.1 什么是检错码？什么是纠错码？两者有什么不同？
答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。

8.2 试述分组码的概念，并说明分组码的码率r的意义。
答：分组码是把信息序列以每k个码元分组，即每k个码元组成一个信息组。n表示码长,k表示信息位的数目，码率r=k/n，它说明在一个码字中信息为所占的比重。

8.3 什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？
答：线性分组码的2个码字将组成n维向量空间的一个k维子空间，而线性空间可由其基底张成，因此线性分组码的 个码字完全可由k个独立的向量组成的基底张成。设k个向量为

　　（7.3-2）
　　将它们写成矩阵形式：

（7.3-3）
　（n,k）码中的任何码字，均可由这组基底的线性组合生成。即
　 C=MG=(mk-1,mk-2,m0)G
式中 M=(mk-1,mk-2,m0)是k个信息元组成的信息组。这就是说，每给定一个信息组，通过式（7.3-3）便可求得其相应的码字。故称这个由k个线性无关矢量组成的基底所构成的k×n阶矩阵G为 码的生成矩阵（Generator Matrix）。
H=
校验矩阵H的每一行代表求某一个校验位的线性方程的系数(n-k)线性分组码有r=n-k个校验元，故须有r个独立的线性方程，因此H矩阵必由线性无关的r行组成，是一个(n-k)×n阶矩阵，一般形式为

一个（n,k）线性分组码生成矩阵有k行n列校验矩阵有(n-k)行n列。

8.4 什么样的码成为系统码？系统码的生成矩阵和校验矩阵在形式上有何特点？
答：若信息组为不变的形式，称在码字的任意k位中出现的码为系统码；一个系统码的生成矩阵G，其左边k行k列是一个k阶单位方阵，系统码的校验矩阵H，其右边r行r列组成一个r阶单位方阵。

8.5 什么是对偶码？试举例说明之。
答：若把（n,k）码的H矩阵看成是(n,r)码的生成矩阵Gd,而（n,k）码的G矩阵就是（n,r），码的校验矩阵Hd,则称这两种码为互为对偶码。例如课本列举的（7，3）码
Gd=H=

8.6 试述码的距离和重量的概念。线性分组码的最小距离有何实际意义？
答：两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离用d(c1,c2)表示。码字中非零码元的个数，称为该码子的汉明重量，简称重量，用w(c)表示。一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。

8.7 如果要构造一个能纠2个错的线性分组码，则其H矩阵中至少应保证多少列线性无关？
答：4列 根据定理8.2检测e个错，则要求码的最小距离d大于等于e+1
纠正t个错，则要求码的最小距离d大于等于2t+1
纠正t个错误同时检测e个错误，则要求d大于等于t+e+1
而根据定理8.3 （n,k）线性分组码有最小距离为d的重要条件是H矩阵中任意d-1列线性无关
所以是4列
8.8 什么是接收序列y的伴随式s？为什么伴随式s只由错误图样e决定？
答：令

其中y为接收码字e为接收图样，称s为接收序列的伴随式。由式可知若e=0，则s=0;若
e≠0,则s≠0,因此伴随式s只由错误图样e决定。

8.9 如何构造一个码的标准阵列？标准阵列有哪些性质？
答：先把子群中的全部个码字,,```,置于表的第一行，并把该子群的加法恒等元==0(即全零码字放在行的首位)在余下的-个n重中，选择一个n重作为第二行得首位元素，意识第二行的元素是和每个码字（i=1,2,```, ）相加，并把+置于的下面即同一列。第三行再从其余的n重 中选择一个作为首位元素，同理将+置于的下面完成第三行。以此类推，一直将n重用完为止。
如下表：
许用码字
=
（陪集首）

…

禁
用
码
字

…

+
+
…
+
+
+
…
+

+
+
…
+
标准阵列的性质有：
如果把陪集看成是错误图样，则每一个陪集中具有相同的错误图样。
每一个陪集中的个n重都有相同的伴随式而不同的陪集具有不同的伴随式。
对于同一列的各子集, ,… , 来说，其中个n重得错误图样虽然不同，但全部对应于同一许用码字。

8.10 如何利用标准阵列译码？为什么说用标准阵列译码时，译码错误概率的大小与陪集首的选择有关？
答：当输入译码的接收序列为y时，经查表总能确定y落在标准阵列的第j行第i列，译码器就能判定发送码字是第i列（即子集）所对应的许用码字而粗我图样即第j行所在陪集的陪集首
用上述方法译码时，译码正确的概率大小与陪集首的选择有关。显然任意选择陪集首不是好的方法。根据最大似然译码准则，重量最轻得错误图样产生的可能性最大，所以应选优先择重量小的n重作为陪集首，这样构造的译码表，可使+与之间的激励最小，从而使译码器以更大的概率正确译码，这就是最小译码距离。

8.11 什么是完备码？为什么说汉明码是完备码？
答：如果某一（n，k）线性分组码能使
=++…+
成立，即错误图样正好等于伴随式数目，则称这种码为完备码。
显然，汉明码是t=1完备码。

8.12 某分组码的校验矩阵为
H =
求：（1） n = ？k= ？该码的码字有多少？
（2） 该码的生成矩阵；
（3） 矢量010111和100011是否为码字。
解：（1）n=6,k=3,该码有8个码字。
（2）由校验矩阵可得
++=0
++=0
++=0
所以
=
=
=
= +
= +
=+
由此可得生成矩阵为：

（3）经验证，010111不是码字，100011是码字。

8.13 某二元（n，k）系统线性分组码的全部码字如下
00000 01011 10110 11101
求：（1） n = ？k= ？
（2） 码的生成矩阵G和校验矩阵H。
解：（1）n=5，k=2。
根据码字可以得n=5，又因为总共4个码字，说明信息位有2位，即k=2。
（2）码的生成矩阵G=，校验矩阵H=。
=·G，且G = [ : P],根据全部的码字可以得出P。进而可以得到G。
又H =[ : ] ，从而推出矩阵H。其中、为单位矩阵

8.14 已知一个线性分组码的校验矩阵为
H=
试求其生成矩阵。当输入信息序列为 1001 1100 1101时，求编码器输出的码字序列。
解：生成矩阵G=

输出的码字序列为：1001100,1100110,1101001。
根据G = [ : P]，H =[ : ]的关系，由H矩阵可以写出G矩阵。
又由 =·G可以分别得出信息序列为1001,1100,1101的码字分别为：
1001100,1100110,1101001。

8.15 设一个（7，4）分组码的生成矩阵为
G=
求：（1） 该码的全部码字
（2） 码的标准序列
（3） 码的简化译码表
答：
(1)

信息组
码字
0000
0000000
0001
0001110
0010
0010011
0011
0011101
0100
0100101
0101
0101011
0110
0110110
0111
0111000
1000
1000111
1001
1001001
1010
1010100
1011
1011010
1100
1100010
1101
1101100
1110
1110001
1111
1111111
（2）标准矩阵列
信息组m
0000
0001
0010
0011
0100
0101
0110
0111
许用码字c
0000000
0001110
0010011
0011101
0100101
0101011
0110110
0111000
有
单
错
的
n
重
0000001
0001111
0010010
0011100
0100100
0101010
0110111
0111001
0000010
0001100
0010001
0011111
0100111
0101001
0110100
0111010
0000100
0001010
0010111
0011001
0100001
0101111
0110010
0111100
0001000
0000110
0011011
0010101
0101101
0100011
0111110
0110000
0010000
0011110
0000011
0001101
0110101
0111011
0100110
0101000
0100000
0101110
0110011
0111101
0000101
0001011
0010110
0011000
1000000
1001110
1010011
1011101
1100101
1101011
1110110
1111000

信息组m
1000
1001
1010
1011
1100
1101
1110
1111
许用码字c
1000111
1001001
1010100
1011010
1100010
1101100
1110001
1111111
有
单
错
的
n
重
1000110
1001000
1010101
1011011
1100011
1101101
1110000
1111110
1000101
1001011
1010110
1011000
1100000
1101110
1110011
1111101
1000011
1001101
1010000
1011110
1100110
1101000
1111001
1111011
1001111
1000001
1011100
1010010
1101010
1100100
1110001
1110111
1010111
1011001
1000100
1001010
1110010
1111100
1100001
1101111
1100111
1101001
1110100
1111010
1000010
1001100
1010001
1011111
0000111
0001001
0010100
0011010
0100010
0101100
0110001
0111111

（3）译码表
伴随式s
错误图样（陪集首）e
000
0000000
001
0000001
010
0000010
100
0000100
110
0001000
011
0010000
101
0100000
111
1000000

8.16 构造8.15题中（7,4）分组码的对偶码，构造其系统码形式的G矩阵和H矩阵，并写出全部码字。
答：
G矩阵

码字：
信息组
码字
000
0000000
001
1110001
010
1011010
011
0101011
100
1101100
101
0011101
110
0110110
111
1000111

8.17 某（5,2）线性分组码的H矩阵
H =
求：（1）该码的G矩阵
（2）该码的标准阵列
（3）该码的简化译码表
（4）说明该码是否为完备码

答：（1）由H矩阵的形式可知，该线性分组码为系统码 根据系统码可知
H =[P : ] G = [ : ] 、为单位矩阵
所以可以求出 G =
（2）根据题意（5,2）的线性分组码可以知道 信息组 m = 然后 根据c = m G可以求出c = * =
所以 根据标准阵列的定义有
信息组m
00
01
10
11
许用码字c
00000
01101
10111
11010
有
单
错
的
n重
00001
01100
10110
11011
00010
01111
10101
11000
00100
01001
10011
11110
01000
00101
11111
10010
10000
11101
00111
01010
有两错的n重
00011
01110
10100
11001
00110
01011
10001
11100
有三错的n重
00111
01010
10000
11101
(3)由标准阵列可以得到错误图样表（陪集首） 与 其伴随式 s = . 根据公式计算有
伴随式s
错误图样（陪集首）e
000
00000
001
00001
010
00010
100
00100
101
01000
111
10000
011
00011
110
00110
（4）不是完备码
根据（2）（3）可以知道伴随式数目为 = 8（个） 又由于完备码的概念是使得
的= 成立
表示错误个数小于等于t的错误图样数
根据（2）（3）可以知道 明显e的个数大于伴随式的个数 所以不相等 也就是说明
改码不是完备码

8.18 试构造GF（2）上的（15,11）汉明码。求出其系统码形式的H矩阵和G矩阵

答：取 r = 4构造GF（2）上的（15,11）的汉明码。
当r = 4时，有15个非全0的四重，即
（0001）（0010）（0100）（1000）（0011）
（0101）（0110）（0111）（1001）（1010）
（1011）（1100）（1101）（1110）（1111）
构成H矩阵

根据H矩阵和G矩阵的关系以及系统码的概念有
H =[P : ] G = [ : ]

、为单位矩阵
所以有G矩阵