How is a CRC32 checksum calculated?

by

The polynomial for CRC32 is:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Or in hex and binary:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

The highest term (x32) is usually not explicitly written, so it can instead be represented in hex just as

0x 04 C1 1D B7

Feel free to count the 1s and 0s, but you’ll find they match up with the polynomial, where 1 is bit 0 (or the first bit) and x is bit 1 (or the second bit).

Why this polynomial? Because there needs to be a standard given polynomial and the standard was set by IEEE 802.3. Also it is extremely difficult to find a polynomial that detects different bit errors effectively.

You can think of the CRC-32 as a series of “Binary Arithmetic with No Carries”, or basically “XOR and shift operations”. This is technically called Polynomial Arithmetic.

To better understand it, think of this multiplication:

(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

If we assume x is base 2 then we get:

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

Why? Because 3x^3 is 11x^11 (but we need only 1 or 0 pre digit) so we carry over:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

But mathematicians changed the rules so that it is mod 2. So basically any binary polynomial mod 2 is just addition without carry or XORs. So our original equation looks like:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

I know this is a leap of faith but this is beyond my capability as a line-programmer. If you are a hard-core CS-student or engineer I challenge to break this down. Everyone will benefit from this analysis.

So to work out a full example:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Now we 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.

Only use a 32-bit number as your divisor and use your entire stream as your dividend. Throw out the quotient and keep the remainder. Tack the remainder on the end of your message and you have a CRC32.

Average guy review:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. Take the first 32 bits.
  2. Shift bits
  3. If 32 bits are less than DIVISOR, go to step 2.
  4. XOR 32 bits by DIVISOR. Go to step 2.

(Note that the stream has to be dividable by 32 bits or it should be padded. For example, an 8-bit ANSI stream would have to be padded. Also at the end of the stream, the division is halted.)

More Related Contents:

  1. Program gives unstable output? [closed]
  2. Using fflush(stdin)
  3. With arrays, why is it the case that a[5] == 5[a]?
  4. size_t vs. uintptr_t
  5. Printing UTF-8 strings with printf – wide vs. multibyte string literals
  6. How to increment a pointer address and pointer’s value?
  7. Measure time in Linux – time vs clock vs getrusage vs clock_gettime vs gettimeofday vs timespec_get?
  8. Initializing variable length array [duplicate]
  9. Why must the variable used to hold getchar’s return value be declared as int?
  10. Practical usage of setjmp and longjmp in C
  11. Are literal strings and function return values lvalues or rvalues?
  12. faster equivalent of gettimeofday
  13. x86_64 ASM – maximum bytes for an instruction?
  14. How to signal select() to return immediately?
  15. Interprocess mutex with pthreads
  16. Reading numbers from a text file into an array in C
  17. multi-word addition using the carry flag
  18. How is this const being used?
  19. Segmentation fault occurring when modifying a string using pointers?
  20. Writing and reading (fwrite – fread) structures with pointers
  21. How does a mutex lock and unlock functions prevents CPU reordering?
  22. Does any C library implement C11 threads for GNU/Linux?
  23. How do I pass a command line argument while starting up GDB in Linux? [duplicate]
  24. Is int main() { } (without “void”) valid and portable in ISO C?
  25. Providing/passing argument to signal handler
  26. What do pty and tty mean?
  27. How to implement a linked list in C?
  28. gcc detect duplicate symbols/functions in static libraries
  29. Serving multiple domains in one box with SNI
  30. Why won’t extern link to a static variable?

Leave a Comment