Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Parity-check matrix
Summary
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 whether a particular vector is a codeword and is also used in decoding algorithms.
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 would 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
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.
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 is in standard form
then the parity check matrix is given by
because
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
then its parity check matrix is
It can be verified that G is a matrix, while H is a matrix.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.