Information Technology Reference
In-Depth Information
D
Redundancy checking
D.1 Cyclic redundancy check (CRC)
The CRC is one of the most reliable error detection schemes and can detect up to 95.5% of
all errors. The most commonly used code is the CRC-16 standard code which is defined by
the CCITT.
The basic idea of a CRC can be illustrated using an example. Suppose the transmitter and
receiver were both to agree that the numerical value sent by the transmitter would always be
divisible by 9. Then should the receiver get a value which was not divisible by 9 then it
would know that there was an error. For example, if a value of 32 were to be transmitted it
could be changed to 320 so that the transmitter would be able to add to the least significant
digit, making it divisible by 9. In this case the transmitter would add 4, making 324. If this
transmitted value were to be corrupted in transmission then there would only be a 10%
chance that an error would not be detected.
In CRC-CCITT, the error correction code is 16 bits long and is the remainder of the data
message polynomial
G
(
x
) divided by the generator polynomial
P
(
x
) (
x
16
+
x
12
+
x
5
+1, i.e.
10001000000100001). The quotient is discarded and the remainder is truncated to 16 bits.
This is then appended to the message as the coded word.
The division does not use standard arithmetic division. Instead of the subtraction opera-
tion an exclusive-OR operation is employed. This is a great advantage as the CRC only re-
quires a shift register and a few XOR gates to perform the division.
The receiver and the transmitter both use the same generating function
P
(
x
). If there are
no transmission errors then the remainder will be zero.
The method used is as follows:
1. Let
P
(
x
) be the generator polynomial and
M
(
x
) the message polynomial.
2. Let
n
be the number of bits in
P
(
x
).
3. Append
n
zero bits onto the right-hand side of the message so that it contains
m
+
n
bits.
4. Using modulo-2 division, divide the modified bit pattern by
P
(
x
). Modulo-2 arithmetic
involves exclusive-OR operations, i.e.
0-1=1
,
1-1=0
,
1-0=1
and
0-0=0
.
5. The final remainder is added to the modified bit pattern.
Example:
For a 7-bit data code 1001100 determine the encoded bit pattern using a CRC
generating polynomial of
P
(
x
)=
x
3
+
x
2
+
x
0
. Show that the receiver will not detect an error if
there are no bits in error.
Answer
P
(
x
)=
x
3
+
x
2
+
x
0
(1101)
G
(
x
)=
x
6
+
x
3
+
x
2
(1001100)
Multiply by the number of bits in the CRC polynomial:
