Application Report
`SPRA530
`
`Cyclic Redundancy Check Computation:
`An Implementation Using the
`TMS320C54x
`
`Patrick Geremia
`
`Abstract
`
`C5000
`
`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(cid:228)
`) TMS320C54x
`digital signal processor (DSP). Various common CRC codes will be used.
`
`TI is a trademark of Texas Instruments Incorporated.
`
`Digital Signal Processing Solutions
`
`April 1999
`
`Patent Owner Ex. 2009 Page 1
`
`

`
`Application Report
`SPRA530
`
`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
`
`Figure 1.
`
`Figures
`CRC Generation Using a Linear Feedback Shift Register (LFSR) .............................................6
`
`Table 1.
`Table 2.
`Table 3.
`Table 4.
`Table 5.
`Table 6.
`
`Tables
`Common CRC Codes and Associated Generator Polynomial ....................................................5
`Benchmarks for CRC-CCITT ......................................................................................................9
`Benchmarks for CRC-32...........................................................................................................10
`Benchmarks for GSM/TCH .......................................................................................................10
`Benchmarks for GSM/TCH/EFS Precoder................................................................................11
`Benchmarks for GSM FIRE Code.............................................................................................11
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`2
`
`Patent Owner Ex. 2009 Page 2
`
`

`
`Application Report
`SPRA530
`
`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 2n possible code words in a binary block code of length n. From these 2n code
`words you may select M = 2k 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 = 2k
`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 dmin 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
`-dmin
`(
`
`)1
`
` errors.
`
`21
`
`of detecting dmin – 1 errors and correcting
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`3
`
`Patent Owner Ex. 2009 Page 3
`
`

`
`Application Report
`SPRA530
`
`im is the k-bits information word, the output of the encoder will result in an
`Suppose
`=
`i =
`k
`
`1,0 2,....,
`(
`)1
`
`i
`
` where G is called the
`ic , defined as
`n-bits code word
`Gmc
`i
`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
`
` [ ],PIG k=
` where
`the k information bits followed by the n-k parity check bits, for example,
`-·
`kk·
` matrix of parity checks. The parity
` identity matrix and P is a
`
` )( knk
`kI is the
`0=TGH
`·-
`)
`(
` matrix so that
`check matrix H is defined as a
`. If the code is
`kkn
`[
`]
`=
`T,IPH
`. Since all code words are linear sums of the rows in G,
`systematic, then
`kn
`0=T
`=
`k
`(
`
`
` 2,....,1,0
`)1
`iHc
`i
` for all I,
`. If a code word c is corrupted during
`we have
`
`
`
`ectransmission so that the receive word is c' = + , where e is a non-zero error pattern,
`then we call syndrome s the result of following multiplication,
`=
`+
`=
`=
`=
`+
`kn-
`T
`T
`T
`T
`T
`'
`(
`)
`HecHcs
`cH
`eH
`eH
` - dimensional vector. The
`)
`(
`, where s is
`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
`kn-
` increases.
`many interesting and powerful codes as
`)
`(
`
`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
`kn-
`. This polynomial is chosen to
`)(xg of degree
`multiples of a generator polynomial
`1+nx
`be a divisor of
` so that a cyclic shift of a code vector yields another code vector. A
` can be mapped to a code word polynomial
`message polynomial
`)(xmi
`=
`=
`kn
`k
`)(
`)(
`)(
`(
`
`
` 2,....,1,0
`)1
`xxmxc
`xr
`i
`
` (systematic form), where
`)(xri
`i
`i
`i
`kn
`)(
`i xxm
` by
`)(xg .
`remainder of the division of
`
` is the
`
`) . This is
`The first step in decoding is to determine if the receive word is a multiple of g x(
`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
`)(xg is nonzero, at least one error has occurred. This is the principle of CRC.
`occurred. If
`More powerful codes attempt to correct the error and use the syndrome to determine the
`locations and values of multiple errors.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`4
`
`Patent Owner Ex. 2009 Page 4
`
`-
`-
`-
`-
`-
`-
`-
`

`
`Application Report
`SPRA530
`
`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).
`
`)(
`xr
`
`In a typical coding scheme, systematic codes are used. Assume the convention that the
`)(xm to be the
`leftmost bit represents the highest degree in the polynomial. Suppose
`)(xg the generator polynomial,
`)(xc the code word polynomial and
`message polynomial,
`xgxmxc =
`)(
`)()(
` which can also be written using the systematic form
`we have
`=
`kn +
`knxxm
`)(
`)(
`)(
`xxmxc
`)(xg
`)(xr
` by
` is the remainder of the division of
`, where
`)(xr
`)(xc contains k-information
` represents the CRC bits. The transmitted message
`and
`kn-
` CRC bits, for example,
`bits followed by
`-------
`=
`+
`+
`+
`1
`1
`n
`kn
`kn
`)(
`...
`xmxc
`xm
`x
`r
`. So encoding is straightforward:
`0
`1
`1
`kn
`k
`knx -
`kn-
`)(xm by
` bits to the message, calculate the CRC bits
`, that is, append
`knxxm
`kn-
`)(
`)(xg , and append the resulting
` CRC bits to the message.
` by
`by dividing
`)(' xc
`For the decoding part, the same algorithm can be used. If
` is the received
`)(' xc
` is a multiple of
`message, then no error or undetectable errors have occurred if
`knxxc
`)('
`)(xg , that is, if
`)(xg , which is equivalent to determining that if
` is a multiple of
`knxxc
`)('
`)(xg is 0.
` by
`the remainder of the division from
`
`multiply
`
`+
`
`r
`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
`CRC-CCITT (X25)
`CRC-32 (Ethernet)
`
`GSM TCH/FS-HS-EFS
`(Channel coding for speech traffic
`channels)
`GSM TCH/EFS pre-coding
`(Preliminary channel coding for Enhanced
`Full Rate)
`GSM control channels – FIRE code
`(Channel coding for control channels)
`
`Generator Polynomial
`+
`+
`+
`12
`16
`15
`x
`x
`x
`+
`+
`+
`+
`+
`12
`11
`22
`16
`23
`x
`x
`x
`x
`x
`++
`+
`+
`+
`+
`7
`5
`2
`8
`4
`1
`xxxxxx
`++ xx
`3
`1
`
`32
`x
`
`+
`26
`x
`+
`10
`x
`
`+
`
`+
`+
`+
`+
`8
`4
`3
`12
`xxxx
`
`40
`x
`
`+
`
`26
`x
`
`+
`
`23
`x
`
`+
`
`17
`x
`
`+
`
`+
`13
`x
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`5
`
`Patent Owner Ex. 2009 Page 5
`
`-
`-
`-
`-
`-
`

`
`Application Report
`SPRA530
`
`Algorithms for CRC Computation
`
`Bitwise Algorithm
`
`The bitwise algorithm (CRCB) is simply a software implementation of what would be done
`in hardware using a linear feedback shift register (LFSR). Figure 1 illustrates a generic
`hardware implementation. The shift register is driven by a clock. At every clock pulse, the
`input data is shifted into the register in addition to transmitting the data. When all input
`bits have been processed, the shift register contains the CRC bits, which are then shifted
`out on the data line.
`
`Figure 1. CRC Generation Using a Linear Feedback Shift Register (LFSR)
`
`g1
`
`g2
`
`gn–k–1
`
`r0
`
`+
`
`r1
`
`+
`
`r2
`
`+
`
`rn–k–1
`
`+
`
`m(x)
`
`c(x
`
`In the software implementation, the following algorithm can be used:
`
`Assume now that the check bits are stored in a register referred as the CRC register, a
`software implementation would be:
`
`1) CRC  0
`
`2)
`
`if the CRC left-most bit is equal to 1, shift in the next message bit, and XOR the CRC
`register with the generator polynomial; otherwise, only shift in the next message bit
`
`3) Repeat step 2 until all bits of the augmented message have been shifted in
`
`Faster implementations can be achieved by handling the data as larger units than bits, as
`long as the size does not exceed the degree of the generator polynomial. However, the
`speed gain corresponds to a memory increase, since precomputed values (lookup tables)
`will be used.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`6
`
`Patent Owner Ex. 2009 Page 6
`
`

`
`Application Report
`SPRA530
`
`Lookup Table Algorithms
`
`])('
`
`=
`+
`=
`+
`kn
`)(
`)(
`)(
`)()(
`)(
`xrxgxaxrxmxxc
` is
`)(xr
`, where
`A code word can be written as
`)(xm . Let us augment the message by a
`the CRC polynomial of the input message
` bits.
`= a
`--a
`+
`=
`+
`+
`1
`a
`)('
`)(
`)(
`)(
`...
`xbxcxxm
`xbxb
`b
`We therefore have
`, where
` is the new
`0
`1
`added a
`)(' xmx kn-
`-bit word. The CRC of the augmented message is the remainder of
`[
`=
`kn
`. Expanding the
`divided by
`. We have
`)('
`)(xg , let us call it
`)(' xr
`xmxRxr
`)
`(
`xg
`dividend, we obtain:
`
`]
`---
`a
`a
`a
`+
`+
`+
`=
`=
`kn
`kn
`kn
`)(
`)(
`)('
`)(
`)()(
`)(
`xbxcx
`xxmx
`xrxxgxaxxbx
`])(
`a+
`=
`kn
`. Expanding the result, we have
`)(
`)('
`xrxxbxRxr
`]
`)
`(
`xg
`+----- aa
`
`-------- a a
`+
`=
`+
`+
`+
`+
`1
`kn
`kn
`kn
`)
`(
`)
`)('
`(
`r
`r
`x
`x
`rb
`x
`bRxr
`
`0
`)
`(
`kn
`kn
`kn
`xg
`
`[
`
`[
`[
`
`1
`
`1
`
`...
`
`
`
`, so that,
`
`
`
`1
`
`1
`
`+
`
`
`
`+
`
`a
`xr
`0
`
`[
`
`The last equation relates the check bits of the augmented message with the check bits of
`a=
`- kn
`the original message. Note that if
`, then
`]kn
`+-----
`---
`a
`=
`+
`+
`+
`+
`kn
`1
`. Different algorithms for CRC
`)('
`(
`)
`(
`...
`)
`bRxr
`x
`r
`rb
`x
`a
`a
`kn
`kn
`xg
`)
`(
`0
`1
`1
`)(' xr
`computation may be viewed as methods to compute
` from
`)(xr
` and
`)(xb . Practical
`values for a
` are 8 or 16, since it corresponds to many machine word lengths.
`
`Standard Lookup Table Algorithm
`
`The idea behind the standard lookup table algorithm is to precompute the CRC values of
`a2
`kn-
`-bit word values are necessary,
`(
`)
`all augmented bits combinations. Therefore,
`which limits practical implementations to small a
` values.
`
`)01,...,r
`
`
`
` bits to 0
`
`Assume now that the check bits are stored in a register named CRC, the algorithm will be
`<a
`kn-
`(if
`):
`1) CRC  0, that is, set the (
`r kn --
`2) XOR the a
`that is, XOR with the (
`
` input bits with the CRC register content shifted right by
`r
`r
`1,...,
`- - - -
`n k
`n k
`
`)
`
`a
`
`--
`kn
`
`a
`
`bits,
`
` bits
`
`3)
`
`find the corresponding value in the lookup table and XOR the CRC register content
` bits, that is, XOR with the (
`)01,...,r
`shifted left by a
` bits. This is the new CRC
`r -a
`
`value.
`
`4) Repeat steps 2 to 3 until you reach the end of the message.
`In the case where a = -n
`k , steps 2) and 3) will be slightly different:
` input bits with the CRC register, that is, XOR with the (
`2) XOR the a
`r kn
`--
`
`)
`
` bits
`
`1,..., r0
`
`
`
`3) Find the corresponding value in the lookup table. This is the new CRC value.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`7
`
`Patent Owner Ex. 2009 Page 7
`
`-
`-
`-
`

`
`Application Report
`SPRA530
`
`Reduced Lookup Table Algorithm
`
`+-- a1
`
` is equal to
`
`]i
`
` with
`
`This algorithm is a variant of the standard lookup table algorithm to fit applications where
`memory space is of primary importance. The amount of required memory to store the
`n k-
`lookup table is significantly reduced and equal to a
` (
`)
`-bit words. The basic idea is
`]kn
`[
`+-----
`---
`a
`+
`+
`+
`+
`1
`kn
`(
`)
`(
`...
`)
` into the sum
`to split the expression
`bR
`r
`x
`rb
`x
`]kn
`]
`[
`[
`a
`a
`1
`)
`(
`0
`1
`kn
`kn
`xg
`+-----
`---
`a
`+
`+
`+
`+
`1
`kn
`(
`)
`...
`(
`)
`. Each term of the sum can be
`bR
`r
`x
`rbR
`x
`]i
`[
`a
`a
`1
`)
`(
`)
`(
`0
`1
`xg
`kn
`kn
`xg
`+------- a
`a
`+
`+
`1
`kn
`)
`either 0 or 1. If
`(
`(
` is 0, then
`)
`r
`bR
`b
`i r ikn
`x
`[
`
`
` ----- a
`1
`)
`(
`1
`1
`1
`ikn
`xg
`i
`
`
`0. So you only need to precompute a
`kn
` values corresponding to
`xg xR
`)
`(
`=
`a
`<a
`kn-
`,...,0
`)1
`(
`. The algorithm will be (if
`):
`i
`1) CRC  0, that is, set the (
`)01,...,r
`
`r kn --
`2) XOR the a
` input bits with the CRC register content shifted right by a
`
`the ( )a----
`,...,
` bits
`r
`r
`1
`kn
`kn
`3) on each bit of this value (a
` bits), if it is equal to 1 then find the corresponding value in
`the lookup table and XOR the CRC register content with it
`
` bits to 0
`
` bits, XOR with
`
`4) XOR this value with the CRC shifted left by a
`bits. This is the new CRC value.
`
` bits, that is, XOR with the(
`
`r
`a - 1
`
`,...,
`
`r
`0
`
`)
`
`5) Repeat steps 2 to 4 until you reach the end of the message.
`In the case where a = -n
`k , steps 2) and 4) will be slightly different:
` input bits with the CRC e.g. XOR with the (
`2) XOR the a
`r kn
`--
`
`1,..., r0
`
`
`
`)
`
` bits,
`
`4) The value computed in step 3) is the new CRC value
`
`Note that only step 3 differs from the standard lookup table algorithm. As expected, there
`is an increase of processing due to the fact that each bit must be tested and if it is equal
`to 1 then a XOR operation must be performed.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`8
`
`Patent Owner Ex. 2009 Page 8
`
`-
`-
`-
`

`
`Application Report
`SPRA530
`
`TMS320C54x Implementation
`
`General Considerations
`
`The TMS320C54x DSP is a 16-bit fixed-point DSP. Interesting for the implementation of
`the examples given:
`
`X 40-bit Arithmetical and Logical Unit (ALU)
`
`X Two 40-bit accumulators (A and B)
`
`X Efficient memory addressing modes
`
`X Multiple bus structure
`
`X Barrel shifter
`
`CRC codes with a size smaller than 40 bits are relatively easy to implement. Depending
`on the type of algorithm used, 8-, 16-, or up to 32-bit data is used.
`
`Results
`
`Tables 2 to 6 illustrate the results obtained from simulation done on 256 input words,
`which were randomly generated by a C-program using the rand() function. CRCB, CRCT,
`and CRCR are the function names corresponding, respectively, to the bit-wise algorithm,
`standard lookup table algorithm, and reduced lookup table algorithm. You can refer to the
`assembly code in the appendixes.
`
`As expected from the theory, we have a trade-off between memory requirement and
`processing speed between the different algorithms. One trade-off is that the reduced
`look-up table algorithm does not offer any advantage over the two others; this is
`understandable, since in both cases, testing of all input bits must be performed.
`
`CRC-CCITT
`
`The standard lookup table algorithm is 2.7 times faster than the bit-wise
`implementation, but requires 16.5 times more memory, due to the lookup table
`essentially (see Table 2).
`
`Table 2. Benchmarks for CRC-CCITT
`
`Program†
`10
`(17§)
`10
`(23§)
`15
`(26§)
`
`Data†
`–
`
`1
`
`–
`
`Tables†
`–
`
`256
`
`16
`
`Algorithm
`CRCB
`
`CRCT
`
`CRCR
`
`Cycles
`91‡
`(25343§)
`12¶
`(9472§)
`91‡
`(25602§)
`† Number of 16-bit words.
`‡ To process one word. Includes return instruction.
`§ To process array of 256 words. Includes function calls, returns, main loop, and
`specific initialization.
`¶ To process one byte. Includes return instruction.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`9
`
`Patent Owner Ex. 2009 Page 9
`
`

`
`Application Report
`SPRA530
`
`CRC-32
`
`The standard lookup table algorithm is 3.8 times faster than the bit-wise
`implementation, but requires 10.7 times more memory, due to the lookup table
`essentially (see Table 3).
`
`Table 3. Benchmarks for CRC-32
`
`Algorithm
`CRCB
`
`CRCT
`
`CRCR
`
`Program†
`12
`(34§)
`11
`(24§)
`22
`(28§)
`
`Data†
`16
`
`–
`
`2
`
`Tables†
`–
`
`512
`
`32
`
`Cycles
`139‡
`(37693§)
`13¶
`(9984§)
`16‡
`(42750§)
`† Number of 16-bit words
`‡ To process one word. Includes return instruction.
`§ To process array of 256 words. Includes function calls, returns, main loop, and
`specific initialization.
`¶ To process one byte. Includes return instruction.
`
`CRC for GSM/TCH
`
`Only one algorithm has been implemented (see Table 4) due to the small CRC size
`(3 bits). The lookup table oriented algorithms would have required to work on 3-bit
`entities that are not really supported efficiently by the TMS320C54x architecture.
`
`Table 4. Benchmarks for GSM/TCH
`
`Algorithm
`CRCB
`
`Program†
`10
`(21§)
`–
`–
`
`Data†
`–
`
`–
`–
`
`Tables†
`–
`
`–
`–
`
`Cycles
`89‡
`(24859§)
`CRCT¶
`–
`CRCR¶
`–
`† Number of 16-bit words
`‡ To process one word. Includes return instruction.
`§ To process array of 256 words. Includes function calls, returns, main loop, and
`specific initialization.
`¶ To process one byte. Includes return instruction.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`10
`
`Patent Owner Ex. 2009 Page 10
`
`

`
`Application Report
`SPRA530
`
`CRC for GSM/TCH/EFS Precoder
`
`The standard lookup table algorithm is 3 times faster than the bit-wise
`implementation, but requires 16.2 times more memory, due to the lookup table
`essentially (see Table 5).
`
`Table 5. Benchmarks for GSM/TCH/EFS Precoder
`
`Algorithm
`CRCB
`
`CRCT
`
`CRCR
`
`Program†
`10
`(17§)
`6
`(19§)
`14
`(25§)
`
`Data†
`–
`
`1
`
`–
`
`Tables†
`–
`
`256
`
`8
`
`Cycles
`91‡
`(25343§)
`8¶
`(8448§)
`53¶
`(31486§)
`† Number of 16-bit words
`‡ To process one word. Includes return instruction.
`§ To process array of 256 words. Includes function calls, returns, main loop, and
`specific initialization.
`¶ To process one byte. Includes return instruction.
`
`GSM FIRE Code
`
`The reduced lookup table algorithm is not implemented, because it would not have had
`any advantages over the bit-wise algorithm. This is even more obvious than for the
`previous codes, since the FIRE code is 40 bits long and fetching 40 bits from memory
`requires extra overhead.
`
`The standard lookup table algorithm is 2.7 times faster than the bit-wise
`implementation, but requires 14.3 times more memory, due to the lookup table
`essentially (see Table 6).
`
`Table 6. Benchmarks for GSM FIRE Code
`
`Algorithm
`CRCB
`
`CRCT
`
`Program†
`12
`(40§)
`18
`(33§)
`–
`
`Data†
`–
`
`–
`
`–
`
`Tables†
`–
`
`768
`
`–
`
`Cycles
`137‡
`(37258§)
`20¶
`(13570§)
`CRCR¶
`–
`† Number of 16-bit words
`‡ To process one word. Includes return instruction.
`§ To process array of 256 words. Includes function calls, returns, main loop, and
`specific initialization.
`¶ To process one byte. Includes return instruction.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`11
`
`Patent Owner Ex. 2009 Page 11
`
`

`
`Application Report
`SPRA530
`
`Summary
`
`Three CRC computation algorithms and their implementation using the TMS320C54x
`DSP have been considered in this application report, as well as various commonly used
`CRC codes.
`
`The bit-wise algorithm and the standard lookup table algorithm appear to be the most
`appropriate depending on the application requirements, that is, memory usage or
`computation time optimization. The results of the simulation based on five CRC codes
`show that the standard lookup table algorithm is about 3 times faster, but requires about
`14 times more memory than the bit-wise algorithms.
`
`The code provided in this application report is easily adaptable to other CRC codes and
`should provide you a good startup point, when considering implementation of cyclic
`redundancy check.
`
`Code Availability
`
`The associated program files are available from Texas Instruments TMS320 Bulletin
`Board System (BBS). Internet users can access the BBS via anonymous ftp.
`
`References
`1. Ramabadran T.V., Gaitonde S.S., “A tutorial on CRC computations”, IEEE Micro, Aug
`1988
`2. ETSI GSM 05.03 Specification, “Channel Coding” , August 1996, Version 5.2.0.
`3. John G. Proakis, “Digital Communications”, 3rd edition.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`12
`
`Patent Owner Ex. 2009 Page 12
`
`

`
`Application Report
`SPRA530
`
`Appendix A CRC-CCITT Listing†
`
`************************************************************
`
`**
`
` (C) Copyright 1997, Texas Instruments Incorporated
`
`**
`
`***********************************************************
`
` .mmregs
` .def Entry, Reset
` .title "CRC CCITT"
`
`genCRC .set 1021h ; Generator CRC Polynomial value
` ; g(x) = x16 + x12 + x5 + 1
`inport .set 0h ; IO address
`
` .asg NOP,PIPELINE
`
`************************************************************
`
`* Stack setup
`* Reset vector
`
`************************************************************
`BOS .usect "stack",0fh ; setup stack
`TOS .usect "stack",1 ; Top of stack at reset
`
` .sect "vectors"
`Reset:
` bd Entry ; reset vector
` stm #TOS,SP ; Setup stack
`
`************************************************************
`
`* Main Program
`
`************************************************************
` .sect "program"
`Entry
` .include "c5xx.inc"
`
` ld #crc,DP ; scratch pad mem -> DP=0
`
` portr #inport,@nbDataIn ; nb words
` addm #-1,@nbDataIn ; for repeat
`
`† Part of the tables are truncated.
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`13
`
`Patent Owner Ex. 2009 Page 13
`
`

`
`Application Report
`SPRA530
`
`************************************************************
`* CRCB (word wise)
`
`************************************************************
` stm #input,AR2 ; copy inputwords in RAM
` rpt @nbDataIn ;
` portr #inport,*AR2+ ; read them from IO space
`
` ld #genCRC,16,B ; BH = CRC gen. poly.
` mvdm @nbDataIn,AR1 ; AR1 = length of message
` stm #input,AR2 ; AR2 points to input word
`
` ld *AR2+,16,A ; initialize CRC register
`next calld CRCB ; perform CRC computation
` or *AR2+,A
` nop
` banz next,*AR1- ; process all input words
`
` sth A,@crc ; store result in memory
`
`************************************************************
`
`* CRCT (byte wise)
`
`************************************************************
`
` stm #input,AR2 ; AR2 points to inputword
` mvdm @nbDataIn,AR1 ; AR1 = length of message
` ld #0,A ; clear Acc A
` rsbx SXM ; no sign extension
`
` stm #t_start,AR3 ; AR3 = LTU start address
`next1 calld CRCT ; process LSByte
` ld *AR2,-8,B ; BL = LSByte
` ld *AR2+,B
` calld CRCT ; process MSByte
` and #0FFh,B ; BL = MSByte
` banz next1,*AR1-
`
` stl A,@crc ; store result
`
`************************************************************
`
`* CRCR (word wise)
`
`************************************************************
`
` stm #input,AR2 ; AR2 points to inputword
` mvdm @nbDataIn,AR1 ; AR1 = length of message
` ld #0,A ; clear Acc A
`
` stm #rtw_start-1,AR3 ; AR3=LTU start address-1
`next2 xor *AR2+,A ; AL = CRC XOR inputWord
` calld CRCRW ; process input word
` and #0FFFFh,A
` banzd next2,*AR1-
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`14
`
`Patent Owner Ex. 2009 Page 14
`
`

`
`Application Report
`SPRA530
`
` stm #rtw_start-1,AR3 ; AR3=LTU start address-1
`
` stl A,@crc ; store result
`
`done b done
`
`************************************************************
`
`* CRCB routine : bit-wise CRC calculation
`
`* input : 1) 16-bit input words in AL
`* 2) CRC generator polynomial in BH
`* 3) OVM = 0
`* ouput : CRC value in AH
`
`* BRC, REA, RSA, A, C, SP modified
`
`* Code size = 10 words
`* Cycles = 11 + 5*N = 91 for N = 16 bits
`
`* A = |A31.............A16 A15................A0|
`* <------ CRC ------> <---- input bits---->
`
`* B = |B31.............B16 B15................B0|
`* <-- polynomial --->
`
`************************************************************
`CRCB stm #16-1,BRC ; BRC = 16-1
` rptb CRC_end-1 ; repeat block
` sftl A,1,A ; A = A << 1, C=MSB
` PIPELINE
` PIPELINE
` xc 1,C ;
` xor B,A ; if C=1,
` ; AH = new CRC
` ; = AH XOR gen.
`CRC_end ret ; end of repeat
`
`************************************************************
`
`* CRCT routine : standard lookup table CRC calculation
`* with bytes as input
`
`* input : 1) 8-bit words in AL
`* 2) AR3 = LTU start address
`* 3) DP = 0 = DP(temp)
`* 4) SXM = 0
`* ouput : CRC value in AL
`
`* A, B, AR4, SP modified
`
`* code size = 10 words
`* cycles = 12 cycles
`
`Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x
`
`15
`
`Patent Owner Ex. 2009 Page 15
`
`

`
`Application Report
`SPRA530
`
`* A = |A31.............A16 A15................A0|
`* <------- CRC ------->
`
`* B = |B31........................B7........B0|
`* <-- input-->
`
`************************************************************
`CRCT ; AL (low part of Acc A) = CRC bits
` stl A,-8,@AR4 ; AR4 = CRC >> 8
` stl A,8,@temp ; temp = CRC << 8
` xor @AR4,B ; B = (inputByte) XOR (CRC>>8)
` ; = Offset in LTU
` adds @AR3,B ; B = Offset + LTU start address
` stlm B,AR4 ; AR4 = absolute address in LTU
` retd
` ld @temp,A ; AL = CRC << 8
` xor *AR4,A ; AL = new CRC
`
`************************************************************
`
`* CRCRW routine : reduced lookup table CRC calculation
`* with words as input
`
`* input : 1) 16-bit words in AL
`* 2) AR3 = LTU start address - 1
`* ouput : CRC value in AL
`
`* A, B, C, AR3, BRC, RSA, REA, SP modified
`
`* Code size = 15 words
`* Cycles = 11 + 5*N = 91 for N = 16 bits
`
`* A = |A31.............A16 A15................A0|
`* <------- CRC ------->
`
`************************************************************
`CRCRW
` stm #16-1,BRC ; BRC = 16-1
`