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

4. Polynomical Arithmetic
-------------------------
While the division scheme described in the previous section is very
very similar to the checksumming schemes called CRC schemes, the CRC
schemes are in fact a bit weirder, and we need to delve into some
strange number systems to understand them.
The word you will hear all the time when dealing with CRC algorithms
is the word "polynomial". A given CRC algorithm will be said to be
using a particular polynomial, and CRC algorithms in general are said
to be operating using polynomial arithmetic. What does this mean?
Instead of the divisor, dividend (message), quotient, and remainder
(as described in the previous section) being viewed as positive
integers, they are viewed as polynomials with binary coefficients.
This is done by treating each number as a bit-string whose bits are
the coefficients of a polynomial. For example, the ordinary number 23
(decimal) is 17 (hex) and 10111 binary and so it corresponds to the
polynomial:
   1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0
or, more simply:
   x^4 + x^2 + x^1 + x^0
Using this technique, the message, and the divisor can be represented
as polynomials and we can do all our arithmetic just as before, except
that now it's all cluttered up with Xs. For example, suppose we wanted
to multiply 1101 by 1011. We can do this simply by multiplying the
polynomials:
(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
At this point, to get the right answer, we have to pretend that x is 2
and propagate binary carries from the 3*x^3 yielding
   x^7 + x^3 + x^2 + x^1 + x^0
It's just like ordinary arithmetic except that the base is abstracted
and brought into all the calculations explicitly instead of being
there implicitly. So what's the point?
The point is that IF we pretend that we DON'T know what x is, we CAN'T
perform the carries. We don't know that 3*x^3 is the same as x^4 + x^3
because we don't know that x is 2. In this true polynomial arithmetic
the relationship between all the coefficients is unknown and so the
coefficients of each power effectively become strongly typed;
coefficients of x^2 are effectively of a different type to
coefficients of x^3.
With the coefficients of each power nicely isolated, mathematicians
came up with all sorts of different kinds of polynomial arithmetics
simply by changing the rules about how coefficients work. Of these
schemes, one in particular is relevant here, and that is a polynomial
arithmetic where the coefficients are calculated MOD 2 and there is no
carry; all coefficients must be either 0 or 1 and no carries are
calculated. This is called "polynomial arithmetic mod 2". Thus,
returning to the earlier example:
(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
Under the other arithmetic, the 3*x^3 term was propagated using the
carry mechanism using the knowledge that x=2. Under "polynomial
arithmetic mod 2", we don't know what x is, there are no carries, and
all coefficients have to be calculated mod 2. Thus, the result
becomes:
= 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."
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.
5. Binary Arithmetic with No Carries
------------------------------------
Having dispensed with polynomials, we can focus on the real arithmetic
issue, which is that all the arithmetic performed during CRC
calculations is performed in binary with no carries. Often this is
called polynomial arithmetic, but as I have declared the rest of this
document a polynomial free zone, we'll have to call it CRC arithmetic
instead. As this arithmetic is a key part of CRC calculations, we'd
better get used to it. Here we go:
Adding two numbers in CRC arithmetic is the same as adding numbers in
ordinary binary arithmetic except there is no carry. This means that
each pair of corresponding bits determine the corresponding output bit
without reference to any other bit positions. For example:
        10011011
       +11001010
        --------
        01010001
        --------
There are only four cases for each bit position:
   0+0=0
   0+1=1
   1+0=1
   1+1=0  (no carry)
Subtraction is identical:
        10011011
       -11001010
        --------
        01010001
        --------
with
   0-0=0
   0-1=1  (wraparound)
   1-0=1
   1-1=0
In fact, both addition and subtraction in CRC arithmetic is equivalent
to the XOR operation, and the XOR operation is its own inverse. This
effectively reduces the operations of the first level of power
(addition, subtraction) to a single operation that is its own inverse.
This is a very convenient property of the arithmetic.
By collapsing of addition and subtraction, the arithmetic discards any
notion of magnitude beyond the power of its highest one bit. While it
seems clear that 1010 is greater than 10, it is no longer the case
that 1010 can be considered to be greater than 1001. To see this, note
that you can get from 1010 to 1001 by both adding and subtracting the
same quantity:
   1010 = 1010 + 0011
   1010 = 1010 - 0011
This makes nonsense of any notion of order.
Having defined addition, we can move to multiplication and division.
Multiplication is absolutely straightforward, being the sum of the
first number, shifted in accordance with the second number.
        1101
      x 1011
        ----
        1101
       1101.
      0000..
     1101...
     -------
     1111111  Note: The sum uses CRC addition
     -------
Division is a little messier as we need to know when "a number goes
into another number". To do this, we invoke the weak definition of
magnitude defined earlier: that X is greater than or equal to Y iff
the position of the highest 1 bit of X is the same or greater than the
position of the highest 1 bit of Y. Here's a fully worked division
(nicked from [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
That's really it. Before proceeding further, however, it's worth our
while playing with this arithmetic a bit to get used to it.
We've already played with addition and subtraction, noticing that they
are the same thing. Here, though, we should note that in this
arithmetic A+0=A and A-0=A. This obvious property is very useful
later.
In dealing with CRC multiplication and division, it's worth getting a
feel for the concepts of MULTIPLE and DIVISIBLE.
If a number A is a multiple of B then what this means in CRC
arithmetic is that it is possible to construct A from zero by XORing
in various shifts of B. For example, if A was 0111010110 and B was 11,
we could construct A from B as follows:
                  0111010110
                = .......11.
                + ....11....
                + ...11.....
                  .11.......
However, if A is 0111010111, it is not possible to construct it out of
various shifts of B (can you see why? - see later) so it is said to be
not divisible by B in CRC arithmetic.
Thus we see that CRC arithmetic is primarily about XORing particular
values at various shifting offsets.

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

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