发信人: micheal (平凡的世界), 信区: ECE
标  题: A Painless Guide to CRC [3]
发信站: 大红花的国度 (Fri Jun  2 09:53:20 2000), 转信

6. A Fully Worked Example
-------------------------
Having defined CRC arithmetic, we can now frame a CRC calculation as
simply a division, because that's all it is! This section fills in the
details and gives an example.
To perform a CRC calculation, we need to choose a divisor. In maths
marketing speak the divisor is called the "generator polynomial" or
simply the "polynomial", and is a key parameter of any CRC algorithm.
It would probably be more friendly to call the divisor something else,
but the poly talk is so deeply ingrained in the field that it would
now be confusing to avoid it. As a compromise, we will refer to the
CRC polynomial as the "poly". Just think of this number as a sort of
parrot. "Hello poly!"
You can choose any poly and come up with a CRC algorithm. However,
some polys are better than others, and so it is wise to stick with the
tried an tested ones. A later section addresses this issue.
The width (position of the highest 1 bit) of the poly is very
important as it dominates the whole calculation. Typically, widths of
16 or 32 are chosen so as to simplify implementation on modern
computers. The width of a poly is the actual bit position of the
highest bit. For example, the width of 10011 is 4, not 5. For the
purposes of example, we will chose a poly of 10011 (of width W of 4).
Having chosen a poly, we can proceed with the calculation. This is
simply a division (in CRC arithmetic) of the message by the poly. The
only trick is that W zero bits are appended to the message before the
CRC is calculated. Thus we have:
   Original message                : 1101011011
   Poly                            :      10011
   Message after appending W zeros : 11010110110000
Now we simply divide the augmented message by the poly using CRC
arithmetic. This is the same division as before:
            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!!!!
The division yields a quotient, which we throw away, and a remainder,
which is the calculated checksum. This ends the calculation.
Usually, the checksum is then appended to the message and the result
transmitted. In this case the transmission would be: 11010110111110.
At the other end, the receiver can do one of two things:
   a. Separate the message and checksum. Calculate the checksum for
      the message (after appending W zeros) and compare the two
      checksums.
   b. Checksum the whole lot (without appending zeros) and see if it
      comes out as zero!
These two options are equivalent. However, in the next section, we
will be assuming option b because it is marginally mathematically
cleaner.
A summary of the operation of the class of CRC algorithms:
   1. Choose a width W, and a poly G (of width W).
   2. Append W zero bits to the message. Call this M'.
   3. Divide M' by G using CRC arithmetic. The remainder is the checksum.
That's all there is to it.
7. 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]

--
┌───────────────────────────────────┐
│　Ｃ = Ｗ·㏒﹝1﹢ＳＮＲ﹞　　　　　　▁▄▇█▇▄▁　　　　　　　　　│
│　﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋      　　▅███████▅　　　　　　　　│
│　噪声不是我的错　:)　　　　　　▃███████████▃　　　　　　│
│　﹌﹌﹌﹌﹌﹌﹌﹌﹌  　　　▂▇█████████████▇▂　　　　│
│▁▁▁▁▁▁▁▂▂▂▃▃▅▇█████████████████▇▄▃▂│

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: sillystone.bbs@smth.]