Author:Zach Crane

Hamming Distance is the number of differences between the corresponding bits of two hamming code values that are of equal length. The hamming distance is calculated by applying the bitwise exclusive or (XOR) operation* on two values.

d(11011, 11100) = 3

Hamming distance is used in simple forms of error detection and correction.

When given a set of hamming code values, the minimum hamming distance can be found to reveal how many errors can be both detected and corrected. The minimum hamming distance can be found by applying the bitwise XOR operator to all values in the hamming code value table.

The number of bit errors that can be detected is as follows:

dmin = z + 1

Where dmin is the minimum hamming distance and z is the number of errors that can be detected.

The number of errors that can be corrected can be found with the equation:

dmin = 2z + 1

Where z is the number of errors that can be corrected.

Applying this logic, to find z errors, a code book with a minimum hamming distance of z + 1 is needed. Similarly, to detect z errors, a code book with a minimum hamming distance of 2z + 1 is needed.

While extremely simple, finding the hamming distance can be quite beneficial. In addition to previously stated uses, the hamming distance is important when writing a code book to use for encryption/decryption. A code book with a small minimum hamming distance is rather ineffective due to the lack of ability to find and correct a significant number of errors. Proper planning and use of hamming distance is key to creating effective code books.

Note: The bitwise exclusive or (XOR) operator is used in comparing bits in two binary values of equal length. Logically the binary values must be broken down into single bits before applying XOR.

If given values are 100110 and 101101 then they break into:

1 0 0 1 1 0
1 0 1 1 0 1

This break down process is done only in logic, not in practice. At this point, it is easy to see the comparison of the bits.

An XOR problem can be written as:

100110
XOR 101101
----------------

The comparison of the two values can now take place using the following truth table:

With this truth table, an XOR problem can be solved:

100110
XOR 101101
-----------------
001011

The number of 1's in the solution are added together to reach a final answer. In this case the answer is 3. What this means is that there are three different bits, or bit-flips, between the two values.

When it is known that the XOR operation will be applied the short-hand version of the problem format can be written as:

(value 1, value 2)

Another variation:

value1 XOR value2

In many programming languages, including the C varieties and Java, the XOR operation is expressed by using a caret (^):

value1 ^ value2

Related Terms:Hamming Code, XOR

Reference Links:
http://www.xcprod.com/titan/XCSB-DOC/binary_xor.html
http://verify.stanford.edu/hyang/thesis/40HD.pdf