1
Error Detection and Correction
Handling Errors (1): Ignore Them!
data in data out
Tx
DATA
frame
Rx
Some errors are not signicant audio video
Handling Errors (2): Do something
data in
Lets meet at 1pm tomorrow
data out
Tx
DATA
frame
Rx
Lets meet at 3pm tomorrow
Most errors are signicant must be detected If only detect errors Reverse Error Correction (REC) must ask for retransmission ARQ protocol unsuited to real-time applications unsuited to simplex communication If detect and correct errors Forward Error Correction (FEC)
A Simple REC System
data in
Lets meet at 1pm tomorrow Lets meet at 3pm tomorrow
Tx
Lets meet at 1pm tomorrow
NAK
Rx
Send data twice Rx delivers data if two copies identical and generates ACK-frame Rx sends NAK-frame if two copies differ
A Simple FEC System
data in
Lets meet at 1pm tomorrow Lets meet at 3pm tomorrow
data out
Tx
Lets meet at 1pm tomorrow Lets meet at 1pm tomorrow
Rx
Lets meet at 1pm tomorrow
Send data thrice Rx delivers the majority
Defeating Error Correction
data in
Lets meet at 1pm tomorrow Lets meet at 3pm tomorrow
data out
Tx
Lets meet at 3pm tomorrow Lets meet at 1pm tomorrow
Rx
Lets meet at 3pm tomorrow
More severe errors may not be detected
The Basis for Error Handling
add redundancy to data to form codewords handle two types of errors: random errors bit error rate (BER) error bursts up to B bits in error Codewords should have enough redundancy to detect probable errors
Example of valid codewords
binary decimal symbol b2 b1 b0 d0 represented 0 0 0 0 A 0 0 1 1 Invalid 0 1 0 2 Invalid 0 1 1 3 Invalid 1 0 0 4 Invalid 1 0 1 5 Invalid 1 1 0 6 Invalid 1 1 1 7 B binary decimal p(if A b2 b1 b0 d0 is sent) 0 0 0 0 0.729 0 0 1 1 0.081 0 1 0 2 0.081 0 1 1 3 0.009 1 0 0 4 0.081 1 0 1 5 0.009 1 1 0 6 0.009 1 1 1 7 0.001
6
Send A
?
0 0 0
Tx
Channel with BER = 0.1
Rx
Coordination Failure with Communication Failure
H1 m1 H2
. . . H1 mn1 H2
H1
mn H2
10
Hamming Distance
b1 6 10 11
1 - b0 b1 6 010 100 000 001 - b0 110 011
00 111
01 - b0
101 > b2
HD is number of bits between codewords e.g. 0002 is HD of two from 0112 , 1012 , and 1102 Error detection/correction based on HD between valid codewords
11
Hamming Distance of Two
110 010 100 000 001 011 101 000 111 010 100 001 110 011 101 111
One bit error will change valid codeword to invalid codeword Two bit error will change valid codeword into different valid codeword
12
Hamming Distance of Three
110 010 100 000 001 011 101 111
One bit error will change valid codeword to invalid codeword invalid code HD of one from only one valid codeword Two bit error will change valid codeword to invalid codeword
13
Examples of Hamming Distance
binary b2 b1 b0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 decimal symbol d0 0 1 2 3 4 5 6 7 HD HD
represented from A from B A Invalid Invalid Invalid Invalid Invalid Invalid B 0 1 1 2 1 2 2 3 3 2 2 1 2 1 1 0
14
Using Hamming Distance
To reliably detect up to e bits in error bits in error must be less than HD e = HD 1
HD = e + 1 To reliably detect and correct up to e bits in error bits in error must be less than halfway of HD e= HD 1 2
HD = 2e + 1
15
Parity Bits
modulo arithmetic no carry 0 +2 0 = 0 r = m0 +2 . . . +2 m6 1 +2 0 = 1 0 +2 1 = 1 ASCII X (10110002 ) 1 1 0 1 1 0 0 0 1 +2 1 = 0
codeword r m6 m5 m4 m3 m2 m1 m0
this denes even parity
16
Parity Bits
codeword r m6 m5 m4 m3 m2 m1 m0
r = m0 +2 . . . +2 m6
ASCII X (10110002 ) 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0
17
Parity Bits
codeword r m6 m5 m4 m3 m2 m1 m0
r = m0 +2 . . . +2 m6
ASCII X (10110002 ) 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 0
18
Parity Bits
codeword r m6 m5 m4 m3 m2 m1 m0
r = m0 +2 . . . +2 m6
ASCII X (10110002 ) 1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0
19
Odd and Even Parity
110 010 100 000 110 010 100 000 001 011 101 001 111 011 101 111 even parity r = m0 +2 . . . +2 mn hardware: XOR returns 0 by eye: even number of one bits odd parity r = m0 +2 . . . +2 mn + 1 hardware: XOR returns 1 by eye: odd number of one bits
Dont need to know which bit is redundant bit Implements HD=2 reliably detects one bit errors
20
Worksheet: Hamming Distance and Parity
1. Draw arcs between the codewords HD=1 0111 0000
1111
1010
1000
1011
1100
1001
2. If 1000 is to be a valid codeword, shade codewords which maintain HD=2. 3. What type of parity do codewords have? 4. If 1010 was received, with single bit, what codewords might have been sent? 5. How bit errors can parity check detect, and how many can it correct?
21
Block Sum Check
r w0 w1 w2 w3 w4 BCC 0 0 0 0 0 0 m6 1 1 1 1 1 1 m5 0 1 1 1 1 0 m4 0 0 0 0 0 0 m3 1 0 1 1 1 0 m2 0 1 1 1 1 0 m1 0 0 0 0 1 1 m0 0 1 0 0 1 0
Parity only detects one bit errors Improve by adding BCC at end, doing column-wise parity
22
Block Sum Check: Random Errors
r w0 w1 w2 w3 w4 BCC 0 0 0 0 0 0 m6 1 1 1 1 1 1 m5 0 0 1 0 1 0 m4 0 0 0 0 0 0 m3 1 1 1 0 1 0 m2 0 1 1 1 1 0 m1 0 0 0 0 1 1 m0 0 1 0 0 1 0
BCC defeated by four bits in error HD=4 detect three bit errors detect and correct one bit errors
23
Block Sum Check: Burst Errors
r w0 w1 w2 w3 w4 BCC 0 0 0 0 0 0 m6 1 1 1 1 1 1 m5 0 1 1 1 1 0 m4 0 0 0 0 0 0 m3 1 0 1 1 1 0 m2 0 1 1 1 1 0 m1 0 0 1 1 1 1 m0 0 1 1 1 1 0
Smallest burst with four bit square is ten bits remember, not all bits in a burst need be in error, just the rst and last BCC copes with 9 bit bursts
24
Hamming Code
b12 20 21 22 23 m8 X 0
b11
b10
b9
b8
b7
b6
b5
b4
b3
b2
b1
m7 1
m6 0
m5 1
r4 ?
m4 1
m3 0
m2 0
r3 ?
m1 0
r2 ?
r1 ?
Each bit position bn where n = 2x used for redundancy bit Parity generated on all bits bm where m has x bit set
25
Numbering bits means each has unique identier
b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1
26
Hamming Code: Compute 20 Value
b12 20 21 22 23 m8 X 0
b11 1
b10
b9 1
b8
b7 1
b6
b5 0
b4
b3 0
b2
b1 ?
m7 1
m6 0
m5 1
r4 ?
m4 1
m3 0
m2 0
r3 ?
m1 0
r2 ?
r1 ?
The value of r1 is the even parity for all bn where n has b1 = 1 Thus r1 = 1
27
Hamming Code: Compute 21 Value
b12 20 21 22 23 m8 X 0
b11
b10
b9
b8
b7
b6
b5
b4
b3
b2
b1
m7 1
m6 0
m5 1
r4 ?
m4 1
m3 0
m2 0
r3 ?
m1 0
r2 ?
r1 1
The value of r2 is the even parity for all bn where n has b2 = 1 Thus r2 = 0
28
Hamming Code: Compute 22 Value
b12 20 21 22 23 m8 X 0 0
b11
b10
b9
b8
b7
b6
b5
b4
b3
b2
b1
m7 1
m6 0
m5 1
r4 ?
m4 1
m3 0
m2 0
r3 ?
m1 0
r2 0
r1 1
The value of r3 is the even parity for all bn where n has b3 = 1 Thus r3 = 1
29
Hamming Code
b12 20 21 22 23 0 0 m8 X 0
b11 1 1
b10 0
b9 1
b8
b7 1 1 1
b6 0 0
b5 0
b4
b3 0 0
b2 0
b1 1
1 m7 1
0 m6 0
1 m5 1
0 r4 0 m4 1 m3 0 m2 0 r3 1 m1 0 r2 0 r1 1
Each bit position bn where n = 2x use for redundancy bit Parity generated on all bits bm where m has x bit set
30
Hamming Code: Error Correction
b12 20 21 22 23 0 0 m8 X 0
b11 1 1
b10 0
b9 1
b8
b7 1 1 1
b6 1 1
b5 0
b4
b3 0 0
b2 0
b1 1
1 m7 1
0 m6 0
1 m5 1
0 r4 0 m4 1 m3 1 m2 0 r3 1 m1 0 r2 0 r1 1
Parity checks failing points to error HD=3 detect and correct one bit errors
31
Worksheet: Hamming Code
m8 m7 m6 m5 r4 m4 m3 m2 r3 m1 r2 r1
1. Write message 11101110 into the message bit boxes above. 2. Compute using even parity the bits r4 r3 r2 r1 3. Invert message bit m6 , and write down in the order r4 r3 r2 r1 a 1 if rn parity is now incorrect, or a 0 if correct. 4. Invert the bit position in the codeword which the number represents.
32
Cyclic Redundancy Check
If we take a number n and divide by divisor d, result is integer quotient q integer remainder r obeys the equation n = qd + r If we add an error e to n, then n + e = q d + r e < d r = r r = r e must be an integer multiple of d CRC uses this idea (but using modulo 2 division)
33
Examples of CRC Checking
n d q r e n + e r OK? 0 1 2 160 161 162 321 322 323 245 84 Yes 246 85 No 247 86 No 405 83 No 406 84 Yes 407 85 No 566 83 No 567 84 Yes 568 85 No
245 161 1 84
First error pattern not detected = 16110 = 101000012 Second error pattern not detected = 32210 = 1010000102
34
Properties of 16 bit CRC
name CRC-16 polynomial binary divisor application
X 16 + X 15 + X 2 + 1 11000000000000101 USB
CRC-CCITT X 16 + X 12 + X 5 + 1 10001000000100001 Bluetooth Choosing values for polynomials need care to achieve the best performance. Those above detect: error bursts of 16 bits all error bursts with an odd number of bits 99.997% of 17 bit errors 99.998% of 18 or longer bit errors
35
Properties of 32 bit CRC
IEEE 802.3 CRC-32 is x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 As a shorthand write as a number representing polynomials (missing off the last +1). e.g. IEEE 802.3 0x82608EDB, iSCSI 0x8F6E37A0
HD max no message bits 0x82608EDB 0x8F6E37A0 0xBA0DC66B 0xD419CC15 0x80108400 8 7 6 5 4 3 91 171 268 2,974 91,607 128K 177 (177) 5,243 (5,243) 128K unknown 152 (152) 16,360 (16,360) 114,663 (114,663) 58 81 1,060 65,505 (65,505) (65,505) 0 0 0 65,505 (65,505) (65,505)
36
Error Bursts
message1 +redundant1 = n1 n1 n1 n1 n1 5 4 3 2 1 message2 +redundant2 = n2 n2 n2 n2 n2 5 4 3 2 1 message3 +redundant3 = n3 n3 n3 n3 n3 5 4 3 2 1 message4 +redundant4 = n4 n4 n4 n4 n4 5 4 3 2 1 transmitted data interleaves codewords
. . . n1 n4 n3 n2 n1 n4 n3 n2 n1 3 2 2 2 2 1 1 1 1
If basic error checking can detect B bit bursts, interleaving N codewords allows N B bursts to be detected
