Paper 2, Section I, H

Coding and Cryptography
Part II, 2013

Let A(n,d)A(n, d) denote the maximum size of a binary code of length nn with minimum distance dd. For fixed δ\delta with 0<δ<1/20<\delta<1 / 2, let α(δ)=lim supn1nlog2A(n,nδ)\alpha(\delta)=\limsup _{n} \frac{1}{n} \log _{2} A(n, n \delta). Show that

1H(δ)α(δ)1H(δ/2)1-H(\delta) \leqslant \alpha(\delta) \leqslant 1-H(\delta / 2)

where H(p)=plog2p(1p)log2(1p)H(p)=-p \log _{2} p-(1-p) \log _{2}(1-p).

[You may assume the GSV and Hamming bounds and any form of Stirling's theorem provided you state them clearly.]