Binary codes with length and distance a power of 2

Question

Let $A_2(n,d)$ denote the maximum number of words in a binary code (not necessarily linear) with length $n$ and distance $d$. The value of this function is not known in general, though there are tables for small values of $n$ and $d$, e.g. http://www.win.tue.nl/~aeb/codes/binary-1.html.

Suppose $n = 2^k$ and $d = 2^j$ (with $j < k$) are both powers of $2$. Is there a known formula for $A_2(2^k,2^j)$? It seems like a strong enough assumption that a closed formula should exist.

I am also interested if there are other exact results that apply when $n$ and $d$ can be large.

Answer 1

I doubt that a general formula is known, even in this special case. But the largest and smallest $2+2$ cases are easy: for all $n$, whether of the form $2^k$ or not, we have:

• $A_2(n,1) = 2^n$ (trivial);
• $A_2(n,2) = 2^{n-1}$ (partiy code);
• $A_2(n,n) = 2$ (repetition code), and most interestingly:
• if $n$ is even then $A_2(n,n/2) \leq 2n$, with equality at least when $n = 2^k$ (extended Hamming code).
• [Likewise $A_2(n-1, n/2) \leq n$, with the same equality condition.]

When $n=2^k$, these are all examples of Reed-Muller codes, and there's one of minimal distance $2^j$ for each $j$; but in general they're far from optimal.