Parity-check matrix

From Wikipedia, the free encyclopedia

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 HTc=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 = \begin{bmatrix} 0011\\ 1100 \end{bmatrix}

specifies that for each codeword, digits 1 and 2 should sum to zero and digits 3 and 4 should sum to zero.

For more information see Hamming code and generator matrix.

[edit] 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 in standard form is

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

the parity check matrix can be calculated as

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

Negation is performed in the finite field mod q. Note that this means in binary codes negation is unnecessary as -1 = 1 (mod 2).

For example, if a binary code has the generator matrix

G = \begin{bmatrix} 10|101 \\ 01|110 \\ \end{bmatrix}

The parity check matrix becomes

H = \begin{bmatrix} 11|100 \\ 01|010 \\ 10|001 \\ \end{bmatrix}

For any valid codeword x, Hx = 0. For any invalid codeword \tilde{x}, the syndrome S satisfies H\tilde{x} = S.

 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Languages