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/