Hamming Distance

Welcome to our comprehensive guide on the Hamming Distance! This lesson is designed for both beginners and intermediate learners, so let's dive right in. 🎯

What is Hamming Distance?

Hamming Distance is a key concept in computer science, especially in areas like error detection and correction, data compression, and genetics. It measures the minimum number of substitutions required to change one string into another. 💡

Real-world Applications

Data Compression: Reducing the Hamming Distance between compressed and original data helps in efficient data compression.
Error Detection: Hamming Distance is used to detect errors in data transmission.
Genetics: It helps in understanding the mutation rate between DNA sequences.

Understanding Binary Strings

Before we delve into Hamming Distance, let's first understand Binary Strings, as they are the foundation of this concept. A binary string is a sequence of 0s and 1s.

Calculating Hamming Distance

Now, let's see how to calculate the Hamming Distance between two binary strings.

Compare each bit of the strings (starting from the leftmost bit) and count the number of bits where the strings differ.
The count of differences gives us the Hamming Distance.

Example 1: Calculating Hamming Distance

Let's calculate the Hamming Distance between the binary strings 10110 and 11101.

Bit Comparison:
Index  | String 1 | String 2 | Difference (if any)
--------|----------|----------|-------------------
   0    |   1      |   1      | No Difference
   1    |   0      |   1      | 1 Difference
   2    |   1      |   1      | No Difference
   3    |   1      |   0      | 1 Difference
   4    |   0      |   1      | 1 Difference

Hamming Distance = Total Differences = 1 + 1 + 1 = 3

Quiz 1

Question: What is the Hamming Distance between the binary strings 1101 and 1011?

A: 0 B: 1 C: 2 Correct: C Explanation: By comparing the binary strings, we find 2 differences.

Implementing Hamming Distance in Python

Here's a Python function to calculate the Hamming Distance between two binary strings:

python

def hamming_distance(s1, s2):
    distance = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            distance += 1
    return distance

Example 2: Implementing Hamming Distance

Let's use our function to calculate the Hamming Distance between the binary strings 10110 and 11101:

python

s1 = "10110"
s2 = "11101"
print(hamming_distance(s1, s2))  # Output: 3

Quiz 2

Question: What is the output of the following Python code?

python

def hamming_distance(s1, s2):
    distance = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            distance += 1
    return distance

s1 = "10110"
s2 = "11101"
print(hamming_distance(s1, s2))

A: 0 B: 1 C: 2 Correct: C Explanation: The code calculates the Hamming Distance between the binary strings 10110 and 11101, which is 3.

Wrapping Up

We've covered the basics of Hamming Distance, its real-world applications, and implemented it in Python. With practice, you'll be able to calculate Hamming Distance with ease and apply it to various problems. 📝

Keep exploring, keep learning, and keep coding! ✅