CRC error correction

I am looking at using a CRC to provide single bit error correction and
multiple bit error detection.  I have worked with CRCs before and know
how to implement them.  But I am lacking some of the theoretical
background on how to choose the polynomial.  My data packets are a
total of 191 bits with a 31 bit header containing the CRC and 160 data
bits.  The header will have its own error correction.  I am trying to
determine an optimal CRC polynomial for the whole packet.  Currently
there is space in the header for a CRC-8.  I may be able to find a few
spare bits to make the CRC 10 or 12 bits if I have to.

Any pointers to show me how to evaluate a polynomial?  Or any shortcuts
that can be recommended?  I guess this has been done before.

"rickman" <spamgoeshere4@yahoo.com> wrote in message 
news:1136591102.008773.180960@g43g2000cwa.googlegroups.com...
>I am looking at using a CRC to provide single bit error correction and
> multiple bit error detection.  I have worked with CRCs before and know
> how to implement them.  But I am lacking some of the theoretical
> background on how to choose the polynomial.  My data packets are a
> total of 191 bits with a 31 bit header containing the CRC and 160 data
> bits.  The header will have its own error correction.  I am trying to
> determine an optimal CRC polynomial for the whole packet.  Currently
> there is space in the header for a CRC-8.  I may be able to find a few
> spare bits to make the CRC 10 or 12 bits if I have to.
>
> Any pointers to show me how to evaluate a polynomial?  Or any shortcuts
> that can be recommended?  I guess this has been done before.
>

You can't correct errors with a CRC. Detection only, then request a 
re-transmit. For error correction you need a block code or something like 
that.

If you end up using a CRC anyway, the web site below will generate VHDL or 
Verilog code to calculate CRCs for any polynomial and any data width. It's 
incredibly useful.

http://www.easics.be/webtools/crctool

As for how to choose a polynomial, that's complicated. I'd stick with one of 
the standard ones. There's a pull-down menu on the site above where you can 
select from a list of standard polynomials. The only 8-bit one is for the 
ATM HEC.

Good luck.

Rob 

RobJ wrote:
> "rickman" <spamgoeshere4@yahoo.com> wrote in message
> news:1136591102.008773.180960@g43g2000cwa.googlegroups.com...
> >I am looking at using a CRC to provide single bit error correction and
> > multiple bit error detection.  I have worked with CRCs before and know
[snip]
> You can't correct errors with a CRC. Detection only, then request a
> re-transmit. For error correction you need a block code or something like
> that.

Actually, you can use a CRC to correct errors, for a sufficiently short
message.

Think about the equivalence of a CRC and a block code.  The terminology
is very different (between the CRC and the block coding camps), which
makes it hard to understand, but if you try you can formulate the CRC
in terms of a generator matrix.

Regards,
Allan

<allanherriman@hotmail.com> wrote in message 
news:1136594549.274038.301910@g14g2000cwa.googlegroups.com...
>
> Actually, you can use a CRC to correct errors, for a sufficiently short
> message.
>
> Think about the equivalence of a CRC and a block code.  The terminology
> is very different (between the CRC and the block coding camps), which
> makes it hard to understand, but if you try you can formulate the CRC
> in terms of a generator matrix.
>

Wow, that's news to me. Can you show how this is done in equation form?

Thanks,
Rob 

rickman wrote:

> I am looking at using a CRC to provide single bit error correction and
> multiple bit error detection.  I have worked with CRCs before and know
> how to implement them.  But I am lacking some of the theoretical
> background on how to choose the polynomial.  My data packets are a
> total of 191 bits with a 31 bit header containing the CRC and 160 data
> bits.  The header will have its own error correction.  I am trying to
> determine an optimal CRC polynomial for the whole packet.  Currently
> there is space in the header for a CRC-8.  I may be able to find a few
> spare bits to make the CRC 10 or 12 bits if I have to.
> 
> Any pointers to show me how to evaluate a polynomial?  Or any shortcuts
> that can be recommended?  I guess this has been done before.
> 
I highly recommend "Error Correction Coding for Digital Communications" 
by Clark & Cain.  It'll tell you how to do it, and if I recall correctly 
the table at the back will even give you some candidate polynomials.

You should probably be searching under the keywords "polynomial codes" 
for information.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

One feature to look for is if your data is likely to have a lot '0's either 
by error or otherwise then to use a algorithm that has a starting preload of 
all '1's in the CRC. '0's then have an effect on the CRC generated right 
from the start of the data and hence errors can be detected. If you have a 
preload of '0's that isn't the case.

John Adair
Enterpoint Ltd. - Home of Broaddown2. The Ultimate Spartan3 Development 
Board.
http://www.enterpoint.co.uk


"rickman" <spamgoeshere4@yahoo.com> wrote in message 
news:1136591102.008773.180960@g43g2000cwa.googlegroups.com...
>I am looking at using a CRC to provide single bit error correction and
> multiple bit error detection.  I have worked with CRCs before and know
> how to implement them.  But I am lacking some of the theoretical
> background on how to choose the polynomial.  My data packets are a
> total of 191 bits with a 31 bit header containing the CRC and 160 data
> bits.  The header will have its own error correction.  I am trying to
> determine an optimal CRC polynomial for the whole packet.  Currently
> there is space in the header for a CRC-8.  I may be able to find a few
> spare bits to make the CRC 10 or 12 bits if I have to.
>
> Any pointers to show me how to evaluate a polynomial?  Or any shortcuts
> that can be recommended?  I guess this has been done before.
> 

>I am looking at using a CRC to provide single bit error correction and
>multiple bit error detection.  I have worked with CRCs before and know
>how to implement them.  But I am lacking some of the theoretical
>background on how to choose the polynomial.  My data packets are a
>total of 191 bits with a 31 bit header containing the CRC and 160 data
>bits.  The header will have its own error correction.  I am trying to
>determine an optimal CRC polynomial for the whole packet.  Currently
>there is space in the header for a CRC-8.  I may be able to find a few
>spare bits to make the CRC 10 or 12 bits if I have to.

Roughly, it takes log2 N bits to tell you which bit to correct
and another bit to tell you if there is an error.  You probably
want more bits to tell you if it's a correctable vs uncorrectable
error.

If you have 160 data bits, an 8 bit code isn't going to work
very well.

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

>One feature to look for is if your data is likely to have a lot '0's either
>by error or otherwise then to use a algorithm that has a starting preload of
>all '1's in the CRC. '0's then have an effect on the CRC generated right
>from the start of the data and hence errors can be detected. If you have a
>preload of '0's that isn't the case.

The glitch that preloading the CRC register to non-0 catches is
leading 0s getting added/or dropped from the message.  (Clock
screwups, not data screwus.)

I'm not a math wiz, but I think it goes roughly like this:

The final CRC is the remainder after dividing the message by the
polynomial.  Leading 0s don't change the answer.

I think that preloading the CRC register is roughly adding
that as high bits to the front of the message.  So adding/dropping
a leading 0 on the message shifts the preload and thus changes the
remainder from the divide.

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

Hal Murray wrote:
> If you have 160 data bits, an 8 bit code isn't going to work
> very well.
Single-error detection requires only a parity bit.
For error correction you need more redundanvy.
Hamming codes are the classical way to correct single-errors.
Below is the table of redundant (Hamming) bits required.
It shows that 8 additional bits can detect and correct a single error
in 255 data bits, including the Hamming bits, so they can protect up to
247 original data bits, providing enough information to perform
single-error correction..
Peter Alfke, from home.

Hamming Single-Bit Error Correction

Max data bits + parity bits = total bits

4				+3		=	7
11				+4		=	15
26				+5		=	31
57				+6		=	63
120				+7		=	127
247				+8		=	255
502				+9		=	511
1013			+10		=	1023
2036			+11		=	2047
4083			+12		=	4095
8179			+13		=	8192

etc.

It takes only 8 Hamming bits to error-correct up to 247 data bits. See
table below.
Peter Alfke, from home

Hamming Single-Bit Error Correction

Max data bits + parity bits = total bits

4				+3		=	7
11				+4		=	15
26				+5		=	31
57				+6		=	63
120				+7		=	127
247				+8		=	255
502				+9		=	511
1013			+10		=	1023
2036			+11		=	2047
4083			+12		=	4095
8179			+13		=	8192

etc.