Linear codes

 

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 = .