Parity-check matrix

Incoding theory,aparity-check matrixof alinear block codeCis a matrix which describes the linear relations that the components of acodewordmust satisfy. It can be used to decide whether a particular vector is a codeword and is also used in decoding algorithms.

Definition

Formally, a parity check matrixHof a linear codeCis agenerator matrixof thedual code,C^⊥.This means that a codewordcis inCif and only ifthe matrix-vector productHc^⊤=0(some authorswould write this in an equivalent form,cH^⊤=0.)

The rows of a parity check matrix are the coefficients of the parity check equations.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{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}$,

that must be satisfied for the vector$(c_{1},c_{2},c_{3},c_{4})$to be a codeword ofC.

From the definition of the parity-check matrix it directly follows the minimum distance of the code is the minimum numberdsuch that everyd - 1columns of a parity-check matrixHare linearly independent while there existdcolumns ofHthat are linearly dependent.

Creating a parity check matrix

The parity check matrix for a given code can be derived from itsgenerator 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^{\top }|I_{n-k}\end{bmatrix}}$,

because

$GH^{\top }=P-P=0$.

Negation is performed in the finite fieldF_q.Note that if thecharacteristicof the underlying field is 2 (i.e., 1 + 1 = 0 in that field), as inbinary 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]$.

It can be verified that G is a$k\times n$matrix, while H is a$(n-k)\times n$matrix.

Syndromes

For any (row) vectorxof the ambient vector space,s=Hx^⊤is called thesyndromeofx.The vectorxis a codeword if and only ifs=0.The calculation of syndromes is the basis for thesyndrome decodingalgorithm.

See also

• Hamming code

References

• Hill, Raymond (1986).A first course in coding theory.Oxford Applied Mathematics and Computing Science Series.Oxford University Press.pp.69.ISBN0-19-853803-0.
• Pless, Vera(1998),Introduction to the Theory of Error-Correcting Codes(3rd ed.), Wiley Interscience,ISBN0-471-19047-0
• Roman, Steven (1992),Coding and Information Theory,GTM,vol. 134, Springer-Verlag,ISBN0-387-97812-7
• J.H. van Lint (1992).Introduction to Coding Theory.GTM.Vol. 86 (2nd ed.). Springer-Verlag. pp.34.ISBN3-540-54894-7.