But now, thanks to another book – Networks on Chips – here’s a slightly more fundamental examination.
CRCs are a form of Cyclic codes – codes where a rotation – eg., make the 0 bit the highest order bit, the previously highest order bit the second highest order bit and so on – produces a new codeword.
As before we can think of code words as polynomials of the power of 2 with coefficients of 0 or 1, eg.,
(And of course any natural number can be represented in this fashion.)
Then a circular shift is similar to multiplying by 2 – though with the proviso that
We can construct a codeword in the form where is the message, is the (monic) generator and a remainder (of the same or lesser order as ).
But if we stipulate that is of the smallest order of a codeword then that means must be zero.
So, what does a generator matrix look like?
If we have a monic generator polynomial of degree and a code word length of :
- Deriving an Incremental Form of the Polynomial Regression Equations (erikerlandson.github.com)
- A smattering of MyForth: CRC16 checksums (toddbot.blogspot.com)
- Selecting a Checksum algorithm (fastcompression.blogspot.com)
- Parity checks as matrix multiplication (cartesianproduct.wordpress.com)