Information Technology Reference
In-Depth Information
Table D.1 lists some typical CRC codes. CRC-32 is used in Ethernet, Token Ring and FDDI
networks, whereas ATM uses CRC-8 and CRC-10.
Table D.1
Typical schemes
Type
Polynomial
Polynomial binary
equivalent
x
8
+
x
2
+
x
1
+1
CRC-8
100000111
x
10
+
x
9
+
x
5
+
x
4
+
x
1
+1
CRC-10
11000110011
x
12
+
x
11
+
x
3
+
x
2
+1
CRC-12
1100000001101
x
16
+
x
15
+
x
2
+1
CRC-16
11000000000000101
x
16
+
x
12
+
x
5
+1
CRC-CCITT
10001000000100001
x
32
+
x
26
+
x
23
+
x
16
+
x
12
+
x
11
+
x
10
+
x
8
+
x
7
+
x
5
+
x
4
+
x
2
+
x
+1
CRC-32
100000100100000010001110110110111
D.1.1 Mathematical representation of the CRC
The main steps to CRC implementation are:
1. Prescale the input polynomial of
M
'
x
)
by the highest order of the generator polynomial
P
(
x
).
n
Mx
'( )
=
xMx
( )
2. Next divide
M
'
x
)
by the generator polynomial to give:
n
M
'
(
x
)
x
M
(
x
)
R
(
x
)
=
=
Q
(
x
)
+
G
(
x
)
G
(
x
)
G
(
x
)
which yields
x
n
M
(
x
)
=
G
(
x
)
Q
(
x
)
+
R
(
x
)
and rearranging gives
x
n
This means that the transmitted message (
M
(
x
)
+
R
(
x
)
=
G
(
x
)
Q
(
x
)
x
n
M
(
x
)
+
R
(
x
)
) is now exactly divisible by
G
(
x
).
D.1.2 CRC example
Question A
A CRC system uses a message of 1 +
x
2
+
x
4
+
x
5
. Design a cyclic encoder circuit with genera-
tor polynomial
G
(
x
)=1+
x
2
+
x
3
and having appropriate gating circuitry to enable/disable the
shift out of the CRC remainder.
Answer A
The generator polynomial is
G
(
x
)=1+
x
2
+
x
3
, the circuit is given in Figure D.3.
