Hamming Distance

• The main concept for error-control: Hamming distance.
• The Hamming distance between 2 words is the number of differences between the corresponding bits.
• Let d(x,y) = Hamming distance between 2 words x and y.
• Hamming distance can be found by
    → applying the XOR operation on the 2 words and
    → counting the number of 1's in the result.
• For example:
    1) The Hamming distance d(000, 011) is 2 because 000⊕011= 011 (two 1's).
    2) The Hamming distance d(10101, 11110) is 3 because 10101⊕11110 = 01011 (three 1's).
Hamming Distance and Error
      ➢ Hamming distance between the received word and the sent code-word is the number of bits
           that are corrupted during transmission.
      ➢ For example:    Let Sent code-word =00000
                                   Received word = 01101
                                   Hamming distance = d(00000, 01101) =3. Thus, 3 bits are in error.
Minimum Hamming Distance for Error Detection
      • Minimum Hamming distance is the smallest Hamming distance b/w all possible pairs of code-             words.
      • Let dmin = minimum Hamming distance.
      • To find dmin value, we find the Hamming distances between all words and select the smallest             one.
      Minimum-distance for Error-detection
       ➢ If ‘s’ errors occur during transmission, the Hamming distance b/w the sent code-word and
            received code-word is ‘s’.
       ➢ If code has to detect up-to ‘s’ errors, the minimum-distance b/w the valid codes must be ‘s+1’
            i.e. dmin=s+1.
       ➢ We use a geometric approach to define dmin=s+1.
              • For example: A code scheme has a Hamming distance dmin =4.
                 This code guarantees the detection of up-to 3 errors (d = s + 1 or s = 3).