For a linear code of dimension , a parity-check matrix is an matrix whose rows form a basis of the dual code . With codewords written as row vectors,Thus gives a full set of independent linear equations defining . A received row vector has syndrome , which is zero exactly when is a codeword.
For example, defines the binary even-weight binary code of length . It has rank , so its kernel has dimension . One can also use a check matrix with redundant rows; the same kernel is defined, but only an independent row selection is a generator matrix whose rows form a basis of .
For a cyclic code whose generator polynomial has distinct roots in a splitting field , the rows impose precisely the codeword conditions . Expanding each value in a basis of over the original finite field, then discarding dependent equations, gives a parity-check matrix over that field of rank . Alternatively choose one root from each Frobenius conjugate orbit and expand its value in the field it generates.
In the usual column convention, a codeword of a linear code obeys , so its nonzero coordinates give a linear dependence among columns of its parity-check matrix. Conversely a dependence gives a nonzero codeword supported on those coordinates. Minimizing the support gives the minimum Hamming distance of a linear code. In the transposed convention , the corresponding objects are the rows of . The size of a dependent set means the number of its coordinate positions, even when some check vectors coincide.
Let over the field with two elements and write . In the quotient ring , multiplication by is represented on coefficient column vectors by the circulant matrixThe kernel is a cyclic code, because multiplication by preserves the condition .
More precisely, set and write , , with and coprime polynomials. Then if and only if . Hence the kernel is generated by , has dimension , and has rank . Selecting independent rows of therefore gives a parity-check matrix for this cyclic code, even when was not supplied as a canonical check polynomial. If for a divisor of , the kernel is exactly the cyclic code generated by .
// Target: algebra.bigb
If a binary length- cyclic code has generator of degree and check polynomial of degree , use the coefficient vectors of as the rows of a parity-check matrix. They have distinct leading positions and are independent. Their scalar products with a word are the coefficients of in its product with , which vanish for codewords.
// Target: algebra.bigb
The syndrome of a received word with respect to a parity-check matrix is . It vanishes exactly when is a codeword and otherwise identifies the coset containing the error pattern.
For a linear code with parity-check matrix , write the received word as , where is a codeword and an error pattern. Its syndrome depends only on the error because . A syndrome decoder chooses a representative error with that syndrome and returns . Choosing a minimum-Hamming weight representative gives minimum-distance decoding; within the guaranteed correction radius it recovers the unique transmitted codeword. Several representatives may tie outside that radius.
For a rank- parity-check matrix of a linear code , two words have equal syndromes exactly when their difference lies in . Thus attainable syndromes label cosets bijectively. For a received word , its syndrome is that of the error , so minimum-weight representatives provide minimum-distance decoding.
// Target: algebra.bigb
A coset leader is a minimum-Hamming-weight word in a coset of a linear code. It represents a most economical error pattern with the associated syndrome. Several leaders can tie; they need not be unique outside the code's guaranteed correction radius.
Articles by others on the same topic
There are currently no matching articles.