CRC error correction

glen herrmannsfeldt  <gah@ugcs.caltech.edu> wrote:

>Tim Wescott <tim@seemywebsite.com> wrote:
>(snip)
> 
>>>> In particular, if the CRC-8 generator polynomial is
>>>> x^8+x^7+x^6+x^4+x^2+1 , can it be used for single error correction ?
>(snip)

>> In the real world errors often come in bursts, so the value of the CRC as 
>> an indication that your whole message is probably corrupted gets totally 
>> lost.

Apparently this polynomial factors, which may mean it looks
more like a Fire Code, which can correct bursts.  Another thing
to check out.

>> Serious FEC schemes use much higher correction bit/data bit ratios.

>Actually, 8 bits as ECC for 64 bit RAM is fairly common.  
>It is especially convenient as it is the same number of bits
>needed for byte parity, which may already be available.

Yes, "serious" FEC methods come in all manner of block sizes
and code rates.

Steve

The OP (edim) noted that

>The polynomial x^8+x^7+x^6+x^4+x^2+1 is not prime because:
>x^8+x^7+x^6+x^4+x^2+1 = (x^5+x^4+x^3+x^2+1)(x^2+x+1)(x+1)

and Steve Pope said

> Apparently this polynomial factors, which may mean it looks
> more like a Fire Code, which can correct bursts. �Another thing
> to check out.

Since (x^2+x+1)(x+1) = x^3 + 1 and x^5+x^4+x^3+x^2+1
is a primitive polynomial of degree 5, the OP's polynomial
x^8+x^7+x^6+x^4+x^2+1 is indeed the generator polynomial
of a Fire  code of length (2^5 - 1)x3 = 31x3 = 93.  This code
can correct bursts of lengths up to 2, that is, it can correct
single errors and *adjacent* double errors.  It *cannot*
correct all patterns of two non-adjacent errors in 93 bits.

Decoders for Fire codes have simple implementations that
slickly hide the basic idea behind the decoding algorithm.
The implementation works as follows.  The received word
is divided by the generator polynomial.  Then the syndrome
is massaged to find the burst error and correct it "on the fly"
as the received word is being read out of the decoder.
But, we can *think* of dividing the received word not by the
generator polynomial, but rather by x^3 + 1 and separately
by x^5+x^4+x^3+x^2+1.  Now, the 93 received bits can be
viewed as 31 3-bit nybbles.  The XOR sum of these nybbles
is, in effect, the result obtained when we divide the received
word by x^3 + 1.  The XOR sum of the 31 nybbles can be

000 (no errors);

100, 010, 001 (one error);

110, 011, 101 (double adjacent bit error: note that the last pattern
corresponds to a two-bit
error pattern that crosses a nybble boundary);

or  111 (undecodable burst error)

In other words, dividing by x^3 - 1 tells us *what* the burst error
is.
Dividing by x^5+x^4+x^3+x^2+1 tells us *which* nybble the burst
error starts in.  Using this, we can correct the burst error.  Not
very
efficient for hardware implementation, but might be useful in a
software implementation, especially if the nybble is a 8-bit byte.

Hope this helps

--Dilip Sarwate

dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

>The OP (edim) noted that

>>The polynomial x^8+x^7+x^6+x^4+x^2+1 is not prime because:
>>x^8+x^7+x^6+x^4+x^2+1 = (x^5+x^4+x^3+x^2+1)(x^2+x+1)(x+1)

>and Steve Pope said

>> Apparently this polynomial factors, which may mean it looks
>> more like a Fire Code, which can correct bursts. &#4294967295;Another thing
>> to check out.

>Since (x^2+x+1)(x+1) = x^3 + 1 and x^5+x^4+x^3+x^2+1
>is a primitive polynomial of degree 5, the OP's polynomial
>x^8+x^7+x^6+x^4+x^2+1 is indeed the generator polynomial
>of a Fire  code of length (2^5 - 1)x3 = 31x3 = 93.  This code
>can correct bursts of lengths up to 2, that is, it can correct
>single errors and *adjacent* double errors.  

I suspected as much.  Thank you, Dilip.

>Decoders for Fire codes have simple implementations that
>slickly hide the basic idea behind the decoding algorithm.
>The implementation works as follows.  The received word
>is divided by the generator polynomial.  Then the syndrome
>is massaged to find the burst error and correct it "on the fly"
>as the received word is being read out of the decoder.

Right. In the way I have done it, I first compute the syndrome, then 
shift the syndrome backwards through the FSR until I see the
desired burst-error pattern.  (In this case, either a single
error or a two bit burst.)  This is often called error-trapping.

Of course with a code this small, one could just use a LUT
on the syndrome.

>But, we can *think* of dividing the received word not by the
>generator polynomial, but rather by x^3 + 1 and separately
>by x^5+x^4+x^3+x^2+1.  Now, the 93 received bits can be
>viewed as 31 3-bit nybbles.  The XOR sum of these nybbles
>is, in effect, the result obtained when we divide the received
>word by x^3 + 1.  The XOR sum of the 31 nybbles can be
>
>000 (no errors);
>
>100, 010, 001 (one error);
>
>110, 011, 101 (double adjacent bit error: note that the last pattern
>corresponds to a two-bit
>error pattern that crosses a nybble boundary);
>
>or  111 (undecodable burst error)
>
>In other words, dividing by x^3 - 1 tells us *what* the burst error
>is.
>Dividing by x^5+x^4+x^3+x^2+1 tells us *which* nybble the burst
>error starts in.  Using this, we can correct the burst error.  Not
>very
>efficient for hardware implementation, but might be useful in a
>software implementation, especially if the nybble is a 8-bit byte.

I like this.  Thanks.

Steve