CRCs as matrix maths

Standard

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)

 

 

 

Related articles