Alternate Checksum Algorithms

There are a variety of checksum schemes (for examples, see ref. 11,15-16) other than the 1's complement algorithm described in this proposal, although other checksums are significantly less easy (often computationally impractical or impossible) to embed in FITS headers in the same fashion.

Checksums, cyclic redundancy checks (or CRCs, see ref. 10 for example), and message digests such as MD5 (ref. 19) are all examples of hash functions. Many possible images will hash to the same checksum--how many depends on the number of bits in the image versus the number of bits in the sum. The utility of a checksum to detect errors (but not forgeries), to one part in however many bits, depends on whether it evenly samples the likely errors.

For instance, a 32-bit checksum or CRC each detects the same fraction of all bit errors (ref. 16), missing only 1 / 2³² of all errors (about 1 out of 4.3 billion) in the limit of long transmissions (the extra zero of 1's complement arithmetic changes this by only a small amount).

CRCs and message digests are basically checksums that use higher order polynomials, thus removing the arithmetic symmetry on which this proposal relies. CRCs are tuned to be sensitive to the bursty nature of communication line noise and will detect all bitstream errors shorter than the size of the CRC. Note that the 1's complement sum is not insensitive to these bit error patterns, it is just not especially sensitive to them. The extra sensitivity of a CRC to burst errors must come at the expense of lessened sensitivity to other bit pattern errors (since the total fraction of errors detected remains the same) and does not necessarily represent the best model for FITS bit errors. CRCs are also designed to be implemented in hardware using XOR gates and shift registers that accumulate the function ``on-the-fly'' and emit the CRC after transmitting the data. This is not well matched to the FITS convention of writing the metadata as a header which preceeds the data records.