>>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.
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
Reply by dvsa...@yahoo.com●January 8, 20092009-01-08
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
Reply by Steve Pope●January 6, 20092009-01-06
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
Reply by glen herrmannsfeldt●January 6, 20092009-01-06
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.
> 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.
-- glen
Reply by glen herrmannsfeldt●January 6, 20092009-01-06
edim <edim0@walla.com> wrote:
> My message length is 72bits and I add 8bits for CRC
> using this generator polynomial.
> Is there a way to correct one bit in the received block of 80bits ?
Maybe. Since 2**8 >= 80 it is enough.
It would be more usual to use Hamming codes, which directly
indicate the bit in error. You need to find out that the
CRC values are unique for each possible bit error, including
errors in the transmitted CRC.
If you find the dependence of each CRC bit on the 72 data
bits, you can find out which one has to change based on
the received CRC bits. I believe, but haven't verified,
that each CRC bit is formed as an exclusive OR of a
set of data bits. If you find that set, you can
find which bit is in error.
(If homework, be sure to reference the newsgroup.)
-- glen
Reply by Tim Wescott●January 6, 20092009-01-06
On Tue, 06 Jan 2009 10:31:50 -0600, Vladimir Vassilevsky wrote:
> edim wrote:
>
>> Hello,
>> Can CRC be used for error correction (not just detection)?
>
> Yes. CRCs are essentially Hamming or BCH codes, so they can be used for
> error correction. However by using them for error correction you are
> compromising the error detection capacity.
>
>> 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 ?
>
> If this is a prime polynomial, then it can correct a single bit error in
> a block of up to 255 bits.
>
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultant http://www.abvolt.com
BUT
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.
Serious FEC schemes use much higher correction bit/data bit ratios.
--
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com
Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by Steve Pope●January 6, 20092009-01-06
edim <edim0@walla.com> wrote:
>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)
In this case you should measure the distance of the resulting
shortened code; if it is at least three, then you can still do single
error correction.
This may be most rapidly done by simulation.
Steve
Reply by Steve Pope●January 6, 20092009-01-06
edim <edim0@walla.com> wrote:
> My message length is 72bits and I add 8bits for CRC using
> this generator polynomial. Is there a way to correct one bit
> in the received block of 80bits ?
Yes, absolutely. A plain vanilla single-error-correcting
BCH code with 7 check bits can correct a single error for
block lengths up to 127 bits. With 8 check bits, properly
constructed, you can also detect all 2-error cases.
See Sloane et. al, "A Survey of Constructive Coding Theory, and
a Table of Binary Codes of Highest Known Rate", in _Discrete Math._,
V. 3, pp 265-294, Sept 1972 for the full details for any
similar problem, especially if you need to go beyond the
BCH limit.
Steve
Reply by edim●January 6, 20092009-01-06
Vladimir,
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)
Reply by edim●January 6, 20092009-01-06
Thanks,
My message length is 72bits and I add 8bits for CRC using this generator
polynomial.
Is there a way to correct one bit in the received block of 80bits ?