Parity-check matrix

In coding theory, a parity-check matrix of a linear block code C is a generator matrix of the dual code. As such, a codeword c is in C if and only if the matrix-vector product Hct = 0.

The rows of a parity check matrix are parity checks on the codewords of a code. That is, they show how linear combinations of certain digits of each codeword equal zero. For example, the parity check matrix

$H = \left[ \begin{array}{cccc} 0&0&1&1\\ 1&1&0&0 \end{array} \right]$

specifies that for each codeword, digits 1 and 2 should sum to zero (according to the second row) and digits 3 and 4 should sum to zero (according to the first row).

Creating a parity check matrix

The parity check matrix for a given code can be derived from its generator matrix (and vice-versa). If the generator matrix for an [n,k]-code is in standard form

$G = \begin{bmatrix} I_k | P \end{bmatrix}$,

then the parity check matrix is given by

$H = \begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}$,

because

$G H^T = P-P = 0$.

Negation is performed in the finite field Fq. Note that if the characteristic of the underlying field is 2 (i.e., 1 + 1 = 0 in that field), as in binary codes, then -P = P, so the negation is unnecessary.

For example, if a binary code has the generator matrix

$G = \left[ \begin{array}{cc|ccc} 1&0&1&0&1 \\ 0&1&1&1&0 \\ \end{array} \right],$

then its parity check matrix is

$H = \left[ \begin{array}{cc|ccc} 1&1&1&0&0 \\ 0&1&0&1&0 \\ 1&0&0&0&1 \\ \end{array} \right].$

For any (row) vector x of the ambient vector space, s = Hxt is called the syndrome of x. The vector x is a codeword if and only if s = 0.