Polynomial rotation accelerates CRC calculations
This idea introduces a method of CRC calculation that rotates a polynomial instead of shifting data.
Josef Valasek, AWOS, Pardubice, Czech Republic; Edited by Paul Rako and Fran Granville -- EDN, September 8, 2011
Engineers commonly use two methods of CRC (cyclic-redundancy-check) calculations. One method uses shift registers, and the other uses precalculated CRC values. The first method shifts the data bit by bit, and, depending on the bit value, a polynomial divides the bits. References 1 and 2 explain this method in detail. You can find assembly-language procedure codes for 8- and 16-bit calculations in references 1, 3, and 4.|
Listings Listing 2 Listing 3 Listing 4 Listing 5 Listing 6 Listing 7 Listing 8 Listing 9 Listing 10 |
The second method for CRC calculations uses the table of precalculated CRC values. References 1, 3, and 4 contain links to 8- and 16-bit assembly-language procedure codes, respectively. The procedures work quickly, but they consume many bytes of program memory, which can cause a problem if you use a microcontroller with little program memory.
This Design Idea introduces a method
of CRC calculation that rotates a
polynomial instead of shifting data. You
know the polynomial’s value before you
write the procedure’s code. Therefore,
you can prepare polynomial values and
write them into the procedure code as
constants. Figures 1 and 2 show the
principle of the method.
The method exclusive-ORs the data
with the old CRC value and places the
result to bits 7 to 0 of a 16-bit register.
Each calculation has eight steps. In each
step, a polynomial value shifts one bit
to the left, and the code tests one bit of
the register. The results of the tested bit
determine whether the code performs
or skips the polynomial division. The
resulting CRC value is subsequently
written to bits 15 to 8 of the register.
When all steps are complete, bits 15 to
8 of the register comprise a new CRC
value. The lowest significant bits of the
register remain unused after testing. You
can use these dormant bits in the register
to store result bits by modifying
the method using polynomial rotation
instead of a polynomial shift. Listings
2 and 5 show this procedure for 8- and 16-bit CRC calculations, respectively.
These routines perform only bit-testing
and polynomial-dividing instructions.
Tables 1 and 2 highlight calculation
procedures for 8- and 16-bit calculations,
respectively, using this method.
The tables describe execution times for
a standard 12-clock 8051 core with a
12-MHz crystal. The code lengths and
execution times of procedure codes come
from Reference 1; references 3 and 4
calculate without saving or restoring
the procedure’s working registers.
You should properly set the initial CRC value before starting CRC calculation. Some communication protocols, such as the one in Reference 2, use an initial CRC value other than 00 Hex. Listings 7 through 10 show the procedure codes for 8- and 16-bit CRC calculation with PIC microcontrollers.
|
References |
|
Talkback
