Finding hamming distance of code

Question

A question asks: find the hamming distance of the following code:

11111  
10101  
01010  
11100  
00011  
11001

The answer is 2. How does this work? I thought hamming distance is only between two strings?

Fidelafidelas

Are you sure it's not asking for the minimum distance? – Leveloff

Answer 1

The Hamming distance of a code is defined as the minimum distance between any 2 codewords. So, in your case, finding the Hamming distance between any 2 of the listed codewords, no one is less than 2.

Brattice

Answer 2

Here is some Python-code to find it automatically:

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

Mandal

Answer 3

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

Frayda

Do you have a source for that theorem? If you have the strings 0000, 1000 and 1110 the minimum hamming distance is obviously 1 but your calculation would return 2 (the xor-sum is 0110) – Hamster