查找编码的汉明距离

Question

一个问题要求：找出以下代码的汉明距离。

11111  
10101  
01010  
11100  
00011  
11001

答案是2。这是怎么回事？我以为汉明距离只能在两个字符串之间计算？

- Celeritas

---

你确定它不是在询问最小距离吗？ - Rody Oldenhuis

Answer 1

代码的汉明距离被定义为任意两个编码单词之间的最小距离。因此，在您的情况下，找到所列任意两个编码单词之间的汉明距离时，没有一个小于2。

- guga

Answer 2

我们有一个定理： d_min=weight(sum(all codes))；其中，weight 是结果字符串中非零元素的数量。例如，在你所提供的例子中，对所有字符串代码进行模加操作，比如第一列加上第二列……然后我们得到代码为[ 0 0 1 1 0 ]，这个代码的重量为2（非零元素的数量），即哈明码的最小距离。

- Arun Kumar

---

你有这个定理的来源吗？如果你有字符串 0000、1000 和 1110，那么它们的最小汉明距离显然是 1，但你的计算将返回 2（异或和为 0110）。 - Keiwan

Answer 3

这里有一些 Python 代码可以自动找到它：

code = [
(0,0,0,0,0,0),
(0,0,1,0,0,1),
(0,1,0,0,1,0),
(0,1,1,0,1,1),
(1,0,0,1,0,0),
(1,0,1,1,0,1),
(1,1,0,1,1,0),
(1,1,1,1,1,1)]

def hammingDistance(a, b):
    distance = 0
    for i in xrange(len(a)):
        distance += a[i]^b[i]
    return distance

def minHammingDistance(code):
    minHammingDistance = len(code[0])
    for a in code:
        for b in code:
            if a != b:
                tmp = hammingDistance(a, b)
                if tmp < minHammingDistance:
                    minHammingDistance = tmp
    return minHammingDistance

print("min Hamming distance: %i" % minHammingDistance(code))

- Martin Thoma