# Hamming Distance

Given two strings of equal length, the HammingDistance is the number of places in which they differ. Or mathematically as usually used in coding theory:

The Hamming distance d(x,y) is the number of coordinates where (the symbols) x and y differ.
• d(x,y) = | {1 <= i <= n : not(x_i = y_i)} |

When dealing with binary numbers this simplifies to the number of bits that are set in the XOR of the two words.

Named after the mathematician RichardWesleyHamming.

I ran across this when evaluating a set of random numbers to be used for generating the hash of a chess position. A random number is assigned for the state of each piece on a chessboard (white bishop on a7 gets a different number than black pawn on e5, for example). The position hash is the XOR combination of the random numbers for all the pieces currently in play. It turns out that hash collisions are minimized when the average Hamming distance between the whole set of random numbers for all pieces is maximized. -- IanOsgood

Also see HammingCode and EditDistance, FactoryMethod.
CategoryMath

View edit of July 30, 2010 or FindPage with title or text search