3.I.4G

Coding and Cryptography
Part II, 2006

What does it mean to say that a binary code CC has length nn, size mm and minimum distance dd ? Let A(n,d)A(n, d) be the largest value of mm for which there exists an [n,m,d][n, m, d]-code. Prove that

2nV(n,d1)A(n,d)2nV(n,12(d1))\frac{2^{n}}{V(n, d-1)} \leqslant A(n, d) \leqslant \frac{2^{n}}{V\left(n,\left\lfloor\frac{1}{2}(d-1)\right\rfloor\right)}

where V(n,r)=j=0r(nj)V(n, r)=\sum_{j=0}^{r}\left(\begin{array}{l}n \\ j\end{array}\right).