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)%2will 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
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