Chapter 2
Bounds on Codes
2.1. Bounds
We have already seen that a linear code C of length n, dimension k
and minimum distance d is efficient if k is large (with respect to n)
and it corrects many errors if d is large (with respect to n). We are
thus prompted to ask the question: Given n and k, how large can d
be? Or, equivalently: Given n and d, how large can k be? In this
chapter, we will consider three partial answers to these questions.
Theorem 2.1. (Singleton Bound) Let C be a linear code of length n,
dimension k, and minimum distance d over Fq. Then d n k + 1.
This shows that the minimum distance of the Reed-Solomon code
RS(k, q) is exactly n k + 1. Any code having parameters which
meet the Singleton Bound is called an MDS code. (MDS stands for
Maximum Distance Separable.)
There are several proofs one can give for this theorem. We will
give one which relies only on linear algebra. For others, see [MS].
Proof of Theorem 2.1. Begin by defining a subset W Fq
n
by
W := {a = (a1,...,an) Fq
n
| ad = ad+1 = · · · = an = 0}.
For any a W , we have wt(a) d 1, so W C = {0}. Thus
dim(W + C) = dim W + dim C, where W + C is the subspace of Fqn
9
http://dx.doi.org/10.1090/stml/007/02
Previous Page Next Page