# An efficient algorithm for Hamming(7,4) decoding and a MATLAB implementation.

This is an explanation for the algorithm I presented in https://aravindvoggu.in/hamming

Hamming(7,4) encodes 4 bits of data into 7 bits and can recover from 1 bit errors. So we encode 4 data bits `[d1, d2, d3, d4]`

to `[p1, p2, p3, d1, d2, d3, d4]`

Let's define parity bits as

```
p1 = d2 + d3 + d4
p2 = d1 + d3 + d4
p3 = d1 + d2 + d4
```

To detect errors, we exploit the property of binary bits that, for any binary bit `k`

, `(k + k)%2`

**will** be 0.

```
if k = 0,
(k + k) = 0 + 0 = 0
mod(0, 2) = 0
else if k = 1,
(k + k) = 1 + 1 = 2,
mod(0, 2) = 0
```

so, `p1 + (d2 + d3 + d4)`

is `p1 + p1`

and will be 0, unless one of the bits got inverted.

If we do the same calculation for all parity bits on the reciever side.

```
s1 = ( p1 + (d2 + d3 + d4) )%2
s2 = ( p2 + (d1 + d3 + d4) )%2
s3 = ( p3 + (d1 + d2 + d4) )%2
```

Here's a table showing combinations of s1, s2, s3 pointing to error in specific bits.

S1 | S2 | S3 | Wrong bit |
---|---|---|---|

0 | 1 | 1 | d1 |

1 | 0 | 1 | d2 |

1 | 1 | 0 | d3 |

1 | 1 | 1 | d4 |

1 | 0 | 0 | p1 |

0 | 1 | 0 | p2 |

0 | 0 | 1 | p3 |

0 | 0 | 0 | No error |

By looking at the values of s1, s2, s3, we can identify the wrong bit, and correct it by flipping it; 'cause this is Binary.

That's the theory. Now let's see how we implement encoding and decoding in the algorithm.

## Encoding

Assume that the number of bits you have is a multiple of 4. Say `4n`

. Since data is usually bytes, and a byte is 8 bits, this is true more often that not. If not, just pad your data.

`[d1, d2, d3, d4, d5, ...... d(4n - 1), d(4n)]`

First, we window the bits into a matrix of size `nX4`

. Like so

```
[
d1, d2, d3, d4,
d5, d6, d7, d8,
.
.
.
d(4n-3), d(4n-2), d(4n-1), d(4n)
]
```

Now we can encode all of them by multiplying it with the generator matrix. For example, look what happens when only 4 bits are there.

```
data = [d1 d2 d3 d4]
|0 1 1 1 0 0 0|
encoded_data = [d1 d2 d3 d4] * |1 0 1 0 1 0 0|
|1 1 0 0 0 1 0|
|1 1 1 0 0 0 1|
```

We can multiply all the 4-bit-windows in parallel with generator matrix.

After multiplying the matrices of size `nX4`

and `4X7`

, we have a resultant matrix of size `nX7`

. This is the encoded matrix

#### Example

Let's encode bits. This is the easy part. Follow along with a paper if that helps.

```
1 1 0 0
1 0 1 0
```

```
function [output_vector] = sevenFourHammingEncode(input_vector)
output_vector = [];
number_of_windows = length(input_vector) / 4; % assumes length to be multiple of four
four_bit_windows = reshape(input_vector, 4, number_of_windows)';
% p1 p2 p3 d1 d2 d3 d4
generator_matrix = [
0 1 1 1 0 0 0 ;
1 0 1 0 1 0 0 ;
1 1 0 0 0 1 0 ;
1 1 1 0 0 0 1 ;
];
output_vector = mod(four_bit_windows * generator_matrix, 2);
output_vector = reshape(output_vector', numel(output_vector), 1)';
end
inputArray = [1, 1, 0, 0, 1, 0, 1, 0]
encodedArray = sevenFourHammingEncode(inputArray)
```

The output would be

```
inputArray =
1 1 0 0 1 0 1 0
number_of_windows = 2
four_bit_windows =
1 1 0 0
1 0 1 0
generator_matrix =
0 1 1 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1
output_vector =
1 1 0 1 1 0 0
1 0 1 1 0 1 0
output_vector =
1 1 0 1 1 0 0 1 0 1 1 0 1 0
encodedArray =
1 1 0 1 1 0 0 1 0 1 1 0 1 0
```

Now let's move on to decoding.

## Decoding

Let's invert some bits to simulate noise. Inverting 4th bit on both the encoded bits.

So,

```
output_vector =
1 1 0 1 1 0 0
1 0 1 1 0 1 0
^
```

becomes

```
output_vector =
1 1 0 0 1 0 0
1 0 1 0 0 1 0
^
```

We do this with

```
encodedArray = sevenFourHammingEncode(inputArray);
flippedBits = [4, 11];
encodedArray(flippedBits) = not(encodedArray(flippedBits))
```

Okay, let's decode and try to fix the errors now.

Window the input into 7-bit-windows again.

```
number_of_windows = numel(input_vector) / 7
seven_bit_windows = reshape(input_vector, 7, number_of_windows)'
Output
~~~~~~~
number_of_windows = 2
seven_bit_windows =
1 1 0 0 1 0 0
1 0 1 0 0 1 0
```

Now we can calculate S1, S2, S3 with a decoder matrix.

```
decoder_matrix = [
1 0 0 0 1 1 1 ;
0 1 0 1 0 1 1 ;
0 0 1 1 1 0 1 ;
];
result_vector = mod(decoder_matrix * seven_bit_windows', 2)';
result
~~~~~~
decoder_matrix =
1 0 0 0 1 1 1
0 1 0 1 0 1 1
0 0 1 1 1 0 1
result_vector =
0 1 1
0 1 1
```

As we know that different combinations of s1,s2,s3 mean errors in different places, let's find out where the errors are.

Calculate `S = (S1*4 + S1*2 + S1*1)`

. This is basically converting `s1s2s3`

from binary to decimal.

S1 | S2 | S3 | S | Wrong bit |
---|---|---|---|---|

0 | 1 | 1 | 3 | d1 |

1 | 0 | 1 | 5 | d2 |

1 | 1 | 0 | 6 | d3 |

1 | 1 | 1 | 7 | d4 |

1 | 0 | 0 | 4 | p1 |

0 | 1 | 0 | 2 | p2 |

0 | 0 | 1 | 1 | p3 |

0 | 0 | 0 | 0 | No error |

The index of the wrong bit in the window is D. (indexes start from 1)

S1 | S2 | S3 | S | Wrong bit | D |
---|---|---|---|---|---|

0 | 1 | 1 | 3 | d1 | 4 |

1 | 0 | 1 | 5 | d2 | 5 |

1 | 1 | 0 | 6 | d3 | 6 |

1 | 1 | 1 | 7 | d4 | 7 |

1 | 0 | 0 | 4 | p1 | 1 |

0 | 1 | 0 | 2 | p2 | 2 |

0 | 0 | 1 | 1 | p3 | 3 |

0 | 0 | 0 | 0 | No error | NA |

The values of S are stored in result_vector in the program.

If we replace S=3 with 4, and S=4 with 1, and S=1 with 3, then result_vector would contain the indices where bit error occured in each window.

**But**, if we if S(S=3) = 4, and then did S(S=4) = 1 for this, along with original S=4, even the ones we mapped from 3->4 would also be converted.

So, instead of 3->4, let's map 3->(8+4), and do mod by 8 at the end. Similarly for the other two mappings.

The number 8 was selected because we can have numbers 0 to 7 in S.

When we do mod with 8, only numbers greater than 8 would be affected. So we would only be changing the numbers we intended to map.

We do all that with these lines

```
result_vector = result_vector * [4 ; 2 ; 1] % summing all elements
result_vector(result_vector == 4) = 9
result_vector(result_vector == 1) = 11
result_vector(result_vector == 3) = 12
result_vector = mod(result_vector, 8)
~~~~~
The contents of result_vector before this are:
result_vector =
0 1 1
0 1 1
Output
~~~~~~
result_vector =
3
3
result_vector =
3
3
result_vector =
3
3
result_vector =
12
12
result_vector =
4
4
```

Good, now we have the index that needs to be flipped in result_vector.

**But**, there's a catch. When there are no bit-flips, the value of result_vector would be 0. And 0 is not a valid index in Matlab.

For this, pad the seven_bit_window with a column of 1s on the left. We're gonna remove this column later, so changes made to this won't matter.

Now, let's increment all the values in result_vector. So 0 becomes 1, and 1 becomes 2, etc.

Now, when there is no error, the 1st bit of the padded seven_bit_window is altered. That's fine, because we're gonna get rid of the padding.

If there's an error, since we padded seven_bit_window and incremented, result_vector, the bit that got corrupted will be correctly flipped.

Okay, now to actually implement it, convert the padded_seven_bit_windows to 1 a row vector again. The dimensions of this would be 1X8n.

Now, the indexes of wrong bits in this form of padded_seven_bit_windows would be (0 + 4), and (8 + 4), right?

Let's convert result_vector to that form. Btw, I'm calling padded_seven_bit_windows, padded_data in this code.

```
seven_bit_windows = [ones(size(seven_bit_windows, 1), 1) seven_bit_windows]; % adding 1 column at start
padded_data = reshape(seven_bit_windows', numel(seven_bit_windows), 1)';
result_vector = [(0:8:rows(result_vector)*8-1)' result_vector];
result_vector = result_vector * [1 ; 1] % summing row and column to add that offset of 8
output
~~~~~~
seven_bit_windows =
1 1 1 0 0 1 0 0
1 1 0 1 0 0 1 0
padded_data =
1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0
^ ^
result_vector =
0 4
8 4
result_vector =
4
12
```

Now we have the padded data as a row vector, and the (indices of wrong bits - 1) in result_vector. Let's increment the result_vector and flip corresponding to it's indices.

```
padded_data(result_vector' + 1) = not(padded_data(result_vector' + 1));
output
~~~~~~
padded_data =
1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0
^ ^
```

Now let's remove the padding we added and output only the corrected bits.

```
padded_data = reshape(padded_data, 8, numel(padded_data) / 8)';
padded_data = padded_data(:, 5:end);
output
~~~~~~
padded_data =
1 1 1 0 1 1 0 0
1 1 0 1 1 0 1 0
padded_data =
1 1 0 0
1 0 1 0
```

Converting this back to row vector to return.

```
output_vector = reshape(padded_data', numel(padded_data), 1)';
output
~~~~~~
output_vector =
1 1 0 0 1 0 1 0
```

These are the bits we encoded. For a MATLAB implementation of the algorithm, see here: https://aravindvoggu.in/hamming/