Namespaces
Variants
Actions

Difference between revisions of "Linear code"

From Encyclopedia of Mathematics
Jump to: navigation, search
(generator and parity check matrices)
m (→‎References: isbn link)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
A [[code]] of fixed length $n$ over a finite field $F$ which forms a subspace of the vector space $F^n$.  
 
A [[code]] of fixed length $n$ over a finite field $F$ which forms a subspace of the vector space $F^n$.  
  
A linear code of rank $r$ may be represented by a ''generator matrix'', an $(r \times n)$ matrix whose rows form a set of linearly independent code words.  A generator matrix can be put in the form $G = (I_r | G_1)$ by row operaions, showing that a linear code is always systematic.  The components of the code word corresponding to the columns of $G_1$ may be referred to as check digits.
+
A linear code of rank $r$ may be represented by a ''generator matrix'', an $(r \times n)$ matrix whose rows form a set of linearly independent code words.  A generator matrix can be put in the form $G = (I_r | G_1)$ by row operations, showing that a linear code is necessarily a [[systematic code]].  The components of the code word corresponding to the columns of $G_1$ may be referred to as check digits.
  
As a linear code, a linear code $C$ has a dual $C^\perp$ consisting of all vectors orthogonal to every element of $C$.  This is a linear code of rank $(n-r)$, and a basis for $C^\perp$ is a set of parity check vectors: a generator matrix for $C^\perp$ is a parity check matrix.
+
A linear code $C$ has a '''dual code''' $C^\perp$ consisting of all vectors in $F^n$ orthogonal to every element of $C$ with respect to the bilinear form $(x,y) = \sum_{i=1}^n x_i y_i$.  This is a linear code of rank $(n-r)$, and a basis for $C^\perp$ is a set of ''parity check'' vectors: a generator matrix for $C^\perp$ is a '''parity check matrix'''.
  
 
See [[Error-correcting code]].
 
See [[Error-correcting code]].
  
 
====References====
 
====References====
* Goldie, Charles M.; Pinch, Richard G.E. ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) ISBN 0-521-40456-8 {{ZBL|0746.94001}}
+
* Goldie, Charles M.; Pinch, Richard G.E. ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) {{ISBN|0-521-40456-8}} {{ZBL|0746.94001}}
* van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics '''86''' Springer (1992) ISBN 3-540-54894-7 {{ZBL|0747.94018}}
+
* van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics '''86''' Springer (1992) {{ISBN|3-540-54894-7}} {{ZBL|0747.94018}}

Latest revision as of 20:28, 15 November 2023

A code of fixed length $n$ over a finite field $F$ which forms a subspace of the vector space $F^n$.

A linear code of rank $r$ may be represented by a generator matrix, an $(r \times n)$ matrix whose rows form a set of linearly independent code words. A generator matrix can be put in the form $G = (I_r | G_1)$ by row operations, showing that a linear code is necessarily a systematic code. The components of the code word corresponding to the columns of $G_1$ may be referred to as check digits.

A linear code $C$ has a dual code $C^\perp$ consisting of all vectors in $F^n$ orthogonal to every element of $C$ with respect to the bilinear form $(x,y) = \sum_{i=1}^n x_i y_i$. This is a linear code of rank $(n-r)$, and a basis for $C^\perp$ is a set of parity check vectors: a generator matrix for $C^\perp$ is a parity check matrix.

See Error-correcting code.

References

  • Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
  • van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
How to Cite This Entry:
Linear code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Linear_code&oldid=39149