For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D. (The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)

Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?

Thank you very much.

  • $\begingroup$ Isn't the variation just asking for MDS code? $\endgroup$
    – Yonatan
    Commented Jun 13, 2012 at 9:36
  • 2
    $\begingroup$ As Yonatan hinted, please check the theory of error correcting codes. There are many results about your question. I cannot see a particular connection to MDS codes, though. $\endgroup$ Commented Jun 13, 2012 at 12:13
  • 1
    $\begingroup$ can you please be bothered to state a relevant one "of the many results about my question"? i could not find one, which is why i am asking in this forum. $\endgroup$
    – Chris K
    Commented Jun 13, 2012 at 12:50
  • $\begingroup$ See en.wikipedia.org/wiki/Singleton_bound and references therein $\endgroup$ Commented Jun 13, 2012 at 14:21
  • $\begingroup$ I think that this should be an answer. It's a valid question and a clear answer. $\endgroup$ Commented Jun 13, 2012 at 15:46

3 Answers 3


In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.


In general this is an open problem, so you should not expect anything like a clean formula or an algorithm. For linear codes (at least) an awful lot is known. The authors of


maintain a database of everything(?) that is known about this problem (lower bounds, upper bounds, constructions).


Try the following command on MATLAB, as you're looking for a practical solution


It gives you a matrix, containing the pairwise hamming distance between binary numbers from 0 to 255. You can plot it using any tool in matlab, such as 'imtool'. But be careful about the 1-based indexing of matrices in MATLAB!


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.