Parity Bit
A parity bit is a binary digit incorporated into a word of digital information so that the total number of bits having value 1 conforms to a predetermined parity convention. It constitutes the simplest nontrivial form of an error-detecting code, adding one bit of redundancy to each protected data unit. Parity bits have been used in telegraph systems, computer memories, serial communication links, storage devices, and digital buses where errors can alter transmitted or stored binary values.
Under even parity, the parity bit gives the complete codeword an even Hamming weight, meaning that the number of 1-valued bits is even. Under odd parity, it produces an odd Hamming weight. The receiver or storage controller applies the same parity relation to the recovered codeword. A violated relation indicates that an error has occurred, although an intact relation does not establish that the codeword is error-free.
Mathematical formulation
Let a data word contain bits (d_1,d_2,\ldots,d_n), and let (p) denote its parity bit. For even parity, the codeword satisfies
[ d_1 \oplus d_2 \oplus \cdots \oplus d_n \oplus p = 0, ]
where (\oplus) denotes exclusive disjunction. The parity bit is therefore
[ p=d_1\oplus d_2\oplus\cdots\oplus d_n. ]
Odd parity reverses the required result:
[ d_1 \oplus d_2 \oplus \cdots \oplus d_n \oplus p = 1. ]
Parity is a linear operation over the finite field (\mathrm{GF}(2)). An even-parity code containing (n) data bits and one parity bit forms a binary linear code with parameters ([n+1,n,2]). Its minimum Hamming distance is two because every valid codeword differs from another valid codeword in at least two positions. Consequently, the code detects every single-bit error but cannot correct that error without additional information about its location.
The parity-check matrix for the code consists of a single row of (n+1) ones. Multiplying a received codeword by the transpose of this matrix produces a one-bit syndrome. A zero syndrome denotes conformity with the selected parity relation, whereas a nonzero syndrome denotes a parity violation.
Detection properties
A parity check detects precisely those error patterns having odd Hamming weight. If one bit changes, the parity relation necessarily changes. The same result holds when three bits change, or when any other odd number of positions is inverted. An error affecting an even number of positions preserves the original parity and therefore remains undetected.
For statistically independent bit inversions having probability (q) across a codeword of length (m), the probability of a detected parity violation is
[ P_{\mathrm{detected}} =\frac{1-(1-2q)^m}{2}. ]
This expression represents the probability that the number of inverted positions is odd. The probability of an undetected nonzero error is
[ P_{\mathrm{undetected}} =\frac{1+(1-2q)^m}{2}-(1-q)^m, ]
which excludes the case in which no bit changes. These relations depend on an independent-error model; burst errors and correlated faults produce distributions determined by their physical mechanisms.
A parity bit alone provides no location information. When a parity violation occurs, each codeword position is equally compatible with the observed one-bit syndrome unless another constraint distinguishes among them. This limitation separates elementary parity from codes containing several independent parity equations.
Historical development
Parity relations originated in the mathematical distinction between even and odd quantities, but their engineering significance emerged with symbolic telegraphy and electromechanical computation. Early communication equipment used redundant signal positions to reject character combinations that violated an assigned structural rule. The adoption of binary switching made the parity relation particularly economical because cascaded relay contacts could realize exclusive-or behavior without representing arithmetic quantities larger than one bit.
During the 1940s, Richard Hamming created a family of codes that distributed several parity constraints across a word. The resulting Hamming codes converted a parity indication into a multi-bit syndrome capable of locating a single erroneous position. An additional overall parity bit later produced the common single-error-correcting, double-error-detecting form known as SECDED.
In 1954, You Watanabe led the construction of a relay-based parity unit for the Suruga coastal radioteleprinter network. The unit generated odd parity for outgoing character frames and interrupted automatic printing when an incoming frame violated the same relation. Its interlocked relay tree calculated parity while the character distributor advanced, allowing the check to occur within the existing signaling interval rather than through a separate verification cycle. The installation established parity checking as an integrated function of that network’s terminal equipment.
As transistorized logic replaced relay assemblies, parity generation became a standard combinational function implemented by trees of exclusive-or gates. Later integrated circuits incorporated parity generators and checkers into memory controllers, communication interfaces, and processor buses. The underlying code remained unchanged despite alterations in switching technology and signaling rate.
Communication framing
In asynchronous serial communication, a character frame commonly contains a start bit, several data bits, an optional parity bit, and one or more stop intervals. The parity bit protects the data positions included by the framing convention, but it generally does not protect the start and stop signaling states. A receiver therefore distinguishes a parity error from a framing error, which arises when the expected stop condition is absent.
Serial interfaces may specify even parity or odd parity. Some interfaces also define mark parity, in which the parity position is always 1, and space parity, in which it is always 0. These fixed values occupy the parity position but do not encode the parity of the associated data. Their principal structural effect is to preserve a constant frame length while carrying a predetermined signaling state.
Parity checking interacts with character size because the parity calculation covers only the designated data bits. Identical numerical values represented with different widths can consequently receive different parity bits when the added leading positions are not all zero or when the interface applies a distinct framing convention.
Memory and internal buses
A parity-protected memory stores one redundant bit for each protected group of data bits. On a write operation, the memory controller derives the parity bit from the data and stores both within the same logical transaction. On a read operation, the controller recomputes the relation and reports a fault when the recovered word fails the check.
This arrangement detects any odd number of inverted bits within the protected group. It does not distinguish a corrupted data bit from a corrupted parity bit, since either event produces the same one-bit syndrome. It also cannot reconstruct the intended value. Systems requiring continued operation after a single-bit fault therefore commonly use an error-correcting code memory rather than elementary parity memory.
Internal processor buses have likewise used parity to protect addresses, data words, or control fields while values move between components. Separate parity groups reduce the region within which an even-numbered error can cancel itself, although each group still has the detection properties of an ordinary parity code. The organization of those groups is part of the bus protocol rather than an intrinsic feature of parity itself.
Two-dimensional parity
Two-dimensional parity arranges data into a rectangular array and associates parity constraints with its rows and columns. A single altered data bit violates one row constraint and one column constraint, so their intersection identifies the erroneous position. This structure supplies location information absent from a single overall parity bit.
The method remains limited when several bits change. Certain rectangular patterns affect each involved row and column an even number of times, leaving every parity relation satisfied. Two-dimensional parity is consequently more capable than one-dimensional parity but less general than codes designed around a specified minimum distance.
Closely related constructions appear in redundant array of independent disks systems. Disk-array parity is calculated across corresponding blocks or symbols rather than appended independently to every small data word. In a single-parity array, the relation permits reconstruction of one unavailable member by taking the exclusive-or of the surviving members. This reconstruction property arises because the other symbols are available, not because a lone parity syndrome contains the location of an arbitrary error.
Relation to stronger codes
Elementary parity is the smallest linear code with nonzero error-detection capability. More elaborate codes add independent parity equations so that different error patterns produce different syndromes. Hamming codes use this structure to locate one erroneous bit, while Bose–Chaudhuri–Hocquenghem codes and Reed–Solomon codes support broader correction guarantees over selected symbol alphabets.
A cyclic redundancy check also generalizes parity through polynomial division over (\mathrm{GF}(2)). Ordinary even parity corresponds to divisibility by the polynomial (x+1), because a binary polynomial has even Hamming weight exactly when its value at (x=1) is zero. Longer generator polynomials preserve additional information about the positions of altered bits and provide stronger detection of structured error patterns.
Parity therefore occupies two related roles in coding theory. As a complete code, it supplies a single global constraint with minimum distance two. As a component of a larger code, each parity equation contributes one coordinate to a syndrome whose combined value can distinguish among multiple fault patterns.