Method, apparatus, and product for use in generating CRC and other remainder based codes

[0001] This application claims priority under 35 USC section 119(e) of provisional application No. 60/183,197, filed on Feb. 17, 2000, entitled “Method and Apparatus for Rapidly Generating CRC Block Codes”.

[0002] Information systems are often exposed to noise and/or other phenomenon, which can lead to data errors. The data errors may occur during any of various processes including, but not limited to, during transmitting, storing, and/or retrieving of data. Consequently, various methods have been developed to help detect and/or correct errors should they occur.

[0003] It is known that signals may be represented as data (e.g., a message, word, byte, etc.) that may be viewed as a number or sequence of numbers (e.g., binary data may be viewed as a binary number). Any such number can be divided by a divisor (e.g., a binary number) to generate a remainder, which may be treated as a type of signature and used to detect errors in the data. For example, assume that the data to be transmitted represents a value of 82. The data can be divided by a predetermined divisor, for example, 7, to generate a remainder, e.g., 5. The remainder may be treated as a signature and transmitted along with the data. Then, if the received data is 81 rather than 82, the receiver, using the same predetermined divisor, will generate a remainder of 4 rather than 5, thereby indicating that the received data has an error.

[0004] Some systems employ cyclic redundancy check (“CRC”) codes, which also may be viewed as a type of signature, to detect errors. For example, in some communication systems, a sender having a block of data to be transmitted, generates a CRC code for the block of data, and transmits both the block of data and the associated CRC code as an appended “checksum.” The transmitted data and associated CRC code reach a receiver, which generates a CRC code for the received data block, and compares such CRC code to that transmitted by the sender, to determine whether the received data has an error.

[0005] Some CRC codes may be understood at least in part by recognizing that at least some data (for example, at least some binary data) may be viewed as representing a kind of polynomial (for example, the data may be viewed as representing coefficients of a polynomial in a dummy variable “x”), and by recognizing that the polynomial may be divided by a second polynomial to generate a remainder. The second polynomial is commonly referred to as a CRC polynomial and is typically known to the sender and the receiver and selected for certain properties which are well documented in literature. The CRC code is, or is based at least in part, on the remainder. By carefully selecting the CRC polynomial, any single bit error causes the remainder generated by the receiver to differ from the remainder generated by the sender, and to therefore be detectable.

[0006] Accordingly, it should be understood that although the discussion hereinbelow refers occasionally to polynomials, we are actually referring to processing data and are viewing the data as a polynomial or as terms of a polynomial to facilitate explanation only.

[0007] For example, FIG. 1A shows a representation of a block of binary data D₁, which is made up of a sequence of bit values “1101011011”. The leftmost bit is the MSB, and the rightmost bit is the LSB. The sequence may be viewed as a series of bits representing the coefficients a₉ . . . a₀ of a polynomial in powers of a variable “x” (a₉x⁹+a₈x⁸+a₇x⁷+a₆x⁶+a₅x⁵+a₄x⁴+a₃x³+a₂x²+a₁x¹+a₀x⁰+) which would thus have the following terms: 1x⁹+1x⁸+0x⁷+1x⁶+0x⁵+1x⁴+1x³+0x²+1x¹+1x⁰, (i.e., reducing to x⁹+x⁸+x⁶+x⁵+x³+x+1). The LSB, “1”, represents the coefficient of the x⁰ term. The second most LSB, “1”, represents the coefficient of the x¹ term. The third most LSB, “0”, represents the coefficient of the x² term, and so on, such that the MSB, “1”, represents a coefficient of a x⁹ term. Note that because the sequence is made up of binary values, all of the coefficients are either “1” or “0”. Hereafter, when we refer to a bit sequence as representing a polynomial, we mean that the bits represent the coefficients of the polynomial including terms with zero coefficients, or the coefficients of only non-zero terms, as appropriate.

[0008] FIG. 1B shows a representation of a bit string made up of a sequence “10011”, which may be viewed as representing a polynomial that has the following terms: x⁴+x+1, and serves as the CRC polynomial in this example. The degree of this CRC polynomial is four, based on the term having the highest exponent, i.e., x⁴.

[0009] In this example, the polynomial represented by the data D₁ is to be divided by the CRC polynomial to generate a remainder. Referring to FIG. 1C, for purposes of this example, a number D₂ of “0” bits is first appended to the LSB of the block of data D₁, so that the remainder will have a particular form. The number of bits appended is chosen to be equal to four, the degree of the CRC polynomial. Thus, the block of data and the appended bits collectively make up the sequence “11010110110000”. This sequence may be viewed as representing a polynomial x¹³+x¹²+x¹⁰+x⁸+x⁷+x⁵+x⁴.

[0010] FIG. 2A shows the sequence D₃ of bits “11010110110000”, formed by the block of data and the appended bits (FIG. 1C), being divided by the sequence D₄ of bits “10011”, shown in FIG. 1B representing the CRC polynomial. It can be seen that the result at each step depends on results of the preceding steps. An error in any bit location in sequence D₃ typically causes the remainder D₅ to differ from the expected remainder. In this example, the sequence “1110”, represents the remainder, which may be viewed as representing a polynomial x³+x²+x.

[0011] It should be recognized that subtraction steps employed in remainder calculation are typically not carried out using common binary subtraction but rather are carried out using modulo-two arithmetic and modulo-two subtraction. Addition and subtraction of polynomials has been developed from algebraic field theory. More specifically, if the data is binary-valued and the polynomials have binary-valued coefficients, the arithmetic is carried out over a Galois Field of 2.

[0012] FIG. 2B illustrates algebraic rules for binary-valued data over a Galois Field of 2. Note that there is no “carrying” in the algebraic rules for addition at 50, and no “borrowing” in the algebraic rules for subtraction at 52. As such, the algebraic rules for addition and the algebraic rules for subtraction are similar to modulo-two arithmetic and modulo-two subtraction, respectively, and are sometimes implemented using an EXCLUSIVE-OR function. The algebraic rule for multiplication, at 54, is sometimes implemented using an AND function.

[0013] While the above discussion and example are helpful to understand CRC codes, it should be understood that a system may employ CRC codes without any express reference to polynomial division. In practice, CRC methods have been implemented in a variety of ways, including, but not limited to, using a linear feedback shift register, a look up table, and/or combinations thereof.

[0014] FIG. 2C and FIG. 2D show examples of linear feedback shift registers (LFSR's). FIG. 2C shows one type of prior art LFSR 60 that is sometimes referred to as a back loaded LFSR. This particular back loaded LFSR 60 has a sixteen bit shift register 62, referred to as the CRC register, and further includes three XOR gates 64, 66, 68 operatively connected to the CRC register 62 as follows so as to enable the LFSR 60 to generate a CRC code for data based on a CRC polynomial having the following terms: x¹⁶+x¹⁵+x²+0.

[0015] An output of a sixteenth bit 70, i.e., the MSB, of the CRC register is supplied to a first input of each of the XOR gates 64, 66, 68. The XOR gate 64 has a second input that receives the block of data D on a line 72, one bit at a time starting with the MSB of the block of data D, as further described below. An output of the XOR gate 64 is supplied on a line 74 to an input of a first bit 76, i.e., the LSB of the CRC register 62. The XOR gate 66 has a second input that receives an output of a second bit 78 of the CRC register 62 on a line 80. An output of the XOR gate 66 is supplied on a line 82 to an input of a third bit 84 of the CRC register 62. The XOR gate 68 has a second input that receives an output of a fifteenth bit 86 of the CRC register 62 on a line 88. An output of the XOR gate 68 is supplied on a line 90 to an input of the MSB 70 of the CRC register 62.

[0016] LFSR's such as that of FIG. 2C are often implemented in hardware and driven by a clock. It is common to append bits to the block of data D, for example as discussed above with respect to FIG. 1C, so that the remainder will have a particular form.

[0017] In operation, the CRC register 62 is often initialized (e.g., each bit in the CRC register is set to a logic “0” state) prior to use. At a first clock pulse, the MSB of the block of data D for which a CRC is desired is supplied through the XOR gate 64 to the LSB 76 of the CRC register 62. Every clock pulse thereafter, the data in the CRC register 62 is shifted one bit to the left and the next most MSB of the block of data D is supplied to the LSB 76 of the CRC register 62, by way of the XOR gate 64. If the MSB 70 of the CRC register 62 has a logic “1” state, then the bits of the CRC register 62 supplied by the XOR gates 64, 66, 68 are XOR'd with a logic state “1”. If the last bit appended to the block of data D has been shifted into the CRC register 62, then the contents of the CRC register 62 indicates the remainder for the block of data D.

[0018] FIG. 2D shows a prior art LFSR 100 that is of a type sometimes referred to as a front loaded LFSR. With the front loaded LFSR 100 of FIG. 2D, there is often no need to append bits to the data D. As with the LFSR 60 of FIG. 2C, this front loaded LFSR 100 has a sixteen bit CRC register 102, and further includes three XOR gates 104, 106, 108 operatively connected to the CRC register 102 so as to enable the LFSR 100 to generate a CRC code for the data D based on a CRC polynomial having the following terms: x¹⁶+x¹⁵+x²+0.

[0019] The XOR gates 104, 106, 108 are connected to the CRC register 102 and the data D is presented to the LFSR 100 as follows. An output of a sixteenth bit 110, i.e., the MSB, of the CRC register 102 is supplied on a line 112 to a first input of one of the XOR gates 104. The XOR gate 104 has a second input that receives the block of data D, one bit at a time starting with the MSB, on a line 114 as further described below. An output of the XOR gate 104 is supplied on a line 116 to an input of each of the other XOR gates 106, 108. The XOR gate 106 has a second input that receives an output of a second bit 118 of the CRC register 102 on a line 120. An output of the XOR gate 106 is supplied on a line 122 to an input of a third bit 124 of the CRC register 102. The XOR gate 108 has a second input that receives an output of a fifteenth bit 126 of the CRC register 102 on a line 128. An output of the XOR gate 108 is supplied on a line 130 to an input to the MSB 110 of the CRC register 102.

[0020] At a first clock pulse, an MSB of the block of data D and the output of the MSB 110 of the CRC register 102 are supplied to the XOR gate 104. Every clock pulse thereafter, the data in the CRC register 102 is shifted one bit to the left and the next most MSB of the data D is supplied to the XOR gate 104. If the output of the XOR gate 104 has a logic “1” state, then the bits of the CRC register supplied by the XOR gates 106, 108 are XOR'd with a logic state “1”. If the last bit of the block of data D has been supplied to the XOR gate 104, then the contents of the CRC register 102 indicates the remainder for the block of data D.

[0021] FIG. 2E shows a functional block diagram of one type of prior art table driven implementation 140 for generating a CRC code. This particular table driven implementation 140 utilizes a 16 bit shift register 142 as the CRC register and is sometimes referred to as back loaded, as is the LFSR of FIG. 2C. A Look Up Table 144 is used to store a plurality of values, e.g., 256 16-bit values. It is common to append bits to the data D, for example as discussed above with respect to FIG. 1C, so that the remainder will have a particular form. In operation, bits are shifted as groups, e.g., 8 bits, into and out of the CRC register 142. Groups of bits into the CRC register 142 are supplied from the data D on lines 145. Groups of bits out of the CRC register 142 are supplied on lines 146 to the Look Up Table 144 and used to identify a location in the Look Up Table 144. The 16 bit value at the indentical location of the Look Up Table is output on lines 148 and XOR'd 150 with the 16 bit CRC register 142, and the result is stored in the CRC register 142. The operation is repeated until all of the bits that have been appended to the data D have been shifted into the CRC register 142. Then, the contents of the CRC register 142 indicates the remainder for the data D.

[0022] FIG. 2F shows a functional block diagram of another type of prior art table driven implementation 160 for generating a CRC code. This particular table driven implementation 160 utilizes a 16 bit shift register 162 as the CRC register and is sometimes referred to as front loaded, as is the LFSR of FIG. 2D. A Look Up Table 164 is used to store a plurality of values, e.g., 256 16 bit values. In operation, groups of bits, e.g., 8 bits, are shifted out of the CRC register 162 on lines 166 and XOR'ed 168 with a group of bits, e.g., 8 bits, shifted in from the data D for which a CRC code is desired. The result of the XOR'ing is supplied on lines 170 and used to identify a location in the Look Up Table 164. The data, e.g., the 16 bit value, at the indentified location in the Look Up Table is supplied on lines 172 and XOR'ed 174 with the 16 bit CRC register 162, and the result is stored in the CRC register 162. The operation is repeated until all of the bits of the data D have been supplied to the XOR 168, wherein the contents of the CRC register 162 then indicates the remainder for the data D.

[0023] FIG. 2G is a flowchart 180 of one prior art algorithm for carrying out a table driven implementation. The CRC register is initialized at a step 182, e.g., by setting all of the bits to a logic “0” state. At a step 184, a group of bits are shifted out of the CRC register and a group of bits are shifted in from the data D for which a CRC code is desired. A value of a register referred to as Table Index is set equal to a result of XOR'ing the group of bits shifted in from the data D with the group of bits shifted out from the CRC register. At a step 186, the CRC register is set equal to a result of XOR'ing the CRC register with the data in the Look Up Table at the location identified by the value of the Table Index register. At step 188, a determination is made as to whether there are any nore bits to shift in from the data D. If there are more bits to shift in, then execution returns to the step 184. If there are no more bits to shift in, then the algorithm ends and the content of the CRC register indicates the remainder for the data D.

[0024] FIG. 2H is a flowchart diagram 190 of another prior art algorithm for carrying out a table driven implementation. The algorithm of FIG. 2H is similar to the algorithm of FIG. 2G except that the algorithm of FIG. 2H is intended for use in association with a processor having a pipelined architecture in which an instruction may be initiated before a preceding instruction is completed. The CRC register is initialized at a step 192, e.g., by setting all of the bits to a logic “0” state. At a step 194, a group of bits are shifted out of the CRC register and a group of bits are shifted in from the data D for which a CRC code is desired. A value of a register referred to as Table Index is set equal to a result of XOR'ing the group of bits shifted in from the data D with the group of bits shifted out from ate CRC register. A WAIT step 196 provides a delay to make sure that the previous step 194 is complete before proceeding to a subsequent step 198 in the algorithm. At the step 198, the CRC register is set equal to a result of XOR'ing the CRC register with the data in the Look Up Table at the location identified by the value of the Table Index register. The WAIT step 196 is needed because the step 198 requires the result from the step 194, yet as stated above, the pipeline architecture enables an instruction to be initiated before a proceeding instruction is complete. Another WAIT step 200 provides a delay to make sure that the step 198 is complete before proceeding to subsequent steps in the algorithm. At a step 202, determination is made as to whether there are any more bits to shift in from the data D. If there are more bits to shift in, then execution returns to the step 194. If there are no more bits to shift in, then the algorithm ends and the contents of the CRC register indicates the remainder for the data D. The WAIT step 200 is needed because the step 194 requires the result fit it the step 198. The duration of the WAIT step 200 is typically greater than that of the WAIT step 196 because more time is typically needed to complete the step 198 that is needed to complete the step 194.

[0025] Because of the WAIT steps 196, 200, the algorithm is not able to fully utilize the pipelined architecture for computation of the CRC. It should be understood however, that during the WAIT steps 196, 200, the pipelined architecture processor may perform other computations, unrelated to computation of the CRC.

[0026] In some communication systems, such as for example those that employ packet switching, parts of a block of data may be received or generated out of order. If such systems use CRC codes for error detection, the system often waits idle until all of the parts of the block of data have been received or generated, and only then generates and evaluates the CRC code for the block of data. In such systems, it would be desirable to be able to begin generating the CRC code as the parts of the block of data are received or generated, so that the amount of time needed to complete the CRC code, measured from the point in time that the final part of the block of data is received or generated, is reduced. It would be desirable to be able to spread the computational burden over a large fraction of the duration during which the parts of the data is being received or generated.

[0027] Ng et al. have suggested a parallel realization for generating the CRC for the header that carries routing information in an asynchronous transfer mode (ATM) protocol (See “Parallel realization of the ATM cell header CRC”, School of Electrical Engineering, University of New South Wales, Sydney 2052, Australia.). However, such realization is somewhat analogous to a look up table and does not overcome the shortcomings described above.

[0028] It has been determined that the task of generating a CRC code for data can be accomplished by generating a plurality of preliminary CRC codes and by synthesizing the CRC code in response at least in part to the preliminary CRC codes.

[0029] According to a first aspect of the present invention, a method implemented by a data processor includes generating a plurality of preliminary CRC codes in response at least to specified data, and synthesizing a CRC code for the specified data, in response at least to the plurality of preliminary CRC codes.

[0030] In accordance with one embodiment, generating a plurality of preliminary CRC codes comprises partitioning the specified data into at least two portions, and generating at least two preliminary CRC codes, each being associated with and being generated in response at least to a respective one of the at least two portions.

[0031] According to another aspect of the present invention, a data processor includes means for generating, a plurality of preliminary CRC codes in response to specified data, and means for synthesizing a CRC code for the specified data, in response at least to the plurality of preliminary CRC codes.

[0032] Here, when we use the term “in response to” we mean “in response at least to”, so as not to preclude being responsive to more than one thing.

[0033] According to another aspect of the present invention, a data processor generates a plurality of preliminary CRC codes in response to specified data, and synthesizes a CRC code for the specified data, in response to the plurality of preliminary CRC codes.

[0034] According to another aspect of the present invention, an information system includes at least one data processor that generates a plurality of preliminary CRC codes in response to portions of specified data, and synthesizes a CRC code for the specified data in response to the plurality of preliminary CRC codes.

[0035] According to another aspect of the present invention, a product includes, a computer readable media, and information stored on the computer readable media to cause a computer to carry out a method for generating a CRC code for specified data, the method including generating a plurality of preliminary CRC codes in response to the specified data, and synthesizing a CRC code for the specified data, in response to the plurality of preliminary CRC codes.

[0036] According to another aspect of the present invention, a communication signal includes information to cause a computer to carry out a method for generating a CRC code for specified data, the method including generating a plurality of preliminary CRC codes in response to the specified data, and synthesizing a CRC code for the specified data, in response to the plurality of preliminary CRC codes.

[0037] One or more embodiments of one or more aspects of the present invention may be used to reduce the amount of time required to generate a CRC code and thereby improve performance, of a system utilizing CRC codes for error detection. For example, some communication systems use a protocol wherein the sender transmits a first block of data but does not transmit a second block of data until the receiver sends a reply indicating that the first block of data has been specified and that no errors have been detected. If such systems use CRC codes for error detection, the receiver must generate and evaluate the CRC code before the sender will begin transmitting the second block of data. Thus, the time required for the receiver to generate the CRC becomes a limitation on system performance. This problem can become more significant as system requirements increase and thereby lead to demands for greater bandwidth or throughput (e.g., higher effective bit rates). While one might expect that the advent of systems having multiple processors could help alleviate the problem above, this is not necessarily the case. For example, as to prior art methods that generate CRC codes in a serial fashion, each step depends on the results of the preceding steps. It is thus difficult for such prior art methods to take advantage of multiple processors to achieve faster CRC, code generation.

[0038] It has been recognized that aspects of the present invention are not limited to CRC codes, but rather may be applied to remainder-based codes and operations in general, where a quotient is net absolutely required. CRC codes can be viewed as one category of remainder-based codes. Another category of remainder-based operations is cryptographic systems. In some applications of cryptographic systems, large keys are manipulated (mod n). One or more aspects of the present invention have applicability to remainder-based codes and operations in general, including but not limited to CRC codes and cryptographic systems. Further, one or more particular embodiments of the invention may be used to greatly reduce the time needed to manipulate large keys that may be associated with cryptographic systems.

[0039] However, it should be understood that there is no requirement that any of the aspects of the present invention address the short comings of the prior art.

[0067] FIG. 3A is a schematic block diagram of a communication system 210 in which various embodiments of the present invention may be used. Communication systems are one type of information system and are used to transfer information, for example between a source and a destination, via a communication link, or transmission channel. Examples of communication systems include dedicated point-to-point systems, wired networks, cellular telephone systems, and a data bus between components of a system, e.g., between a CPU and a storage device and/or between storage devices. A storage medium such as a magnetic disk also may be viewed as a communication link (or portion thereof), with a read/write head being both sender and receiver. It should be further understood that the present invention may be used by any type of information system including but not limited to communication systems.

[0068] The communication system 210 comprises a sender 212, a receiver 214, and a communication link 216 coupled therebetween. The communication link 216 may be any type of communication link, including but not limited to, for example, wired (e.g., conductors, fiber optic cables) or wireless (e.g, microwave links, satellite links, ), and combinations thereof, each of which may be public or private, dedicated, and/or shared, e.g., a network. The communication link 216 may employ circuit switching or packet switching, or combinations thereof. A communication link may employ any protocol or combination of protocols including but not limited to the Internet Protocol. The sender 212 and the receiver 214 may each include any type of interface to the communication link 216, including but not limited to for example, a modem, an Ethernet interface, a wireless interface, or any combination thereof.

[0069] FIG. 3B shows a representation 220 of data which is sought to be transferred from the sender 212 to the receiver 214. The data may be any type of information including, but not limited to, message data, non-message data, and combinations thereof. Generally speaking, data may be from any source. For example, in regard to data residing within the sender 212, the data may be from one or more sources external to the sender 212, sources internal to the sender 212, or any combination thereof. The data may have any form, including, but not limited to, a sequence of binary values, i.e. a bit string. The data may or may not be divided into blocks (e.g., blocks 222, 224) as shown. If divided into blocks, the amount of data in a block may be predetermined (e.g., specified and/or agreed upon in advance) or determined dynamically, and may be fixed (e.g., uniform) or variable.

[0070] It should be further understood that the present invention is not limited to data that is to be transferred from the sender to the receiver but rather may be used with any specified data including, but not limited to, data that is to be transferred, data that has been received, data that has been received and modified, data that has been generated in response to data that has been received, data that is to be used to generate data that is to be transferred, or any other data that is neither to be transferred nor has been received. As used herein, the term specified is defined as to be specified by any source including, but not limited to, the sender, the receiver, the system, or any combination thereof. The data may be specified in any way, shape or form.

[0071] The sender 212 generates one or more CRC codes for the data. For example, if the data is divided into blocks, then the sender 212 may generate a CRC code for each one of the blocks of data. The characteristics of the CRC code are typically known by the sender 212 and the receiver 214, but may or may not be predetermined, and may or may not be uniform.

[0072] There are many different types of CRC codes, a few of which are listed below:

[0073] (1) reflected data implementations;

[0074] (2) reversed data implementations;

[0075] (3) reversed polynomial implementations;

[0076] (4) initialized value implementations;

[0077] (5) reversed final value implementations;

[0078] (6) XOR'ed initial value implementations;

[0079] (7) XOR'ed final value implementations;

[0080] These and some of the other types of CRC codes are discussed in, among others, the following references: Patrick Geremia, Application Report SPRA530, Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54×, Digital Signal Processing Solutions, April 1999, pages 1-35; Ross N. Williams, “A Painless Guide to CRC Error Detection Algorithms”, ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc v3.txt Aug. 19, 1993, pages 1-32 (includes “Program for Writing CRC Lookup Table”, Jun. 3, 1993 and header file for the reference implementation of the Rocksoft TM model CRC Algorithm); Terry Ritter, “The Great CRC Mystery”, Dr. Dobb's Journal of Software Tools, http://www.io.com/-ritter/ARTS/CRCMYST.HTM, February 11(2): 26-34, 76-83, Listing One (CRCLIST1.HTM), pages 1-7, Listing Two (CRCLIST2.HTM), pages 1-10 February 1986; Seong Leong Ng and Bill Dewar, Computer Communications 19 (1996) 257-263 “Parallel Realization of the ATM Cell Header CRC, School of Electrical Engineering, University of New South Wales, Sydney 2052, Australia, pages 258-263; R. J. Glaise, “A Two-Step Computation of Cyclic Redundancy Code CRC-32 for ATM Networks, http://www.research.ibm.com/journal/rd/416/flaise.txt 1997, pages 1-5; Andrew S. Tanenbaum, Computer Networks, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981, pages 129-133.

[0081] Referring to FIG. 3C, the data and any CRC code(s), e.g., 232, 234, may be combined to form a data stream 230. The data stream 230 may or may not be supplied directly to the communication link 216 (FIG. 3A). For example the data stream 230 may be supplied to the communication link 216 (FIG. 3A) by way of one or more encoders that encode the data stream 230, for example, to compress the data stream 2320.

[0082] In the embodiment of FIG. 3C, each CRC code, e.g., 232, 234 is appended to the associated data block, e.g., 222, 224, respectively. It should be understood however, the CRC code(s) and the data may be combined in any way. For example, in other embodiments, the CRC code need not be appended to the associated block of data, but rather, may be positioned anywhere and or may be integrated with the associated data block. Further, in some embodiments, the sender 212 combines the CRC code with the data in such a way that the result represents a polynomial that is evenly divisible by a CRC polynomial. In such embodiments, the receiver 214 may perform a cyclic redundancy check on the data and CRC code, as combined, and may assume that there is no error if the remainder is equal to zero.

[0083] The size of the CRC code may depend on the CRC polynomial, and may be small relative to the size of the block of data, although none of these are requirements for the present invention. The size of the CRC code is often a number in a range of three bits to thirty-two bits, inclusive.

[0084] It has been determined that the task of generating a CRC code for data can be accomplished by generating a plurality of preliminary CRC codes based on the data, at least in part, and by synthesizing the CRC code for the data based on the preliminary CRC codes, at least in part. A preliminary CRC code is defined herein as a CRC code that is not the CRC code for the data but rather is used in the generation of the CRC code for the data.

[0085] Before proceeding, we first provide an example, using decimal values, that demonstrates how a remainder may be synthesized based on a plurality of preliminary remainders. Assume again that the data represents a value of 82, which can be divided by a divisor, for example, 7 to generate a remainder. It has been recognized that the value 82 may be expressed as follows:
82=80+2  eq. 1
=(8*10)+2  eq. 2
and that:
 82/7=((8*10)+2)/7  eq. 3
remainder (82/7)=remainder (((8*10)+2)/7)  eq. 4

[0086] The following relations can be adapted to the above, for example to help generate the remainder:
(a+b)mod c=(a mod c)+(b mod c)  eq. 5
(a*b)mod c=(a mod c)*(b mod c)  eq. 6

[0087] Using equations 5 and 6, the expression on the right side of equation 4 can be expanded as follows:
remainder(82/7)=remainder((8*10)/7)+remainder (2/7)  eq. 7
remainder(82/7)=remainder(8/7)*remainder(10/7)+remainder(2/7)  eq. 8

[0088] The remainder quantities in the expression on the right side of equation 8 are examples of preliminary remainders. The remainder of 82/7 may be generated from these preliminary remainders in accordance with the expression on the right side of equation 8 as follows:
remainder(82/7)=1*3+2  eq. 9
=5  eq. 10

[0089] FIGS. 4A through FIG. 4F, shows an example, using binary valued data, of how a CRC code for data may be generated by generating a plurality of preliminary CRC codes based on the data, at least in part, and by synthesizing the CRC code for the data based on the preliminary CRC codes. In this example, the data is a block D of bits comprising the bit string “11010110110000” of FIG. 1C. As stated above with respect to FIG. 1C, the block D can be viewed as representing a polynomial that has the terms x¹³+x¹²+x¹⁰+x⁸+x⁷+x⁵+x⁴. The CRC polynomial is the CRC polynomial of FIG. 1B, represented by the bit string “10011”, which as stated above with respect to FIG. 1B, may be viewed as representing a polynomial that has the terms x⁴+x+1.

[0090] Referring to FIG. 4A, in this example, a first step in generating a plurality of preliminary CRC codes is to partition the block D into portions e.g., two portions P₀ and P₁. Here, the first portion P₀ comprises a bit sequence “0110000”, i.e., bit zero through bit six of the block D. The second portion P₁ comprises a bit sequence “1101011”, i.e., bits seven through thirteen of block D.

[0091] The portions P₀ may be viewed as representing a polynomial and the portion P₁ can be viewed as representing a polynomial. In this view, the first portion P₀ can be viewed as representing a polynomial having terms: x⁵+x⁴. The second portion P₁ can be viewed as representing a polynomial having terms: x⁶+x⁵+x³+x+1.

[0092] However, the portions can also be viewed as representing portions of the polynomial represented by the block of data D. In this view, the first portion P₀ represents the x⁵+x⁴ terms of the polynomial represented by the block D. The second portion P₁ represents the x¹³+x¹²+x¹⁰+x⁸+x⁷ terms of the polynomial represented by the block D. These terms represented by the second portion P₁ can be expressed as a product of two factors: (x⁶+x⁵+x³+x+1)*x⁷. The factor x⁷ is indicative of the position of the second portion P₁ within the block of data, and more particularly, indicative of the bit-wise position of the LSB of the second portion P₁ within the block of data. Consequently, for other portion sizes, an appropriate factor may be other than x?

[0093] Thus, as to the polynomial, P_D represented by the block of data D, the following relation can be stated:
P_D=(x⁶+x⁵+x³+x+1)*x⁷+(x⁵+x⁴)  eq. 11
=P₁*x⁷+P₀  eq. 12

[0094] where P_D=polynomial represented by the block of data D

• • [0095] P₁=polynomial represented by the second portion P₁
  • [0096] P₀=polynomial represented by the first portion P₀

[0097] To generate the CRC code in this example, it is desired to determine the remainder of a polynomial division operation in which the dividend is the polynomial represented by the block D, and the divisor is the CRC polynomial. As to the remainder, the following relation can be stated:
remainder (P_D)=remainder (P₁*x⁷+P₀)  eq. 13

• • [0098] where remainder (P_D)=remainder of (polynomial represented by (D) divided by the CRC polynomial)
  • [0099] remainder (P₁*x⁷+P₀)=remainder of (polynomial represented by P₁*x⁷+P₀ divided by the CRC polynomial)

[0100] The following relations can be adapted to help generate a remainder for the block D based on portions of the block D:
(a+b)mod c=(a and c)+(b mod c)  eq. 14
(a*b)mod c=(a mod c)*(b mod c)  eq. 15

[0101] So that, as to the remainder(P_D), the expression on the right side of eq. 3 can be expanded to obtain the following:
remainder (P_D)=remainder (P₁*x⁷)+remainder (P₀)  eq. 16
remainder (P_D)=remainder(P₁)*remainder(x⁷)+remainder(P₀)  eq. 17

[0102] FIG. 4B through FIG. 4E show a representation of steps that may be used to compute the remainders in the expression co the right side of eq. 17.

[0103] Referring to FIG. 4B, the second portion P₁ which as stated above represents the polynomial x⁶+x⁵+x³+x+1, is divided by the bit string “10011”, representing the CRC polynomial x⁵+x⁴, to generate a bit string “00001” representing a remainder of 1.

[0104] Referring to FIG. 4C, the polynomial x₇, represented by the bit sequence “10000000”, primarily on the size of the CRC polynomial, rather than the size of the data block. The product represents the remainder for the terms x¹³+x¹²+x¹⁰+x⁸+x⁷ of the polynomial represented by the block of data D. As stated above, the terms x¹³+x¹²+x¹⁰+x⁸+x⁷ are the polynomial terms represented by the block D that are represented by the second portion P₁ of the block D.

[0105] Referring to FIG. 4E, the first portion P₀, i.e., the bit sequence “0110000”, which as stated above represents the polynomial x⁵+x⁴, is divided by the bit string “10011”, representing the CRC polynomial, to generate a remainder “0101”, which represents the polynomial x₂+1. This remainder is not only the remainder for the polynomial represented by the first portion P₀, but is also the remainder for the x⁵+x⁴ terms of the polynomial represented by the block D. As stated above, the x⁵+x⁴ terms are the non-zero terms of the polynomial represented by the first portion P₀ of the block D.

[0106] Referring to FIG. 4F, the remainder of the division of FIG. 4E, i.e., represented in this instance by the bit string “0101”, is added to the product of FIG. 4D, i.e., represented in this instance by the bit string “1011”, to generate a bit sequence “1110”, representing a polynomial x³+x²+x. This sum represents the remainder for the polynomial represented by the block of data D.

[0107] It should be recognized that the remainder produced in FIG. 4F for the polynomial represented by the block of data D, is identical to the remainder generated by the prior art in the example shown in FIG. 2A.

[0108] Referring again to FIG. 4F, in the event that the remainder is greater than or equal to the CRC polynomial, then the remainder may be further reduced by dividing the remainder by the CRC polynomial so as to obtain a remainder that is less than the CRC polynomial, i.e., the divisor.

[0109] Thus, FIGS. 4A through 4F show one example of how to accomplish the task of generating a CRC code for a data block by generating a plurality of preliminary CRC codes based on the data block (at least in part), and by synthesizing the CRC code for the data block based on the preliminary CRC codes (at least in part).

[0110] As stated above, the polynomial term x⁷ in equations 11-13, 16 and 17, and which is represented by the bit string “10000000” in FIG. 4C, is indicative of the position of the second portion P₁ within the block of data, and more particularly, indicative of the bit-wise position of the LSB of the second portion P₁ within the block of data. Hereafter a polynomial indicative of the position of a portion P₁ will be generalized as x^startj, where portion P_j has an LSB located at bit position startj within the block of data.

[0111] Note that the remainder for x⁷ (more generally x^startj where startj is equal to 7), need not be computed (FIG. 4C) every tie but rather the remainder may be computed once (or alternatively, predetermined), stored and accessed as needed. As used herein, generating includes generating in any way including but not limited to computing, accessing predetermined stored data (e.g., in a look up table), and/or combinations thereof.

[0112] It should be recognized that the example of FIGS. 4A-4F is presented only for illustrative purposes, and that the present invention is not limited by the example. Furthermore, it should be understood that the various aspects of the present invention may be embodied without any reference to polynomials or polynomial division, which are merely an analytical tool.

[0113] In some embodiments, the remainders for the two portions may be generated (e.g., FIG. 4B, FIG. 4E) in parallel (i.e., concurrently or partially concurrently) with one another. For example, the block of data D may be partitioned into two approximately equal size portions (e.g., as shown in FIG. 4A by portions P₀ and P₀) whereby the elapsed time required to generate the two remainders will be approximately one-half the time required to generate the remainder without partitioning (FIG. 2A). A multiply operation (e.g., FIG. 4D), an addition operation (e.g., FIG. 4F), and if necessary, a reduction operation (e.g., if the sum is greater than or equal to the CRC polynomial, see discussion above with respect to FIG. 4F) may be performed, resulting in a remainder for the block of data D (e.g., FIG. 4F). For such example, the time required to generate a remainder for an N-bit data block may be approximated as:
t_crc2(n)=t_crc(n/2)+m  eq. 18

[0114] where t_crc(n)=the amount time required to generate a remainder for an N-bit block of data wit out partitioning the block of data, and

[0115] m=the amount of time required for a multiply operation, as addition operation, and if needed, a further reduction operation.

[0116] A reduction by fifty percent in the amount of time needed to generate a CRC code can prove a significant improvement in the performance of some systems, particularly in those systems where the amount of time needed to generate a CRC code has a significant impact on system throughput.

[0117] Nonetheless, it should be recognized that there is no requirement that CRC codes be generated in parallel or that the time required to generate a CRC code be expressed by eq. 18.

[0118] FIG. 5A is a schematic block diagram of a data processor 240 according to one embodiment of one aspect of the present invention, which may, for example, be used in the communication system 210 of FIG. 3A to generate a CRC code for a block of data D.

[0119] As used herein, the term data processor is defined as any type of processor. For example, the data processor may be programmable or non-programmable, general purpose or special purpose, dedicated or non-dedicated, distributed or non-distributed, shared or not shared, and/or any combination thereof. A data processor may comprise hardware, software, firmware, hardwired circuits and or any combination thereof. The data processor may or may not include one or more computer program with one or a plurality of subroutines, or modules, each of which includes a plurality of instructions to be executed by the data processor, and may or may not perform tasks in addition to those associated with generating a CRC code. If the data processor includes more then one module, the modules may be parts of one computer program, or may be parts of separate computer programs.

[0120] The data processor 240 includes a partitioner 242 which receives a block of data D and partitions the block of data D into a plurality of portions, e.g., k portions shown as a first portion P₀ through a kth portion P_k−1. As used herein, the term portion is defined as any part or parts of the data. The portions may have any form and may be generated in any way. A portion may, for example, be a part of a bit string. If a portion comprises a plurality of bits, the bits need not be adjacent to one another in the block of data. The portions may or may not be physically separated from one another. Portions may overlap or not overlap. The number and/or size of each of the plurality of portions may or may not be predetermined. Although the first portion P₀ and the kth portion P_k−1 are shown as approximately equally sized and non-overlapping, there are no such requirements. In some embodiments, it may be advantageous to partition the bit string such that the portions do not have the same number of bits as one another, as discussed hereinbelow.

[0121] FIG. 5B shows characteristics 244 of one embodiment of the partitioner 242. This embodiment of the partitioner 242 receives a block of data D that comprises a bit string, and partitions the bit string into k portions, P₀ through P_k−1. The bit string has N bits including an LSB, bit 0, and an MSB, bit N−1. Portion P₀ comprises bit start P₀ (i.e., the LSB, bit 0) of the data string trough bit end P₀ of the data string. Portion P₀ comprises bit start P_j of the data string through bit end P_j of the data string. Portion P_k−1 comprises bit start P_k−1 of the data string through bit end P_k−1 (i.e., the MSB, bit N−1) of the data string.

[0122] Referring again to FIG. 5A, the plurality of portions are supplied to a preliminary CRC code generator 246, which further receives data representing a CRC polynomial on a line 248. Any CRC polynomial may be used. The CRC polynomial is known by the sender 212 and the receiver 214, and may or may not be fixed. The CRC polynomial may have any form, including but not limited to, a sequence of binary values, i.e., a bit string.

[0123] The preliminary CRC code generator 246 generates data indicative of a plurality of CRC codes, e.g., m CRC codes, which may be identified as CRC code₀ through CRC code_m−1, referred to hereafter as preliminary CRC codes, or PCRC codes, so as to distinguish them from the CRC code that is to be generated in response to the preliminary CRC codes or PCRC codes. In some embodiments, each of the plurality of PCRC codes is associated with a respective one of the plurality of portions of the data block. The value of m may or may not be equal to the value of k. The plurality of PCRC codes are preferably generated independently of one another, and may or may not be generated in parallel with one another. As used herein, independent of one another is defined as not dependent on one another. Generated in parallel is defined as to be generated at least partially concurrently with one another. To operate in parallel with one another is defined as to operate at least partially concurrently with one another.

[0124] The plurality of PCRC codes are supplied on a plurality of lines 250 to a CRC synthesizer 252, which synthesizes data indicative of a CRC code for the block of data D in response thereto. As used herein, the term synthesize is defined as to generate in any way, shape or form, but does not include simply appending the plurality of PCRC codes to one another.

[0125] As stated above, the term in response to is defined herein as in response at least to, so as not to preclude being responsive to more than one thing. Similarly, the term in response thereto is defined herein as in response at least thereto, so as not to preclude being responsive to more than one thing.

[0126] As used herein, a CRC code, which includes PCRC codes, is defined as anode having a specified relation to data indicative of a remainder. The specified relation may be any type of relation, or any combination of any type of relations. It should be understood that data indicative of a remainder may be generated with or without the use of actual division.

[0127] A CRC code is one category of remainder-based codes. As stated above, it has been recognized that aspects of the present invention are not limited to CRC codes, but rather may be applied to remainder based codes and operations in general, where a quotient is not absolutely required. Another category of remainder based operations is employed in cryptographic, systems. In some applications of cryptographic systems, large keys are manipulated (mod n). One or more aspects of the present invention have applicability to remainder-based codes and operations in general, including but not limited to, CRC codes and cryptographic systems. Further, one or more particular embodiments may be used to greatly reduce the time needed to manipulate large keys that may be associated with cryptographic systems.

[0128] Some examples of embodiments for generating CRC codes having a specified relation to data indicative of a CRC remainder include, but are not limited to:

[0129] (1) reflected data implementations;

[0130] (2) reversed data implementations;

[0131] (3) reversed polynomial implementations;

[0132] (4) initialized value implementations;

[0133] (5) reversed final value implementations;

[0134] (6) XOR'ed initial value implementations;

[0135] (7) XOR'ed final value implementations;

[0136] Further, the specified relation may be predetermined and fixed, but is not limited to such. For example, one specified relation may be uniformly applied to all blocks of data, or a specified relation used for some Meeks of data or some portions may be different than that used for other blocks of data D or ether portions.

[0137] As used herein, the term a CRC code for data includes, but is not limited to:

[0138] (1) a code having a specified relation to data indicative of a CRC remainder for the data; and

[0139] (2) a code having a specified relation to data indicative of a CRC remainder for data having a specified relation to the data.

[0140] The CRC code may be generated in any manner, including but not limited to, serial implementation, parallel implementation, and any combination thereof. The CRC code may be of any type and in any form. For example, in one embodiment the data indicative of a CRC code comprises signals retained in memory that coexist with one another. In another embodiment, the data indicative of a CRC code comprises signals that are not retained and/or do not coexist.

[0141] A PCRC code may or may not be associated with one of the portions. If a PCRC code is associated with one of the portions, then it is generated in response to that portion but need not be a PCRC code for that portion. As used herein the term a PCRC code for a portion includes, but is not limited to:

[0142] (1) code having a specified relation to data indicative of a CRC remainder for a portion;

[0143] (2) a code having a specified relation to data indicative of a CRC remainder for data to having a specified relation to a portion.

[0144] The partitioner 242, the preliminary CRC code generator 246 and the CRC code synthesizer 252 may be programmable or non-programmable, general purpose or special purpose, dedicated or non-dedicated, distributed or non-distributed, shared or not shared, and/or any combination thereof. The partitioner 242, the preliminary CRC code generator 246 and the CRC code synthesizer 252 may each comprise hardware, software, firmware, hardwired circuits and/or any combination thereof. The partitioner 242, the preliminary CRC code generator 246 and the CRC code synthesizer 252 may or may not include one or a plurality of subroutines, or modules, each of which includes one or a plurality of instructions to be executed by the data processor 240, and may or may not perform tasks in addition to those associated with generating a CRC code.

[0145] FIG. 6 illustrates another embodiment 260 of the data processor 240 of FIG. 5A. This embodiment of the data processor includes a partitioner 262 that receives a block of data D and partitions the block of data D into exactly two portions, i.e., a first portion P₀ and a second portion P₁. The first portion P₀ and the second portion P₁ are supplied on lines 263, 264 to a preliminary CRC code generator 266, which further receives data indicative of a CRC polynomial on a line 268 and generates two PCRC codes. One of the PCRC codes, referred to as PCRC code for P₀, is associated with the first portion P₀ of the data block. The other of the PCRC codes, referred to as PCRC code for P₁, is associated with the second portion P₁ of the data block. The data indicative of the PCRC code associated with the first portion P₀ and the data indicative of the PCRC code associated with the second portion P₁ are supplied on lines 270, 272 to a CRC synthesizer 274 that combines the PCRC codes for the two portions, to generate data indicative of a CRC code for the data D.

[0146] FIG. 7 shows one illustrative embodiment 280 of the data processor 260 of FIG. 6A. In this embodiment; a preliminary CRC code generator 280 comprises a first preliminary CRC code generator 284 and a second preliminary CRC code generator 286. The first one of the preliminary CRC code generators 284 receives data indicative of the first portion P₀ and data representing a CRC polynomial on a line 288, and generates a PCRC code for the first portion P₀. The second one of the CRC generators 286 receives data indicative of the second portion P₁ and data representing the CRC polynomial on a line 288, and generates a PCRC code for the second portion P₁. The two preliminary CRC code generators 284, 286 may or may not be identical, and may or may no operate in parallel with one another.

[0147] The data indicative of the PCRC code associated with the first portion P₀, CRC P₀, and the data indicative of the PCRC code associated with the second portion P₁, CRC P₁, are supplied on lines 288, 290 respectively, to a CRC synthesizer 292, which combines the PCRC codes for the portions to generate the data indicative of a CRC code for the block of data D.

[0148] FIG. 8A shows one embodiment 300 of the data processor 280 of FIG. 7, and which may for example be used to carry out the operations shown in the example of FIGS. 4A-4F. In this embodiment 300, the data processor includes a partitioner 302 that receives a block of data D representative of a bit string. Referring to FIG. 3B, the bit string has N bits including an LSB, bit 0, and an MSB, bit N−1. The partitioner 302 partitions the bit string into exactly two portions, portion P₀ and portion P₁. Portion P₀ comprises bit start P₀ (i.e., the LSB, bit 0) of the data string through bit end P₀ of the data string. Portion P₁ comprises bit start P₁ of the data string through bit end P_k−1 (i.e., the MSB, bit N−1) of the data string.

[0149] FIG. 8C shows an example of the operation of the partitioner 302. In this example, the block of data D is the bit string “11010110110000” of FIG. 1C. As stated above with respect to FIG. 1C, the block of data D can be viewed as representing coefficients of a polynomial that thus has the following terms: x¹³+X¹²+x¹⁰+x⁸+x⁷+x⁵+x⁴.

[0150] The partitioner 302 partitions the bit string into two portions. The first portion P₀ comprises a bit sequence “0110000”, i.e., bit zero through bit six of the block of data D. The second portion P₁ comprises a bit sequence “1101011”, i.e., bit seven through bit thirteen of the block of data D. Thus, in this example, start P₀ is equal to zero. End P₀ is equal to six. Start P₁ is equal to seven. End P₁ is equal to thirteen.

[0151] The portions P₀ and P₁ can themselves be viewed as representing coefficients of polynomials. In this view, the first portion P₀, i.e., the bit sequence “0110000”, represents a polynomial having terms: x⁵+x⁴. The second portion P₁, i.e. the bit sequence “1101011”, can be viewed as representing coefficients of a polynomial having terms: (x⁶+x⁵+x³+x+1).

[0152] In addition, because the block of data D can be viewed as representing a polynomial, the partitioner 302 can be viewed as partitioning the polynomial into two portions. In this view, the first portion P₀, i.e., the bit sequence “0110000”, represents the terms x⁵+x⁴. The second portion P₁, i.e. the bit sequence “1101011”, represents the terms x¹³+x¹²+x¹⁰+x⁸+x⁷. The latter terms can be factored as (x⁶+x⁵+x³+x+1)*x⁷, and can be expressed as (x⁶+x⁵+x³+x+1)*x^startj, where start_j is equal to seven. Note that the term x⁷ could be represented by a bit string “10000000”.

[0153] A first one of the preliminary CRC code generators 303 includes a CRC remainder generator 304 that receives data indicative of the first portion P₀ on a line 305 and data indicative of the CRC polynomial on a line 306 and generates data indicative of a CRC remainder for portion P₀.

[0154] A second one of the preliminary CRC code generators 308 has a first CRC remainder generator 310 that receives the data indicative of the second portion P₁ on a line 312 and data indicative of the CRC polynomial on the line 306, and generates data indicative of a CRC remainder for the second portion P₁. A second CRC code generator 314 receives data indicative of a polynomial x^star1 on a line 316 and data on the line 306 indicative of the CRC polynomial, and generates data indicative of a CRC remainder for the polynomial x^start1. The data indicative of a CRC remainder for the second portion P₁ and the data indicative of a CRC remainder for polynomial x^start1 are supplied on lines 318, 320 to a multiplier. The multiplier generates data indicative of a product of the two CRC remainders.

[0155] The second one of the CRC code generators includes a CRC remainder generator that receives data indicative of the first portion P₀ and data indicative of the CRC polynomial and generates data indicative of a CRC remainder for portion P₀.

[0156] A CRC synthesizer 322 has an adder 324 that receives the multiplier output data indicative of the product of the two CRC remainders on a line 326, and the data indicative of a CRC remainder for portion P₀ on a line 328. The adder 324 generates data indicative of a sum at line 330, which is supplied to a conditional CRC remainder generator 332. If a polynomial represented by the data indicative of the sum is greater than or equal to the CRC polynomial, then the conditional CRC remainder generator 332 performs a further reduction by dividing the polynomial sum by the CRC polynomial to obtain a remainder which may be used to generate the CRC code for the data D. If a polynomial represented by the data indicative of the sum is not greater than or equal to the CRC polynomial, then the data indicative of the sum is already the remainder, and the conditional CRC remainder generator 332 does not perform a further reduction.

[0157] Each of the CRC remainder generators 304, 310, 314 may be any type of CRC remainder generator, including but not limited to a serial type or a parallel type, table-driven or non- table driven, a bit-by-bit or a multi-bit (e.g., a byte) type, and/or any combination thereof. One or more of the CRC remainder generators 304, 310, 314 may or may not employ a linear feedback shift register (LFSR). Any particular CRC remainder generator need not be the same as any of the other CRC remainder generators.

[0158] In one embodiment, data indicative of a CRC remainder for polynomial x^start1 is stored in the CRC remainder generator 314. If the data indicative of a CRC remainder for polynomial x^start1 is stored in the CRC remainder generator 314, then the CRC remainder generator 314 may generate the remainder for polynomial x^start1 by accessing the stored data, rather than by actually computing the remainder for polynomial x^start1.

[0159] FIG. 9 is a flowchart diagram 350 showing steps carried out by one embodiment of a data processor that generates k portions to generate a CRC code for a block of data D. A block of data is partitioned into k portions at a step 352 or block, the k portions being referred to herein as portion P₁ through P_k−1. At a step 354, a CRC remainder is generated for each of the k portions, the CRC remainder for the j^th portion referred to herein as CRC remainder P_j. At a step 356, a CRC remainder is generated for each of k−1 polynomials, the j^th polynomial being referred to herein as x^startj, the CRC remainder for the j^th polynomial being referred to herein as CRC remainder x^startj. At a step 358, a product is generated for each of portions P₁ through portion P_k−1, according to the equation (CRC remainder P_j)+(CRC remainder x^startj). At a step 360, a CRC remainder for the data block is generated by summing the CRC remainder P₀ and with the k−1 products generated at the step 358. A step 362 determines whether the CRC remainder for the data block is greater than or equal to the CRC polynomial, and if so, the CRC remainder for the data block is further reduced by dividing it by the CRC polynomial.

[0160] In some embodiments, one or more PCRC codes may be generated in parallel with one another, for example to reduce the elapsed time needed to compute the CRC code for the block of data D. Consider for example, one embodiment where the block of data D is partitioned into two approximately equal size portions (e.g., as shown in FIG. 4A) and remainders for each are generated in parallel with one another. The elapsed time required to generate the two remainders is approximately one half the time required to generate the remainder without partitioning (FIG. 2A). A multiply operation(e.g., FIG. 4D), an addition operation (e.g., FIG. 4F), and if appropriate, a reduction operation(e.g., if the sum is greater than or equal to the CRC polynomial, see discussion above with respect to FIG. 4F) may be performed, resulting in a remainder for the block of data D (e.g., FIG. 4F). In regard to such embodiment, the time required to generate a remainder for an N-bit data block may be approximated as:
t_crc2(n)=t_crc(n/2)+m  eq. 18

[0161] where t_crc(n)=the amount of time required to generate a remainder for an N-bit block of data without partitioning the block of data, and

[0162] m=the amount of time required for a multiply operation, an addition operation, and if needed, a further reduction operation.

[0163] It should however, be recognized that there is no requirement that PCRC codes be generated in parallel with one another or that the time required to generate a CRC code be expressed by eq. 18.

[0164] In some embodiments, the data processor comprises a plurality of processor units, which may or may not operate in parallel with one another and may or may not be substantially identical to one another. A plurality of processor units may or may not be integrated into a single package. Examples of processors with processor units that are integrated into a single package and capable of operating in parallel with one another include but are not limited to TigerSHARC and Hammerhead processors available from Analog Devices of Norwood, Mass.; C6X processors available from Texas Instruments, Inc. of Dallas, Tex.; and Power PC processors available from Motorola of Schaumburg, Ill. The processor may be, but does not need to be, of a type that employs very long instruction words (VLIW).

[0165] FIGS. 10A and 10B are flowchart diagrams 370, 372 showing steps carried out in one embodiment that comprises two processors, referred to herein as processor A and processor B. The flowchart diagram 370 of FIG. 10A shows the steps carried out by processor A. The flowchart diagram 372 of FIG. 10B shows the steps carried out by processor B. Referring now to FIG. 10A, a block of data is partitioned into k portions at a step 374, the k portions being referred to herein as portion P₀ through P_k−1. In this embodiment, processor A (FIG. 10A) is responsive to portions P₀ through P_(k/2)−1, and processor B (FIG. 10A) is responsive to portions P₀ through P_(k/2)−1. At a step 376, processor A generates a CRC remainder for each of portions P₀ through P_(k/2)−1, the CRC remainder for the j^th portion referred to herein as CRC remainder P_j. At a step 378, processor A generates a CRC remainder for each of (k/2)−1 polynomials, the j^th polynomial being referred to herein as x^startj, the CRC remainder for the j^th polynomial being referred to herein as CRC remainder x^startj. At a step 380, processor A generates a product for each of portions P₁ through portion P_(k/2)−1, according to the equation (CRC remainder P_j)*(CRC remainder x^startj). At a step 382, processor A generates a first part of a CRC remainder for the data block, referred to herein as CRC remainder_A, by summing the CRC remainder P₀ and the products generated at the step 380.

[0166] Referring now to FIG. 10B, at a step 384, processor B generates a CRC for each of portions P_k/2 through P_k−1, the CRC remainder for the j^th portion referred to herein as CRC remainder P_j. At a step 386, processor B generates a CRC remainder for each of k/2 polynomials, the j^th polynomial being referred to herein as x^startj, the CRC remainder for the j^th polynomial being referred to herein as CRC remainder x^startj. At a step 388, processor B generates a product for each of portions P_k/2 through portion P_k−1, according to the equation (CRC remainder P_j)*(CRC remainder x^startj). At a step 390, processor B generates a second part of a CRC remainder for the data block, referred to herein as CRC remainder_B, by summing the products generated at the step 388.

[0167] Referring again to FIG. 10A, at a step 392, a CRC remainder for the data block is generated by summing first part of a CRC remainder for the data block, CRC remainders_A, and the second part of a CRC remainder for the data block, CRC remainder_B. A step 394, determines whether the CRC remainder for the data block is greater than or equal to the CRC polynomial, and if so, the CRC remainder for the data block is further reduced by dividing it by the CRC polynomial.

[0168] In some embodiments, one or both of processor A and processor B have a pipelined architecture. For example, the TigerSHARC processor available from Analog Devices, Inc, of Norwood, Mass. comprises two processor units each having a pipelined architecture.

[0169] In some embodiments, a processor with a pipelined architecture is used to generate PCRC codes in parallel with one another. FIG. 10C is a flowchart diagram 400 of an algorithm that may be carried out in one embodiment. The algorithm may be carried out in association with a plurality of registers a CRC register0402, a CRC register1404, a Table Index0 register 406, and a Table Index1 register 408 and a Look Up Table 410(each shown in FIG. 10D) which may be located within a pipelined architecture processor 412. At a step 414, the block of data is partitioned into at least two portions, portion P₀ and portion P₁. In this embodiment, portion P₀ and portion P₁ have the same length as each other, as stated above the present invention does not require portions to have the same lengths as each other. At a step 416, the CRC register0 and the CRC register1 are initialized, e.g., by setting all of the bits to a logic “0” state. At a step 418, a group of bits are shifted out of the CRC register0 and a group of bits are shifted in from portion P₀. A value of a register referred to as Table Index0 is set equal to a result of XOR'ing the group of bits shifted in from portion P₀ with the group of bits shifted out from the CRC register0. At a step 420, a group of bits are shifted out of the CRC register1 and a group of bits are shifted in from portion P₁. A value of a register referred to as Table Index1 is set equal to a result of XOR'ing the group of bits shifted in from portion P₁ with the group of bits shifted out from the CRC register1 . At a step 422, the CRC register0 is set equal to a result of XOR'ing the CRC register0 with the data in the Look Up Table at the location identified by the value of the Table Index0 register. At a step 424, the CRC register1 is set equal to a result of XOR'ing the CRC register1 with the data in the Look Up Table at the location identified by the value of the Table Index1 register. At a step 426, a determination is made as to whether there are any more bits to shift in from P₀ and portion P₁. If there are more bits to shift in, then execution returns to the step. If there are no more bits to shift in, then the algorithm ends, wherein the contents of the CRC register0 indicates the remainder for the portion P₀ and the contents of the CRC register1 indicates the remainder for portion P₁.

[0170] Although the algorithm of FIG. 10C has zero WAIT steps, the present invention is not limited to such. For example, other embodiments for use with a pipelined architecture may have more than zero WAIT steps. However, as to the embodiment of FIG. 10C and in regard to computation of the CRC code for the block of data made up of portion P₀ and the portion P₁, this embodiment more effectively utilizes the pipelined architecture of the processor than is possible with the algorithm of FIG. 2H. As a consequence, for a given processor, block size and CRC polynomial, the elapsed time needed to generate the CRC for a block of data in this embodiment is less than that needed to generate the CRC for the block of data using the prior art algorithm shown in FIG. 2H.

[0171] In some embodiments, the algorithm of FIG. 10C, or one or more other algorithms that use a pipeline architecture to generate one or more PCRC codes in parallel with one another, with or without WAIT steps, are used in association with a data processor that comprises a plurality of processor units, where one or more of the processing units comprises a pipelined architecture. For example one embodiment uses the TigerSHARC processor available from Analog Devices, Inc, of Norwood, Mass., which comprises two processor units each having a pipelined architecture. In such embodiment, one or more other algorithms that use a pipeline architecture to generate one or more PCRC codes in parallel with one another may be carried out on one or both of the processing units.

[0172] In some embodiments, the data processor 240 (FIG. 5A) has an architecture that may be viewed as hierarchical or recursive. For example, the PCRC Code that is to be generated by the Preliminary CRC code generator 286 (FIG. 7) may itself be treated as a CRC code for data, wherein the portion P₁ is the data. Thus the CRC code for the portion P₁ may be generated based on the same principals set forth herein for generating the CRC code for the data D. That is, the CRC code for the portion P₁ may itself be generated by first generating a plurality of preliminary CRC codes in response to the portion P₁, and then generating the CRC code for the portion P₁ in response to the plurality of preliminary CRC codes. Thus, for example, in some embodiments the preliminary CRC code generator 286 may comprise a data processor in accordance with the present invention.

[0173] FIG. 11 is a schematic block diagram of another embodiment 430 of the data processor 280 of FIG. 7. The data processor 430 of FIG. 11 includes the partitioner 302 (see also FIG. 8A), a preliminary CRC code generator 432 and the CRC synthesizer 322 (see also FIG. 8A). The partitioner 302 and the CRC synthesizer 322 are the same as the partitioner 302 and the CRC synthesizer 322, respectively, of the data processor of FIG. 8A. The preliminary CRC code generator 432 has two preliminary CRC code generators 434, 436, as in the preliminary code generator of the data processor of FIG. 8A, but the second preliminary CRC code generator 436 is different than the second preliminary CRC code generator 308 of the data processor of FIG. 8A.

[0174] The first one of the preliminary CRC code generators 434 includes a CRC remainder generator 438 that receives the data indicative of the first portion P₀ at line 440 and the data indicative of the CRC polynomial at line 442. The CRC remainder generator 438 generates data indicative of a CRC remainder for portion P₀.

[0175] In this embodiment 430, the second one of the preliminary CRC code generators 436 includes a multiplier 444 which has a first input that receives data indicative of the second portion P₁ at line 446 and a second input that receives data indicative of the polynomial x^start1 at line 448. The multiplier generates data indicative of a product, P₁*x^start1, which is supplied on a line 450 to an input of a CRC remainder generator 452. The CRC remainder 452 generator further receives data indicative of a CRC polynomial on the line 442 and generates data indicative of a CRC remainder for the product P₁*x^start1. The data indicative of a CRC remainder for the product P₁*x^start1 is considered associated with the portion P₁.

[0176] The data indicative of a CRC remainder for the product P₁*x^start1 and the data indicative of a CRC remainder for portion P₀ are input on lines 454, 456 respectively, to an adder 458 that generates a sum thereof . The sum is input on a line 460 to a conditional CRC remainder generator 462, which further receives data indicative of the CRC polynomial on the line 442. If a polynomial represented by the data indicative of the sum is greater than or equal to the CRC polynomial, then the conditional CRC remainder generator 462 performs a further reduction by dividing the polynomial sum by the CRC polynomial to obtain a remainder which may be used to generate the CRC code for the data D. If a polynomial represented by the data indicative of the sum is not greater than or equal to the CRC polynomial, then the data indicative of the sum is already the remainder, and the conditional CRC remainder generator 462 does not perform a further reduction.

[0177] FIG. 12 is a flowchart diagram 500 showing steps carried out by one embodiment of a data processor that generates k portions to generate a CRC code for a block of data D. A block of data is partitioned into k portions at a step 502, the k portions being referred to herein as portion P₁ through P_k−1. At a step 504, a product is generated for each of portions P₁ through P_k−1 according to the relation (Portion P_j)*(x^startj). The product may be generated by multiplication, or, if appropriate, by appending an appropriate number of “0”'s. At a step 506, a CRC remainder is generated for portion P₀ and a CRC remainder is generated for each of the k−1 products generated in the step 504, the k−1 remainders being referred to herein as CRC remainder ((portion P_j)*(x^startj)). At a step 508 a CRC remainder for the data block is generated as a sum of all of the CRC remainders generated at the step, i.e. a summation of the CRC remainder P₀ and the k−1 remainders referred to as CRC remainder (portion P_j)+(x^startj).

[0178] A step 510 determines whether the CRC remainder for the data block is greater than or equal to the CRC polynomial, and if so, the CRC remainder for the data block is further reduced by dividing it by the CRC polynomial.

[0179] The present invention is not limited to the CRC algorithms and polynomials disclosed above. There is no intended limit to the types of CRC algorithms and polynomials that may be used. Furthermore, as stated above, it has been recognized that aspects of the present invention are not limited to CRC codes, but rather may be applied to remainder-based codes and operations in general, where a quotient is not absolutely required. CRC codes can be viewed as one category of remainder-based codes. Another category of remainder-based operations is cryptographic systems. One or more aspects of the present invention have applicability to remainder-based codes and operations in general, including, but not limited to, CRC codes and cryptographic systems.

[0180] In some embodiments that partition the block of data into portions, it may be desirable to take the size of a block into consideration when selecting the number of portions.

[0181] Although the CRC synthesizer described above synthesizes the CRC code by summing the plurality of PCRC codes the CRC synthesizer is not limited to such but rather may synthesize the CRC code in any manner with or without summing the plurality of PCRC codes.

[0182] As stated above, the method and apparatus of the present invention is not limited to use in communication transmission systems but rather may be used in any type of system including but not limited to any type of information system, e.g., transmission systems and storage systems, and/or combinations thereof.

[0183] One or more embodiments of the present invention may be employed anywhere within the information system, including but not limited to the sender, the receiver, or both sender and receiver, and for example may be used in wired interfaces (e.g., modem, Ethernet), wireless interfaces, or any combination thereof.

[0184] As further stated above, the data processor may comprise hardware, software, firmware, hardwired circuits and/or any combination thereof. If the data processor includes one or more computer programs, the one or more computer programs may be implemented as a computer program product tangibly embodied in a machine-readable storage device for execution by a computer. Further, a data processor is not limited to a particular computer platform, particular processor, or a particular programming language. Computer programming languages may include but are not limited to procedural programming languages, object oriented programming languages, and combinations thereof. A general purpose computer system may or may not execute a program called an operating system, which may or may not control the execution of other computer programs and provides scheduling, debugging, input/output control, accounting, compilation, storage assignment, data management, communication control, and/or related services.

[0185] In some embodiments, the data processor comprises at least a processing unit connected to a memory system via an interconnection mechanism. A memory system may include a computer-readable and writable recording medium. The medium may or may not be non-volatile. Examples of non-volatile medium include a magnetic disk, a flash memory, and tape. A disk may be removable, known as a floppy disk, or permanent, known as a hard drive. Examples of volatile memory include but is not limited to random access memory, such as a dynamic random access memory (DRAM) or static memory (SRAM), which may or may not be of a type that uses one or more integrated circuits to store information. A variety of mechanisms are known for managing information movement between the disk and an integrated circuit memory element.

[0186] While there have been shown and described various embodiments, it will be understood by those skilled in the art that the present invention is not limited to such embodiments, which have been presented by way of example only, and that various changes and modifications may be made without departing from the spirit and scope of the invention. Accordingly, the invention is limited only by the appended claims and equivalents thereto.