Transcript Document

Error Detection and Correction
Parity Schemes: Modulo 2 addition (XOR)
• Word parity
• Block Parity
CRC Error Correction
CRC error correction schemes are mechanized using the binary symbol
alphabet {0,1} and modulo 2 arithmetic. However the math behind it
is applicable with any symbol alphabet and any legitimate algebra.
We will explore the method using normal, decimal arithmetic.
Consider a message: [mN-1,mN-2, m1,m0] where the mi are symbols
selected from the symbol alphabet M = {0,1,2,3, ..,8,9}.
The number of symbols in the alphabet is x = 10, each symbol carries
3.32 bits of information. If we were to see the actual digits written out,
we would intuitively associate a value with the message, represented
by the polynomial:
M(x) = mN-1xN-1 + mN-2 xN-2 + .. + m1x1 + m0x0
We are going to append two check digits to the message, [c1,c0]. The
polynomial representing the check digits is of order C = 2:
C(x) = c1x1 + c0x0
The Message digits must be shifted to the left to make room for the check
digits, do the final data word will be represented by the polynomial:
D(x) = xcM(x) + C(x) =M’(x) + C(x)
Here’s the trick. We want to pick C(x) such that D(x) represents a number
which is evenly divisible by some other number, G, called the generator,
represented by the “generator polynomial” G(x). Stated mathematically:
D  x
R  x
 Q0  x   0
G  x
G  x
Where R0(x) =0 is the remainder
polynomial after division.
Consider for a moment performing the division with the check digits set to zero:
M  x
R  x
 Q1  x   1
G  x
G  x
Where R1(x) is the remainder
polynomial after division.
If we set C(x) = G(x) – R1(x), then we can write . . .
D  x
G  x

M  x  C  x
 Q1  x   1 
G  x
0
G  x

M  x
G  x

C  x
G  x
 Q1  x  
R1  x 
G  x

G  x   R1  x 
G  x
And we have zero remainder, as desired.
When the message is received at the destination, it is divided by the
generator, and if the remainder is zero, we may be certain that a single digit
error did not occur.
If the generator is judiciously chosen, when an error occurs, the remainder
will uniquely identify which digit was corrupted.
Consideration of the number of check digits
There must be a unique remainder for every possible error that can occur. In a
binary code (x = 2), there is one possible error for each digit in D(x) .
Since the remainder must be less than G, it is clear that G > N + C.
Since the order of G must be equal to the order of C(x) i.e. C, the maximum
value for G is xC-1. Thus
xC  G  N  C
or,
N  xC  C
Example
We’ll consider an example using decimal arithmetic. We will construct
a message of 5 digits.
For simplicity, we will consider the only possible transmission errors to
consist of increasing or decreasing each digit by one, so two possible
errors per digit in the message (including check digits), so G > 2(N+C),
and G < 10C . Thus, for this scheme:
xC  G  2  N  C 
or,
xC  2C  10
So C = 2 digits will work, and G > 14.
Lets try G = 17 (prime numbers usually work well). We need to verify that
each possible error creates a unique remainder, so lets pick a typical message,
determine the check digits, introduce each possible error, and see if we get a
unique remainder. If we don’t, we have to try another generator.
M  55555
M   5555500
C  G  R1  17  2  15
M  5555500
2

 Q1 
G
17
17
D  M ' C  5555515
Verification
The remainders for each possible error are:
Corrupted
Message Remainder
5555516
1
5555525
10
5555615
15
5556515
14
5565515
4
5655515
6
6555515
9
5555514
16
5555505
7
5555415
2
5554515
3
5545515
13
5455515
11
4555515
8
These are all
unique, so we gave
a good generator.
The sorted
remainders, and
their corresponding
corrections are:
Remainder Correction
1
-1
2
100
3
1000
4
-10000
6
-100000
7
10
8
1000000
9
-1000000
10
-10
11
100000
13
10000
14
-1000
15
-100
16
1
Modulo 2 Division
10 10 010
100101 101101010110
100101000000
01000010110
00000000000
1000010110
1001010000
001000110
0+
00000000
01000110
00000000
1000110
1001010
001100
000000
01100
1
0
0
1
0
1
+
1
0
1
0
+
0
x1
1
x0
0
x1
1
x0
0
x1
0
x1
x0
x
Manipulate the Structure:
10
10
+
01
0x
0
+
1x
10
x
01
x
1x
0x
Flip Over
0
0
1
1
0
+
+
Data
0
Flip Again
+
Data
1
1x
After
Initial
5State
Shifts
State
Final
+
01
1x
0
1
0
1
0
1
0
0
(1)
0x
1x
1x
0x
x
Notes on Generator Choice
• Generator must have one more digit than Check Digits.
• Generator must be of the form:
1XX…X1