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.5.1 (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 pictured below.

Theorem 3.5.2 (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 \leq... ...1} \left( \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.5.3 (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.3. By Lemma 3.3.5, 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$