Linear block code: A linear (error-correcting) block code C is a vector subspace of Fn, where F is a finite field, and its elements are called codewords. (When F=GF(2) it is called a binary code; when F=GF(3) it is called a ternary code; and when F=GF(4) it is called a quaternary code.) Such a code is said to have length n. If its dimension is k (as a vector space over F) then C is called an [n,k]-code.

A linear transformation G:Fk -> C, m |--> mG, is called a message encoder and the vectors m in Fk are sometimes called the message vectors. If Fn is given the usual "standard" vector space basis then the matrix of G is a generating matrix of C. When G has the block matrix form G = (Ik | A), where Ik denotes the k x k idenity matrix and A is some k x (n-k) matrix, then we say G is in standard form.

Remark: We want to give Fn the usual standard basis because each coordinate represents a "bit" which is transmitted across a "noisy channel" with some small probability of transmission error (please see the binary symmetric channel (BSC) for more details). If some other basis is used then this BSC model cannot be used and the Hamming metric (defined next) does not measure the number of errors in transmission, as we want it to.

The Hamming metric is the function d: Fn x Fn --> Z for which d(v,w) is the number of coordinates of v and w which are not the same. In other words, it is given by: d(v,w)=|{i | vi != wi}| = d(v-w,0), where

v = (v1 , ...., vn) and w = (w1 , ...., wn). The Hamming weight of a vector v, denoted wt(v), is simply its distance from the origin: wt(v) = d(v,0). The minimum distance of C is defined to be the number
d(C) = min_{c !=\ 0} d( c, 0 ). (It is not hard to see that this is equal to the closest distance between any two distinct codewords in C.) An [n,k]-code with minimum distance d is called an [n,k,d]-code.

A matrix H : Fn --> Fn-k whose kernel is C is called a check matrix of C (or sometimes a parity check matrix). If C is a code with a generating matrix G in standard form, G = (Ik | A), then H = ( At | In-k ) is a check matrix for C.

Lemma (Singleton bound): Every linear [n,k,d] code C satisfies k+d < n+2.

If C1 and C2 are two codes of length n and if there is a permutation p in Sn for which (c1,...,cn) in C1 if and only if (cp(1),...,cp(n)) in C2, then we say C1 and C2 are permutation equivalent. In more generality, if there is an n x n monomial matrix M : Fn --> Fn which sends C1 isomorphically to C2 then we say C1 and C2 are equivalent.

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

 A code C whose parameters satisfy k+d=n+1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

The parameter d is closely related to the error correcting ability of the code. The following construction illustrates this. The nearest neighbor decoding algorithm:

Input: A "received vector" v in Fn .

Output: A codeword c in C closest to v.

  • Enumerate the elements of the ball of (Hamming) radius t about v, denoted Bt(v), where v is the received word. Set c="fail''.
  • For each w in Bt(v), check if w in C. If so, put c = w and break to the next step; otherwise ,discard w and move to the next element.
  • Return c.

Note: "fail'' is not returned unless t> (d-1)/2.. We say that a linear C is t-error correcting if  there is at most one codeword in Bt(w), for each w in Fn.

Examples: