# Maximum subset of words with Hamming distance ≥ D

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
• 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
• 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

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

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