The rate of a code with prescribed minimum distance

53 Views Asked by At

Fix $\delta\in(0,1)$. For integer $n$, what is the largest size of a subset $C\subset\{0,1\}^n$ such that any two elements of $C$ are at least $\delta n$ away from each other in the Hamming metric? In other words, what is the largest possible size of a (not necessarily linear) binary code of length $n$ with the minimum distance at least $\delta n$?

It is easy to give a very precise answer for $\delta>0.5$. What about $\delta=0.5$ and $\delta<0.5$? In the latter case, the random construction and the sphere-packing bound seem to show that the answer is exponential in $n$; is the exact basis known? What is the threshold behavior near $\delta=0.5$?

No doubt, this has been studied - please, excuse my ignorance, and thanks in advance for sharing your knowledge!