Page 258 - Anatomy of a Robot

09_200256_CH09/Bergren 4/17/03 11:24 AM Page 243
COMMUNICATIONS 243
sum will consist of 1 to 8 bytes of extra information summarizing a block of data that
is between 32 and 1,024 bytes long. These numbers are arbitrary, but common. TCP/IP,
for instance, typically has blocks of data 512 bytes long with checksums that are 2 bytes
long.
Descriptions of the IP checksum method can be found at:
www.ietf.org/rfc/rfc1071.txt
www.netfor2.com/checksum.html

Here are descriptions of TCP checksums:
www.netfor2.com/tcpsum.htm
http://ethereal.ntop.org/lists/ethereal-users/200012/msg00050.html
An interesting statistical analysis of TCP/IP checksum errors in a real-world appli-
cation can be downloaded from www.acm.org/sigcomm/sigcomm2000/conf/paper/sig-
comm2000-9-1.pdf.
The astute observer will note that a data block of 512 bytes can be filled in 2 512 8 dif-
ferent ways. However, a checksum with just 2 bytes can only take on 65,535 (2 2 8 ) dif-
ferent checksum values. This means that for each possible checksum value, about 2 256
(or about 7.4 x 10 19) data blocks will have the very same checksum.
So how do we get away with saying that this sort of checksum is sufficient for an
application? If an error occurs, the erroneous data block just might be identical to one
of the several billion data blocks with the same checksum. The key thing to remember
is that a single error should result in an erroneous data block with only one chance in
65,536 of having the same checksum. If this decrease in the error rate is not good
enough, then design the robot with a stronger checksum, which is perhaps longer.
Certainly, as the mathematical algorithm is chosen for the checksum calculation, make
sure the most common errors all result in a checksum change.
For example, an error in a single bit may be common and should result in a different
checksum. The calculation method for checksums is often described by a polynomial,
a mathematical way to describe the calculations involved in computing a checksum. The
mathematics behind the selection of a good polynomial are beyond the scope of this
book. Fortunately, many standard polynomials (some listed later) exist and we can select
among them without reinventing them.
The following web sites describe using polynomials for the computation of check-
sums:

www.4d.com/ACIDOC/CMU/CMU79909.HTM
www.geocities.com/SiliconValley/Pines/6639/docs/crc.html
www.relisoft.com/Science/CrcMath.html