Tagged: Cyclic redundancy check

ummm, in retrospect…


Update: I had another look at this. Actually, in retrospect, the substance of the lecture notes are not wrong, but they are worded for electronic engineers rather than computer scientists or mathematicians

Normally one would present the process of creating a code word in the form:

P(x) = m(x)G(x)

Where P(x) is the code word, m(x) is the message to be coded and G(x) the generator matrix. The lecture notes present the generator matrix in a systematic form which would be the equivalent of:

P(x) = m(x)IG(x) , where I is the identity matrix.

Here’s a quandry: you are researching “Cyclic Redundancy Codes” (CRCs) – mainly for finding a clearer way to explain them, when you come across some lecture notes from an academic at one of the bigger universities in Western Europe which, initially at least, look like a model of clear exposition.

But as you read on, you realise with growing incredulity that what the lecturer describes as CRCs are not CRCs at all but general linear block codes.

Now, the principles are similar – in that the lecturer discusses generator matrices and parity check matrices, but the details are hopelessly wrong.

So, do you (a) denounce the academic in public, or (b) contact them in private or (c) post a ‘blind’ blog and wonder about what value students and taxpayers are getting for their money?

 

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)

 

 

 

Related articles

Calculating CRCs in hardware


This, dismally crude (sorry), drawing shows how it is done for the simplest type of CRC – a parity bit. This arrangement calculates an even parity bit (ie it ensures that the bit stream transmitted always contains an even number of ones).

Parity bit calculation

The parity bit will be set to 0 if the input has an even number of 1 bits and 1 if it has an odd number of 1s: here is how it works (the gate is a XOR gate).

As this is a CRC the parity bit is originally set to 0. So for input 1011 we have:

(input bit) 1 XOR (parity bit) 0 = (final state of parity bit) 1
0 XOR 1 = 1
1 XOR 1 = 0
1 XOR 0 = 1

(so in this case the bit is set to 1)

And for 100111 we have:

1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 1 = 1
1 XOR 1 = 0
1 XOR 0 = 1
1 XOR 1 = 0

So, as the input already has an even number of bits then the parity bit would be set to 0.

This is the equivalent of a CRC generator polynomial of x^1+x^0 . A parity bit will catch the switching of one (or any odd number) of bits but will fail to detect errors for any even number of bit switches, so it is of some, but limited, use.

For bigger generator polynomials a similar arrangement is used – with more bits where the parity register is (see Computer Networks and Internets).

Related articles

Cyclic Redundancy Checks


Andrew S. Tanenbaum. Picture made with permiss...

Image via Wikipedia

If you have ever downloaded any software from the internet you are quite likely to have seen a reference to a “CRC” – a cyclic redundancy check.

I have been reading about them as I plough on through Andrew Tanenbaum‘s (pictured) Computer Networks: so here is an explanation based closely on his text (though it’s not a copy except where indicated)…

CRCs rely on some properties of polynomial arithmetic, namely polynomials with the coefficients 0 or 1 only.

We say that a k-bit\ frame is a list of coefficients for a polynomial with k terms ie for a polynomial ranging from x^{k-1} to x^0   (which is said to have degree\ k-1 ).

So 11001101 represents x^7 + x^6 +x^3 + x^2 + x^0 .

Polynomial arithmetic is a form of modulo-2 arithmetic “according to the rules of algebraic field theory” (that’s what it says in the book!). In practise what this means is that there are no “carry-overs” and addition and subtraction are identical and the same as exclusive or (XOR).

Hence 11011 + 10111 = 01100 while 10011 - 01011 = 11000 and so on…

To use a CRC a sender and receiver must agree a generator polynomial: in fact these are now generally standardised and IEEE 802 (network protocols) defines:

x^{32}+x^{26}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1

(the last two terms are of course equivalent to x^1+x^0 ).

1. Let us call this generator polynomial G(x) and let M(x) represent the polynomial (ie the sequence of 0s and 1s) we wish to transmit (with m bits) – M(x) must have more bits than G(x) .

2. Let r be the degree of G(x) – so we append r zero bits to the lower end of the frame, which now has m + r bits and is M(x)x^r (or M(x)2^r ).

3. Divide M(x)x^r by G(x) using modulo 2 division.

4. Subtract the remainder (which will always be r or fewer bits (as G(x) is of degree r) from the M(x)x^r string (again using modulo 2 subtraction). This gives the checksummed frame to be transmitted – we shall call this T(x) .

If the frame is transmitted correctly then when it is received it should be cleanly divisible by G(x) (as taking away the remainder in step 4 should leave us with a cleanly divisible frame). The additional checksum is merely the additional r bits at the end.

The power of the checksum relies on some of its mathematical properties – it will always detect single bit errors if G(x) contains more than one term – as the bad frame is now T(x) + E(x) where E(x) is the error but in this case E(x) = x^i where i is the “bad bit” but with a two-termed G(x) , x^i/[x^m + x^n] \neq 0 for any i, m, n.

Similarly, if there are two errors then E(x) = x^i + x^j = x^j(x^{i-j} + 1) so if G(x) does not cleanly divide x^k + 1 where k can be any value from 1 to the maximum of i -j (ie  the frame length) then any two bit error would be detected.

Similarly, if there are an odd number of errors then E(x) cannot be divisible by a G(x) that contains the terms x + 1. We can show by a reductio ad absurdum proof:

1. We know that an E(x) must be capable of evaluating to one: eg x^i + x^j + x^k must evaluate to 1 if x = 1. But if E(x) is divisible by (x + 1) then E(x) = (x + 1)F(x) , but if x = 1 then, modulo 2, x + 1 = 1 + 1 = 0 so E(x) = 0.

To really fool the system the error pattern would have to match G(x) which is, assuming all transmission errors are equally likely (in fact they are not, but we will ignore that for now), has a probability (again, the book says) of \frac{1}{2}^{r -1}   which is pretty small for the IEEE picked G(x) . (The GNU calculator says it is zero – so it’s too small to register there!)

Related Articles