Is it possible to do rudimentary error correction with CRC?

Question

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.

Answer 1

It is possible to do single-bit error correction with a CRC. Assume one has a CRC "register" and has functions to run the CRC algorithm forward and backward a bit at a time, ignoring incoming data

int crc_forward(int old_value, int data_bit)
{
  if (old_value & 0x8000)
    return ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit;
  else
    return (old_value SHL 1) ^ data_bit;
}

int crc_reverse(int old_value)
{
  if (old_value & 1)
    return (old_value SHR 1) ^ 0x8810;
  else
    return old_value SHR 1;
}

Suppose one has a packet which is computed so that initializing the crc to some value and running crc_forward for each bit (MSB first) should yield zero. If one gets a CRC value other than zero, one can run the algorithm in reverse (ignoring data bits) until the computed CRC value is 1. That's the location of the incorrect bit.

Note that this approach may be adequate for software error correction in things like NAND flash. To usefully employ it for hardware error correction, one would have to either be able to delay read operations until the ECC could be processed, or else one would need a table of 'syndrome' values and bit positions.

Answer 2

You CAN do multi-bit error correction with CRCs. Looking at wikipedia, with references to koopmans work, a CRC can detect up its hamming_distance-1 errors. The hamming distance depends on the payload length, and the CRC polynomial in use. So for example Koopmans polynomial of 0xBA0DC66B can detect up to 5 bits of error in messages up to 16360 bits long. The algorithm described in the previous two messages can be extended up to as many bits as needed, but the time goes up exponentially with the number of bits to fix.

1. Calculate error CRC = CRC_gotten ^ CRC_expected.
2. Look through all possible 1 bit messages (ie all 0s, a 1, and all 0s) (there are message_length cases to evaluate. Note this is BITS not BYTES) and the error bit is the message that generates the error CRC.
3. Invert the detected bit to correct the error.

If you can't find 1 bit matching the error CRC, look through all 2-bit, 3-bit up to your hamming_distance-1. Note that this gets slow fast, message_length squared for 2 bits, cubed for 3 bits up to fifth power for five bits.

Answer 3

I recently worked on CRC16 error detection and single bit error correction.

Here's the basic idea:

1. Assume you have a single bit error.
2. If the data+crc includes no error, the CRC will be 0, else it is not.
3. We define the CRC sent as CRCs and CRC received as CRCr.
4. Then the error bits are given by CRCox = CRCs ^ CRCr.
5. The result encompasses both CRC errors and data errors.
6. Have look at what relationship between CRCox and the bit error is.

Is this clear? I have a paper about this. If you want to know more, just let me know.