[simple_series title=”CRC Tutorial”]

Parity comes in two flavors, even and odd. Even parity is defined that the sum of all transmitted bits in a symbol (including the parity bit) is even; odd parity is defined correspondingly. That is, even parity is the exclusive-or of all the data bits (see image on the right), while odd parity is its inverse.

Consider the bit sequence 1010110₂. It already contains an even number of ones (four, to be precise), thus even parity would be 0 (otherwise, it would make the entire symbol contain an odd number of ones); vice versa for odd parity. ^[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 common. Now that a lot of binary data (or national characters) are transmitted, 8N1 (8 data bits, no parity bit, 1 stop bit) is predominant; errors are checked by “checksums” over several hundred bytes.

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. ^[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.

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 parity ^[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. ), 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.