Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-05-10
2002-08-27
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06442747
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to Cyclic Redundancy Code (CRC) check circuits and more particularly relates to a method of optimally synthesizing a CRC check circuit having less delay and lower gate count.
BACKGROUND OF THE INVENTION
In digital data communication systems and other types of systems such as information storage and retrieval systems, memory subsystems, etc., errors may occur as a result of channel noise, interference, media defects or circuit failure. In order to provide reliable communications it is necessary to be able to detect transmission errors. Transmission errors may be detected using a cyclic redundancy code (CRC) check which is a technique in widespread use in binary communication systems to detect errors in communicated data.
In general CRCs are calculated by treating the data as the coefficients of a polynomial, dividing the data by another polynomial, and preserving the remainder. The data and CRC together make up a codeword that is then transmitted over the communication channel. At a receiving end of the channel a CRC is again calculated and compared to the original. A discrepancy between the two CRCs indicates the occurrence of a transmission error.
The data input to the CRC can be viewed as a sequence of binary bits or a sequence of multibit symbols. In general, a bit-oriented CRC is desirable if the expected errors comprise random bit errors and a symbol-oriented CRC is desirable if the expected errors comprise burst errors or random symbol errors.
The computation of a CRC word involves using arithmetic to divide an input block of data by a constant called a generator polynomial. The resultant quotient is discarded while the remainder (i.e. the CRC word) is appended to the original numeric binary value and then transmitted. Typically, CRC words are computed using a multiple section feedback shift register with exclusive-OR (XOR) logic elements between sections to perform the modulo-2 arithmetic calculations. Each bit is provided to the CRC register where it is shifted or circulated through the CRC computational algorithm (circulation referring to the movement of data through the CRC register). The CRC computational algorithms can be implemented in hardware or software. In many cases, a CRC calculation on ‘N’ data bits must be performed within the same clock cycle in order to keep up with very high data rates of transmission. When calculating a CRC function for N data bits in one clock cycle, however, the CRC function becomes much more complex and requires significantly more circuit real estate to implement. The larger sized circuit typically results in a much longer delay that can affect the maximum attainable clock speed for the data.
Therefore, there is a need for a mechanism of creating a CRC circuit implementation having a smaller area and lower delay that does not impede the transmission of high rate data.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with the prior art by providing a method of synthesizing a CRC generator circuit. The method is operative to generate optimized code in a high level hardware description language such as VHDL. In an example embodiment, the invention generates Very High Level Hardware Description Language (VHDL) code for implementing a CRC generator circuit that has significantly less delay and utilizes fewer gates than prior art CRC generator circuit synthesis techniques. The method is operative to generate VHDL code that can then be used to synthesize the circuit. The code generated functions to significantly reduce the gate count and complexity of the resulting circuit as well as significantly reduce the delay.
The method of the invention, as implemented in an example software application described herein below, iteratively generates the remainder equations for a CRC generator given the generator polynomial. During each iteration of the software, the duplicate terms in each remainder equation are eliminated or replaced with zero (which achieves the same thing). Since the terms in a remainder equation are all XORed with each other, duplicate entries can be eliminated based on the fact that anything XORed with itself equals zero. In addition, anything XORed with zero is itself.
The number of iterations is equal to the number of data bits the CRC generator is to process during each clock cycle. Once all the duplicate terms in the remainder equations are removed, the equations are sorted, rebuilt and translated into hardware description language code such as VHDL. The resulting code is then synthesized. Examples of a 10 bit CRC generator processing 32 bits of data are presented. In one example, the synthesis results of a prior art CRC generator is presented without use of the optimized code generated by the method of the present invention. In a second example, the synthesis results of a CRC generator is presented that uses the optimized code generated by the method of the present invention. The results clearly indicate the advantages of the present invention in terms of significantly lower delay times, cell counts and faster run times for the synthesizer.
There is thus provided in accordance with the present invention a method of generating high level circuit description language code representing a cyclic redundancy (CRC) generator circuit, the CRC generator circuit adapted to implement a generator polynomial G(x), the method comprising the steps of generating remainder equations for all bits in the CRC generator in accordance with the generator polynomial G(x), calculating in an iterative fashion remainder equations for all bits in the CRC generator for the k
th
data bit by substitution based on the remainder equations for the k−1 data bit, counting the number of occurrences of each term in each remainder equation, removing all occurrences of any term that occurs twice in a remainder equation, repeating the steps of calculating, counting and removing for each of N data bits, generating high level circuit description language code corresponding to the final set of remainder equations and wherein N is a positive integer.
REFERENCES:
Nair et al., “A Symbol Based Algorithm for Hardware Implementation of Cyclic Redundancy Check (CRC),” IEEE, 1997, pp. 82-87.*
Sait et al., “VLSI Layout Generation of a Programmable CRC Chip,” IEEE Trans. on Consumer Electronics, vol. 39, No. 4, Nov. 1993, pp. 911-916.*
AWK User Guide, MKS Inc., 1999; URL; http//www.datafocus.com/docs/man1/awk.1.htm. No Page #s.
3Com Corporation
Garbowski Leigh Marie
Smith Matthew
Sutton Paul J.
Zaretsky Howard
LandOfFree
Method of synthesizing a cycle redundancy code generator... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of synthesizing a cycle redundancy code generator..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of synthesizing a cycle redundancy code generator... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2940401