Posted 27 May 2011 - 09:16 PM
Anyone know what type of checksum to look for?
Parity byte or parity word
The simplest checksum algorithm is the so-called , which breaks the data into "words" with a fixed number n of bits, and then computes the 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 ]
A variant of the previous algorithm is to add all the "words" as unsigned binary numbers, discarding any overflow bits, and append the of the total as the checksum. To validate a message, the receiver adds all the words in the same manner, including the checksum; if the result is not a word full of zeros, an error must have occurred. This variant too detects any single-bit error, but the probability that a two-bit error will go undetected is a little less than 1/n.
[Position-dependent checksums ]
The simple checksums described above fail to detect some common errors that affect many bits at once, such as changing the order of data words, or inserting or deleting words with all bits set to zero. The checksum algorithms that are most used in practice, such as , , and (CRCs), address these weaknesses by considering not only the value of each word but also its position in the sequence. This feature generally increases the of computing the checksum.