5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Some glossary: binary code here is: subset of $K_n=(\mathbf{Z}/2\mathbf{Z})^n$. Distance is $\ell^1$-distance, aka Hamming distance. $A_2(n,d)$ is the maximum among all cardinals of subsets of $K_n$ in which points are pairwise at distance $\ge d$. $\endgroup$ – YCor Mar 21 '17 at 1:13
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.