Our task is to compute the minimum hamming distance for the following 16-bit words:


This minimum distance is defined as the minimum of all distances between every combination of two of these bitstrings, so the first approach would be to calculate all of these individual distances. I'm pretty sure this is not the right way to do it, since there are 21 possible combinations.

Then I came across this answer on StackOverflow which says that:

We have a theorem that d_min=weight(sum(all codes)); weight is the number of non zeros in the result string . In your example modulo add all string codes like first column of all and second....... then we get code as [ 0 0 1 1 0 ], weight of this is 2 ( no. of non zeros), i.e the minimum distance of hamming code

but is that really true? If we for example take the three bitstrings


the minimum hamming distance is obviously 1 but the calculation based on that answer would result in 0110 and would suggest that the minimum distance is 2. Am I right about this and is that answer wrong? Or did I miss something really simple that I'm just not noticing?

I also read this answer which - if I understood it correctly - states that there is no simple way of finding the result.


1 Answer 1


You are correct.

Here's what's going on. There are two subtly different questions here. The Stack Overflow question is asking: "given a set of bitvectors that form a Hamming code, how do I find the minimum distance?". In contrast, it sounds like you might be asking "given an arbitrary set of bitvectors, how do I find the minimum distance?". Those aren't the same question. Unsurprisingly, they have two different answers.

The answer on Stack Overflow you're referring to isn't 100% clear, but I suspect it is making the following claim: if you have a set of bitvectors that form a Hamming code, then the minimum distance can be obtained by computing the Hamming weight of the xor of all the bitvectors. I don't know whether that claim is true, but let's suppose it is. That still doesn't help you with (what I think is) your question, because in your problem you have an arbitrary set of bitvectors -- they might not form a Hamming code.

It is easy to find counterexamples to demonstrate that the claim doesn't hold in general, for an arbitrary set of bitvectors. For instance, your example is a perfectly good disproof of that.

There are techniques for finding the minimum distance of a set of arbitrary bitvectors (at least, there are heuristics), but hopefully this is enough to answer the question you asked.

  • $\begingroup$ can you please link to the "there ARE techniques"? Do you have any references? $\endgroup$
    – Tommy
    Commented Sep 3, 2019 at 13:09
  • $\begingroup$ @Tommy, I suggest doing some research into nearest-neighbor search and then asking a new question using the 'Ask Question' button in the upper-right if that doesn't meet your need. $\endgroup$
    – D.W.
    Commented Sep 3, 2019 at 17:09

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.