crc-32

32-Bit Cyclic Redundancy Codes for Internet Applications Abstract Standardized 32-bit Cyclic Redundancy Codes provide fewer bits of guaranteed error detection than they could, achieving a Hamming Distance (HD) of only 4 formaximum-length Ethernet messages, whereas HD=6 ispossible. Although research has revealed improved codes,exploring the entire design space has previously beencomputationally intractable, even for special-purposehardware. Moreover, no CRC polynomial has yet beenfound that satisfies an emerging need to attain both HD=6for 12K bit messages and HD=4 for message lengthsbeyond 64K bits. This paper presents results from the firstexhaustive search of the 32-bit CRC design space. Resultsfrom previous research are validated and extended toinclude identifying all polynomials achieving a better HDthan the IEEE 802.3 CRC-32 polynomial. A new class ofpolynomials is identified that provides HD=6 up to nearly16K bit and HD=4 up to 114K bit message lengths,providing the best achievable design point that maximizeserror detection for both legacy and new applications,including potentially iSCSI and application-implementederror checks. 1. Introduction Cyclic Redundancy Codes (CRCs) are used in a wide variety of computer networks and data storage devices to provide inexpensive and effective error detection capabili - ties. As data transfer rates and the amount of data stored in - crease, the need for simple, cheap, and robust errordetection codes increases as well. Thus it is important to besure that the CRCs in use are as effective as possible. Unfortunately, standardized CRC polynomials such as the CRC-32 polynomial used in the IEEE 802.3 (Ethernet)network standard [IEEE85] are known to be grosslysuboptimal for important applications. For example, the802.3 CRC can detect up to three independent bit errors(Hamming Distance HD=4) in an Ethernet MaximumTransmission Unit (MTU) having a 1500 byte payload.But, the theoretical maximum is detection of five independ -ent bit errors (HD=6) using identical error detectiontechniques with a better CRC polynomial. New standards and applications are continually emerg - ing that require a high degree of data integrity. While it isno small matter to refit a widely deployed standard such asEthernet to a new error detection scheme, designers ofemerging technology such as iSCSI (a protocol forInternet-based storage systems [IETF01]) are searching forimproved CRC capabilities. However, no CRC polynomi-als have been previously identified that satisfy both a desirefor high error detection performance at EthernetMTU-length messages as well as good error detection per-formance for relatively long messages. The challenge to finding ideal CRCs is that the effective- ness of any particular code is computationally expensive todetermine, and finding the best code for any particular mes-sage length among all possible codes has in the past provento be computationally intractable. This is particularly trueof message lengths beyond 8K bits, which are commonlyfound on general-purpose computer networks and datastorage devices. In this paper we present the results of the first exhaustive exploration of the design space for 32-bit CRCs. The entireset of 1,073,774,592 distinct polynomials has been evalu - ated for effectiveness for data word sizes of 12112 bits. A result of completing an exhaustive search is that a de - finitive list of classes of polynomials that can and cannotachieve HD better than the 802.3 CRC for MTU-sized mes - sages has been created. The creation of this list led to thediscovery of a previously unexplored class of polynomialthat combines excellent performance for MTU-sized mes - sages with good performance for longer messages. Thisclass of polynomial provides a significantly improved al - ternative to the CRC currently being considered for iSCSI,yielding 5 bit error detection (HD=6) for MTU-size pay - loads and 3 bit error detection (HD=4) to 114K bits. Theclass of polynomial previously considered for iSCSI appli - cations (which was only partially explored by previous 1Philip Koopman ECE Department & ICES Carnegie Mellon University Pittsburgh, PA, USA [email protected] of a regular paper to appear in The International Conference on Dependable Systems and Networks (DSN) 2002. work) has now been proven to have no polynomials with HD>4 for MTU-sized messages. Additionally, two newclasses of polynomials have been characterized that arecomparable in effectiveness to previously known results,but have member polynomials with few feedback taps, po - tentially simplifying high-speed hardware implementa - tions. 2. Background Cyclic redundancy codes (also known sometimes as cy - clic redundancy checks) have a long history of use for errordetection in computing. [Peterson72] and [Lin83] areamong the commonly cited standard reference works forCRCs. A treatment more accessible to non-specialists canbe found in [Wells99]. A CRC can be thought of as a (non-secure) digest func - tion for a data word that can be used to detect data corrup - tion. Mathematically, a CRC can be described as treating abinary data word as a polynomial over GF(2) ( i.e., with each polynomial coefficient being zero or one) and per - forming polynomial division by a generator polynomial G(x). The generator polynomial will be called a CRC poly-nomial for short. (CRC polynomials are also known asfeedback polynomials, in reference to the feedback taps ofhardware-based shift register implementations.) The re-mainder of that division operation provides an error detec-tion value that is sent as a Frame Check Sequence (FCS)within a network message or stored as a data integritycheck. Whether implemented in hardware or software, theCRC computation takes the form of a bitwise convolutionof a data word against a binary version of the CRC polyno - mial. Error detection is performed by comparing an FCS com - puted on a piece of retrieved or received data against theFCS value originally computed and either sent or storedwith the original data. An error is declared to have occurredif the stored FCS and computed FCS values are not equal.However, as with all digital signature schemes, there is asmall, but finite, probability that a data corruption that in - verts a sufficient number of bits in just the right pattern willoccur and lead to an undetectable error. The minimumnumber of bit inversions required to achieve such unde - tected errors ( i.e., the HD value) is a central issue in the de - sign of CRC polynomials. The essence of implementing a good CRC-based error detection scheme is picking the right polynomial. Theprime factorization of the generator polynomial brings withit certain potential characteristics, and in particular gives atradeoff between maximum number of possible detected er - rorsvs.data word length for which the polynomial is effec - tive. Many polynomials are good for short words but poorat long words, and the converse. There are relatively fewpolynomials that are excellent for medium-length datawords while still being good for relatively long data words. Unfortunately, prime factorization of a polynomial is not sufficient to determine the achieved HD value for any par - ticular message length. A polynomial with a promisingfactorization might be vulnerable to some combination ofbit errors, even for short message lengths. Thus,factorization characteristics suggest potential capabilities,but specific evaluation is required of any polynomial beforeit is suitable for use in a CRC function. While many previ - ous results for CRC effectiveness have been published, noprevious work has attempted to achieve complete screeningof all possible 32-bit polynomials. 3. Previously known 32-bit CRC polynomials At a general level, the effectiveness of a CRC can be ex - pressed as the minimum Hamming Distance (“HD”) of thecodewords created by appending computed CRC values tonetwork messages or other data words of interest. If all re - sulting codewords have an inter-codeword Hamming Dis - tance of at least m bits, then the CRC is guaranteed to detectall possible errors involving ( m-1) or fewer bit inversions. Typically, a high percentage of bit errors numbering mor more are detectible. For CRC polynomials divisible by(x+1), all odd numbers of bit inversions are detected, but alleven numbers of bit inversions suffer an undetected errorrate approximately twice as high as for other polynomials.Finally, all burst errors of size less than or equal to the num-ber of bits in the CRC are detected (that property is not theprimary consideration of this work and remains intact forall the codes we consider). A critical measurement of CRC effectiveness for general purpose computing is the HD at an Ethernet MTU messagesize of a 12112 bit data word. Thus the search for CRCpolynomials can be concentrated on maximizing achievedHD for MTU-sized data words. The IEEE 802.3 standard adopts the CRC polynomial: x 32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 (this is irreducible, but not primitive). We represent thispolynomial as a 32-bit hexadecimal number 0x82608EDB.The leading “8” of this number corresponds to the top four(x 32through x29) polynomial coefficients, with lower order bits corresponding to lower order coefficients, down to thetrailing “B,” which refers to the terms (x 4+x2+x). The “+1” term is implicit in this representation, permitting represent - ing a polynomial of degree 32 using a 32-bit integer as iscommon practice in software CRC implementations. A polynomial’s effectiveness is evaluated by computing weights for that polynomial. A weight W iis the number of occurrences of a combination of ierror bits, including bit errors perturbing the CRC value, that would be undetectedby a given polynomial for a given data word length. For ex - 2 ample, the 802.3 CRC has a weight at message length=12112 bits of {W 2=0; W 3=0; W 4=223059; ...}. This means this particular polynomial, when used with a 12112bit data word, will detect all 2-bit errors, and detect all 3-biterrors, but fail to detect the 223,059 four-bit possible errors within 12144 412144 4 12140906 1012   == ⋅! !!different possible combinations of 4-bit errors that could occur across a 12144-bit codeword (slightly more than 1 out ofevery 2 32possible errors would be undetectable). While this is a small proportion of errors to go undetected, the in - creasing amount of data being transmitted and storedworldwide suggests that higher detection rates are desir - able, or at least that lower detection rates should not be ac - cepted without question as longer data words are being sentand stored. Weights beyond the first non-zero weight are largely un - important when evaluating a polynomial for general pur - pose network applications. That is because, assumingindependent and moderate bit error rates (BERs), each suc - cessive number of bit errors is less likely to occur by a fac-tor approximately equal to the BER value. So on a networkwith a 10 -6BER, a five-bit error is approximately 106times less likely than a four-bit error. Additionally, because a CRC can always detect 1-bit errors, weights for positionsless than 2 are always zero and thus not reported. (Whilesituations with high BERs do occur, in most cases other er - ror detection mechanisms such as message format errors,bit encoding phase violations, and high level protocol hand - shake failures also take place. Thus, CRC effectiveness atmoderate BER values at which only a fraction of messagesare corrupted is often the most important networking casefrom a practical point of view.) Figure 1 shows a comparison of the HD values of vari - ous polynomials identified during the survey discussed inthis paper. All HD values are exactly calculated for dataword lengths up to 128K bits (131072 bits). Similarly, Ta - ble 1 gives the data word bit lengths stating which HD val - ues apply to each polynomial. For example, the 802.3polynomial has a HD greater than or equal to 8 up to a dataword length of 91 bits, HD=7 to 171 bits, HD=6 to 268 bits,HD=5 to 2974 bits, HD=4 to 91607 bits, and HD=3 to atleast 128K bits. 3DATA W ORD LEN GTH(Bits) HAMMINGDISTANCE(Bits) 0x992C1A4C {1,1,30} 0xFA567D89 {1,1,15,15} IEEE 802.3 {32}0x8F6E37A0 {1,31}0x90022004 {1,1,30} 0xD419CC15 {32}0x80108400 {32} 0xBA0DC66B {1,3,28} 234864 128 256 512 1K 2K 4K 8K 16K 32K 64K 128K40B Ack Packet 512+40B Packet 1 MTU 2 MTU 4 MTU 8 MTU 2345678 Figure 1. Error detection capabilities of selected 32-bit CRC polynomials. Several significant message lengths are marked on Fig - ure 1. The two most frequently encountered message lengths on Internet traffic are 40-byte acknowledgmentpackets (400 bit data word including 80 bits of protocoloverhead) and acknowledgment packets additionally con - taining 512 bytes of data (4496 bit data word). The Ether - net size for an MTU message is a 12112 bit data word (thisforms a 12144 bit codeword including the 32-bit CRCvalue). Larger potential message sizes of interest are mul - tiples of the 1500-byte MTU payload size. While the general limit to HD that is attainable for an MTU-size message is 6, actually finding a polynomial thatachieves that performance is computationally very expen - sive. The starting point for determining a HD value isbased on the exploitation of the linearity of CRCs. Con - sider the fact that a data corruption is undetectable if andonly if it transforms one codeword (some payload with itsvalid FCS value) into a different valid codeword. But be -cause CRCs are linear, this means that the faulty bits thathave been flipped from the original codeword have tothemselves form a valid codeword. (In other words, the bitsflipped in the message payload have to be compensated forby bits flipped in the FCS field, and the only way this canhappen is if the entire set of bits flipped is itself a validcodeword.) This means that the actual data in a messagepayload is irrelevant in computing error detection abilities,which simplifies things greatly. Because each undetectableerror pattern is itself a codeword, this also means that deter - mining the minimum HD for a polynomial is equivalent todetermining the lowest non-zero weight for that polyno - mial. Furthermore, the weights of a polynomial give thenumber of undetectable errors for corresponding numbersof error bits. Thus, there is a relatively simple way to determine the number of k-bit undetected errors for an r-bit CRC polyno - mial used to provide error detection for an n-bit payload. 4HD IEEE 802.3 0x82608EDB {32}Castagnoli (iSCSI) 0x8F6E37A0 {1,31}Koopman 0xBA0DC66B {1,3,28}Castagnoli 0xFA567D89 {1,1,15,15}Koopman 0x992C1A4C {1,1,30}Koopman 0x90022004 {1,1,30}Castagnoli 0xD419CC15 {32}Koopman 0x80108400 {32} 15 8-10 14  8 13  12 11-12 9-20 8-16 8-11 8-16 8-1711 13-21  18-21 10 22-34 21-47 17-18 12-24 17-26 22-27 9 35-57   8 58-91 48-177 19-152 25-274 27-134 28-587 92-171  59-81 6 172-268 178-5243 153-16360 275-32736 135-32737 8-32738 82-1060 5 269-2974  1061-65505 8-65505 4 2975-916075244- 131072...16361- 11466332737- 6550232738- 6550632739- 65506 391608- 131072......  2 ... ... 114664+ 65503+ 65507+ 65507+ 65506+ 65506+Table 1. Message lengths in bits (exclusive of CRC field) for which the specified HD is achieved. (Computed to data word length of 131072.) All possible combinations of bit patterns with kbits set in anr+nwide bit field can be tested to see if they form a code - word. If no such bit patterns are codewords, then the CRC has W k=0 and provides perfect detection of k-bit errors. To determine the first kmaxweights of a polynomial, this enu - meration can be iterated by increasing kover the range of {2,.., kmax}. The complexity of each iteration for each poly - nomial considered is the combinatorial complexity of con - sidering ( n+r) thinks kat a time, which is proportional to: () nr knr kn r k+  =+ +−! !( ) !. This has a computational complexity of approximately O(( n+r)k) for each value of k for small values of k, with the kmaxthiteration dominating the computational complexity. This computation must be repeated for every possible r-bit polynomial. Each polynomial has its top bit set. Addi - tionally, only one of each pair of reciprocal polynomials need be checked [Peterson72] (reciprocal polynomials arereadily identified by the fact that their coefficients arebit-reversed from each other). These facts reduce the po - tential search space from 2 rto 2r-2polynomials, yielding approximately 230distinct 32-bit CRC polynomials to be evaluated. (There are a few more than 230polynomials be- cause polynomials that are palindromes are self-reciprocaland thus do not permit elimination of a companion recipro-cal polynomial from consideration.) This makes the algo-rithmic complexity for a complete search O(2 r-2(n+r)k) A pure brute force approach would be dominated by the computation time required to evaluate all combinations of 12144 bits taken 6 at a time (4.45 ⋅1021) for each of approxi- mately 230candidate polynomials. This requires examina- tion of more than 4.78 ⋅1030bit combination/polynomial pairs. Even at one billion such pairs per second evaluated by each of one million parallel processors, this computationwould take 151 million years to complete, and thus is in - tractable. Mathematicians have spent many years creating less computationally intensive approaches. The culmination ofthat work for 32-bit CRCs can be found in [Castagnoli93].Castagnoli et al. evolved Fujiwara’s techniques [Fujiwara85] based on constructing dual codes. Addi - tionally, they built special purpose hardware that was ableto evaluate the weights of polynomials that had been care - fully selected based on prime factorization characteristics.The complexity of this technique (when implemented withspecial-purpose hardware capable of many concurrent op - erations) for evaluating a polynomial at a given codewordlength is 2 32operations. While searching all 230candidate polynomials was still intractable, searching selected poly - nomials from promising classes was feasible, with execu - tion time reported to be 107 to 215 seconds per polynomialusing a 40 MHz clock. (At this rate, evaluation of all poly -nomials would have taken in excess of 3600 years on thesingle copy of special-purpose hardware available, so onlypartial exploration was performed. Performing a massivelyparallel distributed computation using otherwise idle com - puters would be impossible because special-purpose hard - ware was required to attain this level of computationalspeed.) In describing previous work and results we use the fol - lowing shorthand notation to represent factorization of apolynomial: {d 1, .., d k}, where each “d” represents the de - gree of a factor. Thus “{1,3,28}” represents the set of allpolynomials whose irreducible factorization is:“(x+1)(x 3+..+1)(x28+..+1)” ( i.e., has irreducible factors of degrees 1, 3, and 28). Using their special-purpose hardware, Castagnoli et al. found optimal (lowest-weight at the lowest HD) polynomi - als for several factorization classes of 32-bit polynomials.Three classes of polynomials of those examined are poten - tially of interest when improving upon the 802.3 CRC. (Itshould be noted that Castagnoli’s work was not specificallyintended to address this particular problem. However, it isthe most relevant existing data source available for that pur-pose.) Those three classes are {1,1,15,15} polynomials,{32} polynomials, and {1,31} polynomials. First, [Castagnoli93] reports that the optimal {1,1,15,15} polynomial is 0xFA567D89=(0x1 /c2150x1/c215 0x4008 /c2150x642f), which gives HD=6 up to almost 32K bits. (No polynomial gives HD=6 at exactly 32K bit data wordlength.) This polynomial would be suitable for MTU-sizeddata words, but does not work well above 32K bit. (Thepublished polynomial in Table XI of [Castagnoli93] has anerror; it is incorrectly given as 1F6ACFB13, but shouldhave been 1F4ACFB13, a one-bit difference. Thefactorization given in that table yields the correct polyno - mial that matches one of the polynomials found in our re - sults. Thus it can be assumed this is merely a minor datatranscription error. The incorrectly published polynomialhas HD=6 up to a length of only 382 bits and so should notbe used.) Second, [Castagnoli93] reports that a {32} polynomial, 0xD419CC15 (irreducible, although not primitive), givesHD=5 up to almost 64K bits. (No polynomial gives HD=5at exactly 64K bit data word length.) This polynomialwould improve upon the 802.3 CRC by one bit of HD, andextend coverage at HD=5 out to almost 64Kb, making it anattractive alternative for messages longer than an MTU.However, it drops to HD=2 above 65505 bits. This polyno - mial was selected from a restricted class of irreduciblepolynomials, but nonetheless achieves the best possible HDvalues at 32Kb to 64Kb. Third, [Castagnoli93] reports that the best evaluated polynomial of the form {1,31}, where the larger factor isprimitive, is 0x8F6E37A0=(0x1 /c2150x7ADA129F). This 5 code has the promising property of keeping HD=4 out to very long data words, but only has HD=6 up to less thanhalf an Ethernet MTU. However, the authors state that thesearch was limited by available compute time on the spe - cial-purpose hardware, and that there was only time to in - vestigate 47,000 such codes out of 6.93 ⋅10 7possibilities (there are more {1,31} polynomials than that, but the au - thors of that study only considered 31-bit polynomials thatwere primitive). The fact that the exploration of {1,31} polynomials was incomplete leaves open the intriguing possibility that theremight be other, previously unknown, polynomials thatachieve HD=6 for an Ethernet MTU without sacrificingachieving HD=4 at data words sizes in excess of 64Kb. Ad - ditionally, there might be other forms of polynomials notexplored that provide other similarly useful message lengthvs.error detection capability tradeoff points. 4. An exhaustive search for 32-bit CRCs While it is easy to argue that retrofitting an existing stan - dard such as Ethernet is impractical, there always seem tobe new standards being created that might well adopt a su-perior CRC polynomial. For example, the team creatingthe draft iSCSI standard is in the process of designing a pro-tocol that will involve messages of MTU size or larger andthat will use 32-bit CRCs to assure data integrity of trans-mitted messages [Satran01]. A study of CRC effectiveness was completed by Sheinwald et al. [Sheinwald00] as part of the iSCSI defini- tion effort. That report recommends adoption ofCastagnoli’s {1,31} polynomial 0x8F6E37A0 to achievegood performance on short data words while not sacrificingHD=4 performance on longer data words. A good way toimprove upon this selection would be to find a polynomialwith HD=5 (or even HD=6) at 12112 bits that still hasHD=4 to somewhat beyond 64Kb. 4.1. The search technique Rather than embellish upon existing mathemati - cally-based approaches, we opted for a brute-forceenumerative approach that could be implemented with highefficiency on standard computing platforms. Beyond al - lowing us to build upon mature software that had alreadyproven itself in use for embedded network error detectionevaluation, using software on conventional computing plat - forms permitted achieving the following goals: Examine all possible polynomials without being limited to those which have certain theoretical properties. Reproduce previous results via an independentmethodology both to validate our approach anddemonstrate reproducibility for previous work. Indeed,our work discovered an data reporting error in[Castagnoli93], which might have caused a problem ifsomeone had simply used the published polynomialgiven without investigation of its properties.Additionally, this validation step provided anindependent check against any transient errors thatmight possibly have affected those earlier computationson special-purpose hardware. Attain scalability via using idle computing cycles andriding the technology curve of standard platforms, bothof which are difficult to achieve with the use of customhardware that is required to attain high speed operationwith other approaches. The software used for the search was very carefully opti - mized and tuned C++ code running on a Digital UnixAlphastation platform (Sparcstation and Windows2000/PC platforms were also used with identical sourcecode). The software examines all possible combinations ofkbit errors across an n-bit data word plus r-bit FCS field, with r=32. While previously argued herein (and by previ - ous publications) that this approach was intractable, suc - cess was achieved by spending extreme care building thecode for speed and using the following algorithmic com-plexity-reduction techniques in combination: Filtering out polynomials rather than computing exact weights. Since it was desirable to improve upon the HD=4 802.3 CRC performance, all polynomials werefirst evaluated for non-zero weights for 2-, 3-, and 4-biterrors. If any of these weights were non-zero, there wasno need to compute weights for 5 and 6 bit errors. Early bailout of weight evaluation. Furthermore, there is no need to compute exact weights for 2, 3, and 4bits for most polynomials. This is because the firstnon-zero contribution to a weight dooms a polynomialto failure, so there is no point in continuing the weightcomputation. Thus, only one undetected pattern oferrors need be found for any polynomial at a givenlength, with a result of terminating evaluation of apolynomial and filtering it out of consideration. Becauseonly a tiny fraction of polynomials has HD>4 at 12112bit data word length, this permitted short-circuiting thecomputation of almost all polynomials quite quicklycompared to complete computation. Exploiting common behavior of error detection failures. After the first few thousand polynomials werechecked, it was determined that the majority ofpolynomials had at least one undetected error thatinvolved bits in the FCS field. Therefore errors with oneor two FCS bits inverted were tried first, speeding theaverage time to encountering an undetected error. (Itshould be emphasized that all reported polynomials withHD>4 were the result of exact weight computations. 6 This approach merely maximizes the filtering speed by looking for likely undetected error cases first.) Filtering with increasing lengths. Because the cost of filtering each candidate is in the worst case O((n+r)4)t o filter for 4-bit error vulnerabilities, polynomials can befirst filtered at a shorter length n. For example,evaluating polynomials for HD>4 at length 1024 isalmost 17,500 times faster than at length 12112 bits, andsuccessfully filters the overwhelming majority ofpolynomials evaluated. Because the HD of apolynomial can only stay equal or be reduced withincreasing data word length n, any polynomial filtered ata short length can be removed from consideration beforefiltering the remaining polynomials for that same HD atlonger lengths. Inverse filtering with decreasing lengths. Once candidate polynomials are identified via filtering,inverse filtering can be applied to determine a maximumlength at which any of a set of polynomials achieves aparticular HD value. Iterative evaluations decreaselengths to establish successively shorter upper lengthbounds. Runs at long lengths reject all polynomialsquickly using the early-out filtering approach, providinga firm upper length bound by proving no polynomialsexamined achieve the desired HD value. Reducing thatbound until run time increases dramatically gives a gooddetection tool to find the maximum length for which theHD being filtered for can be achieved. (An example isprovided below.) Thus, significant speedup was achieved by using a vari- ety of filtering techniques to avoid computing exact weights, and instead using an early-out approach to detectnon-zero weights without completing full weight calcula - tions. Nonetheless, filtering preserves the property that allresults reported at the end of the process are exact. Whilethis discussion is in the context of MTU-sized messages,the techniques are generally applicable to any CRC selec - tion process. An example of the somewhat subtle tradeoffs involved in using these filtering techniques in combination is the cre - ation of the data shown in Figure 1 and Table 1. Considerthe task of determining precisely where the 802.3 polyno - mial from Figure 1 transitions from HD=5 to HD=4. Givenknowledge that this transition cannot happen at a payloadsize greater than 64K bits, a reasonable baseline method todo this might be to perform a classical binary subdivisionsearch for the transition over a span up to 64K bits, lookingfor successively smaller intervals in which the lower of twomessage lengths has HD=5 and the upper of two messagelengths tested has HD=4. A straightforward approach would be to compute the first 5 weights of the polynomial for each length consideredin the search and then evaluate them. If we assume that64K bit payloads have HD=4, then the first point toevaluate in a binary subdivision search might be 32K bits.Evaluating the first 5 weights at 32K bits takes a long time(we estimate it would take more than 5 months, which is farlonger than we were willing to wait for a test run to com - plete). A speedup can be obtained by realizing that computing the value of the fifth weight is unnecessary. In fact, all thatneed be done is compute the first four weights (this is a useof the filtering technique previously described). If all four weights are zero for that length, then it is certain that HD ≥5. If any of the first four weights are non-zero, then HD ≤4. Thus the break point from HD=4 to HD=5 can be foundsimply by looking for the shortest length at which the fourthweight becomes non-zero. Computing only the first fourweights at 32K bits takes approximately 7 minutes – a sub - stantial speedup. A further improvement can be made by implementing early bailout . With early bailout, the evaluation software is modified to check the computation of weights periodicallyto detect any of weights 2 through 4 being non-zero, withthe computation bailing out as soon as that happens. Theresult is not a precise weight value, but rather a logical flagthat is true if any of weights 4 or less is non-zero, and falseif all of them are zero. Because this is actually the only in-formation needed to perform the search for the break-point(namely, deciding whether HD is above 4 or not), this resultsuffices. The execution time now depends on the particularpolynomial and order of evaluation. Adding the exploita- tion of common behavior optimization as well to provoke a bail-out as early as possible results in an execution time ofless than 7 seconds at 32K bits, compared to 7 minutes withjust filtering. Note that this optimization is probabilistic,and depends on the particular polynomial being tested aswell as message lengths. But it works very well in practice,especially when there are a large number of undetectableerrors that are spread throughout the evaluation space forany particular polynomial. Given that evaluations of longer payloads can still take a significant amount of time in the context of examining abillion polynomials, a further improvement is to evaluatethe polynomial at HD=4 for 256 bits, 512 bits, 1K bits, 2Kbits, and so on until the HD=5 to HD=4 break point is strad - dled ( filtering with increasing lengths ). Exact evaluation at 4K bits for HD=4 takes less than 6 seconds, and evaluationat 2K bits takes less than 1.5 seconds, straddling the breakpoint. This means that a search exploiting increasinglengths followed by a binary search to narrow results withinthe first interval spanning the break point succeeds in lessthan a minute of total CPU time. This approach also takesless time than a full binary subdivision search even thoughit generally requires a few more evaluations, because the 7 evaluations performed are concentrated on smaller sized payloads and thus run quickly. The final optimization of inverse filtering relies upon a further exploitation of the early-out evaluation speedup toprovide prediction of results via monitoring of executiontime as well as fast computation of upper length bounds.Consider evaluating the 802.3 polynomial at the breakpoint being discovered, i.e. at lengths of 2974 bits and 2975bits with early-out evaluation. Evaluation of the first fourweights at 2974 bits takes 2.7 seconds to determine that allfour are zero. However, evaluation at 2975 bits takes only1.9 seconds to determine that there is at least one unde - tected 4-bit error at that length. Full evaluation to find outthere is in fact exactly one such undetected error takes thefull 2.7 seconds at 2975 bits, but the early-out approachdoes not have to complete the full computation since it hap - pens to find the undetected error 1.9 seconds into the com - putation. This illustrates that early-out location of anundetected error at a longer length can be faster thandiscovering that all errors are detected at a shorter length. Thus, a search that biases its selections to increase the probability that it will look above a break point rather thanbelow it will tend to run faster. In this particular case thespeed differential is small enough that the results of em-ploying this technique are not clear-cut. But at longer mes-sage lengths the results are significant. An application ofparticular importance is attempting to find the highestlength at which no possible polynomial provides a particu-lar HD as opposed to a search that evaluates many polyno-mials offering a particular HD. As a further example of an opportunity for inverse filter - ing, computing that HD<6 for 0xBA0DC66B at 16361 bitstakes 7.4 seconds via finding at least one non-zero weightamong the first five weights. But confirming that at 16360bits has HD=6 would take approximately 19 days. Thuswhen finding this breakpoint, the binary subdivision searchstrategy was modified to abort an evaluation after 30 sec - onds and to consider long execution time to be an implicitconfirmation of HD=6 for any particular length, homing inon 16361 as the shortest length with HD<6. Then a singlecalculation at a length of 16360 can be permitted to run tocompletion in order to confirm the result. Of course many combinations of these filtering tech - niques are possible. An important one for this work wasfirst obtaining a list of HD=5 and HD=6 polynomials atEthernet MTU data word lengths (as a filtering step basedon increased lengths). Then this small list of polynomialswas inverse filtered with lengths working downward from128K bits to find the maximum data word lengths for HD=5and HD=6 without having to actually compute completeHD values.4.2. Experimental results In the end, even with all the filtering and computational techniques that could be brought to bear, the enumerationof all billion possible 32-bit polynomials was a formidabletask. The initial filtering lasted from late May to early Sep - tember 2001 and made use of otherwise idle workstations.Approximately 50 Alphastations (an even mix of 400 MHzand 500 MHz processors) were kept running continuouslyfor over three months, and 30 UltraSparc machines wereused intermittently for two months. When the computa - tions had been completed, all polynomials with HD>4 at a12112 bit data word length had been discovered via filter - ing out polynomials failing to have zero 2-, 3-, and 4-bitweights. The average computation rate was approximately two polynomials filtered per second per CPU. This filteringtechnique implemented on a general purpose workstationwas an order of magnitude more efficient than exact evalua - tion using special purpose hardware as reported in[Castagnoli93]. Specifically, filtering was more than 200times faster in absolute terms, but took advantage of newertechnology with a 10-time faster clock speed for an overallspeedup of more than 20 on a clock-for-clock basis. Thetime required to filter any particular polynomial was vari-able because it depended on how long it took to encounterthe first non-zero weight, but the vast majority of polyno-mials benefitted from examining errors involving one ortwo bits in the FCS field first. Further filtering at HD=5 of those polynomials left 21,292 polynomials with HD=6 at 12112 bit messagelengths. Evaluating the precise weight of each HD=6 poly- 8# Factors Size of Factors# Distinct Polynomials 3 {1,1,30} 658 3 {1,3,28} 4484 {1,1,15,15} 98874 {1,1,2,28} 8954 {1,3,14,14} 41545 {1,1,1,1,28} 4485 {1,1,2,14,14} 26396 {1,1,1,1,14,14} 2263 Table 2. Number of polynomials having HD=6 at MTU length for different irreducible factorizations. nomial is still impractical, but is expected to become practi - cal in a few years with faster workstations. Of the HD=5 polynomials, the {1,1,15,15} class investi - gated by Castagnoli et al. was verified to indeed provide its claimed properties. Further filtering analysis indicated that the class {1,1,30} had similar properties. A potentially use - ful polynomial reported in Table 1 is 0x90022004=(0x1/c2150x1/c2150x2FFF5FFE), which is the polynomial with the fewest non-zero coefficients that attains HD=6 up to almost32Kb. (Having only five non-zero coefficients may help increating high-speed combinational logic implementation ofCRCs by reducing logic synthesis minterms.)0x992C1A4C=(0x1 /c2150x1/c2150x2D095216) was also selected for characterization as a representative {1,1,30} polyno - mial and has error detection performance comparable toCastagnoli’s {1,1,15,15} polynomial. As it turns out, all polynomials with HD=6 were divisi - ble by (x+1) as shown in Table 2. This gives them the prop - erty of incorporating an implicit parity bit, enabling them todetect all odd number of bit errors. No polynomials were found that best Castagnoli’s {32} primitive polynomial at or above 12112 in terms of HD.Due to computational resource limitations, filtering was notattempted on the very large number of primitive 32-bitpolynomials to see if there were one with HD>4 at a lengthbeyond 1060 bits. However, it is certain that none hasHD>4 at 12112 bits because all {32} polynomials found atthat length are irreducible but non-primitive. The {32}polynomial 0x80108400 was identified as a polynomialwith the minimum possible number of non-zero coeffi-cients that achieved HD=5 up to nearly 64Kb. Inverse filtering was used to ensure that there were no possible polynomials of any class with HD=6 at or above32739 bits and no polynomials with HD=5 at or above65507 bits of data word length. The newly found polyno - mials reported in Table 1 extend one or two bits of dataword length past the Castagnoli polynomials at HD=5 orHD=6, although this is only a negligible improvement formost applications. 4.3. A better iSCSI candidate polynomial An example of an application for a new 32-bit CRC polynomial is iSCSI. iSCSI is a work in progress, but thepoint of discussing it is to demonstrate that new polynomi - als can and are being sought after for new standards as wellas demonstrate a concrete opportunity for improvementover existing recommended 32-bit polynomials. [Sheinwald00] concludes that [Castagnoli93]’s {1,31} polynomial 0x8F6E37A0 presents a good tradeoff betweenbeing no worse than the 802.3 CRC for MTU-size mes - sages, and maintaining HD=4 up to large data word sizes.And in fact, this polynomial is in the draft versions of iSCSIdocuments ( e.g., [Satran01]). Given that single Ethernet-sized packets are likely to be transported on an iSCSI network in addition to packedmulti-MTU data storage packets protected by a singleCRC, it would seem there is an advantage to having HD=6error detection coverage for MTU-sized data words in addi - tion to maintaining the HD=4 detection achieved by theiSCSI polynomial for long messages. Improved error de - tection performance can be achieved by using the {1,3,28}polynomial 0xBA0DC66B=(0x1 /c2150x6/c2150x82CA9A0) de - scribed in Table 1. This polynomial achieves HD=6 up toalmost 16Kb and HD=4 up to 114,663 bits, which is morethan 9 times an Ethernet MTU data word size and suffi - ciently large for iSCSI purposes. Thus, the use of thisnewly evaluated polynomial class offers an opportunity forimproved error detection for an emerging standard. 4.4. Other potential applications Stone et al. [Stone00] discovered that corrupted network packets are far more prevalent than might be anticipatedfrom bit error rates alone, with CRCs being relied upon todetect corrupted data once every few thousand packets. Asa solution they strongly urge use of an application-level er-ror checking code to supplement network error checking.The polynomials described in this paper offer a variety oflength vs. error detection performance tradeoffs for suchapplication usage. Another potential application for a 32-bit CRC polyno- mial that has both HD=6 for Ethernet MTU length mes-sages and HD=4 to longer lengths is for jumbo packets inGigabit Ethernet. Currently available Gigabit Ethernetcards seem to support a de facto standard of 9000-bytejumbo packet payload sizes (data word size of 72112 bits),and such an approach is entering consideration for stan - dardization. These jumbo packets use the existing IEEE802.3 polynomial. It might possibly be argued that sincenew interface cards have to be designed to operate at highbit rates, these new cards could have both the legacy poly - nomial for slower speed backward compatible messagesplus a new polynomial for high-speed messages. Unfortu - nately there is probably already enough hardware alreadybuilt for Gigabit Ethernet that doing so is unrealistic. Butthe opportunity might well remain for the next generationof Ethernet cards beyond 1 Gigabit per second speeds. 4.5. Validation Software validation was accomplished by a combination of reproducing known results for exhaustive searches of 8-and 16-bit polynomials, creating unit and system test pro - grams, comparing answers obtained with “simple” code to 9 optimized code, and comparing results to existing publica - tions for 32-bit polynomials. Two key invariants unrelated to the software implementation were monitored. Polynomials divisible by (x+1) were checked to ensure that all odd-numberedweights computed were in fact zero, even though the soft - ware did not exploit this fact when performing evaluations.Additionally, weight values were ensured to be non-de - creasing when computed over increasing payload lengths.(This weight check revealed a 32-bit counter overflowproblem in an early version of the code. That problemwould not have affected the results presented herein even ifit had not been fixed; but finding it provided some reassur - ance that results were being monitored quite closely.) 5. Conclusions An exhaustive search of all possible 32-bit CRC polyno - mials has revealed the existence of a class of polynomialsthat provides an excellent combination of error detectionperformance for long and short network messages. Arepre - sentative of that polynomial class is: 0xBA0DC66B(x 32+x30+x29+x28+x26+x20+x19+x17+x16+x15+x11+x10+x7+x6 +x4+x2+x+1) = (x+1)(x3+x2+1)(x28+x22+x20+x19+x16+x14 +x12+x9+x8+x6+1). This polynomial achieves HD=6 be- yond one Ethernet MTU (to a 16,360 bit data word length)and HD=4 to 114,663 bits, which is more than 9 times thelength of an Ethernet MTU. This gives two additional bitsof error detection ability at MTU-sized data words com-pared to the Ethernet CRC standard polynomial while notsacrificing HD=4 capability for data word sizes up to andbeyond 72K bits. Beyond the discovery of new polynomials, this work re - produces results using direct evaluation of error detectioncapability that were previously only obtainable using math - ematically based techniques. The results contained hereinhave been found to be consistent with a variety of previ - ously reported results, including results previously createdvia special-purpose hardware. The availability of a moreefficient search capability on standard hardware platformsopens up the possibility of identifying optimal polynomialsthat are customized to the particular message lengths ofspecific applications and special-purpose communicationnetworks. Finally, because complete coverage of all possible poly - nomials was obtained, certain classes of polynomials havebeen conclusively ruled out as viable for providing HD=6coverage for MTU-size data words. This includes all 32-bitprimitive polynomials and all polynomials that are not di -visible by (x+1). One unexpected finding was a publicationerror in the only previously published polynomial thatachieved HD=6 for MTU-size data words. Application of these results is possible in newly emerg - ing network and data storage standards such as InternetSCSI protocols as well as application-level CRCs that pro - vide increased data integrity checks. 6. Acknowledgments Significant use was made of equipment donated by Digi - tal Equipment Corporation (now Compaq). Additionalequipment support was provided by Intel. 7. References [Castagnoli93] Castagnoli, G., Braeuer, S. & Herrman, M., "Optimization of Cyclic Redundancy-Check Codes with 24 and32 Parity Bits", IEEE Trans. on Communications , Vol. 41, No. 6, June 1993. [Fujiwara85] Fujiwara, T., Kasami, T., Kitai, A. & Lin, S., "On the undetected error probability for shortened hamming codes",IEEE Trans. on Communications , vol. 33, no. 6, 1985, pp. 570-573. [IEEE85] IEEE standards for local area networks: carrier sense multiple access with collision detection (CSMA/CD) access method and physical layer specifications , ANSI/IEEE Std 802.3-1985. [IETF01] Internet Engineering Task Force, “IP Storage (ips) Charter,” http://www.ietf.org/html.charters/ips-charter.htm , accessed Nov. 10, 2001. [Lin83] Lin, Shu & d. Costello, Error Control Coding , Prentice-Hall, 1983.[Peterson72] Peterson, W. & E. Weldon, Error-Correcting Codes , MIT Press, Second Edition, 1972. [Satran01] Satran, J. et al. , “iSCSI”, Internet-Draft work in progress, http://www.ietf.org/internet-drafts/draft-ietf-ips-iscsi -08.txt , Sept. 30 2001, accessed Nov. 10, 2001. [Sheinwald00] Sheinwald, D., et al. , “iSCSI CRC/Checksum Considerations”, Internet-Draft work in progress, http://search. ietf.org/internet-drafts/draft-sheinwald-iscsi-crc-00.txt , May 7, 2001, accessed Nov. 10, 2001.[Stone00] Stone, J. & Partridge, C., “When the CRC and TCP checksum disagree”, ACM SIGCOMM Computer Communication Review: Proc. of the conference on Applications,Technologies, Architectures, and Protocols for ComputerCommunication , Aug. 2000, pp. 309-319. [Wells99] Wells, R., Applied coding and information theory for engineers , Prentice-Hall, 1999. 10