Bits do not always arrive as they were sent. A burst of electrical noise on a cable, a cosmic-ray hit on a memory cell or a loose connector can flip a 0 into a 1. The receiver cannot see the original data, so how can it even know something went wrong? The simplest answer, used since the earliest computers and still present in serial ports and memory systems, is the parity bit.
A parity bit is one extra bit added to a group of data bits so that the total number of 1s (data plus parity) is even (even parity) or odd (odd parity). A parity generator computes this bit at the sender; a parity checker recounts at the receiver and flags an error if the count has the wrong parity.
Both circuits turn out to be nothing but XOR gates. In this chapter we design 3-bit generators and 4-bit checkers, see why the K-map gives no simplification, build fast XOR trees, use the 74280 chip, understand exactly which errors parity can and cannot catch, and simulate everything in Verilog. All truth tables were generated and checked by computer, and the Verilog output below is real simulator output.
Why XOR Computes Parity
Recall from Logic Gates that A ⊕ B = 1 when exactly one input is 1. Extend this to many inputs:
A ⊕ B ⊕ C ⊕ ... is 1 when an odd number of the inputs are 1, and 0 when an even number are 1. XOR is the "odd function"; XNOR of all inputs is the "even function".
Intuition: start from 0 and walk through the inputs. Every 1 you meet toggles the result (x ⊕ 1 = x′), every 0 leaves it alone (x ⊕ 0 = x). After the walk, the result has toggled once per 1, so it is 1 exactly when the count of 1s is odd. That is the definition of parity.
Parity Generator
3-Bit Even and Odd Parity Generator
Data bits A, B, C. The even-parity bit P must make the total count of 1s in A, B, C, P even:
A | B | C | Number of 1s in data | P (even parity) | P (odd parity) |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 2 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 2 | 0 | 1 |
1 | 1 | 0 | 2 | 0 | 1 |
1 | 1 | 1 | 3 | 1 | 0 |
Even parity: P = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C
Odd parity: P = Σm(0, 3, 5, 6) = (A ⊕ B ⊕ C)′ = A ⊕ B ⊕ C′
Look at the rule for even parity: if the data already has an even number of 1s, add a 0; if odd, add a 1 to make it even. So the even-parity bit equals "is the data count odd?", which is the XOR of the data bits. Odd parity is just its complement. (Complementing any single input of an XOR chain complements the output, so A ⊕ B ⊕ C′ works too.)
Why the K-Map Does Not Help
P = A ⊕ B ⊕ C BC
00 01 11 10
A 0 | 0 1 0 1
1 | 1 0 1 0
The 1s form a checkerboard: no two 1s are adjacent, because moving to a neighbouring cell changes exactly one input, which always changes the parity. So no grouping is possible, and the minimal SOP is the full canonical form, A′B′C + A′BC′ + AB′C′ + ABC, with 4 terms of 3 literals each. In general the XOR of n variables needs 2n−1 product terms of n literals in two-level SOP form. This is why parity is always built from XOR gates, never from AND-OR logic.
Parity Checker
The receiver gets four bits: A, B, C and P. If the system uses even parity, a correct word has an even number of 1s. The checker output, called PEC (parity error check), is:
Even-parity checker: PEC = A ⊕ B ⊕ C ⊕ P (1 = error: odd number of 1s received)
Odd-parity checker: PEC = (A ⊕ B ⊕ C ⊕ P)′ (1 = error: even number of 1s received)
K-map of the even-parity checker (another checkerboard):
CP
00 01 11 10
AB 00 | 0 1 0 1
01 | 1 0 1 0
11 | 0 1 0 1
10 | 1 0 1 0
Notice that the generator and the checker are the same circuit, an XOR of all bits, just one input wider. That is why chips are sold as "parity generator/checker".
Example 1: Sending the ASCII Letter 'i'
'i' = 0x69 = 1101001 (7 bits, four 1s)
Even parity bit: 1⊕1⊕0⊕1⊕0⊕0⊕1 = 0 → transmit 1101001 0
Odd parity bit: 0′ = 1 → transmit 1101001 1
Receiver (even parity) gets 1101001 0: XOR of all 8 bits = 0 → no error
Bit 2 flips in transit: 1101101 0: XOR of all 8 bits = 1 → ERROR detected
Bits 2 and 3 flip: 1100101 0: XOR of all 8 bits = 0 → error NOT detected
The last line is the key limitation, and we will come back to it.
Building Wide Parity Circuits: Chain vs Tree
An n-input XOR needs n − 1 two-input XOR gates however you connect them, but the connection decides the delay.
Chain (8 bits): ((((((D0⊕D1)⊕D2)⊕D3)⊕D4)⊕D5)⊕D6)⊕D7
7 gates, delay = 7 XOR delays
Tree (8 bits): level 1: D0⊕D1 D2⊕D3 D4⊕D5 D6⊕D7 (4 gates)
level 2: X01⊕X23 X45⊕X67 (2 gates)
level 3: X0123⊕X4567 (1 gate)
7 gates, delay = 3 XOR delays
Because XOR is associative and commutative, any bracketing gives the same answer, so we choose the balanced tree. Its depth is ⌈log2 n⌉ XOR delays.
Bits n | 2-input XOR gates | Chain delay | Tree delay ⌈log2 n⌉ |
|---|---|---|---|
4 | 3 | 3 | 2 |
8 | 7 | 7 | 3 |
9 | 8 | 8 | 4 |
16 | 15 | 15 | 4 |
32 | 31 | 31 | 5 |
The 74280 9-Bit Parity Generator/Checker
The 74280 (74LS280, 74HC280) has nine inputs A to I and two outputs: Σ EVEN, which is HIGH when an even number of inputs are HIGH, and Σ ODD, which is HIGH when an odd number are HIGH (they are always complements).
As an 8-bit even-parity generator: data on A to H, I tied LOW. The parity bit that makes the total even is Σ ODD (it is 1 exactly when the data has an odd count). For odd parity use Σ EVEN.
As a checker: put all 8 data bits and the received parity bit on the 9 inputs. In an even-parity system Σ ODD = 1 means an error; in an odd-parity system Σ EVEN = 1 means an error.
Wider words: feed the Σ ODD output of one 74280 into an input of the next to cover 17, 25, ... bits.
What Parity Can and Cannot Do
Errors in the received word | Total count of 1s changes by | Detected? |
|---|---|---|
1 bit flipped | ±1 (parity changes) | Yes |
2 bits flipped | 0 or ±2 (parity same) | No |
3 bits flipped | odd change | Yes |
Any even number | even change | No |
The parity bit itself flipped | ±1 | Yes (reported as an error even though the data is fine) |
Detects every odd number of bit errors, misses every even number. In coding-theory terms, adding a parity bit gives a minimum Hamming distance of 2: any two valid code words differ in at least 2 bits.
Cannot correct. It tells you that an error happened, not where, so the receiver must ask for a re-transmission or raise an alarm.
Cheap. One extra bit and a few XOR gates, so it is used where errors are rare and usually single: UART serial frames (parity can be set to none, even or odd), older PC memory modules, and many on-chip buses.
Using several parity bits, each covering a different subset of the data, lets the receiver locate a single wrong bit and flip it back. That is the idea of the Hamming code and of the ECC memory used in servers. A simple version is two-dimensional parity: arrange data in a grid with one parity bit per row and per column; a single flipped bit makes exactly one row check and one column check fail, and their crossing point is the bad bit.
Verilog Model
A 4-bit even-parity generator and the matching 5-bit checker. The reduction operator ^{...} XORs all bits of a vector, which synthesis tools turn into an XOR tree.
// Even-parity generator for 4 data bits and checker for the 5-bit word
module parity_gen (input logic [3:0] d, output logic p);
assign p = d[3] ^ d[2] ^ d[1] ^ d[0]; // makes the total count of 1s even
endmodule
module parity_chk (input logic [3:0] d, input logic p, output logic err);
assign err = ^{d, p}; // 1 if the received word has odd 1s
endmodule
module tb;
logic [3:0] data, rx_d; logic p, rx_p, err;
parity_gen gen (.d(data), .p(p));
parity_chk chk (.d(rx_d), .p(rx_p), .err(err));
initial begin
data = 4'b1011; #1;
$display("Data %b -> parity bit %b, sent word %b%b", data, p, data, p);
{rx_d, rx_p} = {data, p}; #1 $display("Received %b%b (no error) -> error = %b", rx_d, rx_p, err);
{rx_d, rx_p} = {data, p} ^ 5'b00100; #1 $display("Received %b%b (1 bit flipped) -> error = %b", rx_d, rx_p, err);
{rx_d, rx_p} = {data, p} ^ 5'b01100; #1 $display("Received %b%b (2 bits flipped) -> error = %b", rx_d, rx_p, err);
end
endmodule
Output (iverilog -g2012, vvp):
Data 1011 -> parity bit 1, sent word 10111
Received 10111 (no error) -> error = 0
Received 10011 (1 bit flipped) -> error = 1
Received 11011 (2 bits flipped) -> error = 0
Data 1011 has three 1s, so the even-parity bit is 1 and the sent word 10111 has four. One flipped bit is caught; two flipped bits slip through, exactly as the table above predicts.
Common Mistakes
Mixing up the parity bit and the parity of the data. For even parity the parity bit is 1 when the data has an odd number of 1s.
Trying to simplify parity with a K-map. It is a checkerboard; the answer is XOR gates.
Saying parity detects all errors. It detects only an odd number of flipped bits, and it never corrects.
Forgetting the parity bit in the checker. The checker XORs all received bits, including P.
Computing tree delay as n − 1. That is the gate count (and the chain delay). A balanced tree has delay ⌈log2 n⌉.
Reading the 74280 outputs the wrong way round. For an even-parity generator, the bit to append is Σ ODD.
Interview and GATE Questions
Q1. Find the odd-parity bit for the 7-bit data 1011001.
The data has four 1s (even). For odd parity the total must be odd, so P = 1.
Q2. An even-parity system receives 10110110. Is there an error?
Count the 1s: 1 + 0 + 1 + 1 + 0 + 1 + 1 + 0 = 5, which is odd. The checker outputs 1: an error is detected (an odd number of bits were flipped, most likely one).
Q3. How many 2-input XOR gates are needed for a 16-bit parity generator, and what is the minimum delay?
15 gates; with a balanced tree, log2 16 = 4 XOR delays.
Q4. How many product terms does the minimal SOP of A ⊕ B ⊕ C ⊕ D have?
24−1 = 8 terms, each with 4 literals, because the K-map is a checkerboard with 8 isolated 1s.
Q5. Can a single parity bit detect a 2-bit error? Why not?
No. Flipping two bits changes the count of 1s by −2, 0 or +2, so its parity (even or odd) is unchanged and the checker sees a valid word.
Q6. Show that the odd-parity bit of A, B, C equals A ⊕ B ⊕ C′.
The odd-parity bit is (A ⊕ B ⊕ C)′. Since X ⊕ C′ = (X ⊕ C)′ for any X, A ⊕ B ⊕ C′ = (A ⊕ B ⊕ C)′.
Q7. With a 74280 used as an 8-bit generator (input I = 0), which output gives the even-parity bit?
Σ ODD. It is 1 when the 8 data bits contain an odd number of 1s, which is exactly when a 1 must be appended to make the total even.
Summary
A parity bit makes the total number of 1s even (even parity) or odd (odd parity).
XOR of n bits is 1 for an odd count of 1s, so the even-parity generator is P = XOR of the data, and odd parity is its complement.
The checker XORs all received bits including P; for even parity, output 1 means an error.
Parity functions have checkerboard K-maps and cannot be simplified in SOP; build them from n − 1 XOR gates in a balanced tree of depth ⌈log2 n⌉.
The 74280 provides Σ EVEN and Σ ODD for 9 inputs and works as both generator and checker.
Parity detects any odd number of bit errors, misses even numbers and cannot correct; Hamming codes extend the idea to correction.
Next, Hazards in Combinational Circuits looks at the short, unwanted glitches that real gate delays can produce at the outputs of the circuits we have been designing.