XOR, XNOR and Parity Circuits
Use XOR as a controlled inverter and an equality test, and build parity circuits as fast trees of XOR gates.
You Will Be Able To
- Apply the laws of XOR algebra.
- Use XOR as a controlled inverter and XNOR as an equality test.
- Build a parity generator and a parity checker.
- Compare the depth of an XOR tree with an XOR chain.
- Lesson
- G2.7
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A byte is stored with one extra bit, so that every stored word holds an even number of 1s. On read, an XOR of all nine bits must give 0. One flipped bit is caught. Two flipped bits are not.
- Cycle 0
The byte 10110010 holds four 1s, so p = 0. Nothing flips, and err is 0.
- Cycle 1
One bit flips in storage. The nine bits now hold an odd count, and err rises.
- Cycle 2
Two bits flip. The count is even again, so err stays 0. The error is missed.
- Cycle 3
The byte 11111111 has eight 1s, so p = 0. The flipped parity bit itself is caught too.
The lines of the lab below, measured on Icarus.
XOR Algebra
XOR, written a ⊕ b or a ^ b, is 1 when its inputs differ. It has its own small set of laws.
| Law | Equation |
|---|---|
| Identity | a ^ 0 = a |
| Inverter | a ^ 1 = a' |
| Self | a ^ a = 0 |
| Complement | a ^ a' = 1 |
| Commutative | a ^ b = b ^ a |
| Associative | (a ^ b) ^ c = a ^ (b ^ c) |
| As AND-OR | a ^ b = ab' + a'b |
| XNOR | (a ^ b)' = a ^ b' |
| AND distributes over XOR | a(b ^ c) = ab ^ ac |
Each equation was checked on every input row. ^ is XOR and the apostrophe is NOT.
The associative law means the brackets do not matter. So a ⊕ b ⊕ c ⊕ ... is well defined: it is 1 when an odd number of the inputs are 1.
Two laws are the most useful. a ⊕ a = 0, so XOR with the same value twice undoes itself. a ⊕ 1 = a', so XOR with 1 inverts.
A Controlled Inverter and an Equality Test
Read a ⊕ b with b as a control. When b = 0 the output is a. When b = 1 the output is a'. So an XOR gate is an inverter you can switch on and off.
XNOR is 1 when its inputs are equal. To test two words for equality, XNOR each pair of bits and AND the results. In logic, this is how a cache compares a tag. A CAM does the same compare on a shared match line, in lesson G8.11.
Parity Generators and Checkers
A parity bit makes the number of 1s in a word even (even parity) or odd (odd parity). The sender computes it. The receiver checks it.
- I/O
- Datapath
- Neutral
- Data
- Control
- Generate
The byte holds four 1s. Its XOR is 0, so p = 0 keeps the count even.
Follow the calls, values and waits
- data 10110010: Data → Generator
- Store
Nine bits are stored. Noise flips one of them.
Follow the calls, values and waits
- data p = 0: Generator → Memory or wire
- Check
The XOR of the nine bits read back is 1: an odd count, so an error.
Follow the calls, values and waits
- data one bit flipped: Memory or wire → Checker
- data err = 1: Checker → err
Read the diagram as text
- Data: 8 bits
- Generator: p = XOR of 8 bits
- Memory or wire: 9 bits; noise may flip some
- Checker: err = XOR of 9 bits
- err: 1: odd count
- Data → Generator: data
- Generator → Memory or wire: data and p
- Memory or wire → Checker: 9 bits read
- Checker → err: verdict
Generator and checker are the same circuit: an XOR of all the bits. The checker has one more input.
For odd parity, invert the result. The generator gives ~^data, and the checker flags an error when the nine bits hold an even count.
A Tree of XORs Against a Chain
An XOR of n bits needs n − 1 two-input gates however you wire them. The wiring sets the delay. A chain adds one bit per gate. A tree pairs the bits, then pairs the results.
| Inputs n | Two-input XOR gates | Chain depth | Tree depth |
|---|---|---|---|
| 8 | 7 | 7 | 3 |
| 9 | 8 | 8 | 4 |
| 16 | 15 | 15 | 4 |
| 32 | 31 | 31 | 5 |
| 64 | 63 | 63 | 6 |
Chain depth is n − 1. Tree depth is log2 n, rounded up. Both use n − 1 gates.
Asked in interviews
How do you check two words for equality with gates?
XNOR each pair of bits, then AND all the results. Each XNOR is 1 when its two bits match, so the AND is 1 only when every bit matches.
What can a single parity bit detect?
Any odd number of flipped bits. An even number of flips leaves the count of 1s unchanged, so it goes unseen. Parity cannot tell which bit flipped either.
Why build a parity circuit as a tree?
A tree has depth log2 n against n − 1 for a chain, with the same number of gates. For 64 bits that is 6 gate delays against 63.
Try It
The generator XORs the eight data bits. The checker XORs all nine stored bits. With even parity it must give 0.
The bench flips bits on the way with stored ^ flips. One flip is caught. Two flips are not. A flipped parity bit is caught like any other bit.
Change the generator to odd parity: assign p = ~^data;. Then change the checker so that a clean word still gives err = 0.
Add a fifth call that flips three bits. Predict err before you run it.
data 10110010 p 0 flipped bits 0 err 0 data 10110010 p 0 flipped bits 1 err 1 data 10110010 p 0 flipped bits 2 err 0 data 11111111 p 0 flipped bits 1 err 1Read included file: tb.sv
// tb.sv: writes a byte with its parity bit, flips bits on the way, and checks the word (read-only).
module tb;
logic [7:0] data;
logic p, err;
logic [8:0] stored, flips;
parity_gen u_gen (.data(data), .p(p));
parity_chk u_chk (.word(stored ^ flips), .err(err));
task automatic send(input logic [7:0] d, input logic [8:0] f);
data = d;
#1 stored = {p, data};
flips = f;
#1 $display("data %b p %b flipped bits %0d err %b", data, p, $countones(f), err);
endtask
initial begin
send(8'b1011_0010, 9'b0);
send(8'b1011_0010, 9'b0_0000_0100);
send(8'b1011_0010, 9'b0_0100_0100);
send(8'b1111_1111, 9'b1_0000_0000);
end
endmodule
Check Yourself
Common Mistakes
Wrong Expect a parity check to catch every error.
Two flipped bits leave the count of 1s even, so the checker sees nothing. The lab shows it.
Fix Parity catches any odd number of flipped bits. Use a stronger code, such as a CRC or Hamming code, for more.
Wrong Mix up even and odd parity.
Even parity makes the total number of 1s even; odd parity makes it odd. The two parity bits are complements.
Fix Even parity bit: ^data. Odd parity bit: ~^data.
assign p = ^data; // even parity, but the bus uses oddassign p = ~^data; // odd parity: the nine bits hold an odd countWrong Chain the XOR gates in a row.
A chain of n − 1 gates is correct, but its delay grows with n. A tree has the same gates and a depth of only log2 n.
Fix Pair the inputs, then pair the results, until one output is left.
Wrong Read a three-input XOR as "exactly one input is 1".
XOR of many inputs is 1 when an odd number of them are 1. For 111 it gives 1.
Fix Count the 1s. Odd gives 1, even gives 0.
Remember
- a ⊕ 0 = a, a ⊕ 1 = a', a ⊕ a = 0. XOR is associative, so many-input XOR is odd parity.
- XOR is a controlled inverter. XNOR is 1 when its inputs are equal.
- A parity bit catches any odd number of flipped bits, and misses an even number.
- An XOR of n bits needs n − 1 gates: a chain has depth n − 1, a tree only log2 n.