Error Correcting Codes
Marist College
CMPT 422
Anthony Giorgio
Parity Bits
Add a single bit to a code word
Able to detect single bit errors
Parity bit set based on number of 1 bits
Can be even or odd parity
Even Parity
Code word 010101
Has three 1's
Parity bit used to make an even number of 1's
Formula:
xor () all bit together to compute value of p
p = 0 1 0 1 0 1 = 1
Parity bit will be 1
Uses of Parity
Can detect 1-bit errors on noisy channel
Cannot correct errors
Receiver knows that there was an error
Can wait for message retransmission in hopes
that it will succeed this time
Information Transmission
Transmission
Message
Hello
Encoded
Sent
100 1000
110 0101
110 1100
110 1100
110 1111
Encoded
Received
100 1000
110 0101
110 1100
110 1100
110 1110
Message
Hell~
Information Transmission
Transmission
Message
Hello
Encoded
Sent
100 1000
110 0101
110 1100
110 1100
110 1111
Encoded
Received
100 1000
110 0101
110 1100
110 1100
110 1110
Message
Hell~
Error!
Information Transmission
with Parity Bit
Transmission
Message
Hello
Even Parity
Encoded
Sent
0100 1000
0110 0101
0110 1100
0110 1100
0110 1111
Encoded
Received
0100 1000
0110 0101
0110 1100
0110 1100
0110 1110
Message
Hell~
Information Transmission
with Parity Bit
Transmission
Message
Hello
Encoded
Sent
0100 1000
0110 0101
0110 1100
0110 1100
0110 1111
Encoded
Received
0100 1000
0110 0101
0110 1100
0110 1100
0110 1110
Message
Hell~
Error Detected
Hamming Codes
Richard Hamming invented in 1950
Worked at Bell Telephone Labs
Was frustrated with error prone punch card
readers
Had to often restart jobs due to input errors
Hamming Codes
Original Hamming code is called Hamming(7,4)
Encodes 4 bits of data into 7 bits
Uses 3 parity bits
Can detect 1 and 2-bit errors
Can correct 1 bit errors!
Hamming Distance
Difference between code words
Counts number of substitutions required to
change one string to another
Difference between 1011101 and 1001001 is 2
Hamming(7,4) has a distance of 3
Every code word requires at least 3 bit changes
to become another valid code word
Hamming Example
4
p1 is for bits xx1 = d1 d2 d4
p2 is for bits x1x = d1 d3 d4
p4 is for bits 1xx = d2 d3 d4
Hamming Example
Data bits are 1011
d1 = 1; d2 = 0; d3 = 1; d4 = 1
p1 = d1 d2 d4 = 1 0 1 = 0
p2 = d1 d3 d4 = 1 1 1 = 1
p4 = d2 d3 d4 = 0 1 1 = 0
Bit pattern is: p1 p2 d1 p4 d2 d3 d4
Hamming encoding is 0 1 1 0 0 1 1
Error Detection con't
Bit pattern is: 0110011
Flip a bit to introduce error: 0110111
Calculate parity:
b1 b3 b5 b7 =
b2 b3 b6 b7 =
b4 b5 b6 b7 =
Error Detection con't
Bit pattern is: 0110011
Flip a bit to introduce error: 0110111
Calculate parity:
b1 b3 b5 b7 = 0 1 1 1 = 1
b2 b3 b6 b7 = 1 1 1 1 = 0
b4 b5 b6 b7 = 0 1 1 1 = 1
Parity of 101 != 000 - error detected!
Error Detection con't
Bit pattern is: 0110011
Flip a bit to introduce error: 0110111
Calculate parity:
b1 b3 b5 b7 = 0 1 1 1 = 1
b2 b3 b6 b7 = 1 1 1 1 = 0
b4 b5 b6 b7 = 0 1 1 1 = 1
Parity of 101 != 000 - error detected!
p1 is bit 1, p4 is bit 4; 1 + 4 = 5
Bit 5 is in error
Extended Hamming Example
p1 = d1 d2 d4 d5 d7
p2 = d1 d3 d4 d6 d7
p4 = d2 d3 d4
p8 = d5 d6 d7
Extended Hamming Example
Data is 0x3A = 0111010
Calculate parity:
p1 = d1 d2 d4 d5 d7
p2 = d1 d3 d4 d6 d7
p4 = d2 d3 d4
p8 = d5 d6 d7
Extended Hamming Example
Data is 0x3A = 0111010
Calculate parity:
p1 = d1 d2 d4 d5 d7
=011000=0
p2 = d1 d3 d4 d6 d7
=01110=1
p4 = d2 d3 d4
=111=1
p8 = d5 d6 d7
=010=1
Extended Hamming Example
Data is 0x3A = 0111010
p1 = 0; p2 = 1; p4 = 1; p8 = 1
Encoding pattern:
p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7
01011111010
Error Detection
Bit pattern is: 01011111010
Introduce error: 01001111010
Calculate parity:
b1 b3 b5 b7 b9 b11 =
b2 b3 b6 b7 b10 b11 =
b4 b5 b6 b7 =
b8 b9 b10 b11
Error Detection
Bit pattern is: 01011111010
Introduce error: 01001111010
Calculate parity:
b1 b3 b5 b7 b9 b11 =
001100=0
b2 b3 b6 b7 b10 b11 =
101110=0
b4 b5 b6 b7 =
0111=1
b8 b9 b10 b11
1010=0
Error Detection
Bit pattern is: 01011111010
Introduce error: 01001111010
Parity bits:
p1 = 0; p2 = 0; p4 = 1; p8 = 0
Since p4 is 1, bit 4 is in error
SEC/DED Hamming Example
Data is 0x3A = 0111010
p1 = 0; p2 = 1; p4 = 1; p8 = 1
Encoding pattern:
p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7
01011111010
Add bit 0 with overall parity
xor all bits together to calculate value
1 0 1 0 1 1 1 1 1 0 1 0
Error Detection
Bit pattern is: 101011111010
Introduce 2-bit error: 101001111110
Calculate parity:
b1 b3 b5 b7 b9 b11 =
b2 b3 b6 b7 b10 b11 =
b4 b5 b6 b7 =
b8 b9 b10 b11
Error Detection
Bit pattern is: 1 01011111010
Introduce 2-bit error: 1 01001111110
Calculate parity:
b1 b3 b5 b7 b9 b11 =
001110=1
b2 b3 b6 b7 b10 b11 =
101110=0
b4 b5 b6 b7 =
0111=1
b8 b9 b10 b11
1110=1
Error Detection
Overall parity check using p0 indicates no error
But calculated parity is 1011, indicating error
Since error indicators do not match, this
indicates an uncorrectable 2-bit error
