[e2e] Ethernet CRC

[Jonathan Stone]

In message <OF136D3ACB.636AA175-ON85256AF8.005B1C78 at LocalDomain>
dfriedman at hns.com writes:

>But, what if try the same CRC on some much larger number of bits, K>k?
>The original (n,k) code would then be lengthened to an (N,K) code where N
>= n + (K-k).  However, this code wouldn't necessarily be cyclic, and so it
>wouldn't necessarily have all the great error-detecting capabilities of the
>original (n,k) code.

CRCs are usually shortened cyclic codes, where the input to the CRC
algorithm is usually (by design) shorter than the length at which the
code is cyclic. The results are so well-known that the EE literature
tends to state them as given, without proof.  Peterson and Weldon's
text proves the standard textbook (Error Correcting Codes, 2nd. Ed.,
MIT Press, 1972, ch. 8 and 9) is one source of a proof; Blauhut's text
(Theory and Practice of Error Control Codes, Addison-Wesley, 1994,
chapters 4, 5, and 7) is another. Both also have good references to
the primary literature (Prange, Peterson, and others).  The exposition
in the first edition of Peterson is good too, albeit rather cryptic.

Distilling that to sound-bytes: suppose you write an expression for a
valid codeword, error, syndrome, a expressing when the error goes
undetected as a polynomial over the roots of unity (in an extended
Galois field) of the generator polynomial g(x) of your chosen CRC.
Then treat those polynomial equations as a system of linear
equations. It can be shown (Blahut does so) that the Vandermonde
matrix of that system of equations is of full rank --- provided all
the polynomials involved are of degree less than x^n-1, where n is the
degree of g(x).

So a 32-bit CRC chosen from a Bose-Chaudhuri-Hocquenghem code protects
against errors of length less than (2^32) bits (perhaps (2^32)-1, I
dont have the references at hand).  Which is one reason you don't see
16-bit CRCs used on packets longer than 8Kbytes (say as
alternatives to the IP checksum): their cyclic length is 2^16 bits,
or some 8192 bytes.

Last, practical CRCs are often modified to not be quite linear, let
alone cyclic. Cyclic codes have the drawback that it fails to detect
insertions or deletions of large blocks of zeros at the start of a
message.  Practical CRC codes use a variety of tricks, such notionally
bit-flipping the start of the data before CRC computation, or
prepending a of 1 bits to the data.  McKee (Computer Design, v14 no10,
Pp 102-106, OCtober, 1975) is the earliest reference I found, but the
trick is explained elsewhere: in Raj Jain's paper analyzing FDDI
frame-level error detection, and in several Web expositions on CRCs.

[...]

>What am I missing here?  (I'm not claiming at all that IPv6 without a
>checksum doesn't work, I'd just like to understand the Ethernet CRC.)

Lets not restart the checksum wars again, but...
don't forget that no matter how good a link-level CRC is, a simple
concatenation of hop-by-hop checks is not end-to-end: the hop-by-hop
checks don't protect against errors before each sending hop has
computed its check, or errors which occur after the receiving hop
verifies the inbound check but before copmuting the next hop-by-hop
check.