crc.txt

Many crc routine in C

   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 polynomial 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
       [phone]
        --------
        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.


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