CRC Error CORRECTION

Discussion in 'VHDL' started by reddy, Apr 21, 2004.

  1. reddy

    reddy Guest

    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, Apr 21, 2004
    #1
    1. Advertising

  2. 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, Apr 21, 2004
    #2
    1. Advertising

  3. 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, Apr 21, 2004
    #3
  4. 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, Apr 21, 2004
    #4
  5. 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, Apr 21, 2004
    #5
  6. reddy

    reddy Guest

    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, Apr 22, 2004
    #6
  7. reddy

    reddy Guest

    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, Apr 22, 2004
    #7
  8. 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, Apr 22, 2004
    #8
  9. reddy

    reddy Guest

    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, Apr 22, 2004
    #9
  10. reddy

    reddy Guest

    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, Apr 22, 2004
    #10
  11. reddy wrote:
    > 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
    >


    Glad I could help :)

    kind regards,

    Yves
    Yves Deweerdt, Apr 22, 2004
    #11
  12. reddy

    sk_effect Guest

    sk_effect, Jun 1, 2005
    #12
  13. reddy

    jtw Guest

    CRC is for error DETECTION, not correction.

    Jason
    "sk_effect" <> wrote in message
    news:...
    > 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
    >
    >
    jtw, Jun 3, 2005
    #13
  14. 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
    Mike Treseler, Jun 3, 2005
    #14
  15. reddy

    fauji86

    Joined:
    Mar 3, 2010
    Messages:
    1
    crc error with c++

    hi,
    for my project i'm trying to correct error.
    can you tell me how to programe crc in c++.
    thank you.
    fauji86, Mar 3, 2010
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. DU
    Replies:
    0
    Views:
    337
  2. Mamut

    crc-8 and crc-16 code...

    Mamut, Feb 21, 2007, in forum: C++
    Replies:
    5
    Views:
    4,016
    Victor Bazarov
    Feb 22, 2007
  3. `Zidane Tribal
    Replies:
    1
    Views:
    2,501
    Joe Smith
    Jul 28, 2007
  4. Chris Long
    Replies:
    1
    Views:
    173
    Chris Long
    Jun 19, 2005
  5. `Zidane Tribal
    Replies:
    3
    Views:
    238
    Sisyphus
    Jul 27, 2007
Loading...

Share This Page