CRCs as matrix maths

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.,

$p(x) = c_02^0 + c_12^1 + c_22^2 + c_32^3 + ... + c_{n - 1}2^{n - 1}$

(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 $c_{n -1} \rightarrow c_0$

We can construct a codeword in the form $p(x) = m(x)g(x) + r(x)$ where $m(x)$ is the message, $g(x)$ is the (monic) generator and $r(x)$ a remainder (of the same or lesser order as $g(x)$ ).

But if we stipulate that $g(x)$ is of the smallest order of a codeword then that means $r(x)$ must be zero.

So, what does a generator matrix look like?

If we have a monic generator polynomial $g(x)$ of degree $k$ and a code word length of $n$ :

$G = \left( {\begin{array} {rrrrrrrr} g_0 & g_1 & g_2 & ... & g_k & 0_l & 0_m & 0_n \\ 0_a & g_0 & g_1 & g_2 & ... & g_k & 0_m & 0_n \\ ... & ... & ... & ... & ... & ... & ... & ... \\ 0_a & 0_b & 0_c & g_0 & g_1 & ... & g_j & g_k \end{array} } \right)$

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)

Related articles

Rate this:

Share this:

Like this:

Related