I know the whole intention of using CRC is to do error detection, but I heard someone state that it can be used to do basic error correction in addition to error detection. I was curious if this was the case, and if so, how powerful is it? I mean, we usually refer to CRC as capable of performing x-bit detection, but I'm curious if it is capable of performing x-bit correction. If so, how does this work? Thanks.
4 Answers
Late answer, but CRC32 polynomial
0x1f1922815 (= 0x787 * 0x557 * 0x465 * 0x3 * 0x3)
can detect up to 7 bit errors and correct up to 3 bit errors for a 1024 bit (992 bit data, 32 bit CRC) message. There are comb(1024,1) + comb(1024,2) + comb(1024,3) = 178957824 correctable bit error patterns. If there is enough memory for a 1431662592 byte table (178957824*8 = ~1.4 GB), then all possible 1, 2, and 3 bit error CRC's could be generated and stored in that table, where each entry would be: 32 bit CRC, a 2 bit error count, and three 10 bit fields for bit error locations.
The table would then be sorted, and when checking a CRC, if it is bad, a binary search of the table (max 28 loops) could determine if it was a 1, 2, or 3 bit error case and corrected using the indexes stored in the table.
However, there is a possibility of mis-correction with 5 or more bit errors. If some 5 error bit pattern produces the same CRC as a 3 error bit pattern, the wrong 3 bits will be changed, resulting in an 8 bit error that appears to have a valid CRC.
Link to example code:
Related