Linear codes are an important type of codes with a particular type of
structure. In particular, a linear code is a code that is a subspace of a finite-dimensional
vector space over a finite field. The main advantages of using linear codes
arise from the efficient procedures for correcting errors. These procedures are
based on matrix computations that can be carried out easily and rapidly.
Definitions:
Let
denote the vector
space of all n-tuples having components from
the finite field Fq . The elements of
are called vectors or
words.
An (n, k)-linear code C over Fq is a k-dimensional
subspace of
over Fq. More precisely, C is a linear
block code, but the qualification “block” is generally omitted.
The code C is referred to as an (n, k, d)-code, where n
is the length of the code, k is the dimension of
the subspace, and d is the distance.
The Hamming weight of a word v Î
is the number
of nonzero coordinates in v.
Let C be an (n, k)-code over Fq.
A generator matrix G for C is a k × n matrix with entries from Fq
whose rows form a basis for C.
If an (n, k)-code C has a generator matrix of the form G
= [Ik |A], then C is called a systematic code, and the
generator matrix G is said to be in standard form.
Let x = (x1, x2, . . . , xn)
and y = (y1, y2, . . . , yn) be two vectors in
. The inner product of x and y is
the field element x ◦ y =
. If x ◦ y = 0, x and y
are orthogonal.
Let C be an (n, k)-code over Fq.
The orthogonal complement of C, denoted
(read “C perp”), is the
set of vectors orthogonal to every vector in C:
= {
x Î
| x ◦ y = 0 for all y Î C }.
is usually called the
dual code of C. A parity check matrix for an
(n, k)-code C is a generator matrix for
. A linear code C is self-orthogonal if
C Í
. It is self-dual if C =
.