In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
, a parity-check matrix of a
linear block code
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
''C'' is a matrix which describes the linear relations that the components of a
codeword
In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...
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
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminol ...
of the
dual code
In coding theory, the dual code of a linear code
:C\subset\mathbb_q^n
is the linear code defined by
:C^\perp = \
where
:\langle x, c \rangle = \sum_^n x_i c_i
is a scalar product. In linear algebra terms, the dual code is the annihilator ...
, ''C''
⊥. This means that a codeword c is in ''C ''
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
the matrix-vector product (some authors 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. That is, they show how linear combinations of certain digits (components) of each codeword equal zero. For example, the parity check matrix
:
,
compactly represents the parity check equations,
:
,
that must be satisfied for the vector
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
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminol ...
(and vice versa). If the generator matrix for an
'n'',''k''code is in standard form
:
,
then the parity check matrix is given by
:
,
because
:
.
Negation is performed in the finite field F
''q''. Note that if the
characteristic of the underlying field is 2 (i.e., 1 + 1 = 0 in that field), as in
binary code
A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also ...
s, then -''P'' = ''P'', so the negation is unnecessary.
For example, if a binary code has the generator matrix
: