Application Report
SPRA530
Digital Signal Processing Solutions April 1999
Cyclic Redundancy Check Computation:
An Implementation Using the
TMS320C54x
Patrick Geremia C5000
Abstract
Cyclic redundancy check (CRC) code provides a simple, yet powerful, method for the detection of
burst errors during digital data transmission and storage. CRC implementation can use either
hardware or software methods. This application report presents different software algorithms and
compares them in terms of memory and speed using the Texas Instruments (TI) TMS320C54x
digital signal processor (DSP). Various common CRC codes will be used.
TI is a trademark of Texas Instruments Incorporated.
Application Report
SPRA530
Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
2
Contents
Introduction ......................................................................................................................................................3
Coding Theory Behind CRC.............................................................................................................................3
Fundamentals of Block Coding.............................................................................................................3
CRC Coding .........................................................................................................................................5
CRC Code Examples............................................................................................................................5
Algorithms for CRC Computation.....................................................................................................................6
Bitwise Algorithm ..................................................................................................................................6
Lookup Table Algorithms......................................................................................................................7
Standard Lookup Table Algorithm ........................................................................................................7
Reduced Lookup Table Algorithm ........................................................................................................8
TMS320C54x Implementation..........................................................................................................................9
General Considerations........................................................................................................................9
Results..................................................................................................................................................9
CRC-CCITT ................................................................................................................................9
CRC-32 10
CRC for GSM/TCH ...................................................................................................................10
CRC for GSM/TCH/EFS Precoder............................................................................................11
GSM FIRE Code.......................................................................................................................11
Summary........................................................................................................................................................12
Code Availability.............................................................................................................................................12
References.....................................................................................................................................................12
Appendix A. CRC-CCITT Listing
†
...................................................................................................................13
Appendix B. CRC-32 Listing
†
.........................................................................................................................18
Appendix C. GSM/TCH Listing.......................................................................................................................23
Appendix D. GSM/TCH/EFS Precoder Listing
†
..............................................................................................25
Appendix E. GSM FIRE Code Listing
†
...........................................................................................................30
Figures
Figure 1. CRC Generation Using a Linear Feedback Shift Register (LFSR) .............................................6
Tables
Table 1. Common CRC Codes and Associated Generator Polynomial....................................................5
Table 2. Benchmarks for CRC-CCITT ......................................................................................................9
Table 3. Benchmarks for CRC-32...........................................................................................................10
Table 4. Benchmarks for GSM/TCH .......................................................................................................10
Table 5. Benchmarks for GSM/TCH/EFS Precoder................................................................................11
Table 6. Benchmarks for GSM FIRE Code.............................................................................................11
Application Report
SPRA530
Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
3
Introduction
Error correction codes provide a means to detect and correct errors introduced by a
transmission channel. Two main categories of code exist: block codes and convolutional
codes. They both introduce redundancy by adding parity symbols to the message data.
Cyclic redundancy check (CRC) codes are a subset of cyclic codes that are also a subset
of linear block codes. The theory behind block coding and more specifically CRC coding
is briefly discussed in this application report as well as most common CRC codes.
CRC implementation can use either hardware or software methods. In the traditional
hardware implementation, a simple shift register circuit performs the computations by
handling the data one bit at a time. In software implementations, handling data as bytes
or words becomes more convenient and faster. You choose a particular algorithm
depending on which memory and speed constraints are required. Different types of
algorithms and the results are presented later in this application report.
Coding Theory Behind CRC
Fundamentals of Block Coding
A block code consists of a set of fixed-length vectors called code words. The length of a
code word is the number of elements in the vector and is denoted by
n
. The elements of
a code word are selected from an alphabet of
q
elements. When the alphabet consists of
two elements, 0 and 1, the code is binary; otherwise, it is nonbinary code. In the binary
case, the elements are bits. The following discussion focuses on binary codes.
There are 2
n
possible code words in a binary block code of length
n
. From these 2
n
code
words you may select M = 2
k
code words
(k < n)
to form a code. Thus a block of
k
information bits is mapped into a code word of length
n
selected from the set of M = 2
k
code words. This is called an (
n
,
k
) code and the ratio
k/n
is defined to be the rate of the
code.
The encoding and decoding functions involve the arithmetic operations of addition and
multiplication performed on code words. These arithmetic operations are performed
according to the conventions of the algebraic field that has, as its elements, the symbols
contained in the alphabet. For binary codes, the field is finite and has 2 elements, 0 and
1, and is called
GF(2)
(Galois Field).
A code is linear if the addition of any two-code vectors forms another code word. Code
linearity simplifies implementation of coding operations.
The minimum distance
d
min
is the smallest hamming distance between two code words.
The hamming distance is the number of symbols (bits in the binary case) in which they
differ. The minimum distance is closely linked to the capacity of the code to detect and
correct errors and is a function of the code characteristics. An (
n
,
k
)
block code is capable
of detecting
d
min
– 1 errors and correcting
)1(
2
1
−
d
min
errors.
Application Report
SPRA530
Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
4
Suppose
i
m
is the k-bits information word, the output of the encoder will result in an
n-bits code word
i
c
, defined as
Gmc
ii
=
)12,....,1,0( −=
k
i
where
G
is called the
generator matrix of dimension
nk
×
. Every linear block code is equivalent to a systematic
code; therefore, it is always possible to find a matrix G generating code words formed by
the
k
information bits followed by the
n-k
parity check bits, for example,
[]
,PIG
k
= where
k
I
is the
kk
× identity matrix and
P
is a )(
knk
−× matrix of parity checks. The parity
check matrix
H
is defined as a
kkn
×−
)( matrix so that 0=
T
GH
. If the code is
systematic, then
[
]
kn
T
,IPH
−
=
. Since all code words are linear sums of the rows in
G
,
we have
0=
T
i
Hc
for all
I,
)12,....,1,0( −=
k
i
. If a code word
c
is corrupted during
transmission so that the receive word is
cce' =+
, where
e
is a non-zero error pattern,
then we call syndrome
s
the result of following multiplication,
TTTTT
eHeHcHHecHcs
=+=+== )('
, where
s
is )(
kn
− - dimensional vector. The
syndrome
s
is dependent on the error pattern. If the error pattern is a code vector, the
errors go undetected. For all other error patterns, however, the syndrome is nonzero.
Decoding then uses standard array decoders that are based on lookup tables to
associate each syndrome with an error pattern. This method becomes impractical for
many interesting and powerful codes as )(
kn
−
increases.
Cyclic codes are a subclass of linear block codes with an algebraic structure that enables
encoding to be implemented with a linear feedback shift register and decoding to be
implemented without using standard array decoders. Therefore, most block codes in use
today are cyclic or are closely related to cyclic codes. These codes are best described if
vectors are interpreted as polynomials. In a cyclic code, all code word polynomials are
multiples of a generator polynomial )(
xg
of degree
kn
− . This polynomial is chosen to
be a divisor of
1+
n
x
so that a cyclic shift of a code vector yields another code vector. A
message polynomial )(
xm
i
can be mapped to a code word polynomial
)()()(
xrxxmxc
i
kn
ii
−=
−
)12,....,1,0( −=
k
i
(systematic form), where )(
xr
i
is the
remainder of the division of
kn
i
xxm
−
)(
by )(
xg
.
The first step in decoding is to determine if the receive word is a multiple of
gx()
. This is
done by dividing it by )(
xg
and examining the remainder. Since polynomial division is a
linear operation, the resulting syndrome )(
xg
depends only on the error pattern. If )(
xg
is the all-zero polynomial, transmission is errorless or an undetectable error has
occurred. If )(
xg
is nonzero, at least one error has occurred. This is the principle of CRC.
More powerful codes attempt to correct the error and use the syndrome to determine the
locations and values of multiple errors.
Application Report
SPRA530
Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
5
CRC Coding
CRC codes are a subset of cyclic codes and use a binary alphabet, 0 and 1. Arithmetic is
based on
GF(2)
, for example, modulo-2 addition (logical XOR) and modulo-2
multiplication (logical AND).
In a typical coding scheme, systematic codes are used. Assume the convention that the
leftmost bit represents the highest degree in the polynomial. Suppose
)(
xm
to be the
message polynomial,
)(
xc
the code word polynomial and
)(
xg
the generator polynomial,
we have
)()()(
xgxmxc
=
which can also be written using the systematic form
)()()(
xrxxmxc
kn
+=
−
, where
)(
xr
is the remainder of the division of
kn
xxm
−
)(
by
)(
xg
and
)(
xr
represents the CRC bits. The transmitted message
)(
xc
contains k-information
bits followed by
kn
−
CRC bits, for example,
0
1
10
1
1
...)(
rxrxmxmxc
kn
kn
knn
k
++++=
−−
−−
−−
−
. So encoding is straightforward:
multiply
)(
xm
by
kn
x
−
, that is, append
kn
−
bits to the message, calculate the CRC bits
by dividing
kn
xxm
−
)(
by
)(
xg
, and append the resulting
kn
−
CRC bits to the message.
For the decoding part, the same algorithm can be used. If
)('
xc
is the received
message, then no error or undetectable errors have occurred if
)('
xc
is a multiple of
)(
xg
, which is equivalent to determining that if
kn
xxc
−
)('
is a multiple of
)(
xg
, that is, if
the remainder of the division from
kn
xxc
−
)('
by
)(
xg
is 0.
CRC Code Examples
The performance of a CRC code is dependent on its generator polynomial. The theory
behind its generation and selection is beyond the scope of this application report. This
application report will only consider the most common used ones (see Table 1).
Table 1. Common CRC Codes and Associated Generator Polynomial
CRC Code Generator Polynomial
CRC-CCITT (X25)
1
51216
+++
xxx
CRC-32 (Ethernet)
+++++++
11121622232632
xxxxxxx
1
2457810
+++++++
xxxxxxx
GSM TCH/FS-HS-EFS
(Channel coding for speech traffic
channels)
1
3
++
xx
GSM TCH/EFS pre-coding
(Preliminary channel coding for Enhanced
Full Rate)
1
2348
++++
xxxx
GSM control channels – FIRE code
(Channel coding for control channels)
1
317232640
+++++
xxxxx
