4.5.3 Parity Codes

One of the simplest and most widely used block error-detection techniques is the parity code, which exploits an important property of binary codes known as parity. The parity of a binary word is defined by whether the number of ‘1’ bits in the word is odd or even.

In a linear block parity code, an additional single check bit (or parity bit) is appended to each data block. This bit is chosen so that the complete transmitted codeword satisfies a specified parity rule:

In odd parity, the parity bit is set to ‘1’ when the number of ‘1’s in the data word is even, thereby making the total count odd.
In even parity, the parity bit is set to ‘1’ when the number of ‘1’s in the data word is odd, making the total count even.

Other parity conventions include mark parity (parity bit always ‘1’), space parity (parity bit always ‘0’), no parity (parity bit not transmitted), and ignore parity, where the extra bit is present but is not used for error detection.

A parity scheme therefore forms the simplest possible error-detecting code, with parameters (n=k+1, k). As illustrated in Figure 4.10, adding an odd-parity bit to a four-bit data word yields a simple (5,4) code.

Figure 4.10. An example of odd parity for a four-bit code.

Any single-bit error in an even-parity codeword necessarily flips the parity from even to odd (and vice versa for odd parity), making detection straightforward. The receiver determines the parity of the received word and compares it with the expected parity: if the parity matches, no error is detected; if the parity is opposite, an error must have occurred.

Parity codes can therefore detect all odd numbers of bit errors, because any odd number of flips changes the parity. However, any even number of bit errors produces the correct parity and therefore goes undetected.

At the receiver, parity checking is implemented using a modulo-2 sum (XOR) of all the bits in the received word. In an even-parity scheme, the syndrome is: ‘0’ → valid codeword (no error detected), and ‘1’ → parity mismatch (error detected).

Figure 4.11 illustrate a simple XOR cascade used to generate the parity bit; an equivalent XOR network is used at the receiver. Because of this simplicity, parity bits are widely used in low-level hardware such as disk-write operations, memory systems, data buses, and physical-layer interfaces like RS-232, where the dominant impairment is the isolated bit error.

Figure 4.11. Generation of a parity bit for a four-bit character.

Example. The Power of the Parity Bit

It is easy to see in this commonly used example how the addition of a simple parity bit provides an error-detecting capability, but the magnitude of the improvement is not always intuitive.

Consider the transmission of a 500-page book with 2,000 7-bit ASCII characters (see Appendix E) per page at a bit rate of 10⁶ bps across a channel with a probability of an error of one in a million (10^–6) bits. 500 pages × 2,000 characters × 7 bits = 7×10⁶ bits transmitted at 10⁶ bps will take 7 s. If the probability of an error in the channel is one in 10^–6 bits, then the probability of an undetected error in a 7-bit ASCII word is 7×10^–6. At that error rate the received book will contain 7 errors.

Now suppose a single parity bit is added to each 7-bit character to form an 8-bit word. The probability that an undetected error occurs is the probability of an even number of bit errors within an 8-bit block. For a channel with very small error probability the dominant undetected event is a double-bit error, with probability approximately 28×10^–12. Thus, the probability that any of the 500 pages × 2,000 characters contains an undetected error is about 28×10^–6. If the 500-page book with 2,000 × 8-bit characters per page (8×10⁶ bits) is transmitted at a bit rate of 10⁶ bps, it will take 8 s to transmit but it could be transmitted 35,000 times before an undetected error occurred.

This illustrates the trade-off between introducing redundancy (1 additional second of transmission time) and obtaining a dramatic reduction in undetected-error probability, even with the simplest possible error-detection scheme.

Of course, this powerful error-detecting capability is not matched by any error-correcting ability. A parity code is a (k+1, k) code with a minimum distance of 2 which means that (checking the rule of thumb we saw at the end of Section 4.5.1) that it can detect single-bit errors (1 < 2) but can correct for none for them (2 × 0 < 2). Parity codes therefore serve as fundamental building blocks for systems that require low-cost error detection, and they illustrate clearly how even a small amount of redundancy can greatly reduce the probability of undetected errors.