On 09/01/2014 10:12 AM, Tony Whyman wrote:
CRCs main use is with low speed modems.
They can be readily implemented in hardware and when the division
polynomial is carefully chosen can give an undetected bit error rate of
better than 1 in 10^8, which is more than sufficient for the data volume
possible. SHA-1 can give a ridiculously low undetected bit error rate
but the computational and bit overhead is not really justified in such
applications.
CRC is invented to do it in hardware (using a shift register and some
XOR gates), and hence happily supports very high speed transfer. But it
can rather efficiently be done in Software using a Table (e.g. 256
entries).
With a decent Polynomial, the "single bit error undetected" rate is zero
(as with all theses algorithms), while the "multi-bit error undetected"
(of course) depends on CTC size (most common is 32 Bits, then 16 bits,
but in theory any bit rate is doable, in certain applications I do use 4
Bits and 5 Bits). This depends on the difference between the count of
CRC bits and the binary log of the count of message bits per block
(Hamming distance -> http://en.wikipedia.org/wiki/Hamming_distance).
Moreover with a "complete" polynomial a single bit error can be not only
detected but also corrected.
CRCs are a class of functions each characterised by a
different division polynomial
More characteristics that can be differ in certain applications are
- bit count
- starting value
- shift count (only data block bits or data block bits plus CRC bits
- order of the bits (including bits in bytes and/or words), as well in
the data block as in the CRC itself
- sometimes the data bits are inverted before the CRC calculation,
sometimes the CRC bits are inverted before transmission.
CRCs are computed by polynomial division. For a given polynomial and bit
layout they are deterministic. if an implementation claims to implement
the same CRC and gives a different result to a standard implementation
then it's a bug and not a feature.
Yep.
-Michael
_______________________________________________
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
