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.

Four Reads of a Byte Stored with Even ParityOne read per step. Each step shows the data, its parity bit, the number of bits that flipped in storage and the checker output.
0123data1011001011111111parity bit pbits flipped0121errtwo flips: not seen
Scroll horizontally ↔
  1. Cycle 0

    The byte 10110010 holds four 1s, so p = 0. Nothing flips, and err is 0.

  2. Cycle 1

    One bit flips in storage. The nine bits now hold an odd count, and err rises.

  3. Cycle 2

    Two bits flip. The count is even again, so err stays 0. The error is missed.

  4. 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.

LawEquation
Identitya ^ 0 = a
Invertera ^ 1 = a'
Selfa ^ a = 0
Complementa ^ a' = 1
Commutativea ^ b = b ^ a
Associative(a ^ b) ^ c = a ^ (b ^ c)
As AND-ORa ^ b = ab' + a'b
XNOR(a ^ b)' = a ^ b'
AND distributes over XORa(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.

XOR as a Controlled Inverter
invay
00
01
10
11
XOR as a Controlled Invertern0 · XORn0=0inv=0a=0
inv=0 a=0
n0 · XORinv=0, a=0 → n0=0
Read the connections
GateKindInputsOutput
n0XORinv, an0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Hold inv at 0 and click a: y follows a. Set inv to 1: y is the opposite of a.

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.

A Parity Bit from Sender to ReceiverArrows show the data. The generator adds one bit. The checker XORs all nine bits after the trip.
  • I/O
  • Datapath
  • Neutral
  • Data
  • Control
CallValueReturnWaiting
A parity bit from sender to receiverArrows show the data. The generator adds one bit. The checker XORs all nine bits after the trip. io Data 8 bits datapath Generator p = XOR of 8 bits neutral Memory or wire 9 bits; noise may flipsome datapath Checker err = XOR of 9 bits io err 1: odd count datadata and p9 bits readverdict
  1. io Data8 bits
    • data → Generator
  2. datapath Generatorp = XOR of 8 bits
    • data and p → Memory or wire
  3. neutral Memory or wire9 bits; noise may flip some
    • 9 bits read → Checker
  4. datapath Checkererr = XOR of 9 bits
    • verdict → err
  5. io err1: odd count
  1. Generate

    The byte holds four 1s. Its XOR is 0, so p = 0 keeps the count even.

    Follow the calls, values and waits
    1. data 10110010: Data → Generator
  2. Store

    Nine bits are stored. Noise flips one of them.

    Follow the calls, values and waits
    1. data p = 0: Generator → Memory or wire
  3. Check

    The XOR of the nine bits read back is 1: an odd count, so an error.

    Follow the calls, values and waits
    1. data one bit flipped: Memory or wire → Checker
    2. 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.

Eight Bits in a Chain
Eight Bits in a Chaing0 · XORx1=0g1 · XORx2=0g2 · XORx3=0g3 · XORx4=0g4 · XORx5=0g5 · XORx6=0g6 · XORp=1d0=0d1=0d2=0d3=0d4=0d5=0d6=0d7=1
d0=0 d1=0 d2=0 d3=0 d4=0 d5=0 d6=0 d7=1
g0 · XORd0=0, d1=0 → x1=0
g1 · XORx1=0, d2=0 → x2=0
g2 · XORx2=0, d3=0 → x3=0
g3 · XORx3=0, d4=0 → x4=0
g4 · XORx4=0, d5=0 → x5=0
g5 · XORx5=0, d6=0 → x6=0
g6 · XORx6=0, d7=1 → p=1
Read the connections
GateKindInputsOutput
g0XORd0, d1x1
g1XORx1, d2x2
g2XORx2, d3x3
g3XORx3, d4x4
g4XORx4, d5x5
g5XORx5, d6x6
g6XORx6, d7p

Outputs: p. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 29. Settled after 29 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920212223242526272829pxxxxxxx00111100000000000000001
Scroll horizontally ↔
Every computed frame
Timep
0x
1x
2x
3x
4x
5x
6x
70
80
91
101
111
121
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
291

  1. Step 9 · d0 changed at time 2. The change ripples through all seven gates. p settles at time 9: seven gate delays.
  2. Step 13 · d7 changed at time 12. d7 enters the last gate, so p follows after one gate delay. The delay depends on which bit changed.
  3. Step 29 · d0 changed at time 22. Again seven gate delays for the first bit of the chain.

The parity-chain preset: even parity of eight bits, seven XOR gates in a row.

Eight Bits in a Tree
Eight Bits in a Treeg0 · XORx0=0g1 · XORx1=0g2 · XORx2=0g3 · XORx3=1g4 · XORy0=0g5 · XORy1=1g6 · XORp=1d0=0d1=0d2=0d3=0d4=0d5=0d6=0d7=1
d0=0 d1=0 d2=0 d3=0 d4=0 d5=0 d6=0 d7=1
g0 · XORd0=0, d1=0 → x0=0
g1 · XORd2=0, d3=0 → x1=0
g2 · XORd4=0, d5=0 → x2=0
g3 · XORd6=0, d7=1 → x3=1
g4 · XORx0=0, x1=0 → y0=0
g5 · XORx2=0, x3=1 → y1=1
g6 · XORy0=0, y1=1 → p=1
Read the connections
GateKindInputsOutput
g0XORd0, d1x0
g1XORd2, d3x1
g2XORd4, d5x2
g3XORd6, d7x3
g4XORx0, x1y0
g5XORx2, x3y1
g6XORy0, y1p

Outputs: p. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 25. Settled after 25 gate delays from t = 0.

Output values at each gate delay012345678910111213141516171819202122232425pxxx00111111111100000000001
Scroll horizontally ↔
Every computed frame
Timep
0x
1x
2x
30
40
51
61
71
81
91
101
111
121
131
141
150
160
170
180
190
200
210
220
230
240
251

  1. Step 5 · d0 changed at time 2. Three levels of XOR: p settles at time 5, three gate delays later.
  2. Step 15 · d7 changed at time 12. Every bit is three gates from the output, so every change takes three gate delays.
  3. Step 25 · d0 changed at time 22. Same gates and same function as the chain, with less than half the worst delay.

The parity-tree preset: the same seven XOR gates as a balanced tree.

Inputs nTwo-input XOR gatesChain depthTree depth
8773
9884
1615154
3231315
6463636

Chain depth is n − 1. Tree depth is log2 n, rounded up. Both use n − 1 gates.

Asked in interviews
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 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 1
Read 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

ConceptWhat is a ⊕ b ⊕ a?
ConceptWhich gate inverts its input a when a control input c is 1, and passes a when c is 0?
ConceptA 16-bit parity tree is built from two-input XOR gates. How many gates and how many levels does it need?
ConceptA word with even parity has three of its bits flipped. What does the checker report?
Predict the outputThe program prints the XOR of the three bits 111, then the XOR of 1, 1 and 0. Predict the exact line.
module tb;
  initial $display("%b %b", 1'b1 ^ 1'b1 ^ 1'b1, 1'b1 ^ 1'b1 ^ 1'b0);
endmodule

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.

Before
assign p = ^data;    // even parity, but the bus uses odd
After
assign p = ~^data;   // odd parity: the nine bits hold an odd count

Wrong 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.

Practice

Report a problem with this page