原创 译A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHM

              http://www.repairfaq.org/filipg/LINK/F_crc_v31.html#CRCV_001

           A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHM

                                             Author : Ross N. Williams

译得不好请指正，谢谢

1.前言（略）

     "Everything you wanted to know about CRC algorithms, but were afraid to ask for fear that errors in your understanding might be detected."

2.介绍: 错误检测

     错误检测的目的是让接收机能够判别从噪声信道传来的信息是否被干扰。为了达到这样的目的，发射机constructs了一个值（校验和），将该值附加在信息的后面，该值是信息的函数。接收机能够用某个函数计算接收信息的校验和，并和附加在信息尾部的校验和比较，从而判断接收到的信息是否正确，比如说，在mod 256中，我们选择的校验和函数仅是bytes的和，则请看下面，所有的数十进制。

    信息  ：                           6    23     4

    信息加校验和 ：           6    23     4    33

    传输后的信息 ：           6    27     4    33 

如上，第二byte23被信道扰乱成了27，然而接收机能够比较传输的校验和33计算的校验和 37(6 + 27 + 4)。如果校验和自身被干扰了，则正确的信息可能被验证为错误的，但是这是一种 safe-side 的误判。dangerous-side 的 误判则发生在信息和/或校验和被这样的方式干扰——传输结果的内部一致。不幸的是这样的结果不可避免，我们能做的是通过增加校验和中信息的数量（如加宽校验和从1byte到2byte ）来使这样的可能性最小化。

其它错误检测技术通过对信息的复杂变换，将冗余信息加入其中。但是, 本文只讲CRC 算法——一种归类为将数据保持原状并在末端附加校验和的算法。

                                     例如：<原始信息><校验和>

3.在复杂之前的准备

      在前面的校验和例子里，我们看见了被污染的信息是如何通过校验和（简单的将bytes以mod256相加）被检测出来。

                       Message:                              6 23  4
                       Message with checksum :      6 23  4 33
                       Message after transmission :  6 27  4 33

但这个算法过于简单了，如果一个随机的干扰发生了，将有1/256不会被检测出来的可能性，比如：

   Message:                      6 23  4
   Message with checksum:        6 23  4 33
   Message after transmission:   8 20  5 33

我们可以通过将8为寄存器改为16位寄存器（比如将bytes以mod65536相加来取代以mod256相加）来降低检测的可能性为1/65536。这仅是一个好的想法，他的不足在于不够“随机”；在这样的简单算法里，每一个incoming byte 只会影响summing register 的一个byte,  而不论这个summing register有多长，比如在上面的第二个例子里， summing register 可以是Megabyte 宽，然而错误仍然检测不出来。这个问题只能通过引入一种会使incoming byte 影响整个checksum register的更先进的算法来解决。因此，我们意识到到至少有两方面影响了校验和函数的强壮性：

宽度(WIDTH)：register宽度足够预先提供一个低的失败可能性(e.g. 32-bits gives a 1/2^32 chance of failure)

扰乱(CHAOS)：使每一个input byte 都有改变任一bit位的潜力。

Note: 术语"校验和"被认为用来描述早期的相加的校验方式，但是现在有了更广泛的意义，包括了更先进的算法，比如CRC算法。CRC算法被认为能很好满足第二个条件，并能在不同的checksum width上运用。

4.CRC算法的基本思想

我们从哪里出发来寻找比相加更复杂的函数呢？各种各样的想法涌入脑中。我们可以用pi值构建一张表，或用register的每一位哈希(hash )incoming byte。我们甚至可以保有一本巨大的“电话簿”，用每一incoming byte 联合 register中的bytes来索引一个新的号码作为下一个register中的值。可能性是不可限量的。

但现在 ，我们不必想太远，下一步算法就足够了。虽然加法明显的不够强大来形成一种有效的校验和机制时，除法却可以。 只要除数和checksum register一样宽。

CRC算法的基本思想简单地就是将信息看成是一个大的二进制数，然后用另一个固定的二进制数来除它，得到余数。根据接收到的信息，接收器用同样的除法得到余数，并和传输来的校验和（一个余数）比较。

 例子：假如信息像前面的例子一样由两bytes（6，23 ）组成，16进制是0617 ，二进制是0000-0110-0001-0111。还假设用一byte宽的 checksum register ，除数恒为1001。本次，计算显然可以用common garden variety 32-bit registers，但普遍情况下这样麻烦。所以，我们用good-'ol long division ，这在学校里学过（还记得吗？）。只是本次是二进制了。

 ...0000010101101 = 00AD =  173 = QUOTIENT（商）
         ____-___-___-___-
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND（被除数）
DIVISOR   0000.,,....,.,,,
          ----.,,....,.,,,
           0000,,....,.,,,
           0000,,....,.,,,
           ----,,....,.,,,
            0001,....,.,,,
            0000,....,.,,,
            ----,....,.,,,
             0011....,.,,,
             0000....,.,,,
             ----....,.,,,
              0110...,.,,,
              0000...,.,,,
              ----...,.,,,
               1100..,.,,,
               1001..,.,,,
               ====..,.,,,
                0110.,.,,,
                0000.,.,,,
                ----.,.,,,
                 1100,.,,,
                 1001,.,,,
                 ====,.,,,
                  0111.,,,
                  0000.,,,
                  ----.,,,
                   1110,,,
                   1001,,,
                   ====,,,
                    1011,,
                    1001,,
                    ====,,
                     0101,
                     0000,
                     ----
                      1011
                      1001
                      ====
                      0010 = 02 = 2 = REMAINDER（余数）

在十进制里为1559/9=173 余2虽然the input message的每一bit对商的影响并不那样重要，4-bit的余数                                                                                       
在计算时已经kicked掉了很多，并且如果更多的bytes加入信息（被除数），余数的值会迅速的发生巨大变化。这就是加法办不到的地方。你是否在想：用4_bit来校验被传输的信息会看起来像这样（16进制）：06172（0617是信息，2是校验和），接收器将用9来除0617，看余数是否为2。

5.多项式算术 

前面讲的除法方式已经很像CRC算法了，CRC算法稍微有些让人迷惑，我们需要探讨一些奇特的数字系统来理解它。

在处理CRC algorithms 时你将总是听见多项式（polynomial）一词。一个特定的 CRC algorithm 被说成是用一个特别的多项式，CRC algorithm 被普遍认为是一种多项是算法，这是什么意思呢？

除数，被除数，商，余数在这里被看成是有二进制系数的多项式而不是正整数。这是因为将每一个数看成了比特串（bit-string ），比特位就是多项式系数。比如，23（dec）是17（hex）和10111（bin），所以多项式形式为：

                                     1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0

或更简单的写为

                                                  x^4 + x^2 + x^1 + x^0

用这种技术，信息和除数可看成是多项式，并且我们可以用前面的所有算术方法，只是被写成了 Xs的形式。比如，我们想将1101 和 1011相乘。则我们将多项式相乘。

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
    + x^5 + x^3 + x^2
    + x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
这时，为了得到正确的答案，我们不得不假设x为2，将3*x^3进位得：

                                         x^7 + x^3 + x^2 + x^1 + x^0

这就像是普通的算术，只不过基数被抽象化了，and brought into all the calculations explicitly instead of being there implicitly. 这意义何在？

意义在于如果我们假装不知道x是多少，我们就不能做进位运算，我们就不知道 3*x^3与x^4 + x^3 等价，因为我们不知道x是2。在这个真多项式算术中，系数间的关系是未知的，因此每个幂(power )的系数变成了强类型；x^2 的系数对于x^3是一种不同的类型。

幂间的系数被很好地隔离开来，数学家简单的通过改变系数运算的法则提出了各种各样的多项式算术方法。在这些方法中有一种和crc相关，是一种将系数通过mod 2和计算，没有进位，所有系数必须是0或1，无进位计算。被称作“多项式模2和算术”（"polynomial arithmetic mod 2"）。因此，回到早先的例子中：

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

在其他算术方式下， 3*x^3知道x="2"的情况下运用进位机制来向前进(propagate)，在"polynomial arithmetic mod 2"下，我们不知道x是几，这里没有进为，所有系数通过模2和计算。因此，结果变为：

= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

As Knuth [Knuth81] says (p.400):

"The reader should note the similarity between polynomial arithmetic and multiple-precision arithmetic (Section 4.3.1), where the radix b is substituted for x. The chief difference is that the coefficient u_k of x^k in polynomial arithmetic bears little or no relation to its neighboring coefficients x^{k-1} [and x^{k+1}], so the idea of "carrying" from one place to another is absent. In fact polynomial arithmetic modulo b is essentially identical to multiple precision arithmetic with radix b, except that all carries are suppressed."

所以 polynomical arithmetic mod 2就是没有进为的二进制算术。多项式为CRC和error-correction 提供有用的分析方法，为了很好的阐明？他们为提供额外的insight 和some encumbrance，and have been discarded in the remainder of this document 而有利于直接操作这个arithmetical system

Thus polynomical arithmetic mod 2 is just binary arithmetic mod 2 with no carries. While polynomials provide useful mathematical machinery in more analytical approaches to CRC and error-correction algorithms, for the purposes of exposition they provide no extra insight and some encumbrance and have been discarded in the remainder of this document in favour of direct manipulation of the arithmetical system with which they are isomorphic: binary arithmetic with no carry.