Error correction

Hamming Code
Hamming code
• detect and correct the errors using redundant bits

• Redundant bits are the extra binary bits that are added to the original
data bits,
• Let m be the number of bits in a message
• Let r be the number of redundant bits
• Then the total message size=m+r

r bits m bits
CODEWORD
Hamming Distance
• Let data send from sender is 10001001 but
• Data received is 10110001
• To find the bit changes do XOR

• The number of bit positions in which two code words differ is called the
Hamming distance
• if the Hamming distance between two code words is d, you would need
exactly d single-bit errors to transform one code word into the other.
• Let's consider an example:Code word 1: 1011101
• Code word 2: 1001001

• 2nd bit and 4th bit are different

• So the hamming distance is 2
• Bit Flips Needed to make them equal is 2
• Change the 2nd bit of 1011101 from 1 to 0.
• Change the 4th bit of 1011101 from 1 to 0.

• In summary, the number of single-bit errors needed to transform one

codeword into another is equal to their Hamming distance.
Selection of number of redundant bits
r
• 2 ≥m+r+1
• Find the minimum value that you can substitute for r if m=7 so that
r
2 ≥ m + r + 1 is true
• Substitute r=1 or 2 or 3 or 4

• R=4
 r
• 2 ≥m+r+1
• Find the minimum value that you can substitute for r if m=4 so that
r
2 ≥ m + r + 1 is true
• Substitute r=1 or 2 or 3 or 4

• R=3
• So if the message size is 7 bits , you need to place 4 redundant
bits/parity bits
• If message size is 3 bits , we need 3 parity/redundant bits
Determining position of parity bits:
• Parity bits are placed at the bit position which is the power of 2
• 1st, 2nd, 4th, 8th ETC…..
 Error Correction
Single bit Error Correction using Hamming code
Calculating the Hamming Code
The key to the Hamming Code is the use of extra parity bits to
allow the identification of a single error.
• Creating the code word is as follows:
✔ Mark all bit positions that are powers of two as parity bits.
(positions 1, 2, 4, 8, 16, 32, 64, etc.)
✔ All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7,
9, 10, 11, 12, 13, 14, 15, 17, etc.)
✔ Each parity bit calculates the parity for some of the bits in the code word.

9
 Error Correction
✔ The position of the parity bit determines the sequence of bits that it alternately checks and
skips.

Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc.
(1,3,5,7,9,11,13,15,...)
Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc.
(2,3,6,7,10,11,14,15,...)
Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc.
(4,5,6,7,12,13,14,15,20,21,22,23,...)
Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc.
(8-15,24-31,40-47,...)

✔ Set a parity bit to 1 if the total number of ones in the positions it

checks is odd.
✔ Set a parity bit to 0 if the total number of ones in the positio73ns it checks is even.
 Calculation of Parity Bits:
• Each parity bit checks the parity of certain bits in the code word
• Parity bit at position 1 checks positions 1, 3, 5, 7, 9, etc.
• Parity bit at position 2 checks positions 2, 3, 6, 7, 10, 11 etc.
• Parity bit at position 4 checks positions 4, 5, 6, 7, 12,13,14,15 etc.
• Parity P1 depends on the data bit D3,D5,D7,D9….(Check one ,skip
one)

• Parity P2 depends on the data bit D3,D6,D7,D10,D11.. (Check two

,skip two)

• Parity P4 depends on the data bit D5,D6,D7,D12,D13,D14,D15(Check

four ,skip four)
• The value of each parity bit is set so that the number of 1s in the
corresponding group of bits (including the parity bit itself) is even (for even
parity).
• During transmission, if a bit flips due to noise or interference, the receiver
recalculates the parity bits.
• The recalculated parity bits are compared with the original ones.
• If they differ, the receiver identifies the position of the error by checking
which parity bits have changed.
• The position of the error is determined by converting the pattern of the
incorrect parity bits into a binary number.
• Once the error bit is identified, it can be flipped back to correct the error.
Example - a 4-bit data 0110 to be transmitted
using Hamming code:
• Calculate Number of Parity Bits:2^𝑟≥4+𝑟+
• For 𝑟=3 8≥7, so 3 parity bits are needed.
Calculate the value of P1
• P1 checks bits at positions 1, 3, 5, and 7.
• ?+0+1+0=1 Make it even by putting P1=1
Calculate value of P2
• P2 (Position 2) checks bits 2, 3, 6, and 7:
• ?+0+1+0=1 To make it even Set P2=1
Calculate Value of P4
• P4 checks bits at positions 4, 5, 6, and 7.

• ? + 1+1+0=2, Even So P4=0

Final Code word is 1100110

Checking for errors @ Receiver received
1101110
• 4th bit is altered
• Apply even parity for position 4,5,6,7=> 0+1+1+1=3 so Parity is => 1
• Apply even parity for position 2,3,6,7=> 1+0+1+0=2 So parity is => 0
• Apply even parity for position 1,3,5,7=> 1+0+1+0=2 So parity is => 0

• combining parities => 100 => 4th Location has error

• So flip 1 in 4th location to 0 and we get
• 1100110
Checking at receiver

Apply even parity for position 4,5,6,7=> 0+1+1+0=2 so Parity is => 0

Apply even parity for position 2,3,6,7=> 1+0+1+0=2 So parity is => 0
Apply even parity for position 1,3,5,7=> 1+0+1+0=2 So parity is => 0

000 means no such location , so no error

Question
• Suppose the data to be transmitted is 0110 using Hamming code
using even parity.
General Algorithm of Hamming code:
• Hamming Code is simply the use of extra parity bits to allow the
identification of an error.
1. Write the bit positions starting from 1 in binary form (1, 10, 11, 100,
etc).
2. All the bit positions that are a power of 2 are marked as parity bits
(1, 2, 4, 8, etc).
3. All the other bit positions are marked as data bits.
General Algorithm of Hamming code:
• Each data bit is included in a unique set of parity bits, as determined its bit position in
binary form.
• a. Parity bit 1 covers all the bits positions whose binary representation includes a 1 in the
least significant position (1, 3, 5, 7, 9, 11, etc).
• b. Parity bit 2 covers all the bits positions whose binary representation includes a 1 in the
second position from the least significant bit (2, 3, 6, 7, 10, 11, etc).
• c. Parity bit 4 covers all the bits positions whose binary representation includes a 1 in the
third position from the least significant bit (4–7, 12–15, 20–23, etc).
• d. Parity bit 8 covers all the bits positions whose binary representation includes a 1 in the
fourth position from the least significant bit bits (8–15, 24–31, 40–47, etc).
• e. In general, each parity bit covers all bits where the bitwise AND of the parity position
and the bit position is non-zero.
1. Since we check for even parity set a parity bit to 1 if the total number of ones in the
positions it checks is odd.
2. Set a parity bit to 0 if the total number of ones in the positions it checks is even.
Question
• If the 7 bit hamming code received by the receiver [Link]
whether the received code word is correct or wrong .If wrong locate
the bit having error.(Assume even parity is used)
Identify the parity bits and data bits in the received code.
The Hamming code has 4 data bits and 3 parity bits. The parity bits are located at positions 1, 2, and 4.
Check the parity of each parity bit.
● Parity Bit 1 (Position 1): Checks bits 1, 3, 5, and 7. The number of '1's in these positions is 3 (odd), which fails the even parity check.
● Parity Bit 2 (Position 2): Checks bits 2, 3, 6, and 7. The number of '1's in these positions is 3 (odd), which fails the even parity check.
● Parity Bit 3 (Position 4): Checks bits 4, 5, 6, and 7. The number of '1's in these positions is 3 (odd), which fails the even parity check.
Determine the error location.
The parity checks failed for all three parity bits. Representing this as a binary number, we get 111, which is equivalent to 7 in decimal
Question
• Suppose the data to be transmitted is 1011001 using hamming code.
How the data is transmitted.
• Suppose the data to be transmitted is 1011001 using hamming code.
How the data is transmitted.

For 7 data bits, 4 parity bits are to be added

2^4- Parity bits at 1,2,4,8
PP1P011P001
Calculate P1 (covers positions 1, 3, 5, 7, 9)- 1+ 0+1 =1
Total 1s = 3 (odd) →Add 1 (to make it even)
Calculate P2 (covers positions 2, 3, 6, 7, 10) -1+1+1=0
Calculate P3 (covers positions 4, 5, 6, 7)-0+1+1=0
Calculate P4((covers positions 8, 9, 10):-0+0+1=1
10100111001
Question
• The data received by the receiver is [Link] whether the
received code word is correct or wrong .If wrong locate the bit having
error.(Assume even parity is used)
Question
• The data received by the receiver is [Link] whether the
received code word is correct or wrong .If wrong locate the bit having
error.(Assume even parity is used)
• Solution at
[Link]