High performance CRC calculation method and system with a matrix transformation strategy

• US 20050149818A1
• Filed: 12/17/2003
• Published: 07/07/2005
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Macronix International Co., Ltd.
• Original Assignee: Macronix International Co., Ltd.
• Inventors: Chang, Joe, Tsai, Kovsky T. J.
• Granted Patent: US 7,219,293 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation

Abstract

A CRC calculation method and system for generating a CRC from a message is provided while improving the process time and simple to implement. A linear mapping matrix is used for the operation of the LFSR to generate the CRC and the maximum value of the non-zero entries in the mapping matrix is reduced by applying one or more raw operations to the linear mapping matrix in advance before the computation of mapping the input message to the CRC result. Flip-flops are additionally inserted before the generator matrix to obtain a pipeline architecture so as to further improving the operation speed thereof.

Claims

1. A CRC calculation method for a message, comprising the steps of:

defining a generator matrix having a maximum value of the non-zero entries for representing an LFSR corresponding to a form for linearly mapping an input vector to a remainder vector;

transforming the generator matrix to a similar matrix for reducing the maximum value of the non-zero entries;

arranging the message inputted in the form to the input vector; and

transforming the message to a CRC result by multiplying the similar matrix to the input vector.

2. A method according to claim 1, wherein the form is a byte-wise form.

3. A method according to claim 1, wherein the form is a doubleword-wise form.

4. A method according to claim 3, wherein the step of arranging the message to the input vector comprises padding the message with one or more dummies.

5. A method according to claim 3, further comprising initiating the LFSR with a specific value.

6. A method according to claim 5, further comprising identify a length type of the message and determining the specific value in accordance with the length type.

7. A method according to claim 3, further comprising comparing the CRC result with a specific pattern.

8. A method according to claim 7, further comprising identify a length type of the message and determining the specific pattern in accordance with the length type.

9. A method according to claim 1, wherein the step of transforming the message to a CRC result comprises performing an iteration procedure between the remainder vector and the input vector.

10. A method according to claim 1, wherein the step of transforming the generator matrix to a similar matrix comprises the steps of:

selecting an invertible matrix;

generating an inverse matrix of the invertible matrix;

and

multiplying the invertible matrix, generator matrix and inverse matrix.

11. A method according to claim 10, further comprising inserting a flip-flop procedure between the multiplying of the invertible matrix and generator matrix for forming a pipeline architecture.

12. A CRC calculation system for generating a CRC result from a message, comprising:

means for arranging the message inputted in a form to an input vector;

a generator matrix having a maximum value of the non-zero entries for representing an LFSR corresponding to the form for linearly mapping the input vector to a remainder vector; and

means for transforming the generator matrix to a similar matrix for reducing the maximum value of the non-zero entries; and

means for multiplying the similar matrix to the input vector.

13. A system according to claim 12, wherein the form is a byte-wise form.

14. A system according to claim 12, wherein the form is a doubleword-wise form.

15. A system according to claim 14, further comprising one or more dummies for padding the message thereto.

16. A system according to claim 14, further comprising a specific value for initiating the LFSR therewith.

17. A system according to claim 16, further comprising means for identifying a length type of the message and determining the specific value in accordance with the length type.

18. A system according to claim 14, further comprising means for comparing the CRC result with a specific pattern.

19. A system according to claim 18, further comprising means for identifying a length type of the message and determining the specific pattern in accordance with the length type.

20. A system according to claim 12, wherein the means for transforming the generator matrix to a similar matrix comprises means for multiplying the generator matrix to an invertible matrix.

21. A system according to claim 20, wherein the means for transforming the generator matrix to a similar matrix comprises means for multiplying an inverse matrix of the invertible matrix to the generator matrix.

22. A system according to claim 12, further comprising means for forming a pipeline architecture between the message and CRC result.