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 matrix
The 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.

Ancestors (6)

  1. Linear code
  2. Coding theory
  3. Algebra
  4. Area of mathematics
  5. Mathematics
  6. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.