The parity of a group of bits says whether the count of 1s in it is odd or even. The bits 1101 hold three 1s, so their parity is odd. The bits 1001 hold two, so their parity is even. Zero 1s counts as even.
The gate that computes parity is XOR. A multi-input XOR outputs 1 exactly when an odd number of its inputs are 1:
- is 1 for one or three 1s.
- Inverting it, , gives 1 for zero or two 1s.
These two functions are the odd function and the even function. Each is 1 in exactly half the rows of its truth table.
You can find parity two ways, and they always agree:
- Count the 1s and check odd or even. Fastest with many bits.
- Chain XORs one bit at a time. Order doesn't matter, because XOR is commutative and associative.
The big application is error detection. A sender adds a parity bit so the total number of 1s has a known parity. If noise flips one bit on the way, the parity changes and the receiver notices. Parity can't tell which bit flipped, and it misses two flips, but it costs only one extra bit and a few XOR gates.
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |