I wrote about CRCs – cyclic redundancy checks – about a year ago, following on from what I had read in Andy Tanenbaum’s Computer Networks – and because you see CRCs used everywhere.
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
:
Related articles
- 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)