TECHNICAL FIELD

The present invention relates to a device and method for calculating a Cyclic Redundancy Check (CRC) value. In particular, the device and method can advantageous be employed for calculating an A/-b i t CRC value from N bits of data, wherein N=2 i is a natural number and M=N/ 2.

BACKGROUND In many wireless systems - such as standardized 3 GPP systems like Long-Term Evolution (LTE), Wideband Code Division Multiple Access (WCDMA), IEEE802.11 (Wi-Fi), etc. - the system includes a CRC procedure. A CRC procedure (or short only“CRC”) is an error- detecting code used to detect accidental changes to transmitted data. Blocks of the data to be transmitted get a short CRC value attached, wherein the CRC value is typically calculated based on the remainder of a polynomial division of the contents of the blocks. Thus, CRC requires the definition of polynomials.

Specific CRC types are characterised by the size and coefficients of the polynomial used as divisor. In many cases, systems are required to support multiple CRC types (generic CRC). For example, in a wireless systems such as 2G-4G, as much as 11 CRC types should be supported. However, for a system to support multiple CRC types, an important challenge is how to assign an efficient solution for each of the used polynomials.

Conventional solutions are either hardware based or are processor instructions. The latter solutions give flexibility with the polynomial types, while the first solution can be tailored to a specific polynomial. A main challenge with generic CRC is that essentially the optimal solution for each CRC type is unique. Thus, multiple CRC types may require either several numbers of different hardware designs, one for each supported polynomial (with the unavoidable consequence of high die-area size-cost) or may require one design that provides an optimal solution for only one of the polynomials, but leads to a lower performance for the other polynomials. An example of a conventional CRC method - as performed in a conventional device for supporting a generic polynomial (multiple CRC types) - is shown in FIG. 5. The device is suitable to perform CRC-32 (i.e. CRC using polynomials up to an order of 32), and thus includes a 32x32-bit matrix register for receiving up to 32x32-bit matrices as generic instructions. However, the device is rather disadvantageous, if it is used to perform CRC- 16 or lower (i.e. CRC using polynomials with an order of 16 or less). For instance, when performing CRC- 16, the conventional device first multiplies a l6x32-bit matrix with 32-bits of input data in a first cycle. This yields a first 16-bit result, which the device then multiplies with a 16x16- bit matrix in a second cycle. This yields a second 16-bit result, which the device finally adds to the first 16-bit result, in order to obtain the 16-bit CRC value as an output of the CRC- 16. Accordingly, the performance of this device is 32 bits of data per two cycles of calculation, i.e. only 16 bits of data per cycle.

As an example, for carrying out CRC- 16 of 6,400 bits, the cycle count of the conventional device is 400 (6,400/32*2=400).

As a further disadvantage, FIG. 6 shows that the conventional device of FIG. 5 does not utilize its hardware efficiently in case that a polynomial order of 16 or less is used. In particular, FIG. 6 shows that the 32x32-bit matrix register (also referred to as“table”) of the conventional device is only utilized half in the first cycle (in which it receives the l6x32-bit matrix as instruction) and only to a quarter in the second cycle (in which it receives the 16x16-bit matrix as instruction).

FIG. 7 shows another example of a conventional device, particularly one that is usable for performing up to CRC-8 (i.e. CRC using polynomials up to an order of 8). The device accordingly includes an 8-bit input register, an 8x8 matrix register, and an 8-bit output register. Further, the device includes 64 AND gates and 63 XOR gates (to perform reduction XOR). The device is with a similar configuration scalable to being suitable for CRC- 16 or CRC-32. The device, however, has the same drawbacks when performing CRC-4 (i.e. CRC using polynomials up to an order of 4) as described above for the method and device of FIG. 5. In particular, the performance of this device in terms of bits of data per cycle is not ideal and its hardware utilization is not efficient. SUMMARY

In view of the above-mentioned challenges and disadvantages, the present invention aims to improve conventional CRC devices and methods. The present invention has thereby the object to provide a generic CRC device and method providing improved performance. Thereby, the hardware utilization of the device and method should be increased compared to conventional devices and methods. Nevertheless, only a minimum of hardware should be added compared to the hardware used conventionally, in order to keep device cost and complexity low.

The object of the present invention is achieved by the solution provided in the enclosed independent claims. Advantageous implementations of the present invention are further defined in the dependent claims.

In particular the present invention proposes a forward prediction of bits within a CRC polynomial, namely by using a superposition of new input data bits and a previously calculated CRC value (output/state).

A first aspect of the present invention provides a device for calculating an \/-b i t Cyclic Redundancy Check, CRC, value from A bits of data, wherein N=2 i is a natural number and M=N! 2, the device comprising an A-bit input register configured to receive A data bits of the data, an \ /-b i t input register configured to receive M state bits, an NxN matrix register configured to receive at least one matrix, and a CRC processing unit configured to calculate, in a current cycle, a first result based on the A data bits in the A-bit input register and an MxN part of the matrix register, a second result based on the M state bits in the \ /-b i t input register and an MxM part of the matrix register, and the \ /-b i t CRC value based on the first result and the second result, wherein the CRC processing unit is further configured to provide the M- bit CRC value calculated in the current cycle to the \ /-b i t input register as the M state bits for the next cycle.

The device is in principle suitable for performing CRC-N (i.e. CRC using polynomials up to an order of N), but is highly advantageous when performing CRC-M (i.e. CRC using polynomials up to an order of M or lower).

For example, for A=32 and when performing CRC- 16, the device generates a first 16-bit result from a l6x32-bits matrix and a 32-bit vector of data bits, generates a second 16-bit result from a 16x16-bits matrix and a 16-bit vector of state bits, and generates the CRC value based on the first and second results. The 16-bit vector of the state bits is then updated in with the calculated 16-bit CRC value. Accordingly, the state bits of the next cycle base on a feedback of the CRC value of the current cycle.

The device of the first aspect uses a similar hardware as a conventional device, with only a small amount of additional hardware. With the minimum of additional hardware, the device is nevertheless able to significantly improve the speed of CRC-M (in the above example CRC- 16) and lower. In particular, the performance of the device is twice as high as that of the conventional device, while the additional hardware is only about 1% of the existing hardware.

When, for example, carrying out CRC- 16 (with L-32 and M= 16) of 6,400 bits, the cycle count of the device of the first aspect is 200 (6,400/32=200), i.e. is only half the cycle count of the conventional device shown in FIG. 5 and FIG. 6. Accordingly, the device of the first aspect is twice as fast.

The same advantages are achieved for any A and M compared to a likewise conventional device.

In an implementation form of the first aspect, the device is configured to calculate an \/-b i t CRC value from N bits of data in each of a plurality of cycles.

After each cycle, the state bits are updated accordingly. Thus, the device can operate continuously with half the cycle count per data bits than the conventional device.

In a further implementation form of the first aspect, the CRC processing unit is configured to calculate the first result by multiplying the N data bits in the A-bit input register with an MxN matrix in the MxN part of the matrix register, and the second result by multiplying the M state bits in the \/-b i t input register with an MxM matrix in the MxM part of the matrix register.

Thus, two operations in the form of two matrices can be provided in parallel in a single instruction, thereby drastically improving the throughput of the device.

In a further implementation form of the first aspect, the CRC processing unit is configured to calculate the first result and/or the second result based on a Galois field multiplication and accumulation computation.

Thus, fast parallel computation is enabled. In a further implementation form of the first aspect, the CRC processing unit is configured to calculate the A/-b i t CRC value by adding the first result and the second result.

In a further implementation form of the first aspect, the MxN part and the MxM part of the matrix register are configured to be respectively programmed with an MxN matrix and an MxM matrix.

The matrix register thus supports the performance improvement of the device.

In a further implementation form of the first aspect, the device further comprises a programming unit configured to program the NxN matrix register with two matrices.

In this way, the device can be flexibly programmed to select generically from different CRC types, and thereby shows an improved performance.

In a further implementation form of the first aspect, each matrix is calculated based on a plurality of CRC polynomials supported by the CRC processing unit.

The matrices are preferably pre-calculated based on the respective polynomials. Thus, fast CRC is enabled.

In a further implementation form of the first aspect, the V/-bit input register is configured to receive M initialization bits as the M state bits for a first cycle.

For instance, the initialization bits can be all zeros. Afterwards, i.e. starting from the second cycle, the state bits are update with the CRC output value.

In a further implementation form of the first aspect, the CRC processing unit includes N ² AND- gates and (N ² + M - 1) XOR-gates.

Compared to the conventional device, only M - 1 XOR gates are added, which only leads to a minimum increase in size and complexity.

In a further implementation form of the first aspect, the CRC processing unit is configured to calculate the first and second results by means of the N ² AND-gates and N ² XOR-gates, and to calculate the M- bit CRC value from the first and second results by means of the M - 1 XOR- gates. In a further implementation form of the first aspect, the device further comprises a first A/-bit output register configured to receive the first result, and a second M bit output register configured to receive the second result.

The results in the two output registers can then be combined easily, in order to obtain the CRC value.

In a further implementation form of the first aspect, the device further comprises multiplexers connecting the input registers with the CRC processing unit.

These M multiplexers are added compared to the conventional device, but lead only to a minimum of additional size and complexity. In a further implementation form of the first aspect, N= 8, 16 or 32.

These numbers yield preferred devices. The N= 32 device is able to carry out CRC- 16 or lower with significantly increased performance compared to the conventional device. The same is true for the N= 16 device when carrying out CRC-8 or lower, and the N= 8 device when carrying out CRC-4 or lower. A second aspect of the present invention provides a method of calculating an \/-b i t Cyclic Redundancy Check, CRC, value from A bits of data, wherein N=2 i is a natural number and M=N! 2, the method comprising receiving N data bits of the data, receiving M state bits, receiving at least one matrix, calculating, in a current cycle, a first result based on the N data bits of the data and an MxN part of the at least one matrix, a second result based on the M state bits and an MxM part of the at least one matrix, and the \ /-b i t CRC value based on the first result and the second result, and providing the M- bit CRC value calculated in the current cycle as the M state bits for the next cycle.

In an implementation form of the second aspect, the method comprises calculating an \/-b i t CRC value from A bits of data in each of a plurality of cycles. In a further implementation form of the second aspect, the method comprises calculating the first result by multiplying the A data bits of the data with an MxN matrix, and the second result by multiplying the M state bits with an MxM matrix. In a further implementation form of the second aspect, the method comprises calculating the first result and/or the second result based on a Galois field multiplication and accumulation computation.

In a further implementation form of the second aspect, the method comprises calculating the A/-b i t CRC value by adding the first result and the second result.

In a further implementation form of the second aspect, the method comprises programming a matrix register with an MxN matrix and an MxM matrix.

In a further implementation form of the second aspect, the method comprises programming an NxN matrix register with two matrices. In a further implementation form of the second aspect, each matrix is calculated based on a plurality of CRC polynomials supported by the method.

In a further implementation form of the second aspect, M initialization bits are received as the M state bits for a first cycle.

In a further implementation form of the second aspect, the method comprises calculating the first and second results by means of N ² AND-gates and N ² XOR-gates, and to calculate the M- bit CRC value from the first and second results by means of M - 1 XOR-gates.

In a further implementation form of the second aspect, N= 8, 16 or 32.

The method of the second aspect and its implementation forms achieve the same advantages and effects as the device of the first aspect and its implementation forms, respectively. A third aspect of the invention provides a computer program product comprising a program code for controlling the device according to the first aspect and any of its implementation forms or for performing, when running on a computer, the method according to the second aspect and any of its implementation forms.

It has to be noted that all devices, elements, units and means described in the present application could be implemented in the software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

The above described aspects and implementation forms of the present invention will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which

FIG. 1 shows a device according to an embodiment of the invention.

FIG. 2 shows CRC-16 carried out in a device suitable for CRC-32 according to an embodiment of the invention.

FIG. 3 shows a device according to an embodiment of the invention suitable for CRC-8. FIG. 4 shows a method according to an embodiment of the invention.

FIG. 5 shows a conventional method for CRC-16.

FIG. 6 shows CRC-16 carried out in a conventional device suitable for CRC-32.

FIG. 7 shows a conventional device suitable for CRC-8.

DETAIFED DESCRIPTION OF EMBODIMENTS

FIG. 1 shows a device 100 according to an embodiment of the invention. The device 100 can be used for calculating an M- bit CRC value 101 from A bits of data 102, wherein N=2 i is a natural number and M=N/2. Preferably, the device 100 is configured to calculate one M- bit CRC value 101 from .\ ^r bits of data 102 in each of a plurality of cycles, i.e. one M- bit CRC value 101 per cycle. The device 100 comprises an L-bit input register 103, an A/-b i t input register 104, an NxN matrix register 106, and a CRC processing unit 107.

The TV-bit input register 103 is configured to receive N data bits 102. It may, in operation of the device 100, receive N data bits per cycle, wherein the data bits 102 received for a current cycle may be the same or different than the data bits 102 received for a next cycle. The \ /-b i t input register 104 is configured to receive M state bits 105. It may, in operation of the device, receive M state bits 105 per cycle, wherein the state bits 105 received for a current cycle may be the same or different than the state bits 105 received for a next cycle. The NxN matrix register 106 is configured to receive at least one matrix 110 as instruction. It may, in operation of the device 100, receive one or more matrices 110 per cycle, wherein the at least one matrix 110 received in a current cycle may be the same or different than the at least one matrix 110 received in a next cycle.

The CRC processing unit 107 is configured to calculate, in a current cycle, a first result 108 based on the N data bits 102 in the TV-bit input register 103 and an MxN part of the matrix register 106. Further, the CRC processing unit 107 is configured to calculate a second result 109 based on the M state bits 105 in the M- bit input register 104 and an MxM part of the matrix register 106. Based on the first result 108 and the second result 109, the CRC processing unit

107 is then configured to calculate the M- bit CRC value for the current cycle.

Thereby, the CRC processing unit 107 may preferably be configured to calculate the first result

108 and/or the second result 109 based on a Galois field multiplication and accumulation computation (GFMAC). Further, the CRC processing unit 107 may be configured to calculate the first result 108 by multiplying the N data bits 102 in the TV-bit input register 103 with an MxN matrix 110 in the MxN part of the matrix register 106, and to calculate the second result

109 by multiplying the M state bits 105 in the M- bit input register 104 with an MxM matrix 110 in the MxM part of the matrix register 106. Then, the CRC processing unit 107 may preferably be configured to calculate the 47-bit CRC value by adding the first result 108 and the second result 109.

Advantageously, the CRC processing unit 107 is further configured to provide the M- bit CRC value 101 calculated in the current cycle to the L / -b i t input register 104 as the M state bits 105 for the next cycle. FIG. 2 shows a device 100 according to an embodiment of the invention. The device 100 shown in FIG. 2 bases on the device 100 shown in FIG. 1. Same components of the devices 100 are labelled with the same reference signs, and have the same functionality. FIG. 2 shows the matrix register 106, the A-bit input register 103, and the \/-b i t input register 104.

The device 100 shown in FIG. 2 is in principle suitable for CRC-32 (i.e. CRC with polynomials up to order 32). Accordingly, the exemplary device 100 has a 32x32-bit matrix register 106 for receiving the at least one matrix 110. If only one matrix 110 is received as instruction in a given cycle, this matrix 110 may in principle have a size of up to 32x32 bits. Further, the device 100 has a 32-bit input register 103 for receiving 32 data bits 102 per cycle, and a 16-bit input register for receiving 16 state bits 105 per cycle.

The device 100 of FIG. 2 may preferably also include (not shown) a 32-bit output register - which may specifically be composed of two 16-bit output registers - in order to receive a calculation result of the device 100, which may include up to 32 bits. In particular, in case of CRC-32, a result obtained by multiplying the 32 data bits 102 in the 32-bit input register 103 with the 32x32 matrix 110 in the matrix register 106 may be received by this 32-bit output register. Preferably, the device 100 further includes 1024 AND gates and 1040 XOR gates (to perform reduction XOR) and 256 multiplexers.

The device 100, although being in principle suitable for CRC-32, is particularly advantageous when performing CRC- 16 (or even lower order CRC), which case is particularly illustrated in FIG. 2. The device 100 is able to carry out such CRC- 16 with a significantly increased performance compared to, for example, the device shown in FIG. 2. In the case of CRC- 16, the device 100 is configured to compute a 16-bit CRC value 101 in each cycle for a CRC polynomial up to an order of 16.

In FIG. 2 a calculation for a current cycle is shown. The matrix register 106 is here provided with two matrices 110. That is, with two instructions in parallel. Namely, with a l6x32-bit matrix 200 provided to a 16x32 part of the matrix register 106, and with a l6xl6-bit matrix 201 provided to a first 16x16 part of the matrix register 106. Another 16x16 part of the matrix register 106 is unused as illustrated, however, this means that the matrix register 106 is still utilized to ¾ (compared to the utilization of ½ and ¼, respectively, in the two consecutive cycles of the conventional device shown in FIG. 2). The device 100 of FIG. 2 is configured to calculate the first result by multiplying the 32 data bits 102 in the 32-bit input register 103 with the 16x32 matrix 200, and at the same time (i.e. in the same cycle) to calculate the second result by multiplying the 16 state bits 105 in the 16-bit input register 104 with the 16x16 matrix. The two results are then added (still in the same cycle), in order to obtain the 16-bit CRC value 101 (output/state). The 16 state bits 105 are then updated by the 16-bit CRC value for use in the next cycle.

FIG. 3 shows a device 100 according to an embodiment of the invention, which builds on the device 100 shown in FIG. 1. Same components are labelled with the same reference signs and have the same functions. Exemplarily, the device 100 in FIG. 3 is suitable for performing CRC-

8.

The device 100 has accordingly an 8-bit input register 103 for receiving 8 data bits 102 per cycle. Further, it has a 4-bit input register 104 for receiving 4 state bits 105 per cycle, and has an 8x8 matrix register. Preferably, the device 100 has in addition 64 AND gates, 68 XOR gates and 16 multiplexers, which are for example part of the CRC processing unit 107. Compared to a conventional device for CRC-8, as for example shown in FIG. 7, only 4 XOR gates and the 16 multiplexers are added.

Advantageously the device 100 is able to calculate CRC-4 and lower with a significantly increased performance compared to the conventional device shown in FIG. 7. To this end, the matrix register 106 is separated into two parts. The input data bits 102 in the input register 103 are multiplied by means of XOR- and AND-gates with a first part of the matrix register 106 (“Matrix line 0” to“Matrix line 3” in FIG. 3), thus yielding the first result 108. At the same time (i.e. in the same cycle), the state bits 105 in the input register 104 are multiplied with another part of the matrix register 106 (“Matrix line 4” to“Matrix line 7” in FIG. 3), thus yielding the second result 109.

Preferably, the first result is received by a first output register 300, and the second result 109 by a second output register 301. The bits in the two output registers 300, 301 may then be added by means of, for instance, XOR-gates to obtain the 4-bit CRC-value 101. The 4-bit CRC value 101 is used to update the state bits 105 in the 4-bit input register 104 before the next cycle.

FIG. 4 shows a method 400 of calculating an 47-bit CRC value 101 from A bits of data, wherein N=2 i is a natural number and M=N/2. The method 400 may particularly be carried out by the device 100 shown in FIG. 1, 2 or 3, respectively. The method 400 includes a step 401 of receiving N data bits 102 of the data, a step 402 of receiving M state bits 105, a step 403 of receiving at least one matrix 110, and a calculating the 404.

The step 404 includes calculating, in a current cycle, a first result 108 based on the N data bits 102 of the data and an MxN part of the at least one matrix 110, a second result 109 based on the M state bits 105 and an MxM part of the at least one matrix 110, and the A /-b i t CRC value 101 based on the first result 108 and the second result 109. The calculating step 404 also includes providing the \/-b i t CRC value 101 calculated in the current cycle as the M state bits 105 for the next cycle.

In summary, a generic CRC device 100 and method 400 are presented, which improve conventional CRC devices and methods, in particular in view of better performance and better hardware utilization. Thereby, only a minimum of additional hardware is necessary, thus keeping costs and complexity low.

The present invention has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed invention, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article“a” or“an” does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.