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

## CRC

```EDIT: Principle is right, but implementation details requires some

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.

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][>>][..]`