Parity Generator and Checker
An XOR tree generates the even-parity bit for four data bits, and a final XOR compares it with a received parity bit. The checker detects any odd number of bit inversions but cannot locate an error or detect every even-numbered error pattern.
An XOR tree generates the parity bit required to make the total number of 1s even. A final XOR compares that generated value with the received parity bit and signals a mismatch.
What You'll Learn
- Generate an even-parity bit by XOR-reducing four data bits.
- Explain why P_even is HIGH for data words with odd Hamming weight.
- Use XOR to compare generated and received parity values.
- Predict which odd-numbered error patterns parity detects.
- Demonstrate why an even-numbered bit error can remain undetected.
How It Works
The four data inputs D3..D0 feed a balanced XOR tree. Its output P_even is HIGH when the data word contains an odd number of 1s. Appending that HIGH parity bit makes the five-bit codeword contain an even number of 1s; if the data already has even weight, P_even is LOW.
The checker in this circuit compares the locally generated parity with the Received P switch. Error = P_even ⊕ P_rx, so Error is HIGH whenever the received parity bit does not match the data. A single altered bit—whether a data bit or the parity bit—changes total parity and is detected. More generally, any odd number of bit inversions is detected.
Parity does not identify which bit changed, and it cannot detect every multi-bit error. An even number of inversions preserves parity, so a two-bit corruption can pass the check. Stronger schemes such as CRCs and error-correcting codes add redundancy to detect broader error patterns or locate and correct faults.
Truth Table
These representative vectors pair selected data words with matching and mismatching received parity. Outputs are the generated even-parity bit and the Error indicator.
| Inputs | Output | ||||||
|---|---|---|---|---|---|---|---|
| D3 | D2 | D1 | D0 | Received P | Even Parity Bit | Error | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | Zero data bits are HIGH, so the matching parity bit is 0. |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | The same data with Received P = 1 produces a mismatch. |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | One data bit is HIGH, so P_even must be 1 to make the total even. |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | Using Received P = 0 for odd-weight data is detected. |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | Two data bits are HIGH; matching even parity is 0. |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | Received P = 1 disagrees with the even-weight data. |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | Three HIGH data bits require parity 1. |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | A parity value of 0 for three HIGH data bits is detected. |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | Four HIGH data bits already have even weight. |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | The wrong parity bit makes the five-bit word odd. |
Boolean Expression
XOR reduction is 1 exactly when the data word has odd Hamming weight; that value is the bit appended for even parity.
The Error output is HIGH when received parity differs from the parity recomputed from the current data.
Try It Step-by-Step
Set the listed controls in the embedded circuit, then compare the observed modeled state with the expected result.
- 1D3..D0=0000Received P=0Expected:
Even Parity Bit = 0, Error = 0What you'll see:The all-zero word has even weight, and Received P = 0 matches it. - 2D3..D0=0001Received P=1Expected:
Even Parity Bit = 1, Error = 0What you'll see:0001₂ has one HIGH data bit, so P_even = 1. Supplying Received P = 1 keeps Error LOW. - 3D3..D0=0011Received P=1Expected:
Even Parity Bit = 0, Error = 1What you'll see:0011₂ has two HIGH bits and requires P_even = 0. A received value of 1 is rejected. - 4D3..D0=0011Received P=0Expected:
Even Parity Bit = 0, Error = 0; the two-bit error is not detectedWhat you'll see:Changing two data bits transforms 0000₂ into 0011₂ without changing even parity. Error remains LOW, exposing parity's even-error limitation.
Components Used
Applications and Design Context
UART frames. Optional parity provides inexpensive detection of many serial transmission errors.
Memory and internal buses. Simple systems may store or transfer one parity bit with each data word and raise an error on mismatch.
Register files and caches. Parity can detect corruption when correction is unnecessary or handled by retry and recovery mechanisms.
Storage and communication education. The XOR tree demonstrates how a global property of a word can be reduced through a logarithmic-depth network.
Building stronger codes. Multiple parity checks arranged over selected bit groups lead to Hamming-style syndromes and other coding structures.
Frequently Asked Questions
Why does even parity use a 1 when the data contains an odd number of 1s?
The appended parity bit is chosen so the complete codeword has even Hamming weight. Adding 1 to an odd-weight data word makes the total number of 1s even.
Does parity detect every single-bit error?
Yes, provided the error flips exactly one protected data or parity bit. One inversion changes even parity to odd parity and asserts Error.
Does parity detect every multi-bit error?
No. It detects any odd number of flipped bits but misses error patterns with an even number of flips, including some two-bit errors.
Can this checker correct the corrupted bit?
No. A single parity equation reports only whether its constraint is satisfied; it does not provide enough information to locate the fault. Multiple independent checks are required for a correction syndrome.
Why use an XOR tree instead of one large XOR gate?
A tree composes standard small-fan-in gates and can reduce logic depth for wider words. XOR is associative, so grouping does not change the parity result.