教材习题详解：9.2码距、监督矩阵及纠错码

时间：2023-06-23 理论教育版权反馈

【摘要】：故此码若用于检错，最多能检测3位错误；若用于纠错，最多能纠正1位错误。两个码字之间的码距即为（7，1）重复码的最小码距，因此d0=7。首先将第3、4行加到第2行得此矩阵不是典型监督矩阵，需将其转换为典型监督矩阵。若信息位全为“1”，求监督码元。检验0100110和0000011是否为码字，若有错，请指出错误并加以纠正。

1.设有一个码，它有三个码字，分别是（001010）、（111100）、（010001）。若此码用于检错，能检出几位错误？若此码用于纠错，能纠正几位错误？若此码同时用于纠错和检错，各能纠、检几位错误？

解：设三个码字分别表示为A₀=[001010]，A₁=[111100]，A₂=[010001]。两两码字之间的距离为： d（A₀，A₁）=W（A₀+A₁）=4

d（A₀，A₂）=W（A₀+A₂）=4

d（A₁，A₂）=W（A₁+A₂）=4

显然，此码的最小码距d₀=4。

（1）此码用于检错，能检测e≤（d₀-1）=3位错误。

（2）此码用于纠错，能纠正t≤（d₀-1）/2=1.5位错误，取整数，因此可纠一位错误。

（3）此码用于检错且纠错时，能检和能纠的个数e和t与最小码距之间应有如下关系：

d₀≥e+t+1 （e＞t）

可见，当d₀=4时，有4≥2+1+1，得e=2，t=1。即同时用于检错和纠错时，纠一位错误的同时最多能检两位错误。

2.已知（7，3）线性分组码的生成矩阵为

求：

（1）所有的码字。

（2）监督矩阵H。

（3）最小码距及纠、检错能力。

（4）编码效率。

解：（1）生成矩阵G有3行7列，可见k=3，n=7，r=n-k=7-3=4。

将信息矩阵M=[000]～[111]代入A=M·G即可求得所有码字为

（2）由于G=[I₃P^T]=[I_kP^T]是一个典型生成矩阵，其中

，由此得到

代入典型监督矩阵H=[PI_r]=[PI₄]求得

（3）码字集中除全0码字外，最小码字重量即为码的最小码距。可见，该码的最小码距d₀=4。故此码若用于检错，最多能检测3位错误；若用于纠错，最多能纠正1位错误。

（4）编码效率为：η=k/n=3/7

3.对（7，1）重复码，求：

（1）全部码字。

（2）最小码距。

（3）用于纠错，最多能纠几位错误？

（4）用于检错，最多能检几位错误？

解：（1）（7，1）重复码的每个码字中有1个信息码元，6个监督码元，且每个监督码元与信息码元相同。故（7，1）重复码有两个码字，分别为0000000和1111111。

（2）两个码字之间的码距即为（7，1）重复码的最小码距，因此d₀=7。

（3）此码用于检错，能检的错误数e≤d₀-1=7-1=6。可见，最多能检6位错误。（4）此码用于纠错，能纠的错误数。可见，最多能纠正3位错误。

4.已知（7，3）分组码的监督关系式为

求其监督矩阵H、生成矩阵G、全部系统码字、纠错能力及编码效率η。

解：将监督方程组写成矩阵的形式

得监督矩阵为

此矩阵不是典型监督矩阵，需将其转换为典型监督矩阵。首先将第3、4行加到第2行得

再将第2、3行加到第1行，得典型监督矩阵为

根据G=[I₃P^T]求得典型生成矩阵为

把由3位信息组成的信息矩阵逐个代入A=M·G，求得全部系统码字为

在线性分组码中，最小码距等于最小码重（除全0码字），即d₀=minW（A_i）=3。代入，可见此码最多能纠一位错误。

编码效率为

5.汉明码的监督矩阵为

（1）求码长n和码字中的信息位数k。

（2）求编码效率η。

（3）求生成矩阵G。

（4）若信息位全为“1”，求监督码元。

（5）检验0100110和0000011是否为码字，若有错，请指出错误并加以纠正。

解：（1）监督矩阵H的行数等于监督元的个数，列数等于码字的长度。根据给定的监督矩阵可知n=7，r=3，k=7-3=4。

（2）编码效率。

（3）此汉明码监督矩阵具有H=[PI₃]形式，是典型监督矩阵，其中

由此可得典型生成矩阵为

（4）当信息M=[1111]时，码字A=M·G=[1111111]，可知监督码元（码字的最后3位）为111。

（5）当接收B=[0100110]时，由公式S=BH^T求得其伴随式为

可见，接收码字B=[0100110]为此（7，4）汉明码的一个码字。

用同样的方法得到接收B=[0000011]的伴随式为(www.xing528.com)

由于伴随式不为0，故B=[0000011]不是此（7，4）汉明码的一个码字，它是某个码字和错误图样的叠加。

要找出B=[0000011]中的错误，必须先找出所有单错误的7个错误图样与伴随式之间的关系。由S=EH^T得伴随式与错误图样间的关系为

E₁=[1000000]⇒S=[111]

E₂=[0100000]⇒S=[110]

E₃=[0010000]⇒S=[101]

E₄=[0001000]⇒S=[011]

E₅=[0000100]⇒S=[100]

E₆=[0000010]⇒S=[010]

E₇=[0000001]⇒S=[001]

由此可见，S=[011]对应的错误图样为E₄=[0001000]，即接收码字B=[0000011]中第4位（从左起）有错。纠错后的码字为A=B+E₄=[0000011]+[0001000]=[0001011]。

6.一码长n=7的汉明码，监督位数r为多少？信息位数k为多少？编码效率η为多少？试设定一种伴随式与错误图样的对照表并写出监督码元与信息码元之间的关系式。

解：汉明码的监督码元个数r与码长n之间满足

n=2^r-1

由n=7得r=3，信息元个数k=n-r=7-3=4。

编码效率。

要求监督关系方程组，必须先求出监督矩阵H。由于H^T中的每一行都是一个伴随式，第一行对应错误图样E₁=[1000000]，第二行对应错误图样E₂=[0100000]，以此类推。（7，4）汉明码的监督矩阵H有3行7列，因此H^T有3列7行，每一行由3位二进制码元构成。3位二进制码元不同的组合共有8种，去掉000，其余7种与7个错误图样的伴随式对应，它们之间的各种一一对应关系都可以。但我们可选择一种能导出典型监督矩阵的对应关系，即错误图样E₅=[0000100]对应S=[100]，E₆=[0000010]对应S=[010]，E₇=[0000001]对应S=[001]，其余E₁～E₄与[111]、[110]、[101]、[011]之间可任意对应。可选择如下的对应关系：