比起奇偶校验码（PCC）只能校验一位错误，循环冗余校验码（CRC）的检错能力更强，可以检出多位错误。
 
1.CRC校验原理
 
CRC校验原理看起来比较复杂，好难懂，因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题，其根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。
 
【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101除以1110，结果得到商为11，余数为1，如图5-9左图所示。如11×11=101，如图5-9右图所示。
 

 图1： "模2除法"和"模2乘法"示例
 
具体来说，CRC校验原理就是以下几个步骤：
 
（1）先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行除法运算的除数（是二进制比较特串，通常是以多项方式表示，所以CRC又称多项式编码方法，这个多项式也称之为“生成多项式”）。
 
（2）看所选定的除数二进制位数（假设为k位），然后在要发送的数据帧（假设为m位）后面加上k-1位“0”，然后以这个加了k-1个“0“的新帧（一共是m+k-1位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC校验码，也称之为FCS（帧校验序列）。但要注意的是，余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。
 
（3）再把这个校验码附加在原数据帧（就是m位的帧，注意不是在后面形成的m+k-1位的帧）后面，构建一个新帧发送到接收端；最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。
 
从上面可以看出，CRC校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为"1"，如在IBM的SDLC（同步数据链路控制）规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式g（x）= x16 + x15 + x2 +1（对应二进制比特串为：11000000000000101）；而在ISO HDLC（高级数据链路控制）规程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多项式g（x）= x^16 + x^15 + x^5 +1（对应二进制比特串为：11000000000100001）。
 
2. CRC校验码的计算示例
 
由以上分析可知，既然除数是随机，或者按标准选定的，所以CRC校验的关键是如何求出余数，也就是校验码（CRC校验码）。
 
下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X） = X^4 + X^3 + 1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：
 
（1）首先把生成多项式转换成二进制数，由G（X） = X^4 + X^3 + 1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。
 
（2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数（即CRC码）为0100，如图2所示。注意参考前面介绍的“模2除法”运算法则。
 
 图2 CRC校验码计算示例
 
（3）把上步计算得到的CRC校验0100替换原始帧101100110000后面的四个"0"，得到新帧101100110100。再把这个新帧发送到接收端。
 
（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以"模2除法"方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。
 
通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。
 
原文出处：https://blog.51cto.com/winda/1063951

CRC校验原理
 CRC校验原理看起来比较复杂，好难懂，因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题，其根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。
 
【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101除以1110，结果得到商为11，余数为1，如图所示。如11×11=101，如图所示。
 
 
具体来说，CRC校验原理就是以下几个步骤：
 
（1）先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行除法运算的除数（是二进制比较特串，通常是以多项方式表示，所以CRC又称多项式编码方法，这个多项式也称之为“生成多项式”）。
 
（2）看所选定的除数二进制位数（假设为k位），然后在要发送的数据帧（假设为m位）后面加上k-1位“0”，然后以这个加了k-1个“0“的新帧（一共是m+k-1位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC校验码，也称之为FCS（帧校验序列）。但要注意的是，余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。
 
（3）再把这个校验码附加在原数据帧（就是m位的帧，注意不是在后面形成的m+k-1位的帧）后面，构建一个新帧发送到接收端，最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。
 通过以上介绍，大家一定可以理解CRC校验的原理，并且不再认为很复杂吧。
 
从上面可以看出，CRC校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”，如在IBM的SDLC（同步数据链路控制）规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式g（x）= x16 + x15 + x2 +1（对应二进制比特串为：11000000000000101）；而在ISO HDLC（高级数据链路控制）规程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多项式g（x）=x16 + x15 + x5 +1（对应二进制比特串为：11000000000100001）。
 CRC校验码的计算示例
 由以上分析可知，既然除数是随机，或者按标准选定的，所以CRC校验的关键是如何求出余数，也就是CRC校验码。
 
下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X） = X4 + X3 + 1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：
 （1）首先把生成多项式转换成二进制数，由G（X） = X4 + X3 + 1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。
 （2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即CRC校验码为0100，如图所示。注意参考前面介绍的“模2除法”运算法则。
 
 
（3）把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。
 
（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。 通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。

循环冗余校验检错方案CRC
 

 
 
 
 1. CRC校验原理
 
 
     CRC校验原理看起来比较复杂，好难懂，因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题，其根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。
 
      【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101除以1110，结果得到商为11，余数为1，如图5-9左图所示。如11×11=101，如图5-9右图所示。
 
 
 
 图5-9 “模2除法”和“模2乘法”示例
 
      具体来说，CRC校验原理就是以下几个步骤：
 
    （1）先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行除法运算的除数（是二进制比较特串，通常是以多项方式表示，所以CRC又称多项式编码方法，这个多项式也称之为“生成多项式”）。
 
    （2）看所选定的除数二进制位数（假设为k位），然后在要发送的数据帧（假设为m位）后面加上k-1位“0”，然后以这个加了k-1个“0“的新帧（一共是m+k-1位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC校验码，也称之为FCS（帧校验序列）。但要注意的是，余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。
 
    （3）再把这个校验码附加在原数据帧（就是m位的帧，注意不是在后面形成的m+k-1位的帧）后面，构建一个新帧发送到接收端；最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。
 
     通过以上介绍，大家一定可以理解CRC校验的原理，并且不再认为很复杂吧。
 
     从上面可以看出，CRC校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”，如在IBM的SDLC（同步数据链路控制）规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式g（x）=x16 + x15 + x2 +1（对应二进制比特串为：11000000000000101）；而在ISO HDLC（高级数据链路控制）规程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多项式g（x）=x16 + x15 + x5 +1（对应二进制比特串为：11000000000100001）。
 
 2.    CRC校验码的计算示例
 
    由以上分析可知，既然除数是随机，或者按标准选定的，所以CRC校验的关键是如何求出余数，也就是校验码（CRC校验码）。
 
     下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X） = X4 + X3 + 1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：
 
    （1）首先把生成多项式转换成二进制数，由G（X） = X4 + X3 + 1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。
 
    （2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数（即CRC码）为0100，如图5-10所示。注意参考前面介绍的“模2除法”运算法则。
 
 
 
 图5-10 CRC校验码计算示例
 
     （3）把上步计算得到的CRC校验0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。
 
     （4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。
 
     通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。
 
  

 
纠错码
 
1.纠错码有什么作用
2.主要概念
**码字：m位数据位和r位校验位组成的n个位单元称为n位码字
**海明码距：两个码字间不同的位数的个数
  
3.检错、纠错
(解释上面的两个Why）用图示的方法理解检错能力、纠错能力与码距之间的关系
  
4.举例说明
**奇偶校验：
  
5.一般性方法（这描述的是一种推广，如何通过增加码距来使设计方案获得更好的检错、纠错能力？）
如何构造一个可以纠正(不是检测)m位数据位中至多有d位错误的校验码呢？这种校验码至少需要多少个校验位呢？
使用该公式求当要求纠正1（即公式中k取1）位错误时所需要的校验位的个数
 

 
1.纠错码有什么作用
 
由于电源的尖峰电压或其他原因，计算机主存的数据在传输的过程中偶尔也会出错。为了防止这些错误产生不良后果，我们在主存中采用检错和纠错的方式来处理错误。
 
2.主要概念
 
**码字：m位数据位和r位校验位组成的n个位单元称为n位码字
 
**海明码距：两个码字间不同的位数的个数
 
 值得注意的是，当存在很多码字的时候，我们将这些码字看作是一个集合，该集合的海明码距的值就是其中任意两个码字产生的最小的海明码距。
 
3.检错、纠错
 
检错：检查d位错误，编码的码距要d+1位。 Why?
 纠错：纠正d位错误，编码的码距要2d+1位 。 Why?
 
(解释上面的两个Why）用图示的方法理解检错能力、纠错能力与码距之间的关系
 
 
如图，a1和a2代表合法的码字，它们之间的距离代表了它们的海明码距，所以说当海明码距为d时任何小于d位的错误都不会使之前的码字变成一个合法码字，因此可以用这种原理判断是否出错(如果出错的位数不小于d的时候，一个合法码字会变成另一个合法码字，这种错误会被当做未出错来处理)。同样的道理，为了使码字出错之后还可以纠正，我们可以通过将错误码字修改成最“近”的合法码字的方法来纠正错误。如图中的c1，我们可以推断出这个错误的码字更有可能是从合法码字a1发生错误而产生的，所以我们将错误码字c1修改成a1来纠正错误。因此我们就要保证海明码距的大小至少是需要纠正的位数的2倍还多出1.
因此总的来说码距越大，检错的和纠错的能力也就越强。
 
4.举例说明
 
**奇偶校验：
 
一位的奇偶校验：给数据位添加一个bit的奇偶校验位的校验码被称为奇偶校验。根据原数据位中1的位数是奇数或是偶数来设置奇偶校验位是0或1。
奇偶校验是海明码距为2的校验法，也就是说任意一个合法码字两个bit位出现错误就会变成另一个合法码字。
如， 11010101，对它进行奇校验，变成011010101（校验位添加在了最前面，以保证1的个数是奇数个），当它的任意一个位发生改变时，便会导致1的个数变成了偶数而引发错误。
因此，通过上面的分析可以知道奇偶校验是一种具有一位错误检错能力的校验码(因为2-1 = 1),但是奇偶校验没有纠错能力(因为(2-1)/2 = 0.5, 0.5 < 1,所以说连一位错误都没办法纠正)。
 
5.一般性方法（这描述的是一种推广，如何通过增加码距来使设计方案获得更好的检错、纠错能力？）
 
如何构造一个可以纠正(不是检测)m位数据位中至多有d位错误的校验码呢？这种校验码至少需要多少个校验位呢？
 
m位数据位就存在2m个合法码字，假设需要r位校验位，则总共有n = m + r个位。由于校验位的取值是由数据位直接决定的而且唯一对应（这是一个好的校验算法必须要做到的事情），所以2n个码字中只有2m个合法码字。
其次，在纠错码的应用中通常有多个错误码字对应同一个合法的码字(使用上面的图来说明就是a1和a2都对应这三个错误码)，一般情况会是多少个呢？我们尝试着去想，可能是1位错、2位错、3位错、、、d位错（因为我们可以纠正到d位，d也可以是1、2或3），所以总共会有${\sum }_{k=1}^d{C}_n^k$个错误的码字与一个合法的码字对应（这里的$C_n^k$是确保错误发生的随机性，计算k个错误发生在n个位置的所有可能性）。为了加上一个合法码字可将公式改写为${\sum }_{k=0}^d{C}_n^k$，该公式表明一个合合法码字所对应的所有码字，因为总共有2m个合法码字，所以总共有2m${\sum }_{k=0}^d{C}_n^k$个不同的码字。
我们现在只要保证n位的纠错码能够表示上述所说的所有不同的码字就行，即得到不等式
 $$2^m\sum _{k=0}^d{C}_n^k\le 2^n$$
 解这个不等式就能构求出n的最小值，从而求出r的最小值。
 
使用该公式求当要求纠正1（即公式中k取1）位错误时所需要的校验位的个数
 
数据位数m
需要的校验位r
总长n
校验位与数据位之比(%)
8
4
12
50
16
5
21
31
32
6
38
19
64
7
71
11
128
8
136
6
能得到几个结论。第一，字长越长，校验位也需要变长。第二，字长越长，校验位在字长中的占比的百分比会变小。
 
**用相同的思想推出能检测出d位错误（不纠正，只发现错误）的检错码的推导不等式是
 $$(2^m+1)\sum _{k=0}^{d-1}{C}_n^d+1\le 2^n$$
 （该公式没有做系统的推导和证明仅做参考）