Dr. Mark Humphrys School of Computing. Dublin City University. coders   JavaScript worlds Search:

# 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).

```
```

# 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:

1. 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.

2. 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:
```000
001
010
011
100
101
110
111
```
(bits 1 to 3).

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

```
```
```
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.

```
000000
010101
100110
110011
111000
101101
011110
001011

```
```
```

```
```

### 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:

```
```
1. 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.

```
```
2. 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:
1. If 1 check bit bad:
Data is good, check bit itself got corrupted.
Ignore check bits. Data is good.

2. 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?
```
```
```
```

```
```

# 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.
```
```
```
```
ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Note: Links on this site to user-generated content like Wikipedia are highlighted in red as possibly unreliable. My view is that such links are highly useful but flawed.