Checksum

related topics
{system, computer, user}
{math, number, function}
{law, state, case}

A checksum or hash sum is a fixed-size data computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and comparing it with the stored one. If the checksums match, the data was almost certainly not altered (either intentionally or unintentionally).

The procedure that yields the checksum from the data is called a checksum function or checksum algorithm. A good checksum algorithm will yield a different result with high probability when the data is accidentally corrupted; if the checksums match, the data is very likely to be free of accidental errors.

Checksum functions are related to hash functions, fingerprints, randomization functions, and cryptographic hash functions. However, each of those concepts has different applications and therefore different design goals. Check digits and parity bits are special cases of checksums, appropriate for small blocks of data (such as Social Security numbers, bank account numbers, computer words, single bytes, etc.). Some error-correcting codes are based on special checksums that not only detect common errors but also allow the original data to be recovered in certain cases.

Contents

Checksum algorithms

Parity byte or parity word

The simplest checksum algorithm is the so-called longitudinal parity check, which breaks the data into "words" with a fixed number n of bits, and then computes the exclusive or of all those words. The result is appended to the message as an extra word. To check the integrity of a message, the receiver computes the exclusive or of all its words, including the checksum; if the result is not a word with n zeros, the receiver knows that a transmission error occurred.

With this checksum, any transmission error that flips a single bit of the message, or an odd number of bits, will be detected as an incorrect checksum. However, an error that affects two bits will not be detected if those bits lie at the same position in two distinct words. If the affected bits are independently chosen at random, the probability of a two-bit error being undetected is 1/n.

Modular sum

Full article ▸

related documents
XChat
User space
Coral 66
SAPHIRE
Karplus-Strong string synthesis
Microsoft Version Number
Electronic Delay Storage Automatic Calculator
Java Data Objects
Presentation Layer
B3ZS
Dillo
Time to live
Raster image processor
XML Metadata Interchange
Inter-process communication
Interior Gateway Routing Protocol
Network mapping
Fractal transform
Advanced Encryption Standard process
Netscape Communicator
Short message peer-to-peer protocol
Automated business process
Back Orifice 2000
Undocumented feature
Handshaking
Fsck
Session Description Protocol
Altair BASIC
Network architecture
BOS/360