 Checksum

A checksum or hash sum is a fixedsize datum 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 were 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 errorcorrecting 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 socalled 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 twobit 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 singlebit error, but the probability that a twobit error will go undetected is a little less than 1/n.
Positiondependent 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 Fletcher's checksum, Adler32, 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 mdimensional hypercube. The effect of a checksum algorithm that yields an nbit checksum is to map each mbit message to a corner of a larger hypercube, with dimension m+n. The 2^{m+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 2^{m} corners.
A singlebit 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 that affects k bits moves the message to a corner that 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 that "typical" transmission errors will end up in an invalid corner.
Checksum tools
 cksum, a Unix command that generates both a 32bit CRC and a byte count for any given input file.
 Bitser, a free Microsoft Windows application that calculates MD5, SHA1 and SHA256 sums for any given input file.
 md5sum, a Unix command that generates an MD5 sum
 jdigest, a Java GUI tool that generates and checks MD5 and SHA sums
 Jacksum, a Java API, usable both through a GUI and a CLI, which incorporates many checksum implementations and allows to extend with as many as you need.
 jcksum, a Java library, that can be used by developers in Java applications to calculate checksums using different algorithms.
See also
 Check digit
 File verification
 Hamming code
 List of hash functions
 Luhn algorithm
 Verhoeff algorithm
 Parity bit
 Frame check sequence
 Bit rot
 ZFS A file system that performs automatic file integrity checking using checksums
External links
Categories: Checksum algorithms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Checksum — [engl.], Prüfsumme … UniversalLexikon
checksum — (SUMmation CHECK) n. final check, examination of several of the bits which are transferred in order to discover transfer errors (Computers) … English contemporary dictionary
checksum — A method of providing information for error detection, usually calculated by summing a set of values. The checksum is usually appended to the end of the data that it is calculated from so that they can be compared. For example, Xmodem, a… … Dictionary of networking
Checksum — Somme de contrôle La somme de contrôle (en anglais checksum) est un concept de la théorie des codes utilisé pour les codes correcteurs, elle correspond à un cas particulier de contrôle par redondance. Elle est largement utilisée en informatique… … Wikipédia en Français
checksum — UK [ˈtʃekˌsʌm] / US noun [countable] Word forms checksum : singular checksum plural checksums computing a number that is the total of the digits in a piece of data that has been stored or sent in digital form. It is used to check that nothing has … English dictionary
Checksum — In der Informatik ist eine Prüfsumme (engl.: checksum) eine einfache Maßnahme zur Gewährleistung von Datenintegrität bei der Datenübermittlung oder speicherung. Sie wird hauptsächlich bei der Datensicherung und bei der Datenübertragung verwendet … Deutsch Wikipedia
checksum — 1. noun a digit or character, derived by applying a suitable algorithm to some data, used to check whether errors have occurred in transmission, storage or data entry 2 … Wiktionary
checksum — A number that represents a larger group of numbers in order to check for errors in data transmission. It is commonly used when downloading a program. The checksum is the result of a mathematical equation, such as adding all the numbers in a group … Dictionary of telecommunications
Checksum — PodWEB A checksum is a value that is used to check the integrity of file. Checksums are often used to verify media files that have been uploaded for distribution … Audio and video glossary
checksum — kontrolinė suma statusas T sritis informatika apibrėžtis Reikšmė, laikoma arba persiunčiama kartu su duomenimis ir apskaičiuojama įvykdžius tam tikrą matematinę funkciją su tais duomenimis. Naudojama patikrinti, ar sudarantys duomenys nebuvo… … Enciklopedinis kompiuterijos žodynas