Transmission error can be caused by noisy communication channel such as scratches on a CD, static on a cell phone, or atmospheric interference. Therefore, there is a need to detect and recover the original message from the corrupted data. One method to detect and correct error is by using Hamming code that was invented by Richard Hamming in 1950. It make use the concept of additional bit called parity. In this page you will learn how to get the formula for 4, 8 and 16 bit Hamming data transmission. Based on the formula, you will see how Hamming can detect and correct error. Though only 4, 8, and 16 bit Hamming is shown, the same concept applies to others.
- 4-bit Data Transmission using Hamming
- 8-bit Data Transmission using Hamming
- 16-bit Data Transmission using Hamming
4-bit Data Transmission using Hamming
The number of parity bit depends on the number of data to be transmitted. The parity bit is inserted at each 2^n location which will make a 4-bit data (i.e. D3,D2,D1,D0) transmission will need 3 parity bit (i.e. at P1, P2, P4)
 |
| 4-bit data with 3 parity bit produce 7 bit number |
This will total up the data transmission to 7 bit. Every 3 bit parity is used to detect group of bit. Every parity bit is for themselves and has bit ‘1’ on certain position bit.
C1 = xx1 (001,011,101,111) = {1,3,5,7}
C2 = x1x (010,011,110,111) = {2,3,6,7}
C4 = 1xx (100,101,110,111) = {4,5,6,7}
Omitting the 2^n number, therefore:
P1 = parity for bit {3,5,7}
P2 = parity for bit {3,6,7}
P4 = parity for bit {5,6,7}
Example: Given a 4-bit number "1100" and assume even parity bit, show how Hamming Code is able to detect and correct the data if the receiver received "1000".
Answer: Arrange the "1100" as below
The question assume even parity, therefore all the the three parity bit and the answer (all together 4 bit) should be even. Another method is by using XOR to the three parity bit.
P1 = parity for bit {3,5,7} = parity for bit {D3,D2,D0}= 1 XOR 1 XOR 0 = 0
P2 = parity for bit {3,6,7}= parity for bit {D3,D1,D0}= 1 XOR 0 XOR 0 = 1
P4 = parity for bit {5,6,7}= parity for bit {D2,D1,D0}= 1 XOR 0 XOR 0 = 1
Put the answer for P1, P2, P4 at their respected location as below:
To check error, execute checking code
C1= XOR {1,3,5,7} = XOR{P1,D3,D2,D0}= 0 XOR 1 XOR 1 XOR 0 = 0
C2= XOR {2,3,6,7} = XOR{P2,D3,D1,D0}= 1 XOR 1 XOR 0 XOR 0 = 0
C4= XOR {4,5,6,7} = XOR{P4,D2,D1,D0}= 1 XOR 1 XOR 0 XOR 0 = 0
C4 C2 C1=000 therefore no error.
Now try to check what happen when data received is "1000"
C1= XOR {1,3,5,7} = XOR{P1,D3,D2,D0}= 0 XOR 1 XOR 0 XOR 0 = 1
C2= XOR {2,3,6,7} = XOR{P2,D3,D1,D0}= 1 XOR 1 XOR 0 XOR 0 = 0
C4= XOR {4,5,6,7} = XOR{P4,D2,D1,D0}= 1 XOR 0 XOR 0 XOR 0 = 1
C4 C2 C1 = 101 which detect the error at location number 5.
The number of parity bit depends on the number of data to be transmitted. The parity bit is inserted at each 2^n location which will make an 8-bit data (i.e. D7,D6....,D1,D0) transmission will need 4 parity bit (i.e. at P1, P2, P4, P8)
This will total up the data transmission to 12 bit. Every 4 bit parity is used to detect group of bit. Every parity bit is for themselves and has bit ‘1’ on certain position bit.
 |
| 8-bit data with 4 parity bit produce 12 bit number |
This will total up the data transmission to 12 bit. Every 4 bit parity is used to detect group of bit. Every parity bit is for themselves and has bit ‘1’ on certain position bit.
C1 = xxx1 (0001,0011,0101,0111, 1001, 1011,
C2 = xx1x (0010,0011,0110,0111,1010,1011,
C4 = x1xx (0100,0101,0110,0111,1100,1101,1110,1111) = {4,5,6,7,12,13,14,15}
C8 = 1xxx (1000,1001,1010,1011,1100,1101,1110,1111) = {8,9,10,11,12,13,14,15}
C8 = 1xxx (1000,1001,1010,1011,1100,
Note that the number above 12 will be removed (i.e. strike-through).
Omitting the 2^n number, therefore:
P1 = parity for bit {3,5,7,9,11}
P2 = parity for bit {3,6,7,10,11}
P4 = parity for bit {5,6,7,12}
P8 = parity for bit {9,10,11,12}
P8 = parity for bit {9,10,11,12}
Example: Given an 8-bit number "11001011" and assume even parity bit, show how Hamming Code is able to detect and correct the data if the receiver received "1001011".
Answer: Arrange the "11001011" as below
P1 = parity for bit {3,5,7,9,11} = parity for bit {D7,D6,D4,D3,D1} = XOR(1,1,0,1,1) = 0
P2 = parity for bit {3,6,7,10,11} = parity for bit {D7,D5,D4,D2,D1} = XOR(1,0,0,0,1) = 0
P4 = parity for bit {5,6,7,12}= parity for bit {D6,D5,D4,D0} = XOR(1,0,0,1) = 0
P8 = parity for bit {9,10,11,12}= parity for bit {D3,D2,D1,D0} = XOR(1,0,1,1) = 1
P8 = parity for bit {9,10,11,12}= parity for bit {D3,D2,D1,D0} = XOR(1,0,1,1) = 1
To check error, execute checking code
C1 = XOR{1,3,5,7,9,11} = XOR{P1,D7,D6,D4,D3,D1} = XOR(0,1,1,0,1,1) = 0
C2 = XOR{2,3,6,7,10,11} = XOR{P2,D7,D5,D4,D2,D1} = XOR(0,1,0,0,0,1) = 0
C4 = XOR{4,5,6,7,12} = XOR{P4,D6,D5,D4,D0} = XOR(0,1,0,0,1) = 0
C8 = XOR{8,9,10,11,12} = XOR{P8,D3,D2,D1,D0} = XOR(1,1,0,1,1) = 0
C8 = XOR{8,9,10,11,12} = XOR{P8,D3,D2,D1,D0} = XOR(1,1,0,1,1) = 0
Now try to check what happen when data received is "1001011"
C2 = XOR{2,3,6,7,10,11} = XOR{P2,D7,D5,D4,D2,D1} = XOR(0,1,0,0,0,1) = 0
C4 = XOR{4,5,6,7,12} = XOR{P4,D6,D5,D4,D0} = XOR(0,0,0,0,1) = 1
C8 = XOR{8,9,10,11,12} = XOR{P8,D3,D2,D1,D0} = XOR(1,1,0,1,1) = 0
C8 = XOR{8,9,10,11,12} = XOR{P8,D3,D2,D1,D0} = XOR(1,1,0,1,1) = 0
The number of parity bit depends on the number of data to be transmitted. The parity bit is inserted at each 2^n location which will make a 16-bit data (i.e. D15,D6....,D1,D0) transmission will need 5 parity bit (i.e. at P1, P2, P4, P8,P15)
 |
| 16-bit data with 5 parity bit produce 21 bit number |
This will total up the data transmission to 21 bit. Every 5 bit parity is used to detect group of bit. Every parity bit is for themselves and has bit ‘1’ on certain position bit.
C1 = xxxx1
= (00001,00011,00101,00111,01001,01011,01101,01111,
10001,10011,10101,10111,11001,11011,11101, 11111)
= {1,3,5,7,9,11,13,15, 17,19,21,23,25,27,29,31}
C2 = xxx1x
= (00010,00011,00110,00111,01010,01011,01110, 01111,
10010,10011,10110,10111,11010,11011,11110, 11111)
= {2,3,6,7,10,11,14,15, 18,19,22,23,26,27,30,31}
C4 = xx1xx= (00100,00101,00110,00111,01100,01101,01110, 01111,
10100,10101,
= {4,5,6,7,12,13,14,15, 20,21,
C8 = x1xxx
= (01000,01001,01010,01011,01100,01101,01110, 01111,
= {8,9,10,11,12,13,14,15, 24,25,26,27,28,29,30,31}
C16= 1xxxx
= (10000,10001,10010,10011,10100,10101,10110, 10111,
11000,11001,11010,11011,11100,11101,11110, 11111)
C16= 1xxxx
= (10000,10001,10010,10011,10100,10101,
= {16,17,18,19,20,21,22,23, 24,25,26,27,28,29,30,31}
Note that the number above 21 will be removed (i.e. strike-through).
Omitting the 2^n number, therefore:
P1 = parity for bit {3,5,7,9,11,13,15, 17,19,21}
P2 = parity for bit {3,6,7,10,11,14,15, 18,19}P4 = parity for bit {5,6,7,12,13,14,15, 20,21}
P8 = parity for bit {9,10,11,12,13,14,15}
P16 = parity for bit {17,18,19,20,21}
Example: Given a 16-bit number "1110 0100 1011 0010" and assume even parity bit, show how Hamming Code is able to detect and correct the data if the receiver received "1110 0100 1011 1010".
Answer: Arrange the "1110 0100 1011 0010" as below
The question assume even parity, therefore all the the five parity bit and the answer (all together 6 bit) should be even. Another method is by using XOR to the five parity bit.
P1 = parity for bit {3,5,7,9,11,13,15, 17,19,21} = XOR(1,1,0,0,0,1,1,1,0,0) = 1
P2 = parity for bit {3,6,7,10,11,14,15, 18,19} = XOR(1,1,0,1,0,0,1,1,0) = 1
P4 = parity for bit {5,6,7,12,13,14,15, 20,21} = XOR(1,1,0,0,1,0,1,1,0) = 1
P8 = parity for bit {9,10,11,12,13,14,15} = XOR(0,1,0,0,1,0,1) = 1
P16 = parity for bit {17,18,19,20,21} = XOR(1,0,0,1,0) = 0
Put the answer for P1, P2, P4, P8, P16 at their respected location as below:
To check error, execute checking code
C1 = XOR{1,3,5,7,9,11,13,15, 17,19,21} = XOR(1,1,1,0,0,0,1,1,1,0,0) = 0
C2 = XOR{2,3,6,7,10,11,14,15, 18,19} = XOR(1,1,1,0,1,0,0,1,1,0) = 0C4 = XOR{4,5,6,7,12,13,14,15, 20,21} = XOR(1,1,1,0,0,1,0,1,1,0) = 0
C8 = XOR{8,9,10,11,12,13,14,15} = XOR(1,0,1,0,0,1,0,1) = 0
C16 = XOR{16,17,18,19,20,21} = XOR(0,1,0,0,1,0) = 0
C16 C8 C4 C2 C1=00000 therefore no error.
Now try to check what happen when data received is "1110 0100 1011 1010"
C1 = XOR{1,3,5,7,9,11,13,15, 17,19,21} = XOR(1,1,1,0,0,0,1,1,1,0,0) = 0
C4 = XOR{4,5,6,7,12,13,14,15, 20,21} = XOR(1,1,1,0,0,1,0,1,1,0) = 0
C8 = XOR{8,9,10,11,12,13,14,15} = XOR(1,0,1,0,0,1,0,1) = 0
C16 = XOR{16,17,18,19,20,21} = XOR(0,1,1,0,1,0) = 1
C16 C8 C4 C2 C1 = 10010 which detect the error at location number 18.
No comments:
Post a Comment