差错控制码编码原理

编码原理：

（1）将整个发送的数据块分为定长为m的n个组，一般m为字符位数或位数的倍数，一组称为一个码字。

（2）每组末位按“1”的个数位奇数或者偶数的规律加一个校验位（），使得每组包括校验位在内“1”的个数为奇数或偶数。为偶数的称为偶校验，为奇数的称为奇校验。

（为一个比特位，运算为二进制运算）

校验位计算为：

偶校验    

奇校验    

举例说明：

每一列代表一个码字：  

偶校验计算的校验位为： 

奇校验计算的校验位为： 

校验能力：只能检测每列码字中的奇数个错误，所有偶数个错误全部漏检。

实现方法：用硬件和软件均可，可以边发送边产生冗余位，接收时可以边接收边去掉冗余位。

2．水平奇偶校验码

编码原理：

（1）将整个发送的数据块分为定长为m的n个组，一般m为字符位数或位数的倍数，一组称为一个码字。

（2）将n个码字排成一个矩阵，对各个码字相应横向位进行奇偶校验。（校验位的生成与垂直奇偶校验码生成方式一致）。

偶校验    

奇校验    

（3）发送时将所有码字发送完后发送校验位。

举例说明：                     奇 偶

每一列代表一个码字：    

校验能力：可以检测各个码字同一位上的奇数位错，对于长度小于或等于m的突发错误，由于分布在不同行中，可以检测到。

实现方式：用硬件和软件均可，需要借助存储器。

3．水平垂直奇偶校验

编码原理：同时进行垂直和奇偶校验。

（过程略）

校验能力：冗余度大，具有更强检错能力。可检验3位以下的全部错误，所有奇数位错，突发长度小于或等于m+1的突发错误以及绝大多数偶数位错。

4、斜奇偶校验

编码原理：在水平垂直奇偶校验码的基础上，按照斜对角线的方向计算出校验位。

校验能力：冗余位更多，编、译码较为复杂，校验能力更强。

正反码：

举例说明：

码长n＝10，信息位k＝5，校验位r＝5，若信息位为11001，校验位为11001，码字为1100111001；若信息位为10001，校验位为01110，码字为1000101110。

纠错规则：

接收码字1100111001（传输中无错），

合成码为11001＋11001＝00000，

接收码信息位有3个1，校验码为00000。据上表，没有发生错误。

接收码字1000111001

合成码为10001＋11001＝01000，

接收码信息位有偶数个1，校验码为合成码的反码10111，据上表，信息位第二位出错。

（同学自己举例说明其他情况）。

循环冗余校验码

1、码多项式

    如果把一个码字中的各位看作是一个多项式的系数，则长为n的码字可以表示为一个多项式：

该多项式称为码字的码多项式。

如：码字11001的码多项式为：

2、多项式的按模运算

    在CRC中，常需要进行码多项式的运算，运算规则为按模2运算。若任意的n次多项式被一个k次多项式除，得到商式和余式（次数必然小余k），则表示为

。

3、循环冗余码

    长为n的码，信息位为k位的码记为（n，k）码。若一个码字集合满足以下两个条件：

（1）循环性：码集中的任一个码字向左或右循环一位，得到的新的码字，仍为码集中的码字。

（2）封闭性：码集中任意两个码字之和仍为码集中的码字。

则称此码集为（n，k）循环码。

例：是码集中的码字，是码集中的码字，全零码字必然是码集中的码字。

4、循环冗余码的生成多项式

    定理1  在循环冗余码（n，k）中，存在且只有一个（n－k）次的码多项式

满足：

（1）此循环冗余码中任一多项式都是的倍式；

（2）任意一个（n－1）次或（n－1）次以下的，又是倍式的多项式必定是此循环码中的一个码多项式。

（生成多项式的寻找有严密的代数背景，略）

5、循环冗余码的编码 

    一般是已知信息位，根据信息位求冗余位。

信息位为，码多项式为

冗余位为，码多项式为

码字为，码多项式为

                                （1）

码字是生成多项式的倍式，则

                                     （2）

由（1）（2）两式得

＝

即              ＝

所以用去除以生成多项式得到的余式就是码字的校验位。

编码算法：

（1）用乘以信息位对应的码多项式；

（2）用生成多项式去除，得余式；

（3）将对应的码字加在信息位后发送即可。

6、循环冗余码的译码

（1）检错过程

    发送方发送码字，设接收方接收码字为，根据

若＝，则有

即除以没有余式。

若<>，则除以有余式，接过收到的码字出错。

据此译码过程可知出现错误。

注意：有时<>，除以也没有余式，这种情况说明错误超过该编码的检错能力，每一种码的检错能力与生成多项式选择有关。

（2）纠错过程

    对于每一种编码，由其生成多项式可得到码的检错能力在某一个范围内，即该码可检m位错，纠s位错。在这个范围内可得到一个特定的错误模式，当余式与这些错误模式存在一一对应关系时，便可以纠错。