hoey@nrl-aic.ARPA (Dan Hoey) (08/11/86)
A couple of errors appeared in recent postings about CRC-16 error
checking.
Date: Fri, 25 Jul 86 15:04:27 PDT
From: Marc Kaufman <kaufman@shasta.stanford.edu>
Subject: RF modem problem / CRC
CRC-16 is extremely susceptible to even-number-of-bit errors. For
example, the following error pattern will not change the CRC:
10000100000010001 (binary), where '1' indicates a bit error....
The example applies to the CCITT V41 polynomial. The CRC-16 polynomial
is different, so the example should be
10100000000000011 (binary), where '1' indicates a bit error.
or, if you are a big-endian,
11000000000000101 (binary), where '1' indicates a bit error.
Subject: Re: Interview with MNP protocol author
Date: 05 Aug 86 17:09:30 EDT (Tue)
From: John Robinson <jr@cc5.bbn.com>
...>>> Using the 16-bit redundancy check, it will detect every
>> error which is 16 bits or smaller, with 100% probability.
No! No! No! Any error in an odd number of bits, and all one-, two-,
and three- bit errors will be detected. 16 bits in a row which are
inverted are detected, yes (I think!), but a sequence of 16 bits in
which some bits are in error is NOT necessarily detected. CRCs aren't
that good....
The original statement is correct. Both CRC-16 and CCITT V41 will
detect any error that is a subset of sixteen consecutive bits. (Not to
say that's all that good, as we have seen.) This can be seen by
noticing that nonzero multiples of a degree sixteen polynomial must
have degree at least sixteen. The only undetected pattern that spans
seventeen bits is the polynomial itself, as shown above.
Dan Hoeykaufman@SHASTA.STANFORD.EDU (Marc Kaufman) (08/12/86)
Thanks for the correction. Note that my example was 17 bits, even if I used the wrong polynomial. The problem is, that this represents only three (3) symbols in the newer RF modems (64- or 256- QAM, etc.). In addition, a symbol error in a differentially encoded modem will cause an error in the next symbol (as the phase is corrected). With trellis coding, the error may propogate to two or more symbols before the codes get back to normal. Just possibly (I have not looked in detail) the generated errors may just cancel the CRC error in some cases. In any event, short polynomials become less useful as the number of bits in a symbol increases. Either the makers of modems should select their transition rules to preserve effectiveness of the CRC, or we should look for better error checking polynomials.