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)