Contents 1 Algorithms 1.1 Parity byte or parity word 1.2 Modular sum 1.3 Position-dependent 1.4 General considerations 2 See also 3 References 4 External links

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 (XOR) 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 consisting of n zeros, the receiver knows a transmission error occurred. With this checksum, any transmission error which flips a single bit of the message, or an odd number of bits, will be detected as an incorrect checksum. However, an error which affects two bits will not be detected if those bits lie at the same position in two distinct words. Also swapping of two or more words will not be detected. 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 two's complement 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 promodular sum is used in SAE J1708.[1] Position-dependent The simple checksums described above fail to detect some common errors which 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 most used in practice, such as Fletcher's checksum, Adler-32, and cyclic redundancy checks (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 cost of computing the checksum. General considerations A message that is m bits long can be viewed as a corner of the m-dimensional hypercube. The effect of a checksum algorithm that yields an n-bit checksum is to map each m-bit message to a corner of a larger hypercube, with dimension m + n {\displaystyle m+n} . The 2m+n corners of this hypercube represent all possible received messages. The valid received messages (those that have the correct checksum) comprise a smaller set, with only 2m corners. A single-bit transmission error then corresponds to a displacement from a valid corner (the correct message and checksum) to one of the m adjacent corners. An error which affects k bits moves the message to a corner which is k steps removed from its correct corner. The goal of a good checksum algorithm is to spread the valid corners as far from each other as possible, so as to increase the likelihood "typical" transmission errors will end up in an invalid corner.

See also General topic Algorithm Check digit Damm algorithm Data rot File verification Fletcher's checksum Frame check sequence cksum md5sum sha1sum Parchive sum SYSV checksum BSD checksum Error correction Hamming code IPv4 header checksum Hash functions List of hash functions Luhn algorithm Parity bit Rolling checksum Verhoeff algorithm ZFS — a file system which performs automatic file integrity checking using checksums Related concepts Isopsephy Gematria

References ^ "SAE J1708". Kvaser.com. Archived from the original on 11 December 2013.

External links The Wikibook Algorithm Implementation has a page on the topic of: Checksums Additive Checksums (C) theory from Barr Group Retrieved from "https://en.wikipedia.org/w/index.php?title=Checksum&oldid=822931117" Categories: Checksum algorithmsHidden categories: Articles needing additional references from August 2012All articles needing additional references