CRC Tutorial: Other Forms of Checking

[ Tutorial/Introduction | Cyclic Redundancy Check ]

Background: Asynchronous Serial Communications (RS-232C)

Parity Bits

XOR of data bits leads to even parity

Error detection capability: Adding a single parity bit to a code of length b bits makes a code of length b+1 bits. The number of valid codewords remains at 2^b, even though the number of possible code words has doubled to 2^b+1. In other words, only half of the possible codewords are still valid: we have added 1 bit of entropy. This implies that if a random codeword is detected, it will pass the parity test with a 50% chance. If ten random codewords have been received, the probability is only (1/2)¹⁰=1/1024 that all pass the test and none raises the "parity mismatch" flag.

But the main property is that the receiver can reliably detect if a single bit has been flipped during transmission of a codeword (even though it will not be able to find out which bit it was): If we flip any of the bits (data or parity3), the number of bits that are set to one increases or decreases by one. As a result, the number will change between even and odd, failing the parity check. Note that it does not matter whether we change a data or the parity bit, the effect will be the same.

This property is achieved because the 50% of the codewords that are illegal are interspersed into the legal code words such that any single-bit change in a legal code word will result in an illegal codeword and vice versa. As a consequence, any two legal codewords are at least two modifications away, giving this code a Hamming distance (least number of modifications between any two codewords) of two.

Typical error modes: Typical errors that occur in environments are misrecognition of data bits or line noise as start bits, line noise interfering with data bits, and bit-rate (bits per second, in such "ASYNC" environments often also known as "baud-rate") mismatch between sender and receiver. Parity bits are helpful in these scenarios, even though they do not catch every problem. When reliable communication is required, such when transferring program files, additional mechanisms need to be added to increase the reliability, such as checksums or CRCs.

Checksums

While parity is adequate to protect a single character or byte, its detection capabilities lack in power when applied to larger messages: Messages often span thousands of bits, and if just two bits are flipped, the corruption will not be detectable. And the chance of having multiple bit errors within a message increases exponentially with the message length.4

Therefore, there is a need for something more powerful. Parity is already a simple form of a checksum (it sums up all the bits in the data, modulo 2). The natural extension is to create a more powerful checksum. Typical versions are summing up the bytes (or 2-/4-byte words) in the message into a checkbyte (or 2-/4-byte checksums). This is again done modulo 256 (or 2¹⁶ or 2³², respectively), which can essentially be implemented by ignoring carry and overflow conditions due to the addition.

Error detection capability: Even though the checksum is much larger than the parity bit and it generally detects many more errors than parity, it is not able to detect all 2-bit modifications to the message: If it clears a bit at position i in one word, but changes the ith bit to one in another word, the sum of these two words and thus the total checksum remains the same. But if two bits at different positions in the same word (or two different words) are flipped, this error will be detected.

As a consequence of the undetected 2-bit modification above, we can also exchange entire words, especially swap adjacent words, and the result will pass the checksum test. (In effect, both the same-bit-swapping and the word-swapping are due to the commutative nature of the addition and will also apply to any other check method with commutative properties.)

Intermission: Classes of errors: For comparison of error detection/correction capabilities, two properties are prevalent: the number of random errors (how many one-bit errors the code is guaranteed to handle, independent of where in the message the errors are introduced) and the size of the largest burst error (in a burst, any non-zero number of distinct bits can be changed, but they have to be closer together than the burst size).

Checksums that are b bits wide are only guaranteed to detect a single random bit error (recall that two well-placed errors can go undetected) and a burst of size b: As long as the error changes only bits in a single word, it will be detected, as it cannot cancel itself out. The same still applies when the boundaries of the burst are no longer limited to coincide with the word boundaries, resulting in an upper part of one number and a lower part of an adjoining number being modified. As long as the two parts do not overlap, no subset of the bits to be modified can cancel each other out. A burst of size b+1 could go undetected, if only its border bits would be flipped (this again is the undetectable 2-bit modification).

The Internet protocol suite (such as IP, TCP, and UDP) use a variant of this basic checksum, the one's complement sum, which wraps the carry from the most significant digit around to the least significant digit. The influence on the detection capabilities is marginal, and the weaknesses of this checksum are widely discusses; for example, a paper by Stone and Partridge provides a good experimental analysis.

Check Digits

While reordering of words may be uncommon in data communication networks, it is quite common for humans to swap digits in large numbers consisting of seemingly random digits, such as those used in the ISBN system or UPC/EAN product codes. Therefore, a checksum is not suitable for these numbers. A common algorithm is to multiply each digit with a different number before it is added to the sum. In addition to digit substitutions, this helps detect many swapped digits, as the position now becomes significant as well.

Using ISBN as an example, we find the following definition: The number consists of 9 decimal digits, followed by the check digit which is decimal or X, a digit representing 10. Each of these digits is weighted: The first has weight 10, the second, 9, and so on until the last data digit with weight 2 and the check digit with weight 1. The check digit is chosen such that the weighted sum is zero (modulo 11).

ISBN Check Digit Rule

Adding 1 to the digit weighted 7 adds ((1*7) modulo 11)=7 to the checksum

Swapping adjacent digits differing by 2 adds or subtracts 2 to the checksum, depending on which digit was larger

Error Correction Codes (ECC)

In addition to the error detection codes discussed so far, there also exist error-correcting codes. For a particular class of errors, these not only raise the flag that an error has occurred, they are able to indicate where the bad bit(s) are. This tutorial does not deal with ECCs, as they are generally even more complex than CRCs and frequently are based on Reed-Solomon codes. However, the interested reader may find single-bit-correcting Hamming codes to be relatively easy to understand and fascinating piece of information, which you might plan to casually introduce in your next geeky small talk.

Footnotes

1 The number of data bits, the type of parity, and the number of stop bits are often encoded in a form [Data bits][Parity type][Stop bits], where [Data bits] is typically between 5 and 8, inclusive; [Parity type] is one of E (even), O (odd), N (none: no parity bit is transmitted), M (mark: send a one), S (space: send a zero); [Stop bits] is one of 1, 1.5, or 2. In the age of keyboard/text terminal communication, 7E1 (7 data bits, an even parity bit, 1 stop bit) was common2. Now that a lot of binary data (or national characters) are transmitted, 8N1 (8 data bits, no parity bit, 1 stop bit) is predominant.

2 One of the error conditions discussed is the possibility of a line noise in "idle" state, which may be misinterpreted as a start bit. To avoid accepting the following idle bits as a character, parity can also be used. When the number of data bits is odd, the parity should be chosen odd as well: the character will have an odd number of ones, followed by a parity bit which is set to one, resulting in an even number of ones and so failing the parity test. For even numbers of data bits, this property is achieved by choosing odd parity. (Correct parity selection when idle is zero and the start bit is one is left to the reader.) Why then was 7E1 much more popular than 7O1? I do not know the answer, but I imagine that the lack of ambiguity in the notation (O (Oh) vs. 0 (zero)) and the saving of an inverter in the circuitry may have contributed to the choice.

3 Only the data bits are protected by the parity, the framing information is not. But flipping any of the framing bits generally results in a framing error. It is important to note that any error detection mechanism also needs to be able to handle modifications of the parity bit.

4 For analysis of error behavior, it is often assumed that bit errors are distributed using an independent identical random process. When the chance of any single bit being flipped is p, the chance of a message of size m not being corrupted is (1-p)^m, an exponentially decreasing function in the message size. The probability of the message surviving with at most one bit error is p₁=(1-p)^m-1, resulting in a probability of 1-p₁ for getting more than the one error which parity can detect.

5 Most modifications to one data digit can be compensated with a modification to another data digit, it is not necessary to revert to updating the check digit. It is only "most", not "all", as only the check digit allows for all necessary 11 values, the data digits lack the X.