检错与纠错原理的分析介绍

实现差错控制，首先是能够检查出错误。常用的办法是在传递的信息位之后，按一定的规则附加几位监督位。接收端检查收到的码序列是否符合预先约定的规则，从而发现有无错误。

（1）垂直奇偶校验。以8位二进制码为例，每传送7个信息位之后，接着传送一个偶校验码位。如果前7位中的“1”的个数是偶数，则第8位是“0”；如果前7位中“1”的个数是奇数，则第8位是“1”。这样使整个字符代码中“1”的个数为偶数。接收端如检测到某字符代码中：“1”的个数不是偶数，即可判断为错码。显然，如果有两位错码，就无法发现错误。其关系如表1-1所示。

表1-1　垂直奇偶校验

（2）水平奇偶校验。水平奇偶校验，是将数据以适当的长度划分成组，然后对水平方向的码元进行偶监督，排列如表1-2的形式。发码按列的顺序发送，最后传送一列是校验码。

表1-2　水平奇偶校验

（3）水平垂直奇偶校验。水平垂直奇偶就是同时对水平方向和垂直方向进行水平偶校验和垂直偶校验，见表1-3。垂直校验与水平校验两者结合起来，就会使错码的漏检率降低。

表1-3　水平垂直奇偶校验

（4）线性分组码。线性分组码是将信息序列分组处理，设有长度为k位的信息组。后面附加r位监督码，就组成总长度为n=k+r的码组，或叫码字，其信息意义可有2k种组合，称为（n，k）分组码。分组码中监督位r越长，纠错能力越强，但编码率就越低。

线性分组码是指码字中的信息组与监督位是线性关系，因为它的监督码是由一组线性方程式计算出来的。设（7，3）线性分组码的7位用C6～C0表示。其中前3位C6～C4是信息位，后4位C3～C0是监督位。它们之间的“模2运算”的关系满足下列线性方程组

需注意的是，式（1-7）运算法是在二进制“1”和“0”之间进行“模2运算”。若上面方程已知信息位（C6C5 C4=101），则用模2运算规则可算出监督位为

计算后整个线性分组码字是（1010011）。按这种规则组成的（7，3）线性分组码见表1-4，共有8种正确的组合称为“许用码字”。其余的任何组合称为“禁用码字”。接收端如果发现了禁用码字，就判为错误。

表1-4　（7，3）线性组码

在分组码中将码字“1”的数目称为码字重量，简称“码重”。同一分组码中任意两个码字对应位上码元不相同的位数称为码字的距离，简称“码距”。同一分组码的任意两个码字的距离有多有少，其中最少者称为该分组码的“最小码距”，又称海明码距。它与检错、纠错能力密切相关。

接收端将收到的数字序列与由“许用码字”组成的“码字典”顺序比较，若发现是禁用的码字即判为错误。常用的纠错方法是采用“最大似然译码原则”，即收到的错误数字序列与哪一个许用码字的距离最小，就把它纠正为这个许用码字。

因此，（7，3）线性分组码不仅能够纠错，还有纠正1位错误码元的能力。(www.xing528.com)

（5）循环码。循环码是线性分组码中的另一类，它是在严密的代数理论基础上建立起来的。其编码和译码设备比较简单，检错与纠错能力较强，所以得到了广泛应用。

循环码除了具有多线性码的一般性质外，还具有循环性，即循环码中任一码字循环一位以后，仍是该循环码中的一个码字。表1-5列出的（7，3）循环码中，若将第2码字第1码元“0”移至最末尾，就变成了第3码字。它的最小码距为4，有一位纠错能力。

表1-5　循环码

设（n，k）循环码的信息有k位，记为M，校验位有n-k=r位，记为R。编制循环码的步骤为：

1）由M得出对应的信息多项式M（X），即

M（X）=A1 XK-1+A2 XK-2+…+AK-1 X1+AK X0

其中的系数A1～AK就是信息组的各个位，即M=（A1～AK）。

2）做乘法M（X）Xr。

3）求（n，k）循环码的生成多项式G（X）。G（X）由式Xn+1进行因式分解而得出。G（X）的阶为r。G（X）可能有多种形式。

4）做除法M（X）Xr/G（X），除法的余式即为R（X），由R（X）得到校验位R。

5）发送码字的信息多项式为F（X），即

F（X）=M（X）Xr+R（X）

6）由F（X）即得到发送的码字F，F也等于信息位M后加上校验位R。

【例1-1】 计算表1-5（7，3）循环码表中第4行信息组（101）的校验位R。

解：M=（101），M（X）=1×X2+0×X1+1×X0=X2+1

M（X）×Xr=（X2+1）×X4=X6+X4

G（X）是Xn+1=X7+1的一个因式，G（X）应为4阶。

X7+1=（X+1）（X3+X+1）（X3+X2+1），所以G（X）=X4+X2+X+1（因式分解时右侧各项展开以后合并同类项是相应系数的模2加法运算）。做除法R（X）=X3+X2，由R（X）得到R=（1100）。

发送码字的信息多项式为F（X）=M（X）X4+R（X）=X6+X4+X3+X2，由F（X）得到F=（1011100）。

它正好是M=（101）与R=（1100）的组合。