[fpc-pascal] Fast CRC functions?
Michael Schnell
mschnell at lumino.de
Mon Sep 1 10:53:13 CEST 2014
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
More information about the fpc-pascal
mailing list