Paper 1, Section II, G

Coding and Cryptography
Part II, 2016

What does it mean to say a binary code CC has length nn, size mm and minimum distance d?

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,(d1)/2)\frac{2^{n}}{V(n, d-1)} \leqslant A(n, d) \leqslant \frac{2^{n}}{V(n,\lfloor(d-1) / 2\rfloor)}

where

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

Another bound for A(n,d)A(n, d) is the Singleton bound given by

A(n,d)2nd+1A(n, d) \leqslant 2^{n-d+1}

Prove the Singleton bound and give an example of a linear code of length n>1n>1 that satisfies A(n,d)=2nd+1A(n, d)=2^{n-d+1}.