Question: What is ``the best'' code?

What is the ``best'' code of a given length? This natural, but very hard, question motivates the following definition.

Definition 3.5.4   Let $F$ be a finite field with $q$ elements. Let $A_q(n,d)$ denote the largest $M$ such that there exists a $(n,M,d)$ code in $F^n$.

Determining $A_q(n,d)$ is one of the main problems in the theory of error-correcting codes^3.1. At the time of this writing, $A_2(n,d)$ is known for $n<30$, $d$ arbitrary. The previous example implies that $A_2(7,3)\geq 16$. (It turns out that $A_2(7,3)= 16$.)

Exercise 3.5.5   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.5.1.)

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

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

Exercise 3.5.8   Find the parameters $n,k,d$ of the ISBN code in Example 3.3.6.

Exercise 3.5.9   Show that as $n\rightarrow \infty$, the Gilbert-Varshamov bound shows that there is a code of parameters $(n,k,d)$ over $\mathbb{F}_q$ for which the point $(d/n,k/n)$ lies above the Gilbert-Varshamov curve

$$y=1-x\log_q(q-1)-x\log_q(x)-(1-x)\log_q (1-x), \ \ \ \ \ \ \ \ \ 0\leq x\leq \frac{q-1}{q}.$$