0
$\begingroup$

Given an alphabet of $q \ge 2$ letters, I want to construct a set $S$ of $x$ strings (of uniform length) such that the minimum Hamming distance between any two strings is $d$. What I need to figure out is the minimum string length $n$ that could produce such a set.

When $d = 1$, then $n = ceiling(log_q(x))$, but I can't figure out how to find $n$ for an arbitrary value of $d > 1$.

$\endgroup$
3
  • $\begingroup$ This is close enough to sphere packing to probably be an open research question. $\endgroup$
    – tergi
    Aug 8, 2012 at 21:52
  • $\begingroup$ Could you please provide some context for this question. On the one hand, this is standard coding theory, but then on the other hand it seems you might be looking for something more specific. So, it is not clear. $\endgroup$
    – user9072
    Aug 8, 2012 at 23:04
  • $\begingroup$ If anyone is interested, here is an implementation of the recommended solution in R: gist.github.com/84bae05a5c3344710fb5 $\endgroup$
    – user25603
    Aug 9, 2012 at 16:27

2 Answers 2

2
$\begingroup$

For $q$ the size of the alphabet and $n$ the length of the code it is costumary to denote by $A_q(n,d)$ the maximal size of a code with minimum distance $d$.

There are numerous investigations on this. tergi already mentioned tables of explicit values. There are however also general bounds known. In particular a classical result is the Gilbert-Varshamov bound that says $$A_q (n,d) \ge \frac{q^n}{\sum_{j=0}^{d-1} C(n,j) (q-1)^j}$$ where by $C(n,j)$ I just mean the binomial coefficient but momentarily fail to typeset it properly.

This is not precisely what you need as you have some $x$ given that corresponds to the $A_q(n,d)$ and need to find a suitable $n$. But for concrete values it would now be easy to solve your problem, and if you need explicit bounds they would (with some additional loss) also be obtainable.

Another question would be how to effectively construct the set then. (Depending on what you are trying to achieve there might be different things to consider.) Yet, without further details from you it is hard/impossible to know what type of information would be most useful.

$\endgroup$
1
  • $\begingroup$ I think this will get me what I want, thank you. The set construction part of the problem is already done, so I don't need any help on that. $\endgroup$
    – user25603
    Aug 9, 2012 at 15:30
1
$\begingroup$

According to my interpretation of Table I of http://neilsloane.com/doc/Me54.pdf it was not known at the time whether you needed bit ($q=2$) strings of length $n=23$, $n=22$, or possibly only of length $n=21$, to construct a set of $x=50$ codewords that are separated from each other by at least Hamming distance $d=10$. This particular example may or may not still be an open question, but there is probably not a known general formula for $n$ in terms of $q$, $x$, and $d$.

Edit: The bounds update at http://webfiles.portal.chalmers.se/s2/research/kit/bounds/unr.html shows that $n$ is now known to be $22$ for the example above, but you can still see that a nice way to compute the function you want has not been discovered.

$\endgroup$
2
  • $\begingroup$ There is also table of good binary codes (linear and not) on S. Litsyn's homepage eng.tau.ac.il/~litsyn/tableand/index.html (updated 1999) $\endgroup$ Aug 9, 2012 at 5:45
  • $\begingroup$ I suspected a general formula might not be available. Thank you for the pointers to those papers. I'd upvote you if I could, but my rep is not high enough yet :) $\endgroup$
    – user25603
    Aug 9, 2012 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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