= Parity function
{title2=$\operatorname{PARITY}_n(x)$}
The <parity function> on <bits> returns whether an odd number of them are one:
$$
\operatorname{PARITY}_n(x_1,\ldots,x_n)=(x_1+\cdots+x_n)\bmod2=x_1\oplus\cdots\oplus x_n.
$$
For example, $\operatorname{PARITY}_4(1,0,1,1)=1$, and flipping any single input flips the output. A chain of <exclusive or> gates computes it with $n-1$ gates and linear depth; a balanced <binary tree> of such gates has logarithmic depth and still linear size.
Appending a parity <bit> to make the total even detects every single-bit error in a transmitted <binary string>. It misses any even number of flipped <bits>, because their changes cancel modulo two. This simple example separates error detection from <error correction>: detecting an odd number of changes does not identify which positions changed.
Back to article page
