Examples for Hamming code:

Examples for Hamming code:
The message you want to send is 4-bits string:

0000	0001	0010	0011
0100	0101	0110	0111
1000	1001	1010	1011
1100	1101	1110	1111

There is 16 different messages.
The 4-bits messages are mapped to the following Sixteen Valid Codewords

0	0 0 0 0 0 0 0	8	1 0 0 1 0 1 1
1	0 0 0 0 1 1 1	9	1 0 0 1 1 0 0
2	0 0 1 1 0 0 1	A	1 0 1 0 0 1 0
3	0 0 1 1 1 1 0	B	1 0 1 0 1 0 1
4	0 1 0 1 0 1 0	C	1 1 0 0 0 0 1
5	0 1 0 1 1 0 1	D	1 1 0 0 1 1 0
6	0 1 1 0 0 1 1	E	1 1 1 1 0 0 0
7	0 1 1 0 1 0 0	F	1 1 1 1 1 1 1

The Hamming Code essentially defines 16 valid codewords. The sixteen words are arranged such that the minimum distance between any two words is 3.

Check the hamming equation:

M=4, R=3, N=7

Left side: (M+R+1)*(2^M)=8*16=128

Right side: 2^N=128

Perfect match!

Exercise 1:  Calculate the Hamming distance between any two codewords in the above table.

The send will only send one of these 16 valid codewords. For example, the send will never send 0000001, which is not a valid codeword.

Due to the transmission error, the receiver might receive invalid codewords. Since the code transmitted is 7-bit long, total amount of possible codes is 128.

When received a code, the receiver will look for the closest valid codeword as a guess for what might be actually transmitted.

Decoding at the Receiver Side

For example: if the sender send m=0000000, and the last bit is inverted due to transmission error, the receiver received r=0000001. The receiver will calculate the Hamming distance between r and all valid codewords. The codeword with the smallest Hamming distance will be the one.

In fact, the table of D(0000001, x) is

Code word	D(r,)	Code word	D(r,)
0 0 0 0 0 0 0	1	1 0 0 1 0 1 1	3
0 0 0 0 1 1 1	2	1 0 0 1 1 0 0	4
0 0 1 1 0 0 1	2	1 0 1 0 0 1 0	4
0 0 1 1 1 1 0	5	1 0 1 0 1 0 1	3
0 1 0 1 0 1 0	4	1 1 0 0 0 0 1	2
0 1 0 1 1 0 1	3	1 1 0 0 1 1 0	5
0 1 1 0 0 1 1	3	1 1 1 1 0 0 0	5
0 1 1 0 1 0 0	4	1 1 1 1 1 1 1	6

Thus the receiver conclude that the actual transmitted code is 0000000, which is the correct.
Exercise 2:  Check that when 0000000 is sent, any 1 bit error can be corrected by above procedure.
The receiver actually might be implemented with a working sheet:

Received codes	After decoding	Received codes	After decoding
0000000,0000001,0000010 0000100,0001000,0010000 0100000,1000000	0 0 0 0 0 0 0		1 0 0 1 0 1 1
0000111,0000110,0000101 0000011,0001111,0010111 0100111,1000111	0 0 0 0 1 1 1		1 0 0 1 1 0 0
0011001,0011000,0011011 0011101, 0010001,0001001, 0111001, 1011001	0 0 1 1 0 0 1		1 0 1 0 0 1 0
0011110, 0011111, 0011100, 0011010, 0010110, 0001110, 0111110, 1011110,	0 0 1 1 1 1 0		1 0 1 0 1 0 1
0101010, 0101011,0101000 0101110, 0100010, 0111010 0001010, 1101010	0 1 0 1 0 1 0		1 1 0 0 0 0 1
0101101, 0101100, 0101111 0101001, 0100101, 0111101 0001101, 1101101	0 1 0 1 1 0 1		1 1 0 0 1 1 0
0110011, 0110010, 0110001 0110111, 0111011, 0100011 000011, 110011	0 1 1 0 0 1 1		1 1 1 1 0 0 0
0110100,110101, 0110110, 0110000, 0111100, 0100100, 000100, 110100	0 1 1 0 1 0 0		1 1 1 1 1 1 1

The right half of the table will be left as an exercise.