Parity-check matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In coding theory, a parity-check matrix of a linear block code C is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide if a particular vector is a codeword and is also used in decoding algorithms.

Definition[edit]

Formally, a parity check matrix, H of a linear code C is a generator matrix of the dual code, C. This means that a codeword c is in C if and only if the matrix-vector product Hc = 0 (some authors[1] would write this in an equivalent form, cH = 0.)

The rows of a parity check matrix are the coefficients of the parity check equations.[2] That is, they show how linear combinations of certain digits (components) 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]
,

compactly represents the parity check equations,

\begin{align} c_3 + c_4 &= 0 \\ c_1 + c_2 &= 0 \end{align},

that must be satisfied for the vector (c_1, c_2, c_3, c_4) to be a codeword of C.

Creating a parity check matrix[edit]

The parity check matrix for a given code can be derived from its generator matrix (and vice-versa).[3] 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^{\top} | I_{n-k} \end{bmatrix},

because

G H^{\top} = 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].

Syndromes[edit]

For any (row) vector x of the ambient vector space, s = Hx is called the syndrome of x. The vector x is a codeword if and only if s = 0. The calculation of syndromes is the basis for the syndrome decoding algorithm.[4]

See also[edit]

Notes[edit]

  1. ^ for instance, Roman 1992, p. 200
  2. ^ Roman 1992, p. 201
  3. ^ Pless 1998, p. 9
  4. ^ Pless 1998, p. 20

References[edit]