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.

  • Isn't the variation just asking for MDS code? – Yonatan Jun 13 '12 at 9:36
  • 2
    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. – Tsuyoshi Ito Jun 13 '12 at 12:13
  • 1
    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. – Chris K Jun 13 '12 at 12:50
  • See en.wikipedia.org/wiki/Singleton_bound and references therein – Tsuyoshi Ito Jun 13 '12 at 14:21
  • I think that this should be an answer. It's a valid question and a clear answer. – Suresh Venkat Jun 13 '12 at 15:46
up vote 13 down vote accepted

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

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

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

squareform(pdist(dec2bin(0:255,8),'hamming')*8)

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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