[<<][math][>>][..]
Wed Oct 23 09:20:49 EDT 2019

CRC

EDIT: Principle is right, but implementation details requires some
additional assumptions.  See end.


CRC is modulo reduction using an irreducible polynomial.  I.e. long
division.  However, how does a bit stream actually map to the input
polynomial?  And why does accumulator chaining work?

Let's try to perform a division and fill in the gaps.

x^3 + x + 1  is  1011

Dividing 10101010 by 1011


10101010 | 1011
10110000 |-------
-------- | 10011
   11010
   10110
   -----
    1110
    1011
    ----
     101

Only the remainder is useful.

How to turn this into something that takes a single bit at a time?
Note that only the first 4 bits of the dividend are necessary.  That
is the key to turning this into a state machine.

To visualize, spell out the zero subtractions explicitly.

10101010 | 1011
10110000 |-------
-------- | 10011
 0011010
 0000000
 -------
  011010
  000000
  ------
   11010
   10110
   -----
    1110
    1011
    ----
     101

Then mask out the bits that do not need to be known at each step,
feeding in a bit when it is necessary.

1010.... | 1011
10110000 |-------
-------- | 10011
 0011...
 0000000
 -------
  0110..
  000000
  ------
   1101.
   10110
   -----
    1110
    1011
    ----
     101

The trick here is that there is no carry!  This allows us to carry on
a step without knowing the downstream bits!

This would not work so smoothly with an addition operation that
carries over into lower significant bits.

To restore symmetry, add zero bits.

........
00000000
--------
1.......
00000000
--------
10......
00000000
--------
101.....
00000000
--------
1010.... | 1011
10110000 |-------
-------- | 000010011
 0011...
 0000000
 -------
  0110..
  000000
  ------
   1101.
   10110
   -----
    1110
    1011
    ----
     101


This property allows to just roll the algoritm.

So the "accumulator" is essentially the first 4 digits of the
intermediate, which will end up as the full modulo at the end.

This all seems plausible.  So let's implement it and see if it holds
up.

There are essentially only two operations:
- devision reduction step
- shift in a new bit

The polynomial is typically represented as bits without the top bit
which is always 1.

In our case, the poly residu is 011.

Suppose the accumulator is
1010

The algorithm step is then:
- store the top bit
- shift in the new bit
- xor with residu if top bit was 1


Now I just need to know what the bit order convention is.  It seems
that shifting in MSB first makes most sense.

Let's check this with a crc8 plucked from the internet.



EDIT: This mentions padding at the end.
https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Still not quite clear.  I'm doing something else.

https://rosettacode.org/wiki/CRC-32

I think I have the definition wrong.

From the wikipedia page:

  This is first padded with zeros corresponding to the bit length n of
  the CRC. This is done so that the resulting code word is in
  systematic form.

https://en.wikipedia.org/wiki/Systematic_code

  A systematic code is any error-correcting code in which the input
  data is embedded in the encoded output.

I don't understand this.
But what I am doing is padding with zeros at the start?


So I give up.  Interpret and generalze a working implementation instead:
https://stackoverflow.com/questions/21001659/crc32-algorithm-implementation-in-c-without-a-look-up-table-and-with-a-public-li

So CRC32 and CRC32B are not the same:

https://stackoverflow.com/questions/15861058/what-is-the-difference-between-crc32-and-crc32b






[Reply][About]
[<<][math][>>][..]