TOPICS
Search

Parity Check Matrix


A parity check matrix H of a linear code C of length n and dimension k over a field F is an n×(n-k) matrix whose columns form a basis for the dual code C^_|_. A row vector w in F^n is a codeword of C iff wH=0. Equivalently, the columns of H form a basis for the null space of a generator matrix G, and H^T is a generator matrix for the dual code. A convention using the transpose of H instead writes the check as H^Tw^T=0.

In the row-check convention, redundant rows may be retained without changing the code, provided their row space remains the dual code. A Tanner graph represents the incidence between coordinates and parity-check equations (Tanner 1981). A low-density parity-check code has a sparse check matrix (Gallager 1962).


See also

Coding Theory, Dual Code, Error-Correcting Code, Generator Matrix, Linear Code

Portions of this entry contributed by David Terr

Explore with Wolfram|Alpha

References

Gallager, R. G. "Low-Density Parity-Check Codes." IRE Trans. Inform. Th. 8, 21-28, 1962. https://doi.org/10.1109/TIT.1962.1057683.Roman, S. Coding and Information Theory. New York: Springer-Verlag, 1992.Tanner, R. M. "A Recursive Approach to Low Complexity Codes." IEEE Trans. Inform. Th. 27, 533-547, 1981. https://doi.org/10.1109/TIT.1981.1056404.van Lint, J. H. Introduction to Coding Theory, 2nd ed. Berlin, Germany: Springer-Verlag, 1992. https://doi.org/10.1007/978-3-662-00174-5.

Referenced on Wolfram|Alpha

Parity Check Matrix

Cite this as:

Weisstein, Eric W., with contributions by David Terr. "Parity Check Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ParityCheckMatrix.html

Subject classifications