Sign in

Not a member? | Forgot your Password?

Search compdsp

Search tips

Free PDF Downloads

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

C++ Tutorial

Introduction of C Programming for DSP Applications

Fixed-Point Arithmetic: An Introduction

Cascaded Integrator-Comb (CIC) Filter Introduction

Discussion Groups

FIR Filter Design Software

Free Online Books

See Also

Embedded SystemsFPGA

Discussion Groups | Comp.DSP | CRC error correction

There are 13 messages in this thread.

You are currently looking at messages 1 to .


Is this discussion worth a thumbs up?

0

CRC error correction - edim - 2009-01-06 11:20:00

Hello,
Can CRC be used for error correction (not just detection)?
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 ?


Re: CRC error correction - Vladimir Vassilevsky - 2009-01-06 11:31:00

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


Re: CRC error correction - glen herrmannsfeldt - 2009-01-06 11:43:00

edim <e...@walla.com> wrote:

> Can CRC be used for error correction (not just detection)?
> 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 ?

It depends on how much data you have.

To be able to do single error correction the word size with ECC
bits must be less than or equal to 2**N where N is the number
of ECC bits.  In addition, it is usually desirable to detect
(but not correct) double bit errors, which requries one more
check bit.  (Usually the parity bit for the rest.)

For magnetic tapes in the past, one used one parity bit
per character, and a CRC (or some other type of check word)
at the end of a block.  If the CRC failed then the character
with the wrong parity bit was likely the one in error. 
Given that, you might be able to correct the error.

-- glen


Re: CRC error correction - edim - 2009-01-06 12:23:00

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 ?


Re: CRC error correction - edim - 2009-01-06 12:28:00

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)


Re: CRC error correction - Steve Pope - 2009-01-06 12:35:00

edim <e...@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


Re: CRC error correction - Steve Pope - 2009-01-06 12:36:00

edim <e...@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


Re: CRC error correction - Tim Wescott - 2009-01-06 12:44:00

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


Re: CRC error correction - glen herrmannsfeldt - 2009-01-06 12:45:00

edim <e...@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


Re: CRC error correction - glen herrmannsfeldt - 2009-01-06 12:49:00

Tim Wescott <t...@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


| 1 | |