Parity Check Matrix

C = c : Hc = 0 — the dual representation of a linear code.

The idea

A parity-check matrix describes a linear code by the constraints its codewords satisfy, so that testing whether a received string is a codeword becomes a calculation rather than a search through the list of codewords.

Over $\mathbb{F}_2$ — bits, with addition modulo $2$, which is XOR — the simplest constraint selects a set of positions and demands that they sum to zero, so that an even number of them are $1$. This is a parity check. Write it as a row of $0$s and $1$s marking the positions it checks, stack several such rows into a matrix $H$, and the code is the set of words satisfying every row: $C = \{\, c : Hc = 0 \,\}.$ This $H$ is the parity-check matrix of $C$. For a code of block length $n$ and dimension $k$ it is $(n - k) \times n$: the $n - k$ independent constraints cut the $n$ coordinates down to $k$ genuinely free ones, which is why the check bits are called redundancy.

The membership test is now a matrix–vector product, and its output carries more than a verdict. For a received word $r$, the vector $s = Hr$ is the syndrome. It is zero exactly when $r$ is a codeword, and when it is nonzero its value depends only on the error added to the codeword, not on the codeword itself. A matrix whose columns make those values distinguishable turns detection into correction.

Ways to work on it

• Walkthrough. Single parity, plus the dimensions of H for a single-error-correcting code.
• Practice. Decode a Hamming (7,4) received word using its syndrome.
• Hardest. Compute the full Hamming syndrome row by row, then decode.

Not sure where to start? Take the ten-question placement test.