Connect with us

Cyclic Redundancy Check

Discussion in 'Electronic Design' started by Jim Tuhey, Feb 10, 2004.

  1. Jim Tuhey

    Jim Tuhey Guest

    Dear All,
    long time listener, first time poster.
    I'm building a laser based communication system as part of a uni
    project, no problems with the laser / optics etc end, but I'm
    wondering what level of CRC would be suitable for something that's
    transferring data at about half a Megabit/second, over a fairly clean,
    low noise medium. In other words I'm expecting it to be pretty good at
    transferring the data, without picking up many errors on the way.
    What size of polynomial would be "right" for this job. I am aware that
    too small a polynomial would introduce an unacceptable bit overhead
    and too large would be overkill and slow down processing.

    yours in anticipation,
    Jim Tuhey
     
  2. If the system is simplex, rather than duplex/half duplex, then you would be
    better off, looking at something like a hamming code, rather than a CRC.
    CRC's are 'best' where recovery is possible by requesting a re-send.
    Otherwise they only offer the possibility of detecting the error, which is
    fine for a packet based duplex system, but doesn't really help much on a
    simplex link. A lot will depend in any case, on the 'nature' of probable
    data losses. For instance, if the interference is likely to damage three or
    four successive bits, but the rest of a quite large block is likely to be
    undamaged, (as might happen from rain, on an optical link, if the data rate
    is high), then provided you have a large enough buffer, 're-ordering' the
    data transmitted, so that the successive bits from each character are sent
    seperated in the packet, combined with a simple 7,4 hamming system, can
    provide a very high probability of recovering the data.

    Best Wishes
     
  3. Jim Tuhey

    Jim Tuhey Guest

    Many thanks for your reply. I'll certainly consider the Hamming
    System, given the system is simplex. Perhaps a CRC is a little over
    the top for this application. Thanks again for your advice.
     
  4. Wim Ton

    Wim Ton Guest

    Have a look at the CCITT CRC16 and CRC32. There are other methods, depending
    of the type of error and the processing capabilities. CRCs are very suiteble
    to implement in hardware, like shift registers. On a processor a Fletcher
    checksum may be more efficient. Other possibilities a are block error
    correcting codes like Reed Solomon or BCH.

    Wim
     
  5. A CRC16 can protect 2^16 bits against a single bit failure.
    This means it can detect a single bit error within a 8kbyte block.
    A CRC32 can protect 2^32 bits against a single bit failure.
    Meaning it can detect a single bit error within a 500MByte block.

    The block size should be somewhat smaller to make retransmission
    economic.

    Calculation of the CRC is best done in hardware, eg an FPGA.

    And yes, from a certain numbers of errors up, a forward error
    correction would make sense.
    Calculation of the Hamming is best done in hardware, eg an FPGA.

    Rene
     
  6. Ian Stirling

    Ian Stirling Guest

    You might want to consider just doing a media converter from ethernet
    (10base2 would probably be easiest) to optical, and doing the rest
    by ethernet.
     
  7. Bill Sloman

    Bill Sloman Guest

    The short answer is "whatever you can find in a chip geared up to do
    the job".

    The original 1980 Ethernet specfication included a 32-bit CRC, and
    IIRR that ran at 10Mbit/sec and there are a bunch of single-chip
    implementations around. I haven't been seriously involved in fast
    serial signalling since 1982, so I can't quote any chip numbers.
     
  8. Mike

    Mike Guest

    What if there happen to be two errors...?

    -- Mike --
     
  9. Oh boy. There's much misinformation about CRCs floating about.


    Single bit error:
    A CRC16 can protect *any number of bits* against a single bit error,
    as can a CRC32.


    Two isolated single bit errors:
    This depends on how the polynomial can be factored:
    (x^k + 1) not being a factor of the poly is sufficient to detect all
    pairs of errors k bits apart.
    Tannenbaum gives the example of x^15 + x^14 + 1 being able to detect a
    pair of errors that aren't more than 32768 bits apart.
    For commonly used polys, all double bit errors can be detected for
    practical (short) packet lengths (IIRC).


    Odd number of single bit errors:
    Polynomials that have (x+1) as a factor have 'parity' detection
    ability and will detect all odd numbers of errors.
    CRC16 has this property; CRC32 does not.
    (This turns out not to be an important property and it compromises the
    performance in other ways, which is why the older polys (e.g. CRC16)
    have it, but the newer ones (e.g. CRC32) do not.)


    Burst of errors:
    CRC16 can detect all error bursts up to 16 bits long.
    CRC32 can detect all error bursts up to 32 bits long.


    Large number of bit errors:
    A small fraction (about 2^-N) of the errored frames will not be
    detected. For CRC16 this is about 15ppm, and for CRC32 this is about
    2e-12.
    IOW, CRC16 will detect 99.998% of errored frames, and CRC32 will
    detect 99.99999998% of errored frames.


    (I made most of this up. You really should refer to a *good* paper on
    CRCs.)

    Regards,
    Allan.
     
  10. Could theoretically go undetected if the CRC value happens to be the
    same as before, or the right bit in the CRC was flipped too.

    Rene
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-