> From:         Nigel Orr[SMTP:nigel@AXONINSTRUMENTS.CO.UK]
> Sent:         Tuesday, May 18, 2004 9:35 AM
> To:   PICLIST@MITVMA.MIT.EDU
> Subject:      [EE:] Short CRCs

> I have implemented standard 16-bit CRCs in the past, but I need to include
> error detection in some short data blocks (4-20 bits).  Each block needs
> it's own error detection, I can't just calculate a CRC and send it after
> every 10 blocks.  The CRC needs to be as short as possible, 4 or fewer bits
> would be good!!

> Are there any 'standard' CRCs like that, or better methods for error
> detection in short blocks?  Or are there mathematical reasons why CRCs
> don't work well for shorter data streams (I suspect there are, but can't
> quite figure it out...)

> TIA,

> Nigel

The CRC algorithm is closely related to that for the Pseudo-Random
Binary Sequence. Exclusive-ORing taps on a shift register and feeding
the result back to the shift input performs a division. If the register is
initialized to a non-zero value and the shift input is just the output of
the XOR, the bit train produced from the register is the quotient
produced by dividing the initial value by the polynomial described by
the tap positions. If the tap positions are chosen correctly, this
sequence will be maximal length and will appear more or less random
until it repeats.

If an input bit stream is XORed with the XOR of the tap positions, the
quotient of the input data and the divisor polynomial will be formed. The
number left in the register after the last of the data is clocked in will
be the remainder of the division. If the tap positions are chosen to
be the same as those that gives the maximal length PRBS, the
remainder will be the CRC. Officially, the divisor should be chosen to
be one of the "industry standard" polynomials, especially if you are
attempting to be compatible with someone else's equipment.

For a length 4 CRC, you could try the tap positions for an N = 4
PRBS. I believe that the maximum length of the input data would
then be 16. Initialize the register to zero. Exclusive OR the input
stream with the output of the tap XORs, and feed that to the
serial input of the register. After 16 clocks, read the contents of
the register.

John Power

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listserv@mitvma.mit.edu with SET PICList DIGEST in the body