循环冗余校验 CRC的算法分析和程序实现
                   西南交通大学计算机与通信工程学院  刘东
摘要   通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其算法实现。

关键字  通信 循环冗余校验  CRC-32  CRC-16  CRC-4

概述
在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。
循环冗余校验CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。

一、循环冗余校验码（CRC）
CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式，由 。如一个8位二进制数10110101可以表示为： 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。
采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。
CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048 kbit/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式g（x）= 。采用16位CRC校验，可以保证在  bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16，其生成多项式g（x）= ；而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式g（x）= 。CRC-32的生成多项式g（x）= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。
二、CRC校验码的算法分析
CRC校验码的编码方法是用待发送的二进制数据t（x）除以生成多项式g（x），将最后的余数作为CRC校验码。其实现步骤如下：
（1）        设待发送的数据块是m位的二进制多项式t（x），生成多项式为r阶的g（x）。在数据块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为 。
（2）        用生成多项式g（x）去除 ，求得余数为阶数为r-1的二进制多项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC校验码。
（3）        用 以模2的方式减去y（x），得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式 ，所以解码时可以用接受到的数据去除g（x），如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t（x）和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。
为了更清楚的了解CRC校验码的编码过程，下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。
设待发送的数据t（x）为12位的二进制数据100100011100；CRC-4的生成多项式为g（x）= ，阶数r为4，即10011。首先在t（x）的末尾添加4个0构成 ，数据块就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余数y（x）。下表为给出了除法过程。
除数次数        被除数/ g（x）/结果            余数
0         1 001000111000000        100111000000
         1 0011       
         0 000100111000000       
1         1 00111000000          1000000
         1 0011        
         0 00001000000       
2         1 000000        1100
         1 0011       
         0 001100       

从上面表中可以看出，CRC编码实际上是一个循环移位的模2运算。对CRC-4，我们假设有一个5 bits的寄存器，通过反复的移位和进行CRC的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：
//reg是一个5 bits的寄存器
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
If (reg首位是1)
reg = reg XOR 0011.
把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。
End
reg的后四位就是我们所要求的余数。
这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一位数据，效率太低。为了提高处理效率，可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理，所以一次处理8位比较合适。
为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。在上面例子中，可以将编码过程看作如下过程：
由于最后只需要余数，所以我们只看后四位。构造一个四位的寄存器reg，初值为0，数据依次移入reg0（reg的0位），同时reg3的数据移出reg。有上面的算法可以知道，只有当移出的数据为1时，reg才和g（x）进行XOR运算；移出的数据为0时，reg不与g（x）进行XOR运算，相当与和0000进行XOR运算。就是说，reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit，所以有 种选择。上述算法可以描述如下，
//reg是一个4 bits的寄存器
初始化t[]={0011,0000}
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit为单位进行处理的，可以将上述算法扩展到8位，即以Byte为单位进行处理，即CRC-32。构造一个四个Byte的寄存器reg，初值为0x00000000，数据依次移入reg0（reg的0字节，以下类似），同时reg3的数据移出reg。用上面的算法类推可知，移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit，所以有 种选择。上述算法可以描述如下：
//reg是一个4 Byte的寄存器
初始化t[]＝{…}//共有 ＝256项
把reg中的值置0.
把原始的数据后添加r/8个0字节.
While (数据未处理完)
Begin
把reg中的值左移一个字节，读入一个新的字节并置于reg的第0个byte的位置。
reg = reg XOR t[移出的字节]
End
算法的依据和多项式除法性质有关。如果一个m位的多项式t（x）除以一个r阶的生成多项式g（x）， ，将每一位 （0=三、CRC-32的程序实现。
为了提高编码效率，在实际运用中大多采用查表法来完成CRC-32校验，下面是产生CRC-32校验吗的子程序。
unsigned long  crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先计算出的参数表，共有256项，未全部列出。

unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long  len)
{
        unsigned long oldcrc32;
        unsigned long crc32;
        unsigned long oldcrc;
        unsigned  int charcnt;
        char c,t;
        oldcrc32 = 0x00000000; //初值为0
    charcnt=0;
        while (len--) {
                t= (oldcrc32 >;>; 24) & 0xFF;   //要移出的字节的值
        oldcrc=crc_32_tab[t];         //根据移出的字节的值查表
                c=DataBuf[charcnt];          //新移进来的字节值
                oldcrc32= (oldcrc32 << 8) | c;   //将新移进来的字节值添在寄存器末字节中
                oldcrc32=oldcrc32^oldcrc;     //将寄存器与查出的值进行xor运算
                charcnt++;
        }
        crc32=oldcrc32;
        return crc32;
}
参数表可以先在PC机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c语言子程序，在Visual C++ 6.0下编译通过。
#include ;
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int Reflect(unsigned long int ref, char ch)
{        unsigned long int value(0);
        // 交换bit0和bit7，bit1和bit6，类推
        for(int i = 1; i < (ch + 1); i++)
        {                if(ref & 1)
                        value |= 1 << (ch - i);
                    ref >;>;= 1;        }
        return value;
}
init_crc32_table()
{        unsigned long int crc,temp;
        // 256个值
        for(int i = 0; i <= 0xFF; i++)
        {   temp=Reflect(i, 8);
                crc32_table[i]= temp<< 24;
                for (int j = 0; j < 8; j++){
             unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
                 t1=(crc32_table[i] << 1);
                 if(flag==0)
                   t2=0;
                 else
                   t2=ulPolynomial;
                 crc32_table[i] =t1^t2 ;                }
                crc=crc32_table[i];
                crc32_table[i] = Reflect(crc32_table[i], 32);
        }
}
结束语
    CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段。

今天看到的两篇，觉得非常经典，不过程序是VC++的，要能转成ANSI  C 就比较通用了。 讲解的也很详细透彻的。

热情推荐给有需要的朋友。
！不支持.doc 文件啊。只能直接贴了。

    校验码辅导讲座
老顽童（原创）
二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），这就有如何发现及纠正误码的问题。所有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。
一、码距
一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。
如图1所示的一个编码系统，用三个bit来表示八个不同信息中。在这个系统中，两个码字之间不同的bit数从1到3不等，但最小值为1，故这个系统的码距为1。如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。
然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图2的表中所示。
信息序号        二进码字
        a2        a1        a0
0        0        0        0
1        0        0        1
2        0        1        0
3        0        1        1
4        1        0        0
5        1        0        1
6        1        1        0
7        1        1        1
图 1         信息序号        二进码字
        a3        a2        a1        a0
0        0        0        0        0
1        1        0        0        1
2        1        0        1        0
3        0        0        1        1
4        1        1        0        0
5        0        1        0        1
6        0        1        1        0
7        1        1        1        1
图 2
注意，图8-2的8个码字相互间最少有两bit的差异。因此，如果任何信息的一个数位被颠倒，就成为一个不用的码字，接收机能检查出来。例如信息是1001，误收为1011，接收机知道发生了一个差错，因为1011不是一个码字（表中没有）。然而，差错不能被纠正。假定只有一个数位是错的，正确码字可以是1001，1111，0011或1010。接收者不能确定原来到底是这4个码字中的那一个。也可看到， 在这个系统中，偶数个（2或4）差错也无法发现。为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。 图8-3的表概括了最小距离为1至7的码的纠错和检错能力。        码距        码 能 力
        检错  纠错
1234567        0    01    02 或 12 加 12 加 23 加 23 加 3
图3
码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。要有专门的研究来解决这些问题。
二、奇偶校验
奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。例如，单个的奇偶校验将使码的最小距离由一增加到二。
一个二进制码字，如果它的码元有奇数个1，就称为具有奇性。例如，码字“10110101”有五个1，因此，这个码字具有奇性。同样，偶性码字具有偶数个1。注意奇性检测等效于所有码元的模二加，并能够由所有码元的异或运算来确定。对于一个n位字，奇性由下式给出：
奇性=a0⊕a1⊕a2⊕…⊕an 
奇偶校验可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。例如，在图8-2中，就是这样做的。可以看出，附加码元d2，是简单地用来使每个字成为偶性的。因此，若有一个码元是错的，就可以分辨得出，因为奇偶校验将成为奇性。奇偶校验编码通过增加一位校验位来使编码中1个个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2。因为其利用的是编码中1的个数的奇偶性作为依据，所以不能发现偶数位错误。
再以数字0的七位ASCII码（0110000）为例，如果传送后右边第一位出错，0变成1。接收端还认为是一个合法的代码0110001（数字1的ASCII码）。若在最左边加一位奇校验位，编码变为10110000，如果传送后右边第一位出错，则变成10110001，1的个数变成偶数，就不是合法的奇校验码了。但若有两位（假设是第1、2位）出错就变成10110011，1的个数为5，还是奇数。接收端还认为是一个合法的代码（数字3的ASCII码）。所以奇偶校验不能发现。
奇偶校验位可由硬件电路（异或门）或软件产生：
偶校验位 an =a0⊕a1⊕a2⊕…⊕an-1， 奇校验位 an =NOT（a0⊕a1⊕a2⊕…⊕an-1）。
在一个典型系统里，在传输以前，由奇偶发生器把奇偶校验位加到每个字中。原有信息中的数字在接收机中被检测， 如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发。
在实际工作中还经常采用纵横都加校验奇偶校验位的编码系统--分组奇偶校验码。
现在考虑一个系统， 它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组，则在这些不同的信息间，也如对单个信息一样，能够作奇偶校验。图4中n个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵向奇偶（VP）的形式编出奇偶校验位。
        m位数字        横向奇偶位
n个码字        a1        a2        …        am-1        am        HP1
b1        b2        …        bm-1        bm        HP2
c1        c2        …        cm-1        cm        HP3
…        …        …        …        …        …
n1        n2        …        nm-1        nm        HPn
VP1        VP2        …        VPm-1        VPm        HPn+1

纵向奇偶位       
图 4 用综横奇偶校验的分组奇偶校验码
研究图4可知：分组奇偶校验码不仅能检测许多形式的错误。并且在给定的行或列中产生孤立的错误时，还可对该错误进行纠正。
在初级程序员试题中（早期也出现在程序员试题中），经常有综横奇偶校验的题目。一般解法应该是这样：先找一行或一列已知数据完整的，确定出该行（或列）是奇校验还是偶校验。并假设行与列都采用同一种校验（这个假设是否正确，在全部做完后可以得到验证）。然后找只有一个未知数的行或列，根据校验性质确定该未知数，这样不断做下去，就能求出所有未知数。
【例】2001年初级程序员试题
由 6 个字符的 7 位 ASCII 编码排列，再加上水平垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校验位，最后一行为垂直奇偶校验位）:
字符        7 位 ASCII 码        HP
3        0        X1        X2        0        0        1        1        0
Y1        1        0        0        1        0        0        X3        1
+        X4        1        0        1        0        1        1        0
Y2        0        1        X5        X6        1        1        1        1
D        1        0        0        X7        1        0        X8        0
=        0        X9        1        1        1        X10        1        1
VP        0        0        1        1        1        X11        1        X12
则 X1 X2 X3 X4 处的比特分别为 __(36)__ ；
   X5 X6 X7 X8 处的比特分别为 ____ ；
   X9 X10 XI1 X12 处的比特分别为 __(38)__ ；Y1 和 Y2 处的字符分别为 __(39)__ 和 __(40)__ 。
[解]
从ASCII码左起第5列可知垂直为偶校验。则：
从第1列可知X4=0；从第3行可知水平也是偶校验。
从第2行可知X3=1；从第7列可知X8=0；从第8列可知X12=1；
从第7行可知X11=1；从第6列可知X10=0；从第6行可知X9=1；从第2列可知X1=1；
从第1行可知X2=1；从第3列可知X5=1；从第4行可知X6=0；
从第4列（或第5行）可知X7=0；整理一下：
(36) X1X2X3X4 = 1110
(37) X5X6X7X8 = 1000
(38) X9X10X11X12 = 1011
(39) 由字符Y1的ASCII码1001001=49H知道，Y1即是“I”（由“D”的ASCII码是1000100=44H推得）
(40) 由字符Y2的ASCII码0110111=37H知道，Y2即是“7”（由“3”的ASCII码是0110011=33H推得）
假如你能记住“0”的ASCII码是0110000=30H；“A”的ASCII码是1000001=41H，则解起来就更方便了。
三、海明校验
我们在前面指出过要能纠正信息字中的单个错误，所需的最小距离为3。实现这种纠正的方法之一是海明码。
海明码是一种多重(复式)奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。实现得合适时，这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能把它分离出来。
推导并使用长度为m位的码字的海明码，所需步骤如下：
1、确定最小的校验位数k，将它们记成D1、D2、…、Dk，每个校验位符合不同的奇偶测试规定。
2、原有信息和k个校验位一起编成长为m+k位的新码字。选择k校验位（0或1）以满足必要的奇偶条件。
3、对所接收的信息作所需的k个奇偶检查。
4、如果所有的奇偶检查结果均为正确的，则认为信息无错误。
如果发现有一个或多个错了，则错误的位由这些检查的结果来唯一地确定。
校验位数的位数
推求海明码时的一项基本考虑是确定所需最少的校验位数k。考虑长度为m位的信息，若附加了k个校验位，则所发送的总长度为m+k。在接收器中要进行k个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个k位的二进字，它可以确定最多2k种不同状态。 这些状态中必有一个其所有奇偶测试试都是真的，它便是判定信息正确的条件。于是剩下的（2k-1）种状态，可以用来判定误码的位置。于是导出下一关系：
2k-1≥m+k
码字格式
从理论上讲，校验位可放在任何位置，但习惯上校验位被安排在1、2、4、8、…的位置上。
图5列出了m=4，k=3时，信息位和校验位的分布情况。
码字位置        B1        B2        B3        B4        B5        B6        B7
校验位        x        x        　        x        　        　        　
信息位        　        　        x        　        x        x        x
复合码字        P1        P2        D1        P3        D2        D3        D4
图5 海明码中校验位和信息位的定位
校验位的确定
k个校验位是通过对m+k位复合码字进行奇偶校验而确定的。
其中：P1位负责校验海明码的第1、3、5、7、…（P1、D1、D2、D4、…）位，（包括P1自己）
P2负责校验海明码的第2、3、6、7、…（P2、D1、D3、D4、…）位，（包括P2自己）
P3负责校验海明码的第4、5、6、7、…（P3、D2、D3、D4、…）位，（包括P3自己）
对m=4，k=3，偶校验的例子，只要进行式次偶性测试。这些测试（以A、B、C表示）在图6所示各位的位置上进行。
奇偶条件        码 字 位 置
        1        2        3        4        5        6        7
ABC        x　 　        　x        xx 　        　x        x　x        　xx        xxx
图6 奇偶校验位置
因此可得到三个校验方程及确定校验位的三个公式：
A=B1⊕B3⊕B5⊕B7=0 得P1=D1⊕D2⊕D4
B=B2⊕B3⊕B6⊕B7=0 得P2=D1⊕D3⊕D4
C=B4⊕B5⊕B6⊕B7=0 得P3=D2⊕D3⊕D4
若四位信息码为1001，利用这三个公式可求得三个校验位P1、P2、P3值。和海明码，如图7则表示了信息码为1001时的海明码编码的全部情况。而图8中则列出了全部16种信息（D1D2D3D4=0000～1111）的海明码。
码字位置        B1        B2        B3        B4        B5        B6        B7
码位类型        P1        P2        D1        P3        D2        D3        D4
信息码        -        -        1        -        0        0        1
校验位        0        0        -        1        -        -        -
编码后的海明码        0        0        1        1        0        0        1
图7 四位信息码的海明编码
P1        P2        D1        P3        D2        D3        D4
0        0        0        0        0        0        0
1        1        0        1        0        0        1
0        1        0        1        0        1        0
1        0        0        0        0        1        1
1        0        0        1        1        0        0
0        1        0        0        1        0        1
1        1        0        0        1        1        0
0        0        0        1        1        1        1
1        1        1        0        0        0        0
0        0        1        1        0        0        1
1        0        1        1        0        1        0
0        1        1        0        0        1        1
0        1        1        1        1        0        0
1        0        1        0        1        0        1
0        0        1        0        1        1        0
1        1        1        1        1        1        1
图8 未编码信息的海明码
上面是发送方的处理
在接收方，也可根据这三个校验方程对接收到的信息进行同样的奇偶测试：
A=B1⊕B3⊕B5⊕B7=0；
B=B2⊕B3⊕B6⊕B7=0；
C=B4⊕B5⊕B5⊕B7=0。
若三个校验方程都成立,即方程式右边都等于0，则说明没有错。若不成立即方程式右边不等于0，说明有错。从三个方程式右边的值，可以判断那一位出错。例如，如果第3位数字反了，则C=0(此方程没有B3），A=B=1（这两个方程有B3）。可构成二进数CBA，以A为最低有效位，则错误位置就可简单地用二进数CBA=011指出。
同样，若三个方程式右边的值为001，说明第1位出错。若三个方程式右边的值为100，说明第4位出错。
海明码的码距应该是3，所以能纠正1位出错。而奇偶校验码的码距才是2，只能发现1位出错，但不能纠正（不知道那一位错）。无校验的码距是1，它出任何一位出错后还是合法代码，所以也就无法发现出错。
这是关于海明码的经典说法，即码距为3，可以发现2位，或者纠正1位错。应满足2k-1≥m+k。
但在清华的王爱英主编的《计算机组成与结构》（该书已成为国内的权威）中还提出了一种码距为4的海明码，可以发现2位，并且纠正1位错。应满足2(k-1)≥m+k。
由于王爱英书上对这两种概念没有很仔细解释（特别对码距为3的海明码），过渡很突然。有些书简单抄袭时没有仔细消化，所以出现一些概念错。对于一般码距为3的海明码，应该是“可以发现2位，或者纠正1位错”，而不是“可以发现2位，并且纠正1位错”。在试题中出现过类似的错误。
四、循环冗余校验码
在串行传送（磁盘、通讯）中，广泛采用循环冗余校验码（CRC）。CRC也是给信息码加上几位校验码，以增加整个编码系统的码距和查错纠错能力。
CRC的理论很复杂，一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关，只能根据书上的结论死记。
循环冗余校验码（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除以生成多项式G(x)得到的余数就是校验码。
几个基本概念
1、多项式与二进制数码
多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。
多项式包括生成多项式G(x)和信息多项式C(x)。
如生成多项式为G(x)=x4+x3+x+1， 可转换为二进制数码11011。
而发送信息位 1111，可转换为数据多项式为C(x)=x3+x2+x+1。
2、生成多项式
是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。
在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
应满足以下条件：
a、生成多项式的最高位和最低位必须为1。
b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。
c、不同位发生错误时，应该使余数不同。
d、对余数继续做模2除，应使余数循环。
将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图9所示：
N        K        码距d        G(x)多项式        G(x)
7        4        3        x3+x+1        1011
7        4        3        x3+x2+1        1101
7        3        4        x4+x3+x2+1        11101
7        3        4        x4+x2+x+1        10111
15        11        3        x4+x+1        10011
15        7        5        x8+x7+x6+x4+1        111010001
31        26        3        x5+x2+1        100101
31        21        5        x10+x9+x8+x6+x5+x3+1        11101101001
63        57        3        x6+x+1        1000011
63        51        5        x12+x10+x5+x4+x2+1        1010000110101
1041        1024        　        x16+x15+x2+1        11000000000000101
图9 常用的生成多项式
3、模2除（按位除）
模2除做法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位。所以实际上就是异或。然后再移位移位做下一位的模2减。步骤如下：
a、用除数对被除数最高几位做模2减，没有借位。
b、除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位。
c、一直做到余数的位数小于除数时，该余数就是最终余数。
【例】1111000除以1101：
1011———商
————
1111000-----被除数
1101———— 除数
————
010000
1101
————
01010
1101
————
111————余数
CRC码的生成步骤
1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
2、将信息码左移R位，相当与对应的信息多项式C(x)*2R
3、用生成多项式（二进制数）对信息码做模2除，得到R位的余数。
4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。
【例】假设使用的生成多项式是G(x)=x3+x+1。4位的原始报文为1010，求编码后的报文。
解：
1、将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。
2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000
3、用生成多项式对应的二进制数对左移4位后的原始报文进行模2除：
1001-------商
------------------------
1010000
1011----------除数
------------
1000
1011
------------
011-------余数（校验位）
5、编码后的报文（CRC码）：
1010000
+       011
------------------
1010011
CRC的和纠错
在接收端收到了CRC码后用生成多项式为G(x)去做模2除，若得到余数为0,则码字无误。若如果有一位出错，则余数不为0，而且不同位出错，其余数也不同。可以证明，余数与出错位的对应关系只与码制及生成多项式有关，而与待测碼字（信息位）无关。图10给出了G(x)＝1011，C(x)＝1010的出错模式，改变C(x)（码字），只会改变表中码字内容，不改变余数与出错位的对应关系。
　        收到的CRC码字        余数        出错位
码位        A7        A6        A5        A4        A3        A2        A1
               
正确        1        0        1        0        0        1        1
        000        无
错 误        1        0        1        0        0        1        0
1        0        1        0        0        0        1
1        0        1        0        1        1        1
1        0        1        1        0        1        1
1        0        0        0        0        1        1
1        1        1        0        0        1        1
0        0        1        0        0        1        1
        001010100011110111101        1234567
图10 （7，4）CRC码的出错模式（G(x)＝1011）
如果循环码有一位出错，用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去，我们将发现一个有趣的结果；各次余数将按图10顺序循环。例如第一位出错，余数将为001，补0后再除，第二次余数为010，以后依次为100，0ll…，反复循环，这就是“循环码”名称的由来。这是一个有价值的特点。如果我们在求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移。图10说明，当出现余数(101)时，出错位也移到A7位置。可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。
通信与网络中常用的CRC
在数据通信与网络中，通常k相当大，由一千甚至数千数据位构成一帧，而后采用CRC码产生r位的校验位。它只能检测出错误，而不能纠正错误。一般取r=16，标准的16位生成多项式有CRC-16＝x16+x15+x2+1 和 CRC-CCITT＝x16+x15+x2+1。
一般情况下，r位生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于r的突发错以及（1-2-(r-1)）的突发长度为r+1的突发错和（1-2-r）的突发长度大于r+1的突发错。例如，对上述r=16的情况，就能检测出所有突发长度小于等于16的突发错以及99．997%的突发长度为17的突发错和99．998%的突发长度大于17的突发错。所以CRC码的检错能力还是很强的。这里，突发错误是指几乎是连续发生的一串错，突发长度就是指从出错的第一位到出错的最后一位的长度(但是，中间并不一定每一位都错)。
【例1】某循环冗余码（CRC）的生成多项式 G(x)＝x3+x2+1，用此生成多项式产生的冗余位，加在信息位后形成 CRC 码。若发送信息位 1111 和 1100 则它的 CRC 码分别为＿A＿和＿B＿。由于某种原因，使接收端收到了按某种规律可判断为出错的 CRC 码，例如码字＿C＿、＿D＿、和＿E＿。（1998年试题11）
供选择的答案
A：① lllll00        ② 1111101        ③ 1111110        ④ 1111111
B：① 1100100        ② 1100101        ③ 1100110        ④ 1100111
C～E：① 0000000        ② 0001100        ③ 0010111       
      ⑤ 1000110        ⑥ 1001111        ⑦ 1010001        ⑧ 1011000
解：
A：G(x)＝1101，C(x)＝1111 C(x)*23÷G(x)＝1111000÷1101＝1011余111
得到的CRC码为1111111
B：G(x)＝1101，C(x)＝1100 C(x)*23÷G(x)＝1100000÷1101＝1001余101
得到的CRC码为1100101
C～E：
分别用G(x)＝1101对①～⑧ 作模2除: ① 0000000÷1101 余000  ② 1111101÷1101 余001
③ 0010111÷1101 余000  ④ 0011010÷1101 余000  ⑤ 1000110÷1101 余000
⑥ 1001111÷1101 余100  ⑦ 1010001÷1101 余000  ⑧ 1011000÷1101 余100
所以＿C＿、＿D＿和＿E＿的答案是②、⑥、⑧
【例2】计算机中常用的一种检错码是CRC，即 _A_ 码。在进行编码过程中要使用 _B_ 运算。假设使用的生成多项式是 G(X)=X4+X3+X+1， 原始报文为11001010101，则编码后的报文为 _C_ 。CRC码 _D_ 的说法是正确的。
在无线电通信中常采用它规定码字长为7位．并且其中总有且仅有3个“1”。这种码的编码效率为_E_。
供选择的答案：
A：① 水平垂直奇偶校验                     ② 循环求和                        ③ 循环冗余                        ④正比率
B：① 模2除法                     ②定点二进制除法                   ③二－十进制除法                 ④循环移位法
C：① 1100101010111           ② 110010101010011      ③ 110010101011100      ④ 110010101010101
D：① 可纠正一位差错                                                ②可检测所有偶数位错
③ 可检测所有小于校验位长度的突发错                  ④可检测所有小于、等于校验位长度的突发错
E：① 3/7       ② 4/7       ③ log23/log27     ④ (log235)/7
解：从前面有关CRC的论述中可得出：  A：③ 循环冗余  B：① 模2除法
C：G(x)＝11011，C(x)＝11001010101，C(x)*24÷G(x)＝110010101010000÷11011 余0011
得到的CRC码为② 110010101010011
D：从前面有关通信与网络中常用的CRC的论述中可得出：④ 可检测所有小于、等于校验位长度的突发错
E：定比码又叫定重码，是奇偶校验的推广。在定比码中，奇数或偶数的性质保持不变，然而附加一种限制，每个字中1的总数是固定的。随用途之不同，定比码要求的附加校验位可能多于一个，但较之单一的奇偶校验将增加更多的检错能力。
所谓7中取3定比码，就是整个码字长度为7位，其中1的位数固定为3。所有128个7位代码（0000000～1111111）中只有1的位数固定为3的才是其合法码字。可以用求组合的公式求出其合法码字数为：C73＝7!/(3!*(7-3)!)＝7*6*5/(1*2*3)＝35
编码效率＝合法码字所需位数/码字总位数＝(log235)/7