views:

691

answers:

5

Is there a CRC library that enables the user not only detect errors but also correct them? I'm looking for a C/C++ or Java library, ideally open-source.

+4  A: 

I believe that CRCs can only detect errors, not correct them. That's certainly true of the most common implementation. You want some kind of error correction technique, not a CRC. I'm not aware of any libraries for doing this, but they must be easy enough to find once you know what you're looking for.

rmeador
This doesn't sound right. According to http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/ecc.html: "Any error checking code that can always detect a two-bit error can always correct any one-bit error". And http://www.dsprelated.com/showmessage/107079/1.php: "To be able to do single error correction the word size with ECCbits must be less than or equal to 2**N where N is the numberof ECC bits"
Gili
That's true on a general level, but the CRC algorithm doesn't do correction.
skaffman
You most certainly CAN do error correction with CRC. Use the fact that CRC(A XOR B) = CRC(A) XOR CRC(B)... let B be the error, A the message transmitted, A XOR B is the message received. Then CRC(B) = CRC(A XOR B) XOR CRC(A).It's true that the Hamming-distance proof isn't particularly applicable to all error checking codes (example would be secure hash codes that can't be reserved without great effort), but CRC has no such difficulty.Then you need a lookup table to go from CRC(B) back to B (for single error correction, the lookup table would contain the index of the single error bit).
Ben Voigt
A: 

I don't think CRC is used often for error correction, however if you want to check and repair sets of files you can always try par2, which is often used on usenet. You can find a lot of documentation and implementations on the internet, for example a win32 library.

miguelle
A: 

You should specify more about the data that you're working with. Are you streaming data or storing? How noisy is the transmission?

heyitsme
I am trying to detect and correct errors in a communication protocol.
Gili
+4  A: 

You don't want CRC, but FEC (forward error correction). You can find an open source implementation in libfec.

florin
+2  A: 

The best technical solution about Error Correction is called turbocode. See http://en.wikipedia.org/wiki/Turbo_code for more information about that.

But I'm afraid you won't find much free implementations of it.

If you really want a free one, give a try at http://rscode.sourceforge.net/

zim2001
turbo codes are rather complex in order to achieve high coding efficiencies.
Jason S