posts/

# An Efficient Algorithm for Hamming (7,4) Decoding

The Matlab implementation of this algorithm is here:

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 just 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 in Matlab)

`````` 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  | Not Applicable
``````

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

Notice how the values of S and D are same, except at a few places.

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

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

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
~~~~~~

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)';

output
~~~~~~

1   1   1   0   1   1   0   0
1   1   0   1   1   0   1   0

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

Tags this post has been filed under: