Bounds on the parameters of a code

In this section, we prove the Singleton bound and the Gilbert-Varshamov bound. For a fixed length $n$, the Singleton bound is an upper bound on the parameters $k,d$. The Gilbert-Varshamov bound is a lower bound - telling us that there must exist a code with ``good parameters''.

Theorem 3.4.21 (The Singleton bound)   Every linear $[n,k,d]$-code $C$ over $\mathbb{F}_q$ satisfies

$$k+d\leq n+1.$$

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. proof: Fix a basis of $\mathbb{F}_q^n$ and write all the codewords in this basis. Delete the first $d-1$ coordinates in each code word. Call this new code $C'$. Since $C$ has minimum distance $d$, these codewords of $C'$ are still distinct. There are therefore $q^k$ of them. But there cannot be more that $q^{n-d+1}=\vert\mathbb{F}_q^{n-d+1}\vert$ of them. This gives the inequality. $\Box$ Before going on to an example, let us discuss a simple consequence of this. Let $C_i$ be a sequence of linear codes with parameters $[n_i,k_i,d_i]$ such that $n_i\rightarrow \infty$ as $i$ goes to infinity, and such that both the limits

$$R=\lim_{i\rightarrow \infty}\frac{k_i}{n_i},\ \ \ \ \delta=\lim_{i\rightarrow \infty}\frac{d_i}{n_i},$$

exist. The Singleton bound implies

$$\frac{k_i}{n_i}+\frac{d_i}{n_i}\leq 1+\frac{1}{n_i}.$$

Letting $i$ tend to infinity, we obtain

$$R+\delta\leq 1.$$

This bound implies that any sequence of codes must have, in the limit, information rate and relative minimum distance in the triangle pictureed below.

Example 3.4.22   Let ${\cal P}=\{P_1,...,P_n\}\subset \mathbb{F}_q$ be a subset of $n$ distinct points. Let

$$L(a)=\{ f\in \mathbb{F}_q[x]\ \vert\ {\rm deg}(f)\leq a\}$$

denote the vector space of all polynomials of degree less than or equal to $a$. The dimension of $L(a)$ is $a+1$ since the polynomials $1$, $x$, ..., $x^a$ form a basis. Assume $n>a$. Define the evaluation map by

$$E_{\cal P}:L(a) \rightarrow \mathbb{F}_q^n$$

$$f\longmapsto (f(P_1),...,f(P_n)).$$

This is 1-1 if $n>a$ since no polynomial of degree $a$ can have more than $a$ zeros. Its image is denoted $C$. This is a linear $[n,a+1,n-a]$-code over $\mathbb{F}_q$. These are called generalized (or shortened or extended) Reed-Solomon codes. (As we shall see later, in the context of cyclic codes, Reed-Solomon codes have $n=q-1$.) Note the parameters satisfy the Singleton bound, so these are MDS codes. The generator matrix for $C$ is of the form $G=(P_i^j)_{0\leq j\leq a,1\leq i\leq n}$.

Theorem 3.4.23 (Gilbert-Varshamov bound)   There exists a code $C\subset \mathbb{F}_q^n$ such that

$$\frac{q^n}{\sum_{i=0}^{d-1} \left( \begin{array}{c} n\\ i \end{array} \right) (q-1)^i } \leq \vert C\vert.$$

proof: Suppose that $C$ has minimum distance $d$ and block length $n$. Suppose moreover that $C$ is as large as possible with these properties. In other words, we cannot increase the size of $C$ by adding another vector into $C$ and still keeping the minimum distance $d$. This implies that each $v\in F^n$ has distance $\leq d-1$ from some codeword in $C$. This implies

$$F^n\subset \cup_{c\in C} B(c,d-1,F^n).$$

Thus

$$q^n=\vert F^n\vert=\vert\cup_{c\in C} B(c,d-1,F^n)\vert \... ... \begin{array}{c} n\\ i \end{array} \right) (q-1)^i .$$

$\Box$ Taking $\delta$ fixed, and various values of $r=[\delta n]$, as $n$ goes to infinity, gives Figure 3.2.

Figure 3.2: The Gilbert-Varshamov bound for binary codes.

Theorem 3.4.24 (Hamming or sphere-packing bound)   For any (not necessarily linear) code $C\subset \mathbb{F}_q^n$ having $M$ elements, we have

$$M\sum_{i=0}^{e} \left( \begin{array}{c} n\\ i \end{array} \right) (q-1)^i \leq q^n,$$

where $e=[(d-1)/2]$.

proof: For each codeword of $C$, construct a ball of radius $e$ about it. These are non-intersecting, by definition of $d$ and Proposition 3.4.12. By Lemma 3.4.2, each such ball has

$$M\sum_{i=0}^{e} \left( \begin{array}{c} n\\ i \end{array} \right) (q-1)^i$$

elements. The result follows from the fact that $C\subset \mathbb{F}_q^n$ and $\vert\mathbb{F}_q^n\vert=q^n$. $\Box$

Exercise 3.4.25   Show that the following result holds. Let $C$ be any (possibly non-linear) code $C\subset \mathbb{F}_q^n$. Then

$$\log_q\vert C\vert+d\leq n+1.$$

(Hint: Modify the proof of Theorem 3.4.21.)

Exercise 3.4.26   Show that the minimum distance of the code in Example 3.4.22 is $n-a$.

Exercise 3.4.27   Let $q=5$, $a=2$ and ${\cal P}={1,2,3}$ in the code in Example 3.4.22. Compute the code words of $C$ and the generator matrix.

Exercise 3.4.28   Find the parameters $n,k,d$ of the ISBN code in Example 3.4.3.