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 eﬃcient 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 deﬁning 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