CRC error correction

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.

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

[snip]

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

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

Thanks, Rob

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.

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.

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.

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.

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

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.

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

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.

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.