Lair Of The Multimedia Guru

2005-12-05

(Mis)using CRCs for error correction

Cyclic Redundancy Check codes are commonly used for detecting errors, but they can also be used to correct single and multibit errors. To be able to correct e errors per code word and detect code words with d errors, its needed for the minimum hamming distance of a code to be > 2e+d
So what is the relation between the code word length and the minimum hamming distances for crc codes?

generator polyom hd≥3 hd≥4 hd≥5 hd≥6 hd≥7 hd≥8
CRC- 4 0xF0000000 5 5 5 5 5 5
CRC- 5 0x28000000 31 4 4 4 4 4
CRC- 7 0xA2000000 15 15 7 7 7 7
CRC- 7 0x12000000 127 6 6 6 6 6
CRC- 7 0x6E000000 63 63 9 9 7 7
CRC- 8 0x07000000 127 127 8 8 8 8
CRC- 8 0x39000000 17 17 17 7 7 7
CRC- 8 0xD5000000 93 93 10 10 8 8
CRC-12 0x80F00000 2047 2047 13 13 12 12
CRC-12 0x80B00000 510 171 36 13 13 13
CRC-12 0x1F100000 65 65 65 21 13 11
CRC-15 0x8B320000 127 127 127 127 22 22
CRC-16 0x10210000 32767 32767 16 16 16 16
CRC-16 0x80050000 32767 32767 16 16 16 16
CRC-16 0xA0970000 32766 32766 83 83 24 24
CRC-16 0xC5030000 7161 496 85 36 24 22
CRC-16 0x90D90000 151 151 151 151 21 21
CRC-24 0x80510100 7161 7161 1030 1030 24 24
CRC-32 0x04C11DB7 4294967295 91638 3006 299 203 122
CRC-32 0x404098E2 1024 1023 1023 1023 1023 1023
CRC-32 0x1EDC6F41 2147483647 2147483647 5275 5275 209 209
CRC-32 0x741B8CD7 114695 114695 16392 16392 184 184
CRC-32 0xF4ACFB13 65534 65534 32768 32768 306 306
CRC-32 0x32583499 65538 65538 32770 32770 166 166
CRC-32 0x20044009 65538 65538 32770 32770 32 32
CRC-32 0xA833982B 65537 65537 65537 1091 113 89
CRC-32 0x00210801 65537 65537 65537 31 31 31

These where found using crc_test.c
Actually correcting errors is pretty trivial, for a single bit error, feeding the code below with the calculated crc XOR the received crc, will give you the distance from the end where the error ocured, and yeah if they match (crc=0) thn theres no single bit error

int get_single_error(int crc, int len){
    int i, v=1;

    for(i=0; i<len ; i++){
        if(v == crc)
            return i;
        v= (v<<1) ^ (generator_polynom & (v>>31));
    }
    return -1;
}

ill post some code examples to fix multibit errors later …

Filed under: Error Correcting Codes — Michael @ 20:23

6 Comments »

  1. Hello,
    I have a question on your article about CRC.

    In the file http://guru.multimedia.cx/wp-content/crc_test_v2.c, you’re speaking about ecs source ? Do you have a link to the paper defining this polynom ?
    {0x404098E2, 32}, //CRC-32 (ecs)

    the polynom is finishing by 0 … or is it smaller than 32 ?

    Seem to be very interresting as it maintains high HD for 1023 bits. Can it be a bug ? Can’t find it in Koopmann doc.

    generator polyom hd≥3 hd≥4 hd≥5 hd≥6 hd≥7 hd≥8
    CRC-32 0×404098E2 1024 1023 1023 1023 1023 1023

    thanks in advance for your help

    best regards

    Comment by Alexandre — 2007-04-09 @ 07:48

  2. i have the 0x1404098E2 polynom from a book “error control systems for digital communication and storage by stephen b. wicker” that book refers to the following paper as source for the polynom: “Optimum cyclic redundancy codes for noisy channels by Merkey, P.; Posern, E. C. IEEE Transactions on Information Theory (ISSN 0018-9448), vol. IT-30, Nov. 1984, p. 865-867.”
    ive not checked that this paper actually contains this polynom …

    and yes the last term is 0 so i guess it could be called CRC-31 …

    Comment by Michael — 2007-04-11 @ 22:27

  3. After further investigation through original papers (Castagnoli and Posner/Merckey, I found that 0×404098E2 is based on factorisation of 3 10 degrees minimal polynom multiply by x and x+1 done only to obtain 32 bit polynom, so it’s a 30 or 31 bit CRC (multiply by x+1 does not change hamming distance, just increase message length by one for a given distance.
    Anyway the more powerful CRC in this categeory (small message length) is CRC-32/8 (Castagnoli) or 0xF1922815 (HD=10 up to 98 bits).

    Comment by Alexandre — 2007-05-28 @ 08:03

  4. Hello, just one cuestion about CRC-32. How many input bits can I use (max) in order not to have repeated outputs?
    Thank you

    Comment by Zero — 2008-01-10 @ 11:07

  5. > Hello, just one cuestion about CRC-32. How many input bits can I use (max) in order not to have
    > repeated outputs?

    Iam not sure what you are asking but, any 32bit checksum will have checksum collisions with more than 32 message bits. For normal CRC-x there are no collisions with x message bits thus CRC is optimal in that sense.

    Comment by Michael — 2008-01-10 @ 19:41

  6. Hi. How should I change crc_test.c code to compute column for hd >=2 too (it is not commented, so I can’t understand it well)?
    Thank you in advance.

    Comment by Peppe Tundo — 2011-01-26 @ 11:13

RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress