CRC Error CORRECTION

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

reddy

On Wed, 21 Apr 2004 07:48:45 -0400, "reddy"
<> 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.

Allan Herriman

reddy 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. Please suggest me some links/suggetions.
> Responses are appreciated.
>
> Thanks and Regards,
> Reddy Patlolla
>
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

Yves Deweerdt

On Wed, 21 Apr 2004 15:05:50 +0200, Yves Deweerdt <>
wrote:

>reddy 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. Please suggest me some links/suggetions.
>> Responses are appreciated.
>>
>> Thanks and Regards,
>> Reddy Patlolla
>>
>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...

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.

Allan Herriman

Allan Herriman wrote:
> On Wed, 21 Apr 2004 15:05:50 +0200, Yves Deweerdt <>
> wrote:
>
>
>>reddy 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. Please suggest me some links/suggetions.
>>> Responses are appreciated.
>>>
>>>Thanks and Regards,
>>>Reddy Patlolla
>>>
>>
>>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...
>
>
> 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.

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

Yves Deweerdt

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

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

reddy wrote:
> 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
>
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!

Yves Deweerdt

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

reddy