CRC循环冗余检测码 及其 检错纠错

小菜鸟~

知识环境：
    数据校验码：通常三种：奇偶校验码；海明校验码；循环冗余校验码。
循环冗余码（CRC）：
    主要用于串行传送，网络，同步通信及磁表面存储等场合。即给信息码右边加上几位校验码，以增加整个编码系统的码距和查错纠错能力。
CRC编码原理：
（1）CRC又叫（N,K）码，整个编码长度:N位；
     信息码长度：K位；
     校验码长度：R(=N-K)位。
（2）多项式包括：信息多项式，生成多项式。
     信息多项式：C(x),K-1次（又称原始报文，数据多项式）；
     生成多项式：G(x),R次（对应R+1位二进制数，但不是校验码）；
（3）信息码与信息多项式可直接对应。如以下例1：
     4位的信息码1111，对应3次的信息多项式C(x)=x^3+x^2+x^1+1.
     校验码与生成多项式不可直接对应，而是利用R次G(x)对(K-1)+R次C(x)*2^R做模2除运算，以生成R位余数（即校验码）。如以下例2：
         3次G(x)=x^3+x+1,对应4位除数1011；
         4位原始报文1010，左移3位得1010000；
         用1011对1010000进行模2除；
         得余数即3位校验码：011.
         最终得CRC码：1010011.
         注意：模2除法与算数除法有不同。
         模2除法举以下例3：
                1110         
             -------   
       1011 /1100000    （1100最高位为1，商1）
             1011
             ----
              1110      （1100与1011异或）
              1011      （1110最高位为1，商1）
              -----
               1010     （1110与1011异或）
               1011     （1010最高位为1，商1）
               -----
                0010    （1010与1011异或）
                0000    （0010最高位为0，商0）
                ----
                 010    （当余数位数小于除数，即为校验码）
K位的信息码左移R位，拼接上R位的校验码，形成完整的N位的CRC码。
（4）关于生成多项式G(x)：
     是接收方与发送方的约定，在整个传输过程中始终不变。
     发送方利用它生成校验码，从而形成完整的CRC码，发送；接收方接收此完整的CRC编码后又利用它做模2除，检测和确定错误位置。
     应满足特定的条件：a.最高位与最低位必须为1；
                       b.当接收方接收的CRC码字正确（与发送的CRC码一致），则用G(x)对其做模2除后，余数为0；else,即接收方接收的CRC码出错，则用生成多项式对其做模2除后，得到余数不为0，并且，不同位出错时，得到的余数不同。
                       c.对余数继续做模2除，应使余数循环。
     已有三种生成多项式成为标准而被广泛运用，他们都具有极高的检错率：
           a.CRC(12)=x^12+x^11+x^3+x^2+x^1+1
           b.CRC(16)=x^16+x^15+x^2+1
           c.CRC(CCITT)=x^16+x^12+x^5+1
CRC检错纠错原理：
首先可确定的是，CRC码是一种检错纠错能力很强的校验码。
当接收方检测到CRC码字出错，要求重发，即可能实现纠错。
检错：CRC码被G(x)整除，所得的余数与出错位之间有唯一的对应关系。根据这一关系便可立即确定出错位的位置。
注：若某位出错，则余数不为0.对此余数补零后继续作模2除法，又得到一个不为0的余数。
    反复这样，将得到一个循环的余数队列。（所以你知道为啥叫“循环码”了吧~）
    比如接着上例1，余数循环如下：011->110->111->101->001->010->100->011.
The End



如觉得我整理的不好，请参见
http://hi.baidu.com/maolang0/blog/item/1457ab1bca62ad1d8618bf19.html

另有一个很好的课件：
http://video.shfc.edu.cn/jpkc/jpkc/jisuanjizucheng2/dianzijiaoan/23.ppt




本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/91801/showart_1807141.html