Hamming Distance Calculator

Calculate the number of differing positions between two equal-length strings

Hamming Distance Calculator

Compare strings and calculate the number of positions where characters differ

Binary String 1

Binary String 2

Quick Examples:

Understanding Hamming Distance

Hamming distance is a fundamental metric in information theory and coding theory that measures the minimum number of single-character edits required to change one string into another when both strings have the same length. Named after Richard Hamming, this distance metric is particularly important in error detection and correction, digital communications, and bioinformatics. Unlike other edit distances, Hamming distance only considers substitutions, not insertions or deletions.

Mathematical Definition

d_H(x, y) = Σ(x_i ≠ y_i) for i = 1 to n

Where x and y are strings of equal length n, and the sum counts positions where characters differ

Requirements:

Both strings must have exactly the same length
Only substitutions are considered (no insertions or deletions)
The result is always a non-negative integer
Distance of 0 means the strings are identical

Mathematical Properties

Metric Properties

✓Non-negativity: d(x, y) ≥ 0
✓Identity: d(x, y) = 0 ⟺ x = y
✓Symmetry: d(x, y) = d(y, x)
✓Triangle inequality: d(x, z) ≤ d(x, y) + d(y, z)

Key Characteristics

•Maximum distance equals string length
•Computationally very efficient O(n)
•Particularly useful for fixed-length codes
•Forms the basis for error-correcting codes

Real-World Applications

Error Detection & Correction

• Hamming codes for error correction
• Parity check matrices
• Single-error correction codes
• Multiple-error detection

Digital Communications

• Channel coding theory
• Noise analysis in transmission
• Signal integrity verification
• Protocol error handling

Bioinformatics

• DNA sequence comparison
• Genetic distance measurement
• Mutation analysis
• Phylogenetic studies

Computer Science

• Hash function analysis
• Cryptographic applications
• Data integrity checking
• Pattern recognition

Machine Learning

• Feature similarity measurement
• Clustering algorithms
• Classification tasks
• Nearest neighbor searches

Quality Control

• Manufacturing defect detection
• Product code verification
• Barcode error checking
• Serial number validation

Distance Metrics Comparison

Metric	Operations	Length Requirement	Example
Hamming	Substitution only	Must be equal	“cat” vs “bat” = 1
Levenshtein	Insert, delete, substitute	Can differ	“kitten” vs “sitting” = 3
Jaro-Winkler	Transposition focus	Can differ	“martha” vs “marhta” = 0.96

Worked Examples

Binary Example: Error Detection

Problem:

Compare transmitted vs received binary code

Sent: 1011001

Received: 1010001

Diff: ---X---

Position: 0123456

Hamming distance = 1 (single bit error at position 3)

Text Example: String Similarity

Problem:

Compare two words of equal length

Word 1: kitten

Word 2: sitten

Diff: X-----

Pos: 012345

Hamming distance = 1 (difference only at position 0: ‘k’ vs ‘s’)

Hamming Codes and Error Correction

Single-Error Correction

Hamming codes can detect and correct single-bit errors. The minimum Hamming distance between valid codewords determines the error correction capability:

• Distance 1: No error detection
• Distance 2: Single error detection
• Distance 3: Single error correction
• Distance 4: Single error correction + double error detection

Hamming(7,4) Code Example

A popular Hamming code that encodes 4 data bits into 7 bits (4 data + 3 parity):

Data bits: d₁ d₂ d₃ d₄

Parity bits: p₁ p₂ p₃

Codeword: p₁ p₂ d₁ p₃ d₂ d₃ d₄

Can correct any single-bit error in the 7-bit codeword

Algorithm Implementation

Python Implementation

def hamming_distance(s1, s2):
    if len(s1) != len(s2):
        raise ValueError("Strings must be equal length")
    
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

# Examples
binary_dist = hamming_distance("1011", "1001")  # 1
text_dist = hamming_distance("cat", "bat")      # 1
numeric_dist = hamming_distance("123", "125")   # 1

JavaScript Implementation

function hammingDistance(s1, s2) {
    if (s1.length !== s2.length) {
        throw new Error("Strings must be equal length");
    }
    
    let distance = 0;
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i]) {
            distance++;
        }
    }
    return distance;
}

// Examples
const binaryDist = hammingDistance("1011", "1001");  // 1
const textDist = hammingDistance("cat", "bat");       // 1

Advanced Concepts

Hamming Weight

The Hamming weight of a string is its Hamming distance from the zero string:

weight(x) = hammingDistance(x, “000...0”)

For binary strings, this equals the number of 1s in the string.

Hamming Bound

The sphere-packing bound for error-correcting codes:

M ≤ 2ⁿ / Σ(k=0 to t) C(n,k)

Where M is the number of codewords, n is the length, and t is the error correction capability.

Extended Hamming Codes

Extended Hamming codes add an additional parity bit to detect double errors while maintaining single error correction capability. This increases the minimum distance from 3 to 4, enabling SECDED (Single Error Correction, Double Error Detection).

Advantages and Limitations

Advantages

• Extremely fast computation O(n)
• Simple to understand and implement
• Perfect for fixed-length data
• Foundation for error-correcting codes
• Satisfies all metric properties
• Ideal for binary and categorical data

Limitations

• Requires equal-length strings
• No insertions or deletions allowed
• May not reflect semantic similarity
• Limited applicability to natural language
• Position-dependent (order matters)
• Not suitable for variable-length data

Hamming Distance Calculator