Hamming Code (1 bit error correction)

Achieves the theoretical limit for minimum number of check bits to do 1-bit error-correction.

Bits of codeword are numbered: bit 1, bit 2, ..., bit n.
Check bits are inserted at positions 1,2,4,8,.. (all powers of 2).
The rest are the m data bits.

Each check bit checks (as parity bit) a number of data bits.
Each check bit checks a different collection of data bits.
Check bits only check data, not other check bits.

Hamming Codes used in:

Wireless comms, e.g. Fixed wireless broadband. High error rate. Need correction not detection.

Any number can be written as sum of powers of 2

First note every number can be written in base 2 as a sum of powers of 2 multiplied by 0 or 1.
i.e. As a simple sum of powers of 2.

Number is sum of these:         1       2       4       8       16

Number:
1                               x
2                                       x
3                               x       x
4                                               x
5                               x               x
6                                       x       x
7                               x       x       x
8                                                       x
9                               x                       x
10                                      x               x
11                              x       x               x
12                                              x       x
13                              x               x       x
14                                      x       x       x
15                              x       x       x       x
16                                                              x
17                              x                               x
18                                      x                       x
19                              x       x                       x
20                                              x               x
21                              x               x               x
22                                      x       x               x
23                              x       x       x               x
24                                                      x       x
25                              x                       x       x
26                                      x               x       x
27                              x       x               x       x
28                                              x       x       x
29                              x               x       x       x
30                                      x       x       x       x
31                              x       x       x       x       x
...

Scheme for check bits

Now here is our scheme for which bits each check bit checks:

Checked by check bit:           1       2       4       8       16

Bit:
1 (not applicable - this is a check bit)                                
2 (n/a)
3                               x       x
4 (n/a)
5                               x               x
6                                       x       x
7                               x       x       x
8 (n/a)
9                               x                       x
10                                      x               x
11                              x       x               x
12                                              x       x
13                              x               x       x
14                                      x       x       x
15                              x       x       x       x
16 (n/a)
17                              x                               x
18                                      x                       x
19                              x       x                       x
20                                              x               x
21                              x               x               x
22                                      x       x               x
23                              x       x       x               x
24                                                      x       x
25                              x                       x       x
26                                      x               x       x
27                              x       x               x       x
28                                              x       x       x
29                              x               x       x       x
30                                      x       x       x       x
31                              x       x       x       x       x
32 (n/a)        
...

Check bit records odd or even parity of all the bits it covers, so any one-bit error in the data will lead to error in the check bit.

Assume one-bit error:
If any data bit bad, then multiple check bits will be bad (never just one check bit).

Calculating the Hamming Code (check bits do even parity here)

How it works

21 (as sum of powers of 2) = 1 + 4 + 16
Bit 21 is checked by check bits 1, 4 and 16.
No other bit is checked by exactly these 3 check bits.
If assume one-bit error, then if exactly these 3 check bits are bad, then we know that data bit 21 was bad and no other.

Assume one-bit error:

Error in a data bit:
Will cause multiple errors in check bits. Will cause errors in exactly the check bits that correspond to the powers of 2 that the bit number can be written as a sum of.
Error in a check bit:
Will affect nothing except that check bit. i.e. One bad check bit (not multiple bad check bits as above).

Hamming Code example for 3-bit data

Consider standard encoding of numbers 0 to 7:

(bits 1 to 3).

Encode this such that a 1 bit error can be detected and corrected.

Add check bits:


cc0c00
cc0c01
cc0c10
cc0c11
cc1c00
cc1c01
cc1c10
cc1c11

(now have bits 1 to 6).

Check bit 1 looks at bits 3 5.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.


0c0c00
0c0c01
1c0c10
1c0c11
1c1c00	(flip previous 4 bits)
1c1c01
0c1c10
0c1c11

Check bit 2 looks at bits 3 6.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.


000c00
010c01
100c10
110c11
111c00	(flip previous 4 bits)
101c01
011c10
001c11

Check bit 4 looks at bits 5 6.
If the number of 1s is 0 or even, set check bit to 0.
If the number of 1s is 1 or odd, set check bit to 1.

Error detection:


Distance from pattern:  0       1       2       3       4       5       6       7

Pattern:
0       000000          -       3       3       4       3       4       4       3
1       010101          3       -       4       3       4       3       3       4
2       100110          3       4       -       3       4       3       3       4
3       110011          4       3       3       -       3       4       4       3
4       111000          3       4       4       3       -       3       3       4
5       101101          4       3       3       4       3       -       4       3
6       011110          4       3       3       4       3       4       -       3
7       001011          3       4       4       3       4       3       3       -

Minimum distance 3.
If assume only 1 bit error, can always tell which pattern nearest.

Error correction:

List all patterns and find nearest one? Computationally expensive. Especially with longer strings (much more patterns).

With Hamming, can find nearest quickly by just looking at one pattern:

Let's say error in a data bit:
100 sent
111000
became: 111001
i.e. data 101, but check bits wrong
Check bit 1 - 1 - checks bits 3,5 - 1 0 - OK
Check bit 2 - 1 - checks bits 3,6 - 1 1 - WRONG
Check bit 4 - 0 - checks bits 5,6 - 0 1 - WRONG
The bad bit is bit 2 + 4 = bit 6. Data was corrupted. Data should be 100.
Let's say error in a check bit:
100 sent
111000
became: 011000
i.e. data 100, but check bits wrong
Check bit 1 - 0 - checks bits 3,5 - 1 0 - WRONG
Check bit 2 - 1 - checks bits 3,6 - 1 0 - OK
Check bit 4 - 0 - checks bits 5,6 - 0 0 - OK
The bad bit is bit 1. Check bit was corrupted. Data is fine.

Summary

If assume 1-bit error:

If 1 check bit bad:
Data is good, check bit itself got corrupted.
Ignore check bits. Data is good.
If more than 1 check bit bad:
Data in error (single-bit error in data). Which check bits are bad shows you exactly where the data error was. They point to a unique bit which is the bit in error.
Can reconstruct data.

i.e. If 1 bit error - can always tell what original pattern was.
This, by the way, proves that distance between two patterns must be at least 3.
Q. Any other way of proving distance >= 3?

Digital Communications course by Richard Tervo
- Intro to Hamming codes
- CGI script for Hamming codes

Q. Show that Hamming code actually achieves the theoretical limit for minimum number of check bits to do 1-bit error-correction.

Example

Hamming code to correct burst errors

Basic Hamming code above corrects 1-bit errors only.
Trick to use it to correct burst errors:

Consider sending k codewords, each length n.
Arrange in matrix (as in diagram), each row is a codeword.
Matrix width n, height k.
Normally would transmit this row-by-row.
Trick: Transmit column-by-column.

If a burst of length k occurs in the entire k x n block (and no other errors) at most 1 bit is affected in each codeword.
So the Hamming code can reconstruct each codeword.
So the Hamming code can reconstruct the whole block.

Yellow is burst error.

Uses kr check bits to make blocks of km data bits immune to a single burst error of up to length k.