SummaryIntroductionCyclic Redundancy Check (CRC)IEEE 802.3 CRC-32Serial Input Hardware Implementation of CRC-32Parallel Data Input Hardware Implementation of CRC-32A Complete Implementation of IEEE 802.3 CRC-32Reference Designcrcgen.plPerl Script DetailsCommand-line ParsingCheck Validity of ParametersGenerate XOR EquationsOptimize XOR equationsGenerate Verilog source for Module Statement and I/O DefinitionsGenerate Internal Strings for Later Verilog Source OutputGenerate Verilog Source for Registers and Control LogicGenerate Verilog Source From Optimized XOR EquationsGenerate Verilog Source for Endmodule StatementDesign FilesPerformance and UtilizationPerformance and Utilization of IEEE 802.3 CRC-32 ImplementationConclusionReferencesRevision HistoryXAPP209 (v1.0) March 23, 2001 www.xilinx.com 11-800-255-7778© 2001 Xilinx, Inc. All rights reserved. All Xilinx trademarks, registered trademarks, patents, and disclaimers are as listed at http://www.xilinx.com/legal.htm. All other trademarks and registered trademarks are the property of their respective owners. All specifications are subject to change without notice.Summary Cyclic Redundancy Check (CRC) is an error-checking code that is widely used in data communication systems and other serial data transmission systems. CRC is based on polynomial manipulations using modulo arithmetic. Some of the common Cyclic Redundancy Check standards are CRC-8, CRC-12, CRC-16, CRC-32, and CRC-CCIT. This application note discusses the implementation of an IEEE 802.3 CRC in a Virtex™ device. The reference design provided with this application note provides Verilog point solutions for CRC-8, CRC-12, CRC-16, and CRC-32. The Perl script (crcgen.pl) used to generate this code is also included. The script generates Verilog source for CRC circuitry of any width (8, 12, 16, 32), any polynomial, and any data input width.Introduction In networking systems a significant role of the Data Link layer is to convert the potentially unreliable physical link between two machines into an apparently very reliable link. This is achieved by including redundant information in each transmitted frame. Depending on the nature of the link and the data, one can include just enough redundancy to make it possible to detect errors and then arrange for the retransmission of damaged frames. The cyclic redundancy check or CRC is a widely used parity bit based error detection scheme in serial data transmission applications. This code is based on polynomial arithmetic.The bits of data to be transmitted are the coefficients of the polynomial. As an example, the bit stream 1101011011 has 10-bits, representing a 10-term polynomial:To compute the CRC of a message, another polynomial called the generator polynomial G(x) is chosen. G(x) should have a degree greater than zero and less than that of the polynomial M(x). Another requirement for G(x) is a non-zero coefficient in the x0 term. This results in several possible options for the generator polynomial, and hence the need for standardization. CRC-16 is one such standard that uses the generating polynomial:CRC-16 detects all single and double errors, all errors with an odd number of bits, all burst errors of length 16 or less, and most errors for longer bursts.CRC-32 uses the generating polynomial:In general, an n-bit CRC is calculated by representing the data stream as a polynomial M(x), multiplying M(x) by xn (where n is the degree of the polynomial G(x)), and dividing the result by a generator polynomial G(x). The resulting remainder is appended to the polynomial M(x) and transmitted. The complete transmitted polynomial is then divided by the same generator polynomial at the receiver end. If the result of this division has no remainder, there are no transmission errors. Mathematically, this can be represented as:Application Note: Virtex Series and Virtex-II FamilyXAPP209 (v1.0) March 23, 2001IEEE 802.3 Cyclic Redundancy Check Author: Chris BorrelliRMx() 1x9⋅ 1x80x7⋅ 1x60x5⋅ 1x41x3⋅ 0x21x1⋅ 1x0⋅++⋅++⋅++⋅++⋅+=Mx() x9x8x6x4x3x11++++++=Gx() x16x15x21+++=Gx() x32x26x23x22x16+++ x12x11x10x8x7x5x4x2x1+ ++++++++++=CRC remainder of M x()xnGx()-------- ----×=2 www.xilinx.com XAPP209 (v1.0) March 23, 20011-800-255-7778IEEE 802.3 Cyclic Redundancy CheckRCyclic Redundancy Check (CRC)CRC computation involves manipulating M(x) and G(x) using modulo 2 arithmetic. Modulo arithmetic yields the same result for addition and subtraction. Therefore it is necessary only to consider three operations involving polynomials namely, addition, multiplication, and division.The addition of two polynomials and yields .The multiplication of two polynomials and results in Note that multiplication of a polynomial by xm results in a shifted bit pattern with zeros in the lower m positions. For example:Dividing by results in a quotient of and a remainder of as shown below. 111001111111001)101100100110111111001100000011110011110010111100110111101111001100111111110011101101111100110100x8x7x5x4x2x1++++++ x5x4x3x2+++x8x7x3x1++++x8x7x5x40x2x1+ + + + + + + 110110111=00x5x4x3x200+ + + + + + + 000111100=x8x700x30x1+ + + + + + + 110001011=----- --------------------------------------- -------------------------------------- -----------------------------------x7x6x5x21++++ x1+x8x5x3x2x1+++++x7x6x5x21++++()x1+()11100101()11()×=x8x7x600x30x0+ + + + + + + + 111001010=0x7x6x500x201+ + + + + + + + 011100101=x800x50x3x2x1+ + + + + + + + 100101111=------- -------------------------------------- -------------------------------------- ---------------------------------------x5x11x10x8x4x3x1++++++()x16x15x13x9x8x6x5+ + ++++=x13x11x10x7x4x3x1+++++++ x6x5x4x31++++x7x6x5x2x1+++++x4x2+x13x11x10x7x4x3x1+ + + + + + + 10110010011011=x6x5x4x31+ + + + 1111001=Qx() 11100111 x7x6x5x2x1+++++==Rx() 10100 x4x2+==IEEE 802.3 Cyclic Redundancy CheckXAPP209 (v1.0) March 23, 2001 www.xilinx.com 31-800-255-7778RIEEE 802.3 CRC-32IEEE 802.3 defines the polynomial M(x) as the destination address, source address, length/type, and data of a frame, with the first 32-bits complemented. The remainder from the calculation of CRC above is complemented, and the result is the IEEE 802.3 32-bit CRC, referred to as the Frame Check Sequence (FCS) field. The FCS is appended to the end of the Ethernet frame, and is transmitted highest order bit first (x31, x30,…, x1, x0).Serial Input Hardware Implementation of CRC-32The single-bit data input (serial) calculation of CRC-32 is implemented
View Full Document
Unlocking...