6.没有进位的二进制算术

让我们暂时忽略多项式，这样能让我们专注于算术本身，既是CRC 计算时的无进位的二进制计算。它通常被叫为多项式算术，但我已声明暂时忽略多项式，所以我们叫它CRC算术。因为这个算法是CRC计算的关键，我们最好熟练他。开始啦：

CRC算法的两个数相加除了没有进为，其他的都和普通的二进制算法一样。这意味着每对相对应的位决定了相对应位的输出，而不用涉及到其他位。比如：

         10011011
       +11001010
        --------
          01010001
        --------

这里只有4种可能情况 :

   0+0=0
   0+1=1
   1+0=1
   1+1=0  (no carry)无进为

减法也一样：

         10011011
       -11001010
        --------
         01010001
        --------

在这里：

   0-0=0
   0-1=1  (wraparound)
   1-0=1
   1-1=0

事实上 ，CRC算法中的加和减都等价于异或运算（XOR）.异或运算是自身的反转？ 这有效的降低了the first level of power (addition, subtraction) 为单一的自身取反运算，这是该算法一个很有用的性质。

通过整合加法和减法，这种算术摒弃了magnitude beyond the power of its highest one bit的观念。显然，1010比10大，但是1010不再认为比1001大。为了说明这一点，请注意我们可以同过加或减相同的数由1010得到1001：

   1010 = 1010 + 0011
   1010 = 1010 - 0011

这使任何次序的观念变的没有意义，定义完加，我们可以转移到乘和除上，乘法很直接，就是第一个数根据第二个数作右移的和：

         1101
      x 1011
        ----
        1101
       1101.
      0000..
     1101...
     -------
     1111111  Note: The sum uses CRC addition（和使用CRC加法）
     -------
除法要麻烦一些，因为我们需要知道何时一个数变为另一个数，我们回忆一个早先关于量的弱定义，如果x的最高位等于或大于y的最高位，那么我们说x大于或等于y，向下面是详细的除法运算。 (nicked from [Tanenbaum81]). 照搬于[Tanenbaum81]

                     1100001010
           _______________
10011 ) 11010110110000
             10011,,.,,....
             -----,,.,,....
               10011,.,,....
               10011,.,,....
               -----,.,,....
                 00001.,,....
                 00000.,,....
                 -----.,,....
                   00010,,....
                   00000,,....
                    -----,,....
                     00101,....
                     00000,....
                      -----,....
                       01011....
                       00000....
                        -----....
                         10110...
                         10011...
                         -----...
                           01010..
                           00000..
                            -----..
                             10100.
                             10011.
                              -----.
                             01110
                             00000
                               -----
                               1110 = Remainder余数

这就是除法，在更深入前，我们应稍微练习一下来熟悉他。

我们已讲了加和减，它们是一回事。然而在这里，我们应注意算术A+0=A 和        A-0=A。这个明显的性质待会儿很有用。

在处理CRC乘法和除法前，值得建立乘法和除法的观念。

如数A是数B 的倍数，这意味着在CRC运算里，可以用B的多个位移相异或从0 得到A。比如，如果A是0111010110，B是11，我们可以用B构建A：

                  0111010110
                =       .......11.
                  +  ....11....
                  + ...11.....
                  . 11.......

但如果，A是0111010111，就不可能从B的多个位移相异或从0 得到A。（这是为什么？过后再讲），所以在CRC算术里被说成不能被B 整除。

由此我们得知，CRC算术主要就是异或一个特殊数的多个位移。

7.一个详尽的例子

定义完CRC算术后，我们可以简单的用除法来构建CRC计算，因为那就是CRC的全部。本部分讲述细节并给出例子。我们需要选一个除数来作CRC运算。在数学里，这个除数被称为生成多项式，或简单叫做多项式，是CRC算法的一个主要参数。或许将除数叫做其他的更好，但是“poly”这个说法在这个领域里是如此的根深蒂固以至如果避开它反而会带来不便，于是我们妥协一下，把CRC多项式叫poly。 Just think of this number as a sort of parrot. "Hello poly!"

你可以选任何一个多项式来提出一个CRC 算法。但是，一些 poly比其他的要好，因此聪明的做法是尽量使用那些已经被测试过的polys。随后的章节将说明这一点。

poly的宽度W（最高一位的位置）是很重要的，因为它控制作整个计算。典型的选择宽度W16或32，以便于在计算机上实施。 poly 的宽度实际上就是最高一位的比特位。比如，10011的宽度W是4，而不是5。我们选择10011作为poly（宽度W为4）

选择 poly以后，我们就可以进行计算了。就是用 poly来除信息 message ，唯一的变化就是先将W个0加在信息后，然后再计算。因此，我们有：

   Original message                           : 1101011011
   Poly                                              :           10011
   Message after appending W zeros : 11010110110000

现在，我们用CRC arithmetic，用poly来除这个被放大了的信息。这和前面的除法一样：

                          1100001010 = Quotient (nobody cares about the quotient)
                 _______________
     10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
       =Poly  10011,,.,,....
                  -----,,.,,....
                    10011,.,,....
                    10011,.,,....
                    -----,.,,....
                      00001.,,....
                      00000.,,....
                   -----.,,....
                        00010,,....
                        00000,,....
                         -----,,....
                          00101,....
                          00000,....
                           -----,....
                            01011....
                            00000....
                            -----....
                              10110...
                              10011...
                              -----...
                                01010..
                                00000..
                                -----..
                                  10100.
                                  10011.
                                       -----.
                                    01110
                                    00000
                                       -----
                                       1110 = Remainder = THE CHECKSUM!!!!

这个除法产生了一个商，我们不管他。也产生了一个余数，就是校验和。计算结束。

通常情况下，将校验和附在信息后进行传输。本例中，传输的是：

11010110111110

在接收端，接收机作下面两件事之一:

1.将信息和校验和分开。计算信息的校验和（在附加了W个0后），然后比较两个校验和。

2.将接收的数做校验，看结果是否为0！

这两个选择是相等的。但在下一节，我们选择2，因为在数学上这样更干净，清楚。

CRC算术的总结：

1.选择宽度W ，和一个poly  G（宽为W）                                                                       2.在信息后附加W个0。称做M'                                                                                         3.使用  CRC arithmetic  用G除M' ，余数是校验和

That's all there is to it.

Chapter 8) Choosing A Poly

Choosing a poly is somewhat of a black art and the reader is referred to [Tanenbaum81] (p.130-132) which has a very clear discussion of this issue. This section merely aims to put the fear of death into anyone who so much as toys with the idea of making up their own poly. If you don't care about why one poly might be better than another and just want to find out about high-speed implementations, choose one of the arithmetically sound polys listed at the end of this section and skip to the next section.

First note that the transmitted message T is a multiple of the poly. To see this, note that 1) the last W bits of T is the remainder after dividing the augmented (by zeros remember) message by the poly, and 2) addition is the same as subtraction so adding the remainder pushes the value up to the next multiple. Now note that if the transmitted message is corrupted in transmission that we will receive T+E where E is an error vector (and + is CRC addition (i.e. XOR)). Upon receipt of this message, the receiver divides T+E by G. As T mod G is 0, (T+E) mod G = E mod G. Thus, the capacity of the poly we choose to catch particular kinds of errors will be determined by the set of multiples of G, for any corruption E that is a multiple of G will be undetected. Our task then is to find classes of G whose multiples look as little like the kind of line noise (that will be creating the corruptions) as possible. So let's examine the kinds of line noise we can expect.

SINGLE BIT ERRORS

A single bit error means E="1000"...0000. We can ensure that this class of error is always detected by making sure that G has at least two bits set to 1. Any multiple of G will be constructed using shifting and adding and it is impossible to construct a value with a single bit by shifting an adding a single value with more than one bit set, as the two end bits will always persist.

TWO-BIT ERRORS

To detect all errors of the form 100...000100...000 (i.e. E contains two 1 bits) choose a G that does not have multiples that are 11, 101, 1001, 10001, 100001, etc. It is not clear to me how one goes about doing this (I don't have the pure maths background), but Tanenbaum assures us that such G do exist, and cites G with 1 bits (15,14,1) turned on as an example of one G that won't divide anything less than 1...1 where ... is 32767 zeros.

ERRORS WITH AN ODD NUMBER OF BITS

We can catch all corruptions where E has an odd number of bits by choosing a G that has an even number of bits. To see this, note that 1) CRC multiplication is simply XORing a constant value into a register at various offsets, 2) XORing is simply a bit-flip operation, and 3) if you XOR a value with an even number of bits into a register, the oddness of the number of 1 bits in the register remains invariant. Example: Starting with E="111", attempt to flip all three bits to zero by the repeated application of XORing in 11 at one of the two offsets (i.e. "E=E XOR 011" and "E=E XOR 110") This is nearly isomorphic to the "glass tumblers" party puzzle where you challenge someone to flip three tumblers by the repeated application of the operation of flipping any two. Most of the popular CRC polys contain an even number of 1 bits. (Note: Tanenbaum states more specifically that all errors with an odd number of bits can be caught by making G a multiple of 11).

BURST ERRORS

A burst error looks like E="000"...000111...11110000...00. That is, E consists of all zeros except for a run of 1s somewhere inside. This can be recast as E=(10000...00)(1111111...111) where there are z zeros in the LEFT part and n ones in the RIGHT part. To catch errors of this kind, we simply set the lowest bit of G to 1. Doing this ensures that LEFT cannot be a factor of G. Then, so long as G is wider than RIGHT, the error will be detected. See Tanenbaum for a clearer explanation of this; I'm a little fuzzy on this one. Note: Tanenbaum asserts that the probability of a burst of length greater than W getting through is (0.5)^W.

That concludes the section on the fine art of selecting polys.

Some popular polys are:

16 bits: (16,12,5,0)                              [X25 standard]
         (16,15,2,0)                              ["CRC-16"]
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)  [Ethernet]