CRC error correction

Could you write your CRC+ specs., so.... maybe some of us (me) could
send you some code
to you..?!

>> 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.

Thanks.  I was off by (most of) 1 bit.

You don't need a separate bit to tell you that there is/isn't an
error if you can reserve one of the 2^N positions for the no-error
case.  Thus 8 bits of Hamming only covers a 255 bit message rather
than 256.

There is still the question of how well a Hamming code matches
the error pattern.  Serial links often make multi-bit errors
and things get even more interesting when you run an error
on the serial link through 8b/10b decoders.

-- 
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.

>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..

True enough. If you can guarantee only single-bit errors.
-- 
	mac the na�f

Nobody can ever guarantee the number of errors. It's all a question of
probability.
There are many different codes that are more efficient for detecting
and even correcting error bursts. Fire codes have been popular, and
Reed-Solomon codes are used extensively on audio CDs, where errror
bursts are likely.

Peter Alfke, Xilinx Applications

Some friends and I had a discussion about this a month or two ago. I 
remember being educated about this:-

"Of all practical error correction methods known to date, turbo codes, 
together with Low-density parity-check codes, come closest to approaching 
the Shannon limit, the theoretical limit of maximum information transfer 
rate over a noisy channel."
http://en.wikipedia.org/wiki/Turbo_code
http://en.wikipedia.org/wiki/Low-density_parity-check_code
Cheers, Syms.

"Peter Alfke" <alfke@sbcglobal.net> wrote in message 
news:1136823157.745092.145560@g43g2000cwa.googlegroups.com...
> Nobody can ever guarantee the number of errors. It's all a question of
> probability.
> There are many different codes that are more efficient for detecting
> and even correcting error bursts. Fire codes have been popular, and
> Reed-Solomon codes are used extensively on audio CDs, where errror
> bursts are likely.
>
> Peter Alfke, Xilinx Applications
> 

Symon wrote:
> Some friends and I had a discussion about this a month or two ago. I 
> remember being educated about this:-
> 
> "Of all practical error correction methods known to date, turbo codes, 
> together with Low-density parity-check codes, come closest to approaching 
> the Shannon limit, the theoretical limit of maximum information transfer 
> rate over a noisy channel."
> http://en.wikipedia.org/wiki/Turbo_code
> http://en.wikipedia.org/wiki/Low-density_parity-check_code
> Cheers, Syms.

Although those codes are the best by that standard, that of course does 
not mean they are the best for all situations. Plain CRC codes are very 
simple and very fast. If you are in a situation that is unlikely to 
suffer burst errors, there is probably no reason to use anything else. 
Reed-Solomon codes are not so simple, but still very fast, though with a 
bit of latency. They have strong burst error correction ability and 
achieve a pretty good percentage of the Shannon limit.

Turbo codes and LPDC codes are complicated and (relatively) slow, mainly 
because they use an iterative process to arrive at a solution (I am only 
vaguely familiar with the LPDC codes). Back not so long ago, when 
hardware was expensive, you needed a good reason to use the more 
complicated codes, but that reason is slipping away as hardware gets 
much cheaper and much faster. If you are trying to squeeze every last 
tenth of a db of noise immunity out of a signal (for example, receiving 
signals from a spacecraft), it now might be worth it in many situations.

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.

Thanks for all the replys.  I am aware of the various tradeoffs and I
don't require help with the code for a CRC.  I was trying to pick a
polynomial that would be useful for a data packet of this size.  There
was one resource mentioned in the thread.  I'll see if I can find it.