Parity Bits
Part of Data Storage
Single-bit error detection through bit counting — the simplest form of data integrity checking and the foundation of all error-correcting codes.
Why This Matters
Parity is the entry point to error detection: conceptually simple, cheap to implement in hardware, and sufficient for many applications. A single parity bit added to every byte in a memory system costs 12.5% overhead but catches every single-bit error — the most common form of corruption in RAM, serial communications, and disk sector headers.
Understanding parity deeply also provides the foundation for understanding all more complex codes. Hamming codes are multiple parity bits. Reed-Solomon codes extend the parity concept to multi-bit symbols in finite fields. CRCs are polynomial remainders that generalize the parity sum. Every error detection and correction technique in common use is, at some level, a generalization of the parity bit concept.
For practical rebuilding, parity checking is implementable in a handful of logic gates — no microcontroller required. Add one XOR gate tree to your memory interface and you have immediate detection of any single-bit memory corruption.
The Mathematical Basis
A parity bit is defined such that the count of 1-bits in the resulting word (data bits + parity bit) is either always even (even parity) or always odd (odd parity). Even parity is more common.
Even parity for a byte:
- Data byte: 0b10110100 → count of 1-bits = 4 (even) → parity bit = 0
- Data byte: 0b10110110 → count of 1-bits = 5 (odd) → parity bit = 1
The full 9-bit word (8 data bits + 1 parity bit) always has an even number of 1-bits.
Error detection: Read back the stored byte and parity bit. Count the 1-bits in the 9-bit word. If the count is even, either there was no error or an even number of bits flipped (undetectable). If the count is odd, at least one bit flipped — a detectable error.
Why XOR is equivalent: The XOR of all bits in the word is 0 if and only if the count of 1-bits is even. So:
- To generate even parity bit: P = D7 XOR D6 XOR D5 XOR D4 XOR D3 XOR D2 XOR D1 XOR D0
- To check: P XOR D7 XOR D6 XOR … XOR D0 = 0 (correct) or 1 (error)
This XOR representation is how parity is implemented in logic circuits.
Parity in Memory Systems
Memory parity was a standard feature of mainframes and minicomputers from the 1960s through the 1990s. Most PC memory before the late 1990s used 9-bit-wide memory chips (one extra bit per byte for parity). ECC memory (which corrects as well as detects errors) has since replaced simple parity in servers and high-reliability systems.
Hardware implementation:
For each byte of RAM:
- During write: compute parity from data bus D0–D7 using an XOR tree (74x280 or equivalent parity generator chip) and write the parity bit to the ninth memory chip alongside the 8 data chips.
- During read: read 8 data bits and 1 parity bit simultaneously. Feed all 9 bits into a parity checker (same XOR tree). If the output is non-zero, assert the PARITY ERROR signal to the CPU.
The 74280 (9-bit parity generator/checker): A single DIP chip with 9 inputs and two outputs (sum-even and sum-odd). Connect data bits D0–D7 to inputs; read the stored parity from memory and connect to the ninth input. Sum-even output goes low when the total count of 1-bits is even — indicating no single-bit error for even parity systems.
Response to parity error: When parity error is detected, the CPU’s NMI (Non-Maskable Interrupt) is asserted. The operating system handles the NMI by printing an error message and halting the system — “PARITY ERROR” or “MEMORY PARITY ERROR” screens were a familiar sight on 1980s–1990s computers. The halt is deliberate: continuing with corrupted data could produce worse results than stopping.
Longitudinal and Lateral Parity for Tape
For magnetic tape storage, a more powerful scheme combines row parity and block parity:
Lateral parity (LRC — Longitudinal Redundancy Check): A parity bit appended to each byte across all tracks simultaneously. On 9-track tape, 8 data tracks + 1 parity track per frame = 9 tracks. The ninth track provides even parity across the other 8 tracks for each frame.
Longitudinal parity (VRC — Vertical Redundancy Check): At the end of each tape block, an extra frame is written containing the column parity — the XOR of all corresponding track bits across all frames in the block. This is essentially parity computed “down the tape” (longitudinally) for each track.
Combined detection: With both LRC and VRC:
- A single-bit error fails LRC (its row parity is wrong) AND fails VRC for the column where it occurred.
- The position of the error is known: it is at the intersection of the failing row and the failing column.
- For a 9-track tape, this also identifies which bit within the byte failed — allowing correction.
This combination of row parity and column parity is historically called a “Hamming” organization even though it is not precisely a Hamming code. It was used on 9-track tape and some early disk systems.
Parity in Serial Communications
Serial communication protocols (RS-232, UART, many radio protocols) routinely include a parity bit at the end of each transmitted character.
UART parity configuration: Most UART (Universal Asynchronous Receiver-Transmitter) chips support configurable parity modes: None (no parity bit), Even, Odd, Mark (parity always 1), Space (parity always 0). The configuration must match on both ends of the link.
Framing: In an RS-232 serial frame, the sequence is: start bit (0), data bits (5–8), optional parity bit, stop bits (1–2). At 9600 baud with 8-N-1 (8 data bits, no parity, 1 stop bit), each character takes 10 bit times. Adding parity (8-E-1) increases to 11 bit times — about 9% overhead.
Effectiveness: Parity detects single-bit errors (which are the majority of errors on typical serial links). Two-bit errors in the same character are undetected — but at typical error rates of 1 in 10^5 or better, two simultaneous bit errors in one 10-bit frame are extremely rare.
Limitations of Single-Bit Parity
Parity’s weakness is well-known: it cannot detect or correct any even number of errors in the same protected word.
Two-bit error: If bits 3 and 5 both flip, the parity count changes by 2 — still even. The parity check passes, reporting no error, despite the data being corrupted. For this reason, parity is not suitable alone for high-reliability data storage or high-noise communications channels.
Cannot locate the error: Parity tells you that one bit (among 8 data bits + 1 parity bit = 9 total) has flipped, but does not tell you which one. This means you cannot correct the error — you can only report it and request a retransmission or discard the corrupt block.
Solution for correction: Hamming codes add multiple parity bits, each covering a different subset of data bits. From the combination of which parity bits fail, the exact position of a single-bit error can be determined and corrected.
Building a Parity Checker: Worked Example
A parity checker for an 8-bit data bus using discrete logic:
Components needed:
- Two 74HC86 quad XOR gates (8 two-input XOR gates, in two packages)
- One 74HC04 hex inverter (for polarity, if needed)
- Pull-up resistor for the error output line
- LED + resistor for visual error indication
Wiring:
- Gate 1: D0 XOR D1 → result A
- Gate 2: D2 XOR D3 → result B
- Gate 3: D4 XOR D5 → result C
- Gate 4: D6 XOR D7 → result D
- Gate 5: A XOR B → result E
- Gate 6: C XOR D → result F
- Gate 7: E XOR F → result G (this is the parity of all 8 data bits)
- Gate 8: G XOR P (stored parity bit) → ERROR output
If ERROR output is 1, a single-bit error has occurred.
This circuit has a propagation delay of 4 gate delays (about 20–40 ns for HC logic), fast enough for any practical memory system.
Test procedure: Apply 0x00 with parity 0 — ERROR should be 0. Apply 0x01 with parity 0 — ERROR should be 1. Apply 0xFF with parity 0 — ERROR should be 1. Apply 0xFF with parity 1 — ERROR should be 0. These four tests verify all gate paths.