### (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 …

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

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

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

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

> 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

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