CRC Error CORRECTION

[reddy]

Hi all,
I want to 'CRC16 (for input data 16bits) Error Correction (Not
Detection)algorithm/VHDL code'. I have searched, but I could not found any
document for Error CORRECTION. Please suggest me some links/suggetions.
Responses are appreciated.

Thanks and Regards,
Reddy Patlolla

[Allan Herriman]

On Wed, 21 Apr 2004 07:48:45 -0400, "reddy"
<patloll...@india.com> wrote:

>Hi all,
> I want to 'CRC16 (for input data 16bits) Error Correction (Not
>Detection)algorithm/VHDL code'. I have searched, but I could not found any
>document for Error CORRECTION.

That may be because CRC16 isn't designed to be an error correction
code. It is only designed to be an error *detection* code.

What are you really trying to do?

Regards,
Allan.

[Yves Deweerdt]

have a look at this one:

http://www.cuj.com/documents/s=8235/cuj0306mcdaniel/

it is c++ though, but you should get the picture and be able to
transform it to vhdl...

kind regards,

Yves

[Allan Herriman]

On Wed, 21 Apr 2004 15:05:50 +0200, Yves Deweerdt <yv...@news.be>
wrote:

That link contains the text:
"It turns out that you can also use CRCs to correct a single-bit error
in any transmission."

That statement is false in general.

For CRC32, it is theoretically possible to uniquely locate the single
bit error in packets up to 2^32 bits long, which covers any practical
packet length, but not e.g. large files.
(Umm, that might be 2^32-1, rather than 2^32.)

For CRC16, it's a little worse. For starters, it's only 16 bits long,
so only 2^16 bits can be corrected.
Also, CRC16 isn't a primitive polynomial; it has (x+1) as a factor. I
think this means only 2^15 bits can be corrected. (Please, someone
correct me if I'm wrong.)
If all your packets are less than 4k bytes, this might be ok.

Note that in assuming that all possible values of the CRC represent
single bit errors, we have lost the ability to detect multi-bit
errors; they will appear as correctable single bit errors.

I suggest that if the OP is having a problem with single bit errors,
multiple bit errors will also be a problem. Thus some additional form
of error detection is required.

Regards,
Allan.

[Yves Deweerdt]

suppose you have a message of x bits you want to protect with a CRC16,
then you are actually generating codewords of (x+16) bits.
you have to do the CRC16 calculation on the entire code word. If a code
word is correct you will get a remainder of 0. A code word wit biterrors
will result in a remainder different from 0.

The error detection/correction capabilities of the CRC16 depend on how
much x is... If x is small enough you can prove that all possible single
bit errors have a unique remainder, this remainder is the one they store
in a lookup table as it gives you the position of the erronous bit.
remainders that are not in the table correspond to code words with more
than 1 bit error...

If I'm not mistaken it was possible to protect 24 bits of information
with a CRC6 (this one is out of memory, I'm not sure any more...)

Regards,

Yves

[reddy]

Thank You for your response. I found some useful info in the link given.
I need to calculate HEC16 for a 16bit or 32 bit header, for this i need
single bit error correction. This is a part of GFP (Generic Framing
Procedure). As one of the friends asked where to I needed this Iam telling
all this. If you found any relevent links let you please send me.
Thank You once again,

Pradeep

[reddy]

[Yves Deweerdt]

Check this one out:
http://www.easics.be/webtools/crctool

it generates a vhdl package containing a function you have to call to
calculate a CRC.
The only thing that you have to do yourself is, implement the lookup
table in vhdl.

just calculate the remainder of all the codewords of this form:

100.......000 -> remainder1
010.......000 -> remainder2
001.......000 -> remainder3
.............
000...1...000 -> ...
.............
000.......100
000.......010
000.......001 -> remainder(number of bits of the codeword)

if calculate a hec of the header and you get remainder1 then it means
that you have to flip the bit at the leftmost position, and so on...

If you get a remainder not in the lookup table there is a multiple bit
error...

Good luck!

[reddy]

I agree with you, but one moredoubt is:
For multiple inputs the remainder may be 10....000. I feel this because
check-sum will be of 32 bit(2pow 32-1 combinations). So, there is a chance
that for more than one check-sum we get the remainder as 10....000 (I took
this remainder here as an example).
According to the concept you said, for CRC16(for 16bit Header), we have
only 32 outcomes(in the LookUp table). Please clear me this doubt. If you
did not understand this, let me know, I shall explain in detail in the
next mail.

thanks and regards,
Pradeep

[reddy]

Yes, I got it now. I worked out now, and the result is nothing but what you
explained in the last mail. I gave the reply (last mail), with out working
on.

ThankYou for your help Mr.Yves.

regards,
pradeepreddy

[Yves Deweerdt]

Glad I could help :-)

kind regards,

Yves

[sk_effect]

Please refer this paper for CRC-16 single bit error correction
implementation in hardware. Its a highly optimized and time efficient
method.

http://www.itee.uq.edu.au/~sunil/publications.htm

Cheers,
Sunil

[@hotmail.invalid jtw]

CRC is for error DETECTION, not correction.

Jason
"sk_effect" <sunilk...@gmail.com> wrote in message
news:74cc822a1f71ea40...@localhost.talkaboutprogramming.com...

[Mike Treseler]

jtw wrote:
> CRC is for error DETECTION, not correction.

That's the most common application,
but not the only one.

> Jason wrote:
>>Please refer this paper for CRC-16 single bit error correction
>>implementation in hardware. Its a highly optimized and time efficient
>>method.

Is it worth $35 to read?

-- Mike Treseler