Parity-check matrix

{{Short description|Part of coding theory}} 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 [[Code word (communication)|codeword]] must 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 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 {{nowrap|1=''H'''''c'''^⊤ = '''0'''}} (some authors<ref>for instance, {{harvnb|Roman|1992|loc=p. 200}}</ref> would write this in an equivalent form, '''c'''''H''^⊤ = '''0'''.)

The rows of a parity check matrix are the coefficients of the parity check equations.<ref>{{harvnb|Roman|1992|loc=p. 201}}</ref> That is, they show how linear combinations of certain digits (components) of each codeword equal zero. For example, the parity check matrix

:<math>H =

\left[ \begin{array}{cccc} 0&0&1&1\\ 1&1&0&0 \end{array} \right] </math>,

compactly represents the parity check equations, :<math>\begin{align} c_3 + c_4 &= 0 \\ c_1 + c_2 &= 0 \end{align}</math>, that must be satisfied for the vector <math>(c_1, c_2, c_3, c_4)</math> to be a codeword of ''C''.

From the definition of the parity-check matrix it directly follows the minimum distance of the code is the minimum number ''d'' such that every ''d - 1'' columns of a parity-check matrix ''H'' are linearly independent while there exist ''d'' columns of ''H'' that are linearly dependent.

==Creating a parity check matrix==

The parity check matrix for a given code can be derived from its [[generator matrix]] (and vice versa).<ref>{{harvnb|Pless|1998|loc=p. 9}}</ref> If the generator matrix for an [''n'',''k'']-code is in standard form : <math>G = \begin{bmatrix} I_k | P \end{bmatrix}</math>, then the parity check matrix is given by : <math>H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix}</math>, because : <math>G H^{\top} = P-P = 0</math>. Negation is performed in the finite field '''F'''_''q''. Note that if the [[Characteristic (algebra)|characteristic]] of the underlying field is 2 (i.e., 1 + 1 = 0 in that field), as in [[binary code]]s, then -''P'' = ''P'', so the negation is unnecessary.

For example, if a binary code has the generator matrix

: <math>G = \left[ \begin{array}{cc|ccc} 1&0&1&0&1 \\ 0&1&1&1&0 \\ \end{array} \right]</math>,

then its parity check matrix is

: <math>H = \left[ \begin{array}{cc|ccc} -1&-1&1&0&0 \\ 0&-1&0&1&0 \\ -1&0&0&0&1 \\ \end{array} \right]</math>.

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

==Syndromes==

For any vector '''x''' of the ambient vector space, '''s''' = ''H'''''x''' is called the [[Syndrome decoding|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.<ref>{{harvnb|Pless|1998|loc=p. 20}}</ref>

==See also== *[[Hamming code]]

==Notes== {{reflist|3}}

==References== * {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | publisher=[[Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | date=1986 | isbn=0-19-853803-0 | pages=[https://archive.org/details/firstcourseincod0000hill/page/69 69] | url=https://archive.org/details/firstcourseincod0000hill/page/69 }} * {{citation|first=Vera|last=Pless|author-link=Vera Pless|title=Introduction to the Theory of Error-Correcting Codes|title-link= Introduction to the Theory of Error-Correcting Codes |edition=3rd|publisher=Wiley Interscience|year=1998|isbn=0-471-19047-0}} * {{citation|first=Steven|last=Roman|title=Coding and Information Theory|series=[[Graduate Texts in Mathematics|GTM]]|volume=134|publisher=Springer-Verlag|year=1992|isbn=0-387-97812-7}} * {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | pages=[https://archive.org/details/introductiontoco0000lint/page/34 34] | url=https://archive.org/details/introductiontoco0000lint/page/34 }}

[[Category:Coding theory]]