Computer NetworksHamming Code

Hamming Code: Error Correction in Digital Communications

LevelIntermediate

Duration75 mins

TopicHamming Code

4 / 5

Single Error Correction

From Detection to Correction

The true power of Hamming codes lies not in their ability to detect errors—simple parity can do that—but in their ability to correct them without any retransmission or additional information from the sender.

This page explores the complete single error correction (SEC) process: receiving a potentially corrupted codeword, identifying the error location, performing the correction, and recovering the original data with mathematical certainty.

By the end, you'll be able to implement a complete Hamming decoder and understand exactly why it works.

What You Will Learn

By the end of this page, you will understand the complete single error correction workflow, why correction always succeeds for single-bit errors, how to handle edge cases (no error, error in check bit, error in data bit), the limitations of SEC with multiple errors, and performance analysis of the correction process.

The SEC Guarantee

Hamming codes provide a provable guarantee: any single-bit error can be corrected. This isn't a probabilistic claim—it's a mathematical certainty based on the code's design.

Theorem (Single Error Correction):

For any Hamming(n, m) code where n = 2^r - 1 and m = n - r:

If a valid codeword c experiences a single-bit error at position j, producing received word r = c ⊕ e_j (where e_j has a 1 only at position j), then:

The syndrome S = H × rᵀ equals column j of H
Column j is the binary representation of j
Therefore, S (interpreted as binary) equals j
Flipping bit j of r recovers the original codeword c

Proof Sketch:

Since r = c ⊕ e_j and H × cᵀ = 0 (c is valid), we have: S = H × rᵀ = H × (c ⊕ e_j)ᵀ = H × cᵀ ⊕ H × e_jᵀ = 0 ⊕ H × e_jᵀ = H × e_jᵀ

The product H × e_jᵀ extracts column j of H, which by construction is the binary representation of j. ∎

Why This Matters

The SEC guarantee is unconditional within its scope: ANY single-bit error in ANY position is correctable—data bit or check bit, position 1 or position 127. No exceptions, no special cases, no failure modes (for single-bit errors). This reliability is why Hamming codes power billions of memory modules worldwide.

SEC Guarantee Summary
Property	Guarantee	Condition
Error Detection	100% for 1-bit errors	Single bit flipped
Error Location	100% accurate	Syndrome gives exact position
Error Correction	100% successful	Flip identified bit
Data Recovery	100% of original data	After correction
Overhead	r check bits for 2^r - r - 1 data bits	Logarithmic growth

Complete Correction Workflow

Let's trace through the complete single error correction process step by step, from receiving a corrupted word to extracting valid data.

The SEC Process:

Correction Workflow Steps

•Receive — Accept the n-bit received word r (potentially corrupted)
•Compute Syndrome — Calculate S = H × rᵀ (or equivalently, compute each parity check)
•Check Syndrome — If S = 0, no error detected; proceed to extract data
•Locate Error — If S ≠ 0, interpret S as binary number giving error position
•Correct — Flip the bit at position S: corrected[S] = r[S] ⊕ 1
•Extract Data — Return bits from non-power-of-two positions as the decoded data

complete_sec_workflow.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class HammingDecoder:
    """
    Complete Single Error Correction Decoder for Hamming codes.
    
    This class encapsulates the full SEC workflow with detailed
    logging for educational purposes.
    """
    
    def __init__(self, n: int):
        """
        Initialize decoder for Hamming(n, n-r) code.
        
        Args:
            n: Codeword length (should be 2^r - 1 for perfect Hamming code)
        """
        self.n = n
        self.r = 0
        while (1 << self.r) < n + 1:
            self.r += 1
        self.m = n - self.r
        
        # Precompute which positions are data vs check
        self.check_positions = [1 << k for k in range(self.r)]
        self.data_positions = [p for p in range(1, n+1) 
                               if p not in self.check_positions]
    
    def compute_syndrome(self, received: list[int], verbose: bool = False) -> int:
        """
        Compute syndrome from received word.
        
        Returns:
            Syndrome as integer (0 if no error, else error position)
        """
        syndrome = 0
        
        if verbose:
            print(f"Computing syndrome for: {received}")
            print(f"Position: " + " ".join(f"{i+1:>2}" for i in range(self.n)))
            print(f"Received: " + " ".join(f"{b:>2}" for b in received))
            print()
        
        for k in range(self.r):
            check_pos = 1 << k
            parity = 0
            covered = []
            
            for pos in range(1, self.n + 1):
                if pos & check_pos:
                    parity ^= received[pos - 1]
                    covered.append(pos)
            
            if verbose:
                values = [received[p-1] for p in covered]
                print(f"Check P{check_pos}: covers {covered}")
                print(f"         values {values} → XOR = {parity}")
            
            if parity == 1:
                syndrome |= check_pos
        
        if verbose:
            print(f"\nSyndrome = {syndrome} (binary: {bin(syndrome)})")
        
        return syndrome
    
    def correct(self, received: list[int], verbose: bool = False) -> list[int]:
        """
        Perform single error correction.
        
        Returns:
            Corrected codeword
        """
        syndrome = self.compute_syndrome(received, verbose)
        corrected = received.copy()
        
        if syndrome == 0:
            if verbose:
                print("\nNo error detected - returning as-is")
        elif syndrome <= self.n:
            if verbose:
                print(f"\nError detected at position {syndrome}")
                print(f"Flipping bit {syndrome}: {corrected[syndrome-1]} → {1 - corrected[syndrome-1]}")
            corrected[syndrome - 1] ^= 1
        else:
            raise ValueError(f"Invalid syndrome {syndrome} for codeword length {self.n}")
        
        return corrected
    
    def decode(self, received: list[int], verbose: bool = False) -> list[int]:
        """
        Complete decode: correct and extract data.
        
        Returns:
            Extracted data bits
        """
        corrected = self.correct(received, verbose)
        
        data = [corrected[pos - 1] for pos in self.data_positions]
        
        if verbose:
            print(f"\nExtracting data from positions: {self.data_positions}")
            print(f"Decoded data: {data}")
        
        return data
    
    def verify(self, codeword: list[int]) -> bool:
        """
        Verify if a codeword is valid (syndrome = 0).
        """
        return self.compute_syndrome(codeword) == 0
 
 
# Demonstration
print("=" * 70)
print("COMPLETE SINGLE ERROR CORRECTION DEMONSTRATION")
print("=" * 70)
 
decoder = HammingDecoder(7)  # Hamming(7,4)
 
# Test case: Error at position 5
print("\n" + "-" * 70)
print("TEST CASE: Error at position 5 (data bit)")
print("-" * 70 + "\n")
 
original = [0, 1, 1, 0, 0, 1, 1]  # Valid codeword for data [1,0,1,1]
received = original.copy()
received[4] ^= 1  # Corrupt position 5
 
print(f"Original codeword:  {original}")
print(f"Received (corrupt): {received}\n")
 
data = decoder.decode(received, verbose=True)
print(f"\nFinal result: {data}")
print(f"Expected:     [1, 0, 1, 1]")
print(f"Match: {data == [1, 0, 1, 1]}")

Handling Different Error Cases

The correction workflow handles several scenarios differently. Understanding these cases is essential for implementing robust decoders.

Case 1: No Error (Syndrome = 0)

When the received word is valid:

All parity checks pass
Syndrome is zero
No correction needed
Data extraction proceeds directly

Received: 0110011 (valid codeword)
Syndrome: 000 = 0
Action: Extract data directly → [1, 0, 1, 1]

Case 2: Error in Check Bit (Syndrome = power of 2)

When a check bit is corrupted:

Only one parity check fails (the one at that position)
Syndrome equals that check bit position
Correction is optional—data bits are unaffected

Received: 1110011 (error at P₁)
Syndrome: 001 = 1
Action: Flip position 1, OR just extract data (same result)

Error in Check Bit - Data Unaffected
Position	1	2	3	4	5	6	7
Type	P₁	P₂	D₁	P₄	D₂	D₃	D₄
Original	0	1	1	0	0	1	1
Corrupted	1	1	1	0	0	1	1
Data bits	—	—	1	—	0	1	1

Case 3: Error in Data Bit (Syndrome = non-power of 2)

When a data bit is corrupted:

Multiple parity checks fail (those whose coverage includes this position)
Syndrome equals the corrupted position
Correction is essential—data would be wrong without it

Received: 0110111 (error at D₂, position 5)
Syndrome: 101 = 5
Action: Must flip position 5 to recover correct data

Error in Data Bit - Correction Required
Position	1	2	3	4	5	6	7
Type	P₁	P₂	D₁	P₄	D₂	D₃	D₄
Original	0	1	1	0	0	1	1
Corrupted	0	1	1	0	1	1	1
Extracted (wrong)	—	—	1	—	1	1	1
Corrected	0	1	1	0	0	1	1
Extracted (right)	—	—	1	—	0	1	1

Optimization for Check Bit Errors

Since check bit errors don't affect data, some implementations skip correction for power-of-two syndromes and directly extract data. This saves one XOR operation but requires careful handling to avoid returning incorrect check bits if the full codeword is needed downstream.

Multi-Bit Error Behavior

While Hamming codes guarantee correction for single-bit errors, understanding their behavior with multiple errors is crucial for system design.

Two-Bit Errors: Detected but Miscorrected

When two bits are corrupted:

The syndrome equals the XOR of both positions
This non-zero syndrome triggers correction
But the "corrected" position is wrong, introducing a third error

Example: Double Error Miscorrection

Two-Bit Error at Positions 3 and 5
Stage	Position 1	2	3	4	5	6	7
Original	0	1	1	0	0	1	1
Corrupted (3,5)	0	1	0	0	1	1	1
Syndrome = 3⊕5 = 6
'Corrected' pos 6	0	1	0	0	1	0	1
Actual errors	—	—	✗	—	✗	✗	—

The syndrome was 6 (= 3 ⊕ 5), so the decoder "corrected" position 6. But position 6 was correct! Now we have three corrupted bits (3, 5, and 6) instead of two.

Three-Bit Errors: May Appear as Single Errors

With three errors, the syndrome equals the XOR of all three positions. This might accidentally equal a single valid position:

Errors at positions 1, 2, 3: syndrome = 1 ⊕ 2 ⊕ 3 = 0 (undetected!)
Errors at positions 1, 2, 4: syndrome = 1 ⊕ 2 ⊕ 4 = 7 (miscorrected)

Statistical Analysis:

For random multi-bit errors in Hamming(7,4):

2-bit errors: Always detected, always miscorrected (100%)
3-bit errors: Some undetected (syndrome = 0), others miscorrected
4+ bit errors: Unpredictable behavior

The Correction Paradox

Attempting to correct two-bit errors makes things worse. This is why basic Hamming codes are only deployed in environments where single-bit errors dominate (like ECC memory with cosmic ray protection). For channels with higher error rates, SEC-DED or more powerful codes are needed.

multi_bit_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def analyze_multi_bit_errors():
    """
    Analyze behavior of Hamming(7,4) under various error patterns.
    """
    from itertools import combinations
    
    def calc_syndrome(word):
        syndrome = 0
        for k in range(3):
            check_pos = 1 << k
            parity = sum(word[p-1] for p in range(1, 8) if p & check_pos) % 2
            if parity:
                syndrome |= check_pos
        return syndrome
    
    original = [0, 1, 1, 0, 0, 1, 1]
    
    print("Multi-Bit Error Analysis for Hamming(7,4)")
    print("=" * 60)
    print(f"Original codeword: {original}\n")
    
    # Analyze 2-bit errors
    print("TWO-BIT ERRORS:")
    print("-" * 60)
    
    for pos1, pos2 in combinations(range(1, 8), 2):
        corrupted = original.copy()
        corrupted[pos1 - 1] ^= 1
        corrupted[pos2 - 1] ^= 1
        
        syndrome = calc_syndrome(corrupted)
        expected_syndrome = pos1 ^ pos2
        
        if syndrome == 0:
            result = "UNDETECTED!"
        else:
            result = f"Miscorrects to pos {syndrome}"
        
        print(f"Errors at ({pos1}, {pos2}): syndrome = {syndrome} ({pos1}⊕{pos2} = {expected_syndrome}) → {result}")
    
    print()
    print("THREE-BIT ERRORS (sample):")
    print("-" * 60)
    
    undetected = 0
    total = 0
    
    for pos1, pos2, pos3 in combinations(range(1, 8), 3):
        corrupted = original.copy()
        corrupted[pos1 - 1] ^= 1
        corrupted[pos2 - 1] ^= 1
        corrupted[pos3 - 1] ^= 1
        
        syndrome = calc_syndrome(corrupted)
        total += 1
        
        if syndrome == 0:
            undetected += 1
            print(f"Errors at ({pos1}, {pos2}, {pos3}): UNDETECTED (syndrome = 0)")
        elif total <= 5:
            print(f"Errors at ({pos1}, {pos2}, {pos3}): syndrome = {syndrome}")
    
    print(f"\n3-bit error statistics: {undetected}/{total} undetected ({100*undetected/total:.1f}%)")
 
analyze_multi_bit_errors()

Performance Analysis

Understanding the computational performance of Hamming decoding is essential for real-time applications like memory access.

Time Complexity:

Operation	Time Complexity	Notes
Syndrome calculation	O(n)	Each bit participates in O(1) checks on average
Error location	O(1)	Syndrome directly encodes position
Correction	O(1)	Single bit flip
Data extraction	O(m)	Read m data positions
Total	O(n)	Linear in codeword length

Space Complexity:

Structure	Size	Notes
Received word	n bits	Input
Syndrome	r bits	O(log n)
Corrected word	n bits	Can be in-place
Output data	m bits	Output

Decoding Performance for Common Hamming Codes
Code	n	r	XOR Operations	Typical Hardware Latency
Hamming(7,4)	7	3	~12	< 1 ns
Hamming(15,11)	15	4	~34	~1 ns
Hamming(31,26)	31	5	~78	~2 ns
Hamming(63,57)	63	6	~172	~3 ns
Hamming(127,120)	127	7	~371	~5 ns

Hardware Parallelism:

In hardware implementations, syndrome bits are computed in parallel:

Each syndrome bit requires XORing ~n/2 positions
An XOR tree of depth O(log n) computes each in parallel
All r syndrome bits compute simultaneously
Total latency: O(log n) gate delays

Memory Access Overhead:

In ECC DRAM:

Read path adds ~3-5 ns for ECC checking
Write path adds ~3-5 ns for ECC generation
Compared to 50-100 ns DRAM latency, overhead is ~5%
Negligible performance impact for significant reliability gain

Real-World Performance

Modern ECC memory controllers perform Hamming encoding/decoding on every memory access at full memory bandwidth. A DDR4-3200 system processes ~25 GB/s of ECC-protected data transparently. The performance cost is virtually zero.

Implementation Patterns

Different contexts call for different implementation approaches. Here are common patterns used in practice.

Pattern 1: Table-Based Lookup

For small codes (n ≤ 16), precompute correction actions:

CORRECTION_TABLE = {
    0: None,     # No error
    1: 0,        # Flip bit 0 (position 1)
    2: 1,        # Flip bit 1 (position 2)
    3: 2,        # Flip bit 2 (position 3)
    # ... etc
}

Advantages: Constant-time lookup, minimal logic Disadvantages: Table size grows with code size

implementation_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# Pattern 1: Table-Based (for small codes)
def decode_table_based(received: list[int]) -> list[int]:
    """
    Table-lookup decoder for Hamming(7,4).
    O(1) syndrome interpretation via precomputed table.
    """
    SYNDROME_TO_FLIP = {
        0: None, 1: 0, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6
    }
    DATA_POSITIONS = [2, 4, 5, 6]  # 0-indexed: positions 3,5,6,7
    
    # Compute syndrome
    s = 0
    for k in range(3):
        mask = 1 << k
        parity = sum(received[i] for i in range(7) if (i+1) & mask) % 2
        s |= parity << k
    
    # Correct
    corrected = received.copy()
    if SYNDROME_TO_FLIP[s] is not None:
        corrected[SYNDROME_TO_FLIP[s]] ^= 1
    
    return [corrected[i] for i in DATA_POSITIONS]
 
 
# Pattern 2: Bit-Parallel (for SIMD/hardware)
def decode_bit_parallel(received: int) -> int:
    """
    Bit-parallel decoder using integer operations.
    received is a 7-bit integer (LSB = position 1).
    Returns 4-bit data.
    """
    # Syndrome calculation using bit manipulation
    # P1 covers bits 0,2,4,6 (positions 1,3,5,7)
    s0 = ((received >> 0) ^ (received >> 2) ^ (received >> 4) ^ (received >> 6)) & 1
    # P2 covers bits 1,2,5,6 (positions 2,3,6,7)
    s1 = ((received >> 1) ^ (received >> 2) ^ (received >> 5) ^ (received >> 6)) & 1
    # P4 covers bits 3,4,5,6 (positions 4,5,6,7)
    s2 = ((received >> 3) ^ (received >> 4) ^ (received >> 5) ^ (received >> 6)) & 1
    
    syndrome = s0 | (s1 << 1) | (s2 << 2)
    
    # Correct by flipping bit (syndrome-1) if syndrome > 0
    corrected = received
    if syndrome > 0:
        corrected ^= (1 << (syndrome - 1))
    
    # Extract data: bits 2,4,5,6 → positions 3,5,6,7
    data = ((corrected >> 2) & 1) | \
           (((corrected >> 4) & 1) << 1) | \
           (((corrected >> 5) & 1) << 2) | \
           (((corrected >> 6) & 1) << 3)
    
    return data
 
 
# Pattern 3: Matrix-Based (for flexibility)
import numpy as np
 
def decode_matrix_based(received: np.ndarray, H: np.ndarray) -> np.ndarray:
    """
    Matrix-based decoder using parity check matrix.
    Generalizes to any linear code.
    """
    syndrome = (H @ received) % 2
    syndrome_val = sum(int(s) << k for k, s in enumerate(syndrome))
    
    corrected = received.copy()
    if syndrome_val > 0 and syndrome_val <= len(received):
        corrected[syndrome_val - 1] ^= 1
    
    # Extract non-power-of-two positions
    n = len(received)
    data_indices = [i for i in range(n) if (i+1) & i]  # Not power of 2
    return corrected[data_indices]
 
 
# Demonstration
print("Implementation Pattern Comparison")
print("=" * 60)
 
# Test input: valid codeword with error at position 5
test = [0, 1, 1, 0, 1, 1, 1]  # Error at index 4 (position 5)
test_int = 0b1110110  # Same as list, LSB = position 1
 
print(f"Input (list): {test}")
print(f"Input (int): {test_int:07b}")
print()
 
result1 = decode_table_based(test)
result2 = decode_bit_parallel(test_int)
 
print(f"Table-based result: {result1}")
print(f"Bit-parallel result: {result2:04b} = {[int(b) for b in f'{result2:04b}']}")
print(f"Expected: [1, 0, 1, 1]")

Choosing an Implementation

Table-based: Best for small codes in software. Bit-parallel: Best for hardware and SIMD. Matrix-based: Best for flexibility and larger codes. Production systems often combine approaches—table lookup for syndrome interpretation with parallel XOR for syndrome computation.

Real-World SEC Applications

Single error correction via Hamming codes is deployed in numerous critical systems where reliability is paramount.

ECC Memory (DRAM)

Modern servers use ECC DIMMs that protect each 64-bit data word:

64 data bits + 8 check bits = 72-bit codeword
Hamming-based SECDED (covered next page) protects against single-bit errors
Error logging tracks soft errors (cosmic rays, alpha particles)
Typical soft error rate: ~1 error per 10^12 bit-hours
Without ECC, a 64GB server might see ~1 error per week

Flash Memory Controllers

NAND flash has inherent error rates that Hamming codes address:

Early flash: 1-bit ECC per 512 bytes was sufficient
Modern MLC/TLC flash: Requires BCH/LDPC codes (stronger than Hamming)
Hamming still used for metadata and page headers

SEC Applications by Domain

•Data Centers — ECC memory in all server-class systems; protects against cosmic ray-induced soft errors
•Aerospace — Radiation-hardened systems use enhanced Hamming codes for mission-critical data
•Automotive — Safety-critical ECUs require ECC for functional safety certification (ISO 26262)
•Medical Devices — Implantable devices use Hamming codes for telemetry reliability
•Industrial Control — PLCs and safety controllers protect memory against electrical noise
•Consumer Electronics — Some high-end routers and NAS devices offer ECC memory options

SEC Deployment Examples
System	Codeword Size	Protection Level	Error Rate Context
DDR4 ECC DIMM	72 bits (64+8)	SEC-DED	~10^-12 BER
Intel CPU Cache	45-bit codes	SEC-DED	~10^-15 BER
Space Systems	16-32 bit codes	SEC + scrubbing	~10^-6 BER (radiation)
Network ASICs	Custom codes	SEC or parity	~10^-12 BER

Silent Protection

The beauty of Hamming-based SEC is its transparency. Users never see errors being corrected. Systems simply work reliably, and error counters in management interfaces quietly log the saves. Every server running today benefits from invisible Hamming code protection.

Summary: Single Error Correction

We have thoroughly examined single error correction—the core capability that makes Hamming codes valuable in practice. Let's consolidate the key takeaways:

Key Takeaways

•SEC is guaranteed for single-bit errors — Mathematical certainty, not probability
•The workflow is: syndrome → locate → flip → extract — Simple, fast, reliable
•Check bit errors don't affect data — Power-of-two syndromes indicate recoverable situations
•Two-bit errors cause miscorrection — Fundamental limitation of basic Hamming codes
•Performance is excellent — O(n) time, O(log n) hardware latency
•Real-world deployment is ubiquitous — ECC memory, flash controllers, safety-critical systems

What's Next:

The final page covers SEC-DED (Single Error Correction, Double Error Detection) codes—an enhancement to basic Hamming codes that adds the ability to detect (though not correct) two-bit errors. This extension is crucial for systems where silent data corruption is unacceptable.

Page Complete

You now understand the complete single error correction process—from receiving a corrupted codeword to recovering valid data. This capability is the practical value of Hamming codes. Next, we'll extend this with double error detection.

4 / 5

Loading learning content...

Computer NetworksHamming Code

Hamming Code: Error Correction in Digital Communications

LevelIntermediate

Duration75 mins

TopicHamming Code

4 / 5

Single Error Correction

From Detection to Correction

By the end, you'll be able to implement a complete Hamming decoder and understand exactly why it works.

What You Will Learn

The SEC Guarantee

Hamming codes provide a provable guarantee: any single-bit error can be corrected. This isn't a probabilistic claim—it's a mathematical certainty based on the code's design.

Theorem (Single Error Correction):

For any Hamming(n, m) code where n = 2^r - 1 and m = n - r:

If a valid codeword c experiences a single-bit error at position j, producing received word r = c ⊕ e_j (where e_j has a 1 only at position j), then:

The syndrome S = H × rᵀ equals column j of H
Column j is the binary representation of j
Therefore, S (interpreted as binary) equals j
Flipping bit j of r recovers the original codeword c

Proof Sketch:

Since r = c ⊕ e_j and H × cᵀ = 0 (c is valid), we have: S = H × rᵀ = H × (c ⊕ e_j)ᵀ = H × cᵀ ⊕ H × e_jᵀ = 0 ⊕ H × e_jᵀ = H × e_jᵀ

The product H × e_jᵀ extracts column j of H, which by construction is the binary representation of j. ∎

Why This Matters

SEC Guarantee Summary
Property	Guarantee	Condition
Error Detection	100% for 1-bit errors	Single bit flipped
Error Location	100% accurate	Syndrome gives exact position
Error Correction	100% successful	Flip identified bit
Data Recovery	100% of original data	After correction
Overhead	r check bits for 2^r - r - 1 data bits	Logarithmic growth

Complete Correction Workflow

Let's trace through the complete single error correction process step by step, from receiving a corrupted word to extracting valid data.

The SEC Process:

Correction Workflow Steps

•Receive — Accept the n-bit received word r (potentially corrupted)
•Compute Syndrome — Calculate S = H × rᵀ (or equivalently, compute each parity check)
•Check Syndrome — If S = 0, no error detected; proceed to extract data
•Locate Error — If S ≠ 0, interpret S as binary number giving error position
•Correct — Flip the bit at position S: corrected[S] = r[S] ⊕ 1
•Extract Data — Return bits from non-power-of-two positions as the decoded data

complete_sec_workflow.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class HammingDecoder:
    """
    Complete Single Error Correction Decoder for Hamming codes.
    
    This class encapsulates the full SEC workflow with detailed
    logging for educational purposes.
    """
    
    def __init__(self, n: int):
        """
        Initialize decoder for Hamming(n, n-r) code.
        
        Args:
            n: Codeword length (should be 2^r - 1 for perfect Hamming code)
        """
        self.n = n
        self.r = 0
        while (1 << self.r) < n + 1:
            self.r += 1
        self.m = n - self.r
        
        # Precompute which positions are data vs check
        self.check_positions = [1 << k for k in range(self.r)]
        self.data_positions = [p for p in range(1, n+1) 
                               if p not in self.check_positions]
    
    def compute_syndrome(self, received: list[int], verbose: bool = False) -> int:
        """
        Compute syndrome from received word.
        
        Returns:
            Syndrome as integer (0 if no error, else error position)
        """
        syndrome = 0
        
        if verbose:
            print(f"Computing syndrome for: {received}")
            print(f"Position: " + " ".join(f"{i+1:>2}" for i in range(self.n)))
            print(f"Received: " + " ".join(f"{b:>2}" for b in received))
            print()
        
        for k in range(self.r):
            check_pos = 1 << k
            parity = 0
            covered = []
            
            for pos in range(1, self.n + 1):
                if pos & check_pos:
                    parity ^= received[pos - 1]
                    covered.append(pos)
            
            if verbose:
                values = [received[p-1] for p in covered]
                print(f"Check P{check_pos}: covers {covered}")
                print(f"         values {values} → XOR = {parity}")
            
            if parity == 1:
                syndrome |= check_pos
        
        if verbose:
            print(f"\nSyndrome = {syndrome} (binary: {bin(syndrome)})")
        
        return syndrome
    
    def correct(self, received: list[int], verbose: bool = False) -> list[int]:
        """
        Perform single error correction.
        
        Returns:
            Corrected codeword
        """
        syndrome = self.compute_syndrome(received, verbose)
        corrected = received.copy()
        
        if syndrome == 0:
            if verbose:
                print("\nNo error detected - returning as-is")
        elif syndrome <= self.n:
            if verbose:
                print(f"\nError detected at position {syndrome}")
                print(f"Flipping bit {syndrome}: {corrected[syndrome-1]} → {1 - corrected[syndrome-1]}")
            corrected[syndrome - 1] ^= 1
        else:
            raise ValueError(f"Invalid syndrome {syndrome} for codeword length {self.n}")
        
        return corrected
    
    def decode(self, received: list[int], verbose: bool = False) -> list[int]:
        """
        Complete decode: correct and extract data.
        
        Returns:
            Extracted data bits
        """
        corrected = self.correct(received, verbose)
        
        data = [corrected[pos - 1] for pos in self.data_positions]
        
        if verbose:
            print(f"\nExtracting data from positions: {self.data_positions}")
            print(f"Decoded data: {data}")
        
        return data
    
    def verify(self, codeword: list[int]) -> bool:
        """
        Verify if a codeword is valid (syndrome = 0).
        """
        return self.compute_syndrome(codeword) == 0
 
 
# Demonstration
print("=" * 70)
print("COMPLETE SINGLE ERROR CORRECTION DEMONSTRATION")
print("=" * 70)
 
decoder = HammingDecoder(7)  # Hamming(7,4)
 
# Test case: Error at position 5
print("\n" + "-" * 70)
print("TEST CASE: Error at position 5 (data bit)")
print("-" * 70 + "\n")
 
original = [0, 1, 1, 0, 0, 1, 1]  # Valid codeword for data [1,0,1,1]
received = original.copy()
received[4] ^= 1  # Corrupt position 5
 
print(f"Original codeword:  {original}")
print(f"Received (corrupt): {received}\n")
 
data = decoder.decode(received, verbose=True)
print(f"\nFinal result: {data}")
print(f"Expected:     [1, 0, 1, 1]")
print(f"Match: {data == [1, 0, 1, 1]}")

Handling Different Error Cases

The correction workflow handles several scenarios differently. Understanding these cases is essential for implementing robust decoders.

Case 1: No Error (Syndrome = 0)

When the received word is valid:

All parity checks pass
Syndrome is zero
No correction needed
Data extraction proceeds directly

Received: 0110011 (valid codeword)
Syndrome: 000 = 0
Action: Extract data directly → [1, 0, 1, 1]

Case 2: Error in Check Bit (Syndrome = power of 2)

When a check bit is corrupted:

Only one parity check fails (the one at that position)
Syndrome equals that check bit position
Correction is optional—data bits are unaffected

Received: 1110011 (error at P₁)
Syndrome: 001 = 1
Action: Flip position 1, OR just extract data (same result)

Error in Check Bit - Data Unaffected
Position	1	2	3	4	5	6	7
Type	P₁	P₂	D₁	P₄	D₂	D₃	D₄
Original	0	1	1	0	0	1	1
Corrupted	1	1	1	0	0	1	1
Data bits	—	—	1	—	0	1	1

Case 3: Error in Data Bit (Syndrome = non-power of 2)

When a data bit is corrupted:

Multiple parity checks fail (those whose coverage includes this position)
Syndrome equals the corrupted position
Correction is essential—data would be wrong without it

Received: 0110111 (error at D₂, position 5)
Syndrome: 101 = 5
Action: Must flip position 5 to recover correct data

Error in Data Bit - Correction Required
Position	1	2	3	4	5	6	7
Type	P₁	P₂	D₁	P₄	D₂	D₃	D₄
Original	0	1	1	0	0	1	1
Corrupted	0	1	1	0	1	1	1
Extracted (wrong)	—	—	1	—	1	1	1
Corrected	0	1	1	0	0	1	1
Extracted (right)	—	—	1	—	0	1	1

Optimization for Check Bit Errors

Multi-Bit Error Behavior

While Hamming codes guarantee correction for single-bit errors, understanding their behavior with multiple errors is crucial for system design.

Two-Bit Errors: Detected but Miscorrected

When two bits are corrupted:

The syndrome equals the XOR of both positions
This non-zero syndrome triggers correction
But the "corrected" position is wrong, introducing a third error

Example: Double Error Miscorrection

Two-Bit Error at Positions 3 and 5
Stage	Position 1	2	3	4	5	6	7
Original	0	1	1	0	0	1	1
Corrupted (3,5)	0	1	0	0	1	1	1
Syndrome = 3⊕5 = 6
'Corrected' pos 6	0	1	0	0	1	0	1
Actual errors	—	—	✗	—	✗	✗	—

The syndrome was 6 (= 3 ⊕ 5), so the decoder "corrected" position 6. But position 6 was correct! Now we have three corrupted bits (3, 5, and 6) instead of two.

Three-Bit Errors: May Appear as Single Errors

With three errors, the syndrome equals the XOR of all three positions. This might accidentally equal a single valid position:

Errors at positions 1, 2, 3: syndrome = 1 ⊕ 2 ⊕ 3 = 0 (undetected!)
Errors at positions 1, 2, 4: syndrome = 1 ⊕ 2 ⊕ 4 = 7 (miscorrected)

Statistical Analysis:

For random multi-bit errors in Hamming(7,4):

2-bit errors: Always detected, always miscorrected (100%)
3-bit errors: Some undetected (syndrome = 0), others miscorrected
4+ bit errors: Unpredictable behavior

The Correction Paradox

multi_bit_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def analyze_multi_bit_errors():
    """
    Analyze behavior of Hamming(7,4) under various error patterns.
    """
    from itertools import combinations
    
    def calc_syndrome(word):
        syndrome = 0
        for k in range(3):
            check_pos = 1 << k
            parity = sum(word[p-1] for p in range(1, 8) if p & check_pos) % 2
            if parity:
                syndrome |= check_pos
        return syndrome
    
    original = [0, 1, 1, 0, 0, 1, 1]
    
    print("Multi-Bit Error Analysis for Hamming(7,4)")
    print("=" * 60)
    print(f"Original codeword: {original}\n")
    
    # Analyze 2-bit errors
    print("TWO-BIT ERRORS:")
    print("-" * 60)
    
    for pos1, pos2 in combinations(range(1, 8), 2):
        corrupted = original.copy()
        corrupted[pos1 - 1] ^= 1
        corrupted[pos2 - 1] ^= 1
        
        syndrome = calc_syndrome(corrupted)
        expected_syndrome = pos1 ^ pos2
        
        if syndrome == 0:
            result = "UNDETECTED!"
        else:
            result = f"Miscorrects to pos {syndrome}"
        
        print(f"Errors at ({pos1}, {pos2}): syndrome = {syndrome} ({pos1}⊕{pos2} = {expected_syndrome}) → {result}")
    
    print()
    print("THREE-BIT ERRORS (sample):")
    print("-" * 60)
    
    undetected = 0
    total = 0
    
    for pos1, pos2, pos3 in combinations(range(1, 8), 3):
        corrupted = original.copy()
        corrupted[pos1 - 1] ^= 1
        corrupted[pos2 - 1] ^= 1
        corrupted[pos3 - 1] ^= 1
        
        syndrome = calc_syndrome(corrupted)
        total += 1
        
        if syndrome == 0:
            undetected += 1
            print(f"Errors at ({pos1}, {pos2}, {pos3}): UNDETECTED (syndrome = 0)")
        elif total <= 5:
            print(f"Errors at ({pos1}, {pos2}, {pos3}): syndrome = {syndrome}")
    
    print(f"\n3-bit error statistics: {undetected}/{total} undetected ({100*undetected/total:.1f}%)")
 
analyze_multi_bit_errors()

Performance Analysis

Understanding the computational performance of Hamming decoding is essential for real-time applications like memory access.

Time Complexity:

Operation	Time Complexity	Notes
Syndrome calculation	O(n)	Each bit participates in O(1) checks on average
Error location	O(1)	Syndrome directly encodes position
Correction	O(1)	Single bit flip
Data extraction	O(m)	Read m data positions
Total	O(n)	Linear in codeword length

Space Complexity:

Structure	Size	Notes
Received word	n bits	Input
Syndrome	r bits	O(log n)
Corrected word	n bits	Can be in-place
Output data	m bits	Output

Decoding Performance for Common Hamming Codes
Code	n	r	XOR Operations	Typical Hardware Latency
Hamming(7,4)	7	3	~12	< 1 ns
Hamming(15,11)	15	4	~34	~1 ns
Hamming(31,26)	31	5	~78	~2 ns
Hamming(63,57)	63	6	~172	~3 ns
Hamming(127,120)	127	7	~371	~5 ns

Hardware Parallelism:

In hardware implementations, syndrome bits are computed in parallel:

Each syndrome bit requires XORing ~n/2 positions
An XOR tree of depth O(log n) computes each in parallel
All r syndrome bits compute simultaneously
Total latency: O(log n) gate delays

Memory Access Overhead:

In ECC DRAM:

Read path adds ~3-5 ns for ECC checking
Write path adds ~3-5 ns for ECC generation
Compared to 50-100 ns DRAM latency, overhead is ~5%
Negligible performance impact for significant reliability gain

Real-World Performance

Implementation Patterns

Different contexts call for different implementation approaches. Here are common patterns used in practice.

Pattern 1: Table-Based Lookup

For small codes (n ≤ 16), precompute correction actions:

CORRECTION_TABLE = {
    0: None,     # No error
    1: 0,        # Flip bit 0 (position 1)
    2: 1,        # Flip bit 1 (position 2)
    3: 2,        # Flip bit 2 (position 3)
    # ... etc
}

Advantages: Constant-time lookup, minimal logic Disadvantages: Table size grows with code size

implementation_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# Pattern 1: Table-Based (for small codes)
def decode_table_based(received: list[int]) -> list[int]:
    """
    Table-lookup decoder for Hamming(7,4).
    O(1) syndrome interpretation via precomputed table.
    """
    SYNDROME_TO_FLIP = {
        0: None, 1: 0, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6
    }
    DATA_POSITIONS = [2, 4, 5, 6]  # 0-indexed: positions 3,5,6,7
    
    # Compute syndrome
    s = 0
    for k in range(3):
        mask = 1 << k
        parity = sum(received[i] for i in range(7) if (i+1) & mask) % 2
        s |= parity << k
    
    # Correct
    corrected = received.copy()
    if SYNDROME_TO_FLIP[s] is not None:
        corrected[SYNDROME_TO_FLIP[s]] ^= 1
    
    return [corrected[i] for i in DATA_POSITIONS]
 
 
# Pattern 2: Bit-Parallel (for SIMD/hardware)
def decode_bit_parallel(received: int) -> int:
    """
    Bit-parallel decoder using integer operations.
    received is a 7-bit integer (LSB = position 1).
    Returns 4-bit data.
    """
    # Syndrome calculation using bit manipulation
    # P1 covers bits 0,2,4,6 (positions 1,3,5,7)
    s0 = ((received >> 0) ^ (received >> 2) ^ (received >> 4) ^ (received >> 6)) & 1
    # P2 covers bits 1,2,5,6 (positions 2,3,6,7)
    s1 = ((received >> 1) ^ (received >> 2) ^ (received >> 5) ^ (received >> 6)) & 1
    # P4 covers bits 3,4,5,6 (positions 4,5,6,7)
    s2 = ((received >> 3) ^ (received >> 4) ^ (received >> 5) ^ (received >> 6)) & 1
    
    syndrome = s0 | (s1 << 1) | (s2 << 2)
    
    # Correct by flipping bit (syndrome-1) if syndrome > 0
    corrected = received
    if syndrome > 0:
        corrected ^= (1 << (syndrome - 1))
    
    # Extract data: bits 2,4,5,6 → positions 3,5,6,7
    data = ((corrected >> 2) & 1) | \
           (((corrected >> 4) & 1) << 1) | \
           (((corrected >> 5) & 1) << 2) | \
           (((corrected >> 6) & 1) << 3)
    
    return data
 
 
# Pattern 3: Matrix-Based (for flexibility)
import numpy as np
 
def decode_matrix_based(received: np.ndarray, H: np.ndarray) -> np.ndarray:
    """
    Matrix-based decoder using parity check matrix.
    Generalizes to any linear code.
    """
    syndrome = (H @ received) % 2
    syndrome_val = sum(int(s) << k for k, s in enumerate(syndrome))
    
    corrected = received.copy()
    if syndrome_val > 0 and syndrome_val <= len(received):
        corrected[syndrome_val - 1] ^= 1
    
    # Extract non-power-of-two positions
    n = len(received)
    data_indices = [i for i in range(n) if (i+1) & i]  # Not power of 2
    return corrected[data_indices]
 
 
# Demonstration
print("Implementation Pattern Comparison")
print("=" * 60)
 
# Test input: valid codeword with error at position 5
test = [0, 1, 1, 0, 1, 1, 1]  # Error at index 4 (position 5)
test_int = 0b1110110  # Same as list, LSB = position 1
 
print(f"Input (list): {test}")
print(f"Input (int): {test_int:07b}")
print()
 
result1 = decode_table_based(test)
result2 = decode_bit_parallel(test_int)
 
print(f"Table-based result: {result1}")
print(f"Bit-parallel result: {result2:04b} = {[int(b) for b in f'{result2:04b}']}")
print(f"Expected: [1, 0, 1, 1]")

Choosing an Implementation

Real-World SEC Applications

Single error correction via Hamming codes is deployed in numerous critical systems where reliability is paramount.

ECC Memory (DRAM)

Modern servers use ECC DIMMs that protect each 64-bit data word:

64 data bits + 8 check bits = 72-bit codeword
Hamming-based SECDED (covered next page) protects against single-bit errors
Error logging tracks soft errors (cosmic rays, alpha particles)
Typical soft error rate: ~1 error per 10^12 bit-hours
Without ECC, a 64GB server might see ~1 error per week

Flash Memory Controllers

NAND flash has inherent error rates that Hamming codes address:

Early flash: 1-bit ECC per 512 bytes was sufficient
Modern MLC/TLC flash: Requires BCH/LDPC codes (stronger than Hamming)
Hamming still used for metadata and page headers

SEC Applications by Domain

•Data Centers — ECC memory in all server-class systems; protects against cosmic ray-induced soft errors
•Aerospace — Radiation-hardened systems use enhanced Hamming codes for mission-critical data
•Automotive — Safety-critical ECUs require ECC for functional safety certification (ISO 26262)
•Medical Devices — Implantable devices use Hamming codes for telemetry reliability
•Industrial Control — PLCs and safety controllers protect memory against electrical noise
•Consumer Electronics — Some high-end routers and NAS devices offer ECC memory options

SEC Deployment Examples
System	Codeword Size	Protection Level	Error Rate Context
DDR4 ECC DIMM	72 bits (64+8)	SEC-DED	~10^-12 BER
Intel CPU Cache	45-bit codes	SEC-DED	~10^-15 BER
Space Systems	16-32 bit codes	SEC + scrubbing	~10^-6 BER (radiation)
Network ASICs	Custom codes	SEC or parity	~10^-12 BER

Silent Protection

Summary: Single Error Correction

We have thoroughly examined single error correction—the core capability that makes Hamming codes valuable in practice. Let's consolidate the key takeaways:

Key Takeaways

•SEC is guaranteed for single-bit errors — Mathematical certainty, not probability
•The workflow is: syndrome → locate → flip → extract — Simple, fast, reliable
•Check bit errors don't affect data — Power-of-two syndromes indicate recoverable situations
•Two-bit errors cause miscorrection — Fundamental limitation of basic Hamming codes
•Performance is excellent — O(n) time, O(log n) hardware latency
•Real-world deployment is ubiquitous — ECC memory, flash controllers, safety-critical systems

What's Next:

Page Complete

4 / 5