|
|
|
|
|
|
在串行传送（磁盘、通信）中，广泛采用循环冗余校验码（CRC码）。
|
|
|
|
循环冗余校验码的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N,K）码。对于一个给定的（N,K）码，可以证明存在一个最高次幂为N-K=R的多项式G（x）。根据G(x）可以生成K位信息的校验码，而G（x）叫作这个CRC码的生成多项式。
|
|
|
|
|
|
|
|
|
|
|
|
校验码的具体生成过程为：假设发送信息用信息多项式C（x）表示，将C（x）左移R位，则可表示成C（x）×2R，这样C（x）的右边就会空出R位，这就是校验码的位置。通过对多项式C（x）×2R用模2除法除以生成多项式G（x）得到的余数就是校验码。
|
|
|
|
模2除法是指在进行除法运算的过程中进行减法运算时不考虑借位的问题，也就是0-0=0，0-1=1, 1-0=1, 1-1=0。
|
|
|
|
|
|
|
|
|
|
如果循环码有一位出错，用G（x）做模2除将得到一个不为0的余数。如果对余数补0继续除下去，将发现一个有趣的结果：各次余数将按顺序循环。例如，第7位出错，余数将为001，补0后再除（补0后若最高位为1，则用除数做模2除取余；若最高位为0，则其最低3位就是余数），得到第二次余数为010。以后继续补0作模2除，依次得到余数为100，011，反复循环，这就是"循环码"名称的由来。这是一个有价值的特点。如果在求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移，当出现余数101时，出错位也移到A1位置，可通过异或门将它纠正后在下一次移位时送回A7。这样就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
