Tuesday, 23 March 2021

Is there something wrong with my Python Hamming distance code?

I am trying to implement the Hamming distance in Python. Hamming distance is typically used to measure the distance between two codewords. The operation is simply performing exclusive OR. For example, if we have the codewords 10011101 and 10111110, then their exclusive OR would be 00100011, and the Hamming distance is said to be 1 + 1 + 1 = 3.

My code is as follows:

def hamming_distance(codeword1, codeword2):
    """Calculate the Hamming distance between two bit strings"""
    assert len(codeword1) == len(codeword2)
    x, y = int(codeword1, 2), int(codeword2, 2) # '2' specifies that we are reading a binary number
    count, z = 0, x^y
    while z:
        count += 1
        z &= z - 1
    return count

def checking_codewords(codewords, received_data):
    closestDistance = len(received_data) # set default/placeholder closest distance as the maximum possible distance.
    closestCodeword = received_data # default/placeholder closest codeword
    for i in codewords:
        if(hamming_distance(i, received_data) < closestDistance):
            closestCodeword = i
            closestDistance = hamming_distance(i, received_data)
    return closestCodeword

print(checking_codewords(['1010111101', '0101110101', '1110101110', '0000000110', '1100101001'], '0001000101'))

hamming_distance(codeword1, codeword2) takes the two input parameters codeword1 and codeword2 in the form of binary values and returns the Hamming distance between the two input codewords.

checking_codewords(codewords, received_data) should determine the correct codeword IFF there are any errors in received data (i.e., the output is the corrected codeword string). Although, as you can see, I haven't added the "IFF there are any errors in received data" part yet.

I just tested the checking_codewords function with a set of examples, and it seems to have worked correctly for all of them except one. When I use the set of codewords ['1010111101', '0101110101', '1110101110', '0000000110', '1100101001'] and the received data '0001000101' the output is 0101110101, which is apparently incorrect. Is there something wrong with my code, or is 0101110101 actually correct and there is something wrong with the example? Or was this just a case where there was no error in the received data, so my code missed it?



from Is there something wrong with my Python Hamming distance code?

No comments:

Post a Comment