How Does a Single Parity Bit Detect Odd Bit Flips?
A single parity bit is a simple error-detection mechanism used in classical computing to verify the integrity of binary data during storage or transmission. By appending one extra bit to a data word, a system can ensure that the total number of ones in the word is always either even or odd. This property allows the receiver to immediately spot any single-bit error or other odd-numbered bit flips, though it cannot detect when two bits—or any even number of bits—flip at the same time.
What Is a Parity Bit?
In binary arithmetic, data is represented as strings of \(0\)s and \(1\)s. A parity bit \(p\) is calculated from the \(n\) data bits \(d_1, d_2, \dots, d_n\) and appended to the message before it is sent or stored. There are two standard conventions:
- Even parity: The parity bit is chosen so that the total count of \(1\)s in the entire \((n+1)\)-bit word is even.
- Odd parity: The parity bit is chosen so that the total count of \(1\)s in the entire \((n+1)\)-bit word is odd.
Mathematically, for even parity, the parity bit is the modulo-\(2\) sum (or exclusive OR, \(\oplus\)) of all data bits:
\[p = d_1 \oplus d_2 \oplus \dots \oplus d_n\]
When the receiver gets the \((n+1)\)-bit word, it recomputes the modulo-\(2\) sum of all bits, including \(p\). Under even parity, a valid, uncorrupted word always satisfies:
\[d_1 \oplus d_2 \oplus \dots \oplus d_n \oplus p = 0\]
Why Odd Numbers of Bit Flips Are Detected
Each bit flip changes a \(0\) to a \(1\) or a \(1\) to a \(0\). In modulo-\(2\) arithmetic, flipping a single bit adds \(1 \pmod 2\) to the total sum.
Suppose a valid even-parity word has an even number of \(1\)s, so its modulo-\(2\) sum is \(0\). If an odd number of bits \(k = 2m + 1\) flip during transmission, the sum changes by:
\[(2m + 1) \equiv 1 \pmod 2\]
Because the resulting sum is \(1\) instead of \(0\), the parity of the word has inverted from even to odd. The receiver's parity check immediately flags this mismatch as an error.
Why Two-Bit Errors Go Undetected
If two bits flip simultaneously, each flip adds \(1 \pmod 2\) to the sum. Together, two flips add:
\[1 + 1 = 2 \equiv 0 \pmod 2\]
Whether two \(0\)s become \(1\)s, two \(1\)s become \(0\)s, or one \(0\) becomes a \(1\) while one \(1\) becomes a \(0\), the total number of \(1\)s changes by \(-2\), \(0\), or \(+2\). In every case, an even count of \(1\)s remains even, and an odd count remains odd.
Because the parity check only inspects whether the total count of \(1\)s is even or odd, any even number of bit flips leaves the parity invariant. As a result, a single parity bit has a Hamming distance of \(2\), meaning it can detect \(1\)-bit errors (and any odd number of errors) but is completely blind to \(2\)-bit errors and cannot correct any errors on its own.