Hamming Distance

Between 2 strings of bits

• The number of bit positions in which 2 strings differ
• E.g. the distance between $1011101\to 1001001$
  • is 2 as $1001001$

Minimum Hamming Distance of a code

• If distance is $d$, then $d\text{–}\text{single}$ bit errors are required to convert any one valid code ( string ) into another code with the same checksum

For example, a simple checksum:

• Data of 8 bits:
  • $\boxed{{\displaystyle 0110}}\boxed{{\displaystyle 1010}}$
• Checksum of 4 bits:
  • XOR the two 4-bit blocks $\to \boxed{{\displaystyle 1100}}$

What is the minimum hamming distance of this code?
If one bit changes, the XOR will always result in a different truth value due to its nature
However, if the same two bits change ( i.e. the 3rd bit in the first block and the 3rd bit in the second ) then the XOR value will not change and therefore the checksum would be valid
As a result the minimum hamming distance must be 2, as with 2 errors you can still get a valid checksum