{'fraction_non_alphanumeric': 0.08217300271343668, 'fraction_numerical': 0.03026092181734534, 'mean_word_length': 3.28827958288038, 'pattern_counts': {'":': 0, '<': 81, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 85, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fast CRCs (Extended Version)

CRCs have desirable properties for effective error detection. But their software implementation, which relies on many steps of the polynomial division, is typically slower than other codes such as weaker checksums. A relevant question is whether there are some particular CRCs that have fast implementation. In this paper, we introduce such fast CRCs as well as an effective technique to implement them. For these fast CRCs, even without using table lookup, it is possible either to eliminate or to greatly reduce many steps of the polynomial division during their computation.


INTRODUCTION
This paper considers cyclical redundancy checks (CRCs), which are effective for detecting errors in communication and computer systems. An h-bit CRC is typically generated by a binary polynomial of the form M (X) = (X + 1)M 1 (X) (1) where M 1 (X) is a primitive polynomial of degree h − 1. Existing CRCs include the CRC-16 generated by X 16 + X 15 + X 2 + 1 = (X + 1)(X 15 + X + 1), and the CRC-CCITT generated by X 16 + X 12 + X 5 + 1 = (X + 1)(X 15 + X 14 + X 13 + X 12 + X 4 + X 3 + X 2 + X + 1). The CRC generated by (1) has the following desirable properties: (a) its maximum length is 2 h−1 − 1 bits, (b) its minimum distance is d = 4, i.e., all single and double errors are detected, (c) its burst-error detecting capability is b = h, i.e., all error bursts of length up to h bits are detected, and (d) its codewords have even weights, i.e., all odd numbers of errors are detected. These properties are called the guaranteed error-detecting capability. The CRC may detect other errors, but not guaranteed, e.g., it can detect a large percentage of error bursts of length greater than h [2,12,18]. General theory and applications of error-detection codes are presented in [8].
General-purpose computers and compilers are increasingly faster and more sophisticated. Software algorithms are commonly used in operations, modeling, simulations, and performance analysis of systems and networks. CRC implementation in software is desirable, because many computers do not have hardware circuits dedicated for CRC computation. However, software implementation of typical CRCs is slow, because it relies on many steps of the polynomial division during CRC computation. It is this speed limitation of CRCs that leads to use of checksums (which are fast and typically do not rely on table lookup) as alternatives to CRCs in many high-speed networking applications, although checksums are weaker than CRCs. For example, the 16-bit one's-complement checksum is used in Internet protocol and the Fletcher checksum is used in ISO [6,21]. There are also other fast error-detection codes [4,5,14,15], but they do not have all the desirable properties of CRCs.
A relevant question is whether there is a new family of CRCs that are faster the existing CRCs. In this paper, we introduce such CRCs, as well as a technique for their efficient implementation. For these fast CRCs, it is possible either to eliminate or to greatly reduce many steps of the polynomial division during their computation.
A common existing technique for reducing the many steps during CRC computation is to use table lookup, which requires extra memory [11,17,18,20]. In contrast, even without table lookup, our fast CRCs require only a small number of steps for their computation. Algorithms that do not rely on table lookup have an advantage of being less dependent on issues such as cache architecture and cache miss. In particular, it is possible to use as low as 1.5 operations per input message byte to encode our fast 64-bit CRC (which is implemented in C and requires no table lookup).
This paper, an extension of [16], is organized as follows. In Section 2, we review known facts about CRCs, which serve as the background for our discussions. We present several different algorithms for computing CRCs, some of which are designed especially for our fast CRCs. In Section 3, we identify the form of the generator polynomials for the fast CRCs, and introduce a new technique for their implementation. We R M(X) (0, 0, . . . , 0, U (X))X h = R M(X) U (X)X h = P (X). That is, the first tuple now also has s bits, the (s − r) left-hand bits of which are always zeros.
Because each tuple i has s bits, it can be represented by a polynomial Q i (X) of degree < s. Thus, the input message is represented by U (X) = (Q 0 (X), Q 1 (X), . . . , Q n−1 (X)). We emphasize that, for given h and l, we are free to choose the value of s (commonly chosen values are s = 8, 16, 32, and 64 bits). As shown later, the choice of s can have significant impact on CRC speed.
Define U i (X) = (Q 0 (X), Q 1 (X), . . . , Q i (X)) to be the first i + 1 input tuples, i.e., U 0 (X) = Q 0 (X) U 1 (X) = (Q 0 (X), Q 1 (X)) · · · U n−1 (X) = (Q 0 (X), Q 1 (X), . . . , Q n−1 (X)) = U (X) Thus, for i = 1, 2, . . . , n − 1, U i (X) is determined from U i−1 (X) and Q i (X) by For i = 0, 1, . . . , n − 1, let P i (X) be the CRC check polynomial for the partial input message U i (X), i.e., In particular, we have P 0 (X) = R M(X) Q 0 (X)X h , and which is the CRC check polynomial for the entire input message U (X). Substituting (2) into (3), we have Using (3), we then have for i = 1, 2, . . . , n − 1. Note that (4) is a straightforward generalization of a result in [18], which deals with the special cases h = 16 and s ∈ {8, 16}. Thus, the check tuple P i (X) is computed from Q i (X) and the previous check tuple P i−1 (X). Recall that P 0 (X) = R M(X) Q 0 (X)X h and P (X) = P n−1 (X) is the CRC check tuple for U (X). Using (4), P (X) is then computed via the following pseudocode: 1 P = 0; 2 for (0 ≤ i < n) 3 P = R M P X s + Q i X h ; 4 return P ; Remark 1. We now review the computational complexity of the polynomial division, which is needed in CRC computation. Given 2 polynomials W (X) and Y (X), let V (X) = R W (X) [Y (X)] be the remainder polynomial that is obtained when Y (X) is divided by W (X). Let w and y be the degrees of W (X) and Y (X), respectively. If y < w (i.e., y − w + 1 ≤ 0), then V (X) = Y (X), i.e., no polynomial division is needed to obtain the remainder V (X). If y ≥ w, we then need the polynomial division that requires a loop of y − w + 1 iterations to obtain the remainder V (X) (see [9], p. 421). To summarize, the polynomial "long division" for computing R W (X) [Y (X)] requires a loop of max(0, y − w + 1) iterations. ⊔ ⊓

Two CRC Algorithms
From (4), we have P i (X) = R M(X) (P i−1 (X) + Q i (X)X h−s )X s (5) if s < h, and if s ≥ h. The CRC algorithms based on (5) and (6)

Two Alternative CRC Algorithms
We now present 2 alternative CRC algorithms, which will be applied to our fast CRCs (see Section 3).
Case 1: s < h. The CRC check polynomial P j (X) for the partial input message U j (X) can be divided into 2 parts as P j (X) = (P j,1 (X), P j,2 (X)) = P j,1 (X)X h−s + P j,2 (X) (7) where P j,1 (X) and P j,2 (X) are polynomials with degree(P j,1 (X)) < s and degree(P j,2 (X)) < h − s. That is, P j,1 (X) and P j,2 (X) are the s left-hand bits and (h − s) right-hand bits of P j (X), respectively. Substituting (7) into (4), we have Because degree(P i−1,2 (X)X s ) < h = degree(M (X)), we have R M(X) [P i−1,2 (X)X s ] = P i−1,2 (X)X s . Thus, P i (X) = R M(X) (P i−1,1 (X) + Q i (X))X h + P i−1,2 (X)X s The CRC algorithm based on (8), called Algorithm 3, is shown in Fig. 3. Case 2: s ≥ h. Multiplying both sides of (6) by X s−h , we have P i (X)X s−h = R M(X) (P i−1 (X)X s−h + Q i (X))X h X s−h = R M(X)X s−h (P i−1 (X)X s−h + Q i (X))X h X s−h = R M(X)X s−h (P i−1 (X)X s−h + Q i (X))X s Define L j (X) = P j (X)X s−h . From (9), we then have L i (X) = R N (X) [(L i−1 (X) + Q i (X))X s ] (10) where N (X) = M (X)X s−h . Thus, L i (X) is computed from L i−1 (X) and Q i (X). Note that L 0 (X) = P 0 (X)X s−h , where P 0 (X) = R M(X) Q 0 (X)X h . We then have Because L i (X) = P i (X)X s−h , the term P i (X) is obtained by shifting L i (X) to the right by (s − h) bits. Note that degree(L i (X)) < s. We will show in Remark 2 that computing P i (X) via (10) is slightly faster than via (6). The CRC algorithm based on (10), called Algorithm 4, is shown in Fig. 4, where N (X) = M (X) s−h .   Remark 2. Suppose that s ≥ h. The check polynomial P (X) = P n−1 (X) = R M(X) U n−1 (X)X h can then be computed by Algorithm 2 (Fig. 2) or by Algorithm 4 (Fig. 4). We now show that, for bitwise implementation, Algorithm 4 is slightly faster than Algorithm 2. By comparing these 2 algorithms, we observe the following. First, the computation of R M(X) A(X)X h (in Fig. 2) and the computation of R N (X) [A(X)X s ] (in Fig. 4) have the same complexity, because each requires s iterations (by Remark 1). Next, the factor X s−h at line 4 of Fig. 2 disappears from line 4 of Fig. 4. Finally, one extra operation is required at line 7 of Fig. 4 to extract the h left-hand bits of the final B(X). The above observations imply that Algorithm 4 requires n − 1 fewer operations than Algorithm 2. Thus, for bitwise implementation, we will use Algorithm 4 when s ≥ h.

Basic CRC Algorithms
Given an input message U (X) and a generator polynomial M (X) of degree h, Algorithms 1-4 produce the same CRC check tuple P (X). That is, they are 4 different ways for accomplishing the same thing. The main difference among these algorithms is how the input message is divided into s-tuples Q i (X). Algorithms 1 and 3 are for s < h, whereas Algorithms 2 and 4 are for s ≥ h. As shown later, CRC speed depends on the choice of s. For flexibility, we allow the possibility that the same CRC is used by computers that have different architectures and capabilities. For example, one computer can choose a value of s for encoding a message to transmit to another computer (with different capabilities), which can choose a different value of s for detecting the errors in the received message. The above CRC algorithms require the polynomial divisions. In particular, Algorithm 1 requires the polynomial division R M(X) [A(X)X s ], Algorithms 2 and 3 require the polynomial division R M(X) A(X)X h , and Algorithm 4 requires the polynomial division R N (X) [A(X)X s ]. To simplify the presentation, we will use the single notation B(X) to denote all these polynomial divisions, i.e., we define where N (X) = M (X)X s−h . Note that degree(A(X)) < h in Algorithm 1, and degree(A(X)) < s in Algorithms 2-4. As seen in Figs. 1-4, CRC computation using any of the above 4 algorithms requires the computation of B(X) for n times. A known technique for computing B(X) is to use the polynomial long division algorithm mentioned in Remark 1. For example, consider Algorithms 2 and 3. We then have B(X) = R M(X) A(X)X h , where degree(A(X)) < s. Because degree(A(X)X h ) ≤ s + h − 1 and degree(M (X)) = h, from Remark 1, B(X) can be computed via the polynomial long division that requires a loop of s iterations. Similarly, it can be shown that computing B(X) in Algorithms 1 and 4 also requires a loop of s iterations. That is, the computational complexity for computing B(X) is O(s). Definition 1. The technique for computing the polynomial B(X) as given in (11) is called the basic technique. Using the polynomial long division, B(X) can be computed in s iterations. An algorithm (or a CRC) is basic if it uses the basic technique for computing B(X).

FAST CRCS
Recall that we are given an input message U n−1 (X) = (Q 0 (X), Q 1 (X), . . . , Q n−1 (X)), where Q i (X) is an s-tuple. We protect this message by an h-bit CRC generated by a polynomial M (X) of degree h. The check h-tuple P (X) = P n−1 (X) = R M(X) U n−1 (X)X h can be computed by Algorithm 1 or 3 (if s < h), or by Algorithm 2 or 4 (if s ≥ h). We emphasize that each of these algorithms requires the calculation of B(X) defined in (11), which involves the polynomial division.

Fast h-Bit CRCs
Our goal is to find some CRCs that have fast implementation, i.e., to find a new family of generator polynomials M (X) for CRCs that have low complexity. Recall that the CRC algorithms (Figs. 1-4) depend on the term B(X). Computation of B(X) is also the most expensive step in the algorithms. Thus, finding fast CRCs requires finding the polynomials M (X) that yield fast computation of B(X). The first technique for computing B(X) is the basic technique in Definition 1. Using the polynomial division, we can compute B(X) by a loop of s iterations. In the following, we present the second technique, called the new technique, for computing B(X). While the new technique is applicable to any generator polynomial M (X), it is more effective for some special CRC generator polynomials, called the fast polynomials. Recall that the basic CRCs can use Algorithm 1 or 3 (if s < h), or by Algorithm 2 or 4 (if s ≥ h). However, as seen in the following, the fast CRCs use only Algorithms 3 (for s < h) and 4 (for s ≥ h) for their bitwise implementation.
We now introduce a new family of CRCs, which are generated by the following polynomials for all h ≥ 4. We ignore the case h = 3, which yields the trivial repetition code {(0000), (1111)}. We call F h (X) the "fast polynomial," which can be factored into where G m (X) = X m + X m−1 + · · · + X 3 + X 2 + 1 (13) i.e., G m (X) includes all the terms except X. At first, it is not clear why this particular polynomial F h (X) will speed up the computation of B(X). We now introduce a technique that is applied to F h (X) to yield fast computation of B(X). By considering Algorithms 3 and 4, we have from (11) 14) where N (X) = M (X)X s−h , and A(X) is a polynomial of degree less than s. We now transform B(X) into a new form that will be used by the fast CRCs. First, note that Thus, (14) becomes where N (X) = M (X)X s−h . Definition 2. Using Algorithms 3 and 4, the technique (15) for computing the polynomial B(X) is called the new technique. The CRC that is generated by the fast polynomial F h (X) = X h + X 2 + X + 1 and uses the new technique for computing B(X) is called the fast h-bit CRC. Theorem 1. Using Algorithms 3 and 4, the polynomial B(X) for the fast CRC generated by F h (X) = X h + X 2 + X + 1 is given by where N (X) = F h (X)X s−h , and A(X) is a polynomial of degree less than s. Further, using the polynomial division, B(X) can be computed with max(0, s − h + 2) iterations.

⊔ ⊓
Let us briefly compare the computational complexity of B(X) for (a) the basic h-bit CRC generated by M (X) and (b) the fast h-bit CRC generated by F h (X). For the basic CRC, by Definition 1, B(X) is computed via a loop of s iterations, regardless of the form of M (X). However, for the fast CRC, by Theorem 1, B(X) is computed via a loop of only max(0, s − h + 2) iterations. Thus, the fast CRC is much faster than the basic CRC if s is chosen such that s − h + 2 is much small than s. Further, if s + 1 < h, then max(0, s − h + 2) = 0 and B(X) = A(X)(X 2 + X + 1), i.e., the polynomial division is eliminated. Section 4 presents CRC software complexity in more detail.
We emphasize that the fast h-bit CRC denotes a CRC that meets the following 2 conditions: (a) it is generated by the fast polynomial F h (X) = X h + X 2 + X + 1, and (b) the polynomial B(X) is computed via Theorem 1 by applying the new technique (15) to F h (X). That is, the fast CRC refers to a CRC that is generated by a specific polynomial and is implemented by a specific technique. Note that a CRC that meets only one of the above 2 conditions may not have any speed advantage over a basic CRC. For example, suppose that, instead of the new technique (15), the basic technique (in Definition 1) is applied to the CRC generated by the fast polynomial F h (X). This CRC is then not different from a basic CRC in terms of computational complexity. Application of the new technique to polynomials other than F h (X) is considered in Appendix C.
To summarize, the fast h-bit CRC is generated by F h (X) = X h + X 2 + X + 1. Under bitwise implementation, the fast CRC uses Algorithm 3 if s < h and Algorithm 4 if s ≥ h. The term B(X) in these algorithms is given in Theorem 1.

A Fast 16-Bit CRC
We now consider the important case h = 16. Many CRCs (as well as weaker checksums) used in practice have 16 check bits, e.g., the CRC-16 and CRC-CCITT mentioned in Section 1. With a small amount of overhead, these CRCs can have length up to 2 15 − 1 bits ≈ 4,096 bytes. Our goal here is to present a concrete example of a new 16-bit CRC that is not only much faster than but also as good as existing 16-bit CRCs.
Our new 16-bit CRC is generated by which can be factored into It can be shown that G 15 (X) is a primitive polynomial, i.e., F 16 (X) is a product of X + 1 and a primitive polynomial (however, as seen later, this is not true for many values of h). Thus, this fast 16-bit CRC also has length up to 2 15 − 1 bits. Although the polynomial (17) is different from the generator polynomials for existing 16-bit CRCs, it does generate a CRC that has the same guaranteed error-detecting capability as existing 16-bit CRCs. From Theorem 1, we have In the following, we consider 2 cases: s = 8 and s = 16. First, assume that s = 8, i.e., the input message is organized in 8-bit bytes. Because s < 16, we have B(X) = R F16(X) A(X)(X 2 + X + 1) . Because degree(A(X)) < s = 8, we have degree(A(X)(X 2 + X + 1)) < 10, which is smaller than degree(F 16 (X)) = 16. From Remark 1, we have B(X) = A(X)(X 2 + X + 1) i.e., B(X) is simply the sum of A(X) and its translations. Thus, computing B(X) via the new technique requires no polynomial division. In contrast, computing B(X) via the basic technique requires the polynomial division that has a loop of s = 8 iterations (see Definition 1). Next, assume that s = h = 16, i.e., the input message is organized in 16-tuples. Because s = 16, we have degree(A(X)) < 16 and degree(A(X)(X 2 + X + 1)) < 18. Thus, by Remark 1, B(X) is computed by the polynomial division that has a loop of 2 iterations. This contrasts with computing B(X) via the basic technique, which requires a loop of s = 16 iterations (see Definition 1). Thus, the loop iteration count of our new technique is less than that of the basic technique by the factor of 16/2 = 8.
To summarize, when the input message is organized in s-tuples, it is possible to have a fast 16-bit CRC that requires no polynomial division (when s = 8), or that requires the polynomial division that has only 2 loop iterations (when s = 16). Further, this fast 16-bit CRC has the same guaranteed error-detecting capability as existing 16-bit CRCs.
When computing B(X) via the new technique, although the case s = 16 requires more loop iterations than the case s = 8, we will see later in Section 4 that the case s = 16 has lower overall computational complexity (i.e., lower overall operation count per input byte). This is because, when s = 16, there is no need to compute P j,1 (X) and P j,2 (X) as defined in (7). Further, the overhead processing cost per input byte when s = 16 is lower than when s = 8. The C programs for the fast 16-bit CRC are shown in Fig. 8 and in Fig. 12 of Appendix A.

Error-Detection Capability of Fast CRCs
Recall that the maximum length of the h-bit CRC generated by (1) is 2 h−1 − 1 bits, i.e., this CRC has minimum distance d = 4 if its total bit length ≤ 2 h−1 − 1. In general, we define the maximum length of an error-detection code to be the total bit length at or below which its minimum distance is d ≥ 3, and beyond which its minimum distance will reduce to d ≤ 2. In the following, we determine the maximum lengths of the fast CRCs.
By definition, the period of a polynomial G(X) is the smallest positive integer i such that R G(X) X i = 1. In particular, it can be shown that the period of M (X) in (1), which is the product of X + 1 and a primitive polynomial of degree h − 1, is 2 h−1 − 1. Note that some polynomials, such as X 2 , do not have periods.
The period of the fast polynomial F h (X) = X h + X 2 + X + 1 can be computed directly from the definition (for small h) or from the technique in [1,Section 6.2]. The periods of F h (X), h ≥ 4, are shown in Fig. 5. The following theorems, which are slight variations of well-known results from cyclic codes [12,Chapter 4], show that the maximum length of a CRC equals the period of its generator polynomial. Theorem 2. Let C be a CRC generated by a polynomial M (X) of degree h ≥ 3. Assume that M (X) is not a multiple of X. Let n b and d be the bit length and minimum distance of C, respectively. We then have 3. C detects all error bursts of length up to h bits, i.e., b = h. Proof. Let t be the period of M (X). We must have t ≥ h. By definition, each codeword of C has the form where U (X) is the polynomial representing the input message, and P (X) is the check polynomial. Because for some polynomial K(X). Thus, we have i.e., C is a linear code. If d = 1, then X i = K(X)M (X), for some i. This implies that M (X) = X j for some j, which contradicts our assumption that M (X) is not a multiple of X. Thus, d ≥ 2. 1. We now prove, by contradiction, the statement d ≥ 3 if n b ≤ period of M (X). Thus, suppose that there is a codeword V (X) with length n b ≤ t and weight 2. Then V (X) = X j + X i for some i and j such that We also have V (X) = K(X)M (X) for some polynomial K(X). Thus, X i (X j−i + 1) = K(X)M (X). Because M (X) is not a multiple of X by assumption, M (X) must divide X j−i + 1, i.e., R M(X) X j−i = 1. Thus, j − i ≥ t = period of M (X). Then j ≥ t ≥ n b , which contradicts the condition n b > j. Thus, all the codewords of length n b ≤ t must have weight ≥ 3, i.e., d ≥ 3. 2. We construct a codeword with length > t and weight 2 as follows. Let U (X) = X t−h . Then P (X) = R M(X) U (X)X h = R M(X) [X t ]. We have P (X) = 1 because t is the period of M (X). Thus, the codeword V (X) = U (X)X h + P (X) = X t + 1 has length t + 1 and weight 2. That is, d = 2 if n b > t. 3. The fact that C detects all error bursts of length up to h bits (i.e., b = h) is well-known [12]. ⊔ ⊓ Theorem 3. Let C be the CRC generated by the fast polynomial F h (X) = X h + X 2 + X + 1. Let n b and d be the bit length and minimum distance of C, respectively. We then have 3. C detects all error bursts of length up to h bits, i.e., b = h. Proof. Let t be the period of F h (X). From the proof of Theorem 2, every codeword of C has the form V (X) = K(X)(X h + X 2 + X + 1) for some polynomial K(X). Thus, the codewords of C have even weight, i.e., d is even. Suppose now that the input message is U (X) = 1. Then P (X) = R F h (X) X h = X 2 + X + 1, which implies V (X) = U (X)X h + P (X) = X h + X 2 + X + 1. That is, the codeword V (X) has weight 4. Thus, d is either 2 or 4. From Theorem 2.1, we must have d = 4 if n b ≤ t. From Theorem 2.2, we must have d = 2 if n b > t. The fact that C detects all error bursts of length up to h bits is well-known [12].
⊔ ⊓ Parts 1 and 2 of Theorem 2 show that the maximum length of a CRC equals the period of its generator polynomial (which, by assumption, is not a multiple of X). Theorem 2 also explains why, as seen above, both the maximum length of the h-bit CRC generated by (1) and the period of its generator polynomial equal 2 h−1 − 1. Similarly, parts 1 and 2 of Theorem 3 show that the maximum length of the fast h-bit CRC equals the period of its generator polynomial F h (X) = X h + X 2 + X + 1.  5 shows that the maximum length of the fast h-bit CRC is also 2 h−1 − 1 in many important cases, namely when h = 8, 16,24,48,64,128. In fact, F h (X) = X h + X 2 + X + 1 is also the product of X + 1 and a primitive polynomial at these values of h, i.e., the polynomial G h−1 (X) in (13) is primitive when h = 8, 16,24,48,64,128. Fig. 5 also shows that the maximum lengths of many fast h-bit CRCs are substantially less than the upper bound 2 h−1 − 1 (e.g., when h = 12 and h = 32). However, in Appendix C, we apply our new technique to more general generator polynomials to yield other fast CRCs whose maximum lengths can approach the upper bound.  Fig. 5 The period of F h (X) = X h + X 2 + X + 1 [= the maximum length of the fast h-bit CRC generated by F h (X)].

CRC SOFTWARE COMPLEXITY
We now analyze and compare CRC software complexity. Software complexity of an algorithm refers to the number of operations (i.e., operation count) used to implement the algorithm. Our goal in this paper is to compute the CRC check h-tuple P (X) for an input message that consists of n tuples Q 0 (X), Q 1 (X), . . . , Q n−1 (X). Each tuple Q i (X) has s bits. This CRC can be either a basic CRC generated by a polynomial M (X) of degree h, or the fast CRC generated by F h (X) = X h + X 2 + X + 1. For bitwise implementation, while Algorithm 1, 2, 3, or 4 can be used for the basic CRC, only Algorithm 3 or 4 are used for the fast CRC. The check tuple P (X) is computed by using a loop that computes B(X) for n times, where B(X) is given in Definition 1 for the basic CRC and in Theorem 1 for the fast CRC.
In this section, we compute e b and e f , which denote the software operation counts per input byte required for computing the check tuple P (X) for the basic CRC and the fast CRC, respectively. These operation counts will then be used to compare the complexity among our fast CRCs, the basic CRCs, the other fast CRCs in [5], and the block-parity checksum. An error-detection code is said to be "faster" than another if, for a similar level of memory requirement, it has lower software complexity.

General Complexity Analysis
We now provide the complexity analysis for the important case s = h for the basic CRC and the fast CRC (other cases can be analyzed similarly). Both Algorithms 2 and 4 (shown in Figs. 2 and 4) then reduce to Fig. 6. Here, we have for the basic CRC (see Definition 1), and for basic CRC RF A(X 2 + X + 1) ; for fast CRC 6 } 7 P = B; 8 return P ;   (18) can be computed as follows. First, we write A(X)X s = (· · · (A(X)X) · · ·)X. Thus, B(X) can be computed in s iterations via the following pseudocode: Let us now consider the term B(X) in (19) for the fast CRC. We have where also has operation count u. There are also 2 binary additions (i.e., 2 XOR operations) in (22). Thus, the operation count required for computing B(X) in (22) for the fast CRC is 2u + 2.
Let us now determine the total operation counts t b and t f for computing the check tuple P (X) for the basic CRC and the fast CRC, respectively. The CRC algorithm for computing P (X), which is shown in Fig. 6, has a loop of n iterations. In addition to the operation count for B(X), there is also one addition as indicated in line 4 of Fig. 6. Let l n be the operation count for the loop overhead shown at line 2 of Fig. 6. We then have The basic CRC and the fast CRC require t b and t f operations, respectively, to compute the check tuple P (X) for the input message that has ns bits, i.e., t b /(ns) and t f /(ns) operations are required per input bit.
Recall that e b and e f denote the operation counts per input 8-bit byte required for computing the check tuple P (X), for the basic CRC and the fast CRC, respectively. We then have e b = 8t b /(ns) and e f = 8t f /(ns). Using (23) and (24), we have Simple estimates are t b ≈ nsu [by ignoring l n + 1 and l s in (23)] and t f ≈ n2u [by ignoring l n + 3 in (24)]. Substituting these into (27), we have i.e., the fast CRC is approximately h/2 times faster than the basic CRC. We use the following 2 rules to count the number of software operations Appendix A: (R1) The operation count of a program statement is defined as the number of operations, other than the equal sign (=), that appear in that statement. (R2) For an if-statement, we average the operation count of the if-statement and the operation count of its alternative (e.g., an else-statement).

CRC Complexity Under C Implementation
The non-zero operation count for each C program statement is recorded between the comment quotes (/* */). The programs show that l n = l s = 2. Using (20)  Further, if s = h = 64, then e f = 1.50, e b = 44.4, and e b /e f = 29.6, i.e., the fast 64-bit CRC is 29.6 times faster than the basic 64-bit CRC. These results are recorded in Fig. 9. We now briefly present the complexity results for s, h ∈ {8, 16, 32, 64}, but without the restriction s = h. From (37) and (39) of Appendix A, we have For a given h, recall from Section 2.1 that we are free to choose the value of s. The complexity of the basic CRCs is rather insensitive to the choice of s. As seen in Fig. 9, when h ∈ {8, 16, 32, 64}, the complexity of the fast CRCs is fairly low when s < h, and is minimized when s = h. When h / ∈ {8, 16, 32, 64}, it is shown in Appendix A that the complexity of the fast CRCs is minimized (i.e., e f is minimized) either at s = h or at s = h − 2.
To summarize, we introduce the new family of CRC generator polynomials that have the explicit form F h (X) = X h + X 2 + X + 1, for all h ≥ 4, as well as the new technique (15) for their implementation. This family includes F 8 (X), which generates the ATM CRC-8. For this particular CRC, by choosing s = h = 8, our new technique provides a new bitwise implementation that is 3.92 times faster than the basic bitwise technique (see Fig. 9).

Remark 4.
There exist well-known techniques for reducing the operation counts used in CRC implementation. An example is the use of table lookup (at the cost of increased memory and cache usage), which is presented in Appendix A. Note that, to keep our C programs compact, readable, and general, we ignore software optimization techniques (such as loop unrolling) in our C programs. However, these techniques certainly can be used to reduce the operation counts in the programs. For example, if loop unrolling is used (at the cost of code size expansion) in the inner for-loop of the C program in Fig. 7, then the index increment and the end-of-loop test are eliminated, i.e., the loop overhead l s is reduced from l s = 2 to l s = 0. Using loop unrolling (i.e., l s = 0), it can be shown that (30)

Other Techniques for Error-Detection Codes
The complexity results for the basic CRC algorithm, which are rather insensitive to the input parameters s, h, and the form of the generator polynomial M (X), are shown in Fig. 9. In particular, when h = 16 and s = 8, we have e b = 48 operations per input byte. Our CRC software implementation in C for this case is shown Fig. 11 of Appendix A, which is more efficient than the one given in [2, pp. 555-556], which has 63 operations per input byte according to rules (R1) and (R2).
There are other CRC algorithms that are much faster than the basic algorithm. As expected, those algorithms are effective for some particular generator polynomials. For example, the clever "add and shift" algorithm of [5] is fast for the CRCs generated by M 1 (X) = X 32 + X 31 + X 8 + 1 (for h = 32) and M 2 (X) = X 64 + X 63 + X 2 + 1 (for h = 64), which are found by computer search [5]. According to rules (R1) and (R2) for determining the operation counts, these CRCs use 20 operations to process each tuple of s = 32 input bits (see Fig. 2 in [5]). Thus, these CRCs use 5 operations per input byte. In contrast, from Fig. 9, for s = 32, our fast CRCs use only 3 and 2.5 operations per input byte for h = 32 and h = 64, respectively. Thus, our fast CRCs are faster than the above shift-and-add CRCs. Further, our fast 64-bit CRC is even much faster when s = 64, because it uses only 1.5 operations per input byte (see Fig. 9).
As mentioned in Section 1, alternatives to CRCs are checksums. Although checksums are weaker than CRCs, they can be substantially faster than CRCs. For example, let s = h and consider the block-pariry checksum. The check tuple P (X) of this checksum is simply the sum of all the input tuples, i.e., P (X) = n−1 i=0 Q i (X). As shown in Section B.1, the operation count per input byte required for computing P (X) of the checksum is e = 24/s. From (31), the fast CRC has e f = 96/s. Thus, e f /e = 96/24 = 4, i.e., the checksum is 4 times faster than the fast CRC.

SUMMARY AND EXTENSION
Error control coding is essential for reliable transmission and storage, and CRCs are known to be effective for error detection. In software, an h-bit CRC is typically implemented by dividing the input message into stuples (i.e., blocks of s bits). The output CRC check bits are obtained by recursively carrying the polynomial division on these tuples.
Thus, the crucial part in CRC computation is the polynomial division on s-tuples. For the basic CRCs, this division requires s iterations, which may be expensive for many applications. A common technique for reducing the many steps during CRC computation is to use additional memory in the form of table lookup. In this paper, we introduce the fast h-bit CRCs, which are generated by F h (X) = X h + X 2 + X + 1, as well as the new technique (15) to implement them. Using our fast CRCs, the polynomial division on s-tuples requires only max(0, s − h + 2) iterations, which are much less than the s iterations required for the basic CRCs, as long as s is chosen such that s − h + 2 is much smaller than s. We study the computational complexity of the CRCs, which refers to the operation count per input byte required for computing the CRC check tuples. Our fast CRCs have low complexity and require no table lookup. For the important case s = h, the fast h-bit CRCs are approximately h/2 times faster than the basic h-bit CRCs.
As an illustration, we implement the CRCs in C programming language, and then study their computational complexity for the bitwise technique (i.e., without table lookup). We show that the complexity of the fast h-bit CRCs varies greatly with s, and is minimized either at s = h − 2 or at s = h. In contrast, the complexity of the basic h-bit CRCs varies little with s. Because modern computers typically process information in bytes or words, we also present the complexity results when s is restricted to multiples of byte size and word size.
In the Appendices, we provide several extensions to the baseline ideas presented in this paper. In particular, we present the results for CRC table-lookup techniques, which illustrate tradeoffs between computational complexity and memory requirement. We show that when s = h, the fast CRCs can be made 20 percent faster by using tables of only 4 entries. We apply our new technique to some weaker CRCs to yield even faster CRCs, i.e., there are tradeoffs between speed and capability. Further, we use the new technique to construct some fast extended Hamming perfect codes. In particular, we construct h-bit non-CRC codes that not only have low complexity but also have the following optimal properties. They have the minimum distance d = 4, the burst-error-detecting capability b = h, and the maximum code length 2 h−1 . We also apply the new technique to arbitrary CRCs, and then determine the conditions under which the new technique remains effective. In particular, the new technique is substantially faster than the basic technique for the CRC-64-ISO generated by X 64 + X 4 + X 3 + X + 1. Using computer search, we obtain CRCs that have minimum distance greater than 4 and can be efficiently implemented by the new technique. We also obtain CRC weight distributions required for estimating the undetected error probability over binary symmetric channels. Finally, we show how the CRCs algorithms, which are originally designed for sequential implementation on a single processor, can be adapted for parallel implementation on multiple processors.

APPENDIX A CRC SOFTWARE IMPLEMENTATION AND COMPLEXITY EVALUATION
The purpose of this appendix is to present software implementation for the CRC algorithms as well as to evaluate their computational complexity. Software complexity of an algorithm refers to the number of operations (i.e., operation count) used to implement the algorithm. Consider an h-bit CRC, which is generated by a polynomial M (X) of degree h. Our goal is to compute the check h-tuple P (X) for an input message that consists of n tuples Q 0 (X), Q 1 (X), . . . , Q n−1 (X). Each tuple Q i (X) has s bits.
The CRC can be implemented by any of the 4 algorithms shown in Figs. 1-4. Although the value of h is fixed, we are free to choose the value of s. Algorithms 1 and 3 are for s < h, whereas Algorithms 2 and 4 are for s ≥ h. One algorithm can be faster than another, depending the value of s and the form of M (X).
For example, Remark 2 shows that, for bitwise implementation, Algorithm 4 is faster than Algorithm 2 when s ≥ h. Thus, we will use Algorithm 4 for bitwise implementation when s ≥ h, as indicated in Fig. 10. As stated in Theorem 1, Algorithm 3 must be used for the fast CRCs when s < h. Fig. 10 lists the CRC algorithms that are used in our software implementation.
We recognize that accurate software evaluation is complicated, and requires experiments with different processors, memory organizations, programming languages, and compilers. Other complicating factors include programming styles and the extend the CRCs must share with (or compete against) other concurrent/interupting programs. Instead of dealing with these complex issues, which are beyond the scope of this paper, we simply use software operation counts for our complexity evaluation. Our technique of software comparison is as follows. We write a program (e.g., in C) for each CRC. We then use the operation count as the primary measure of complexity, and a CRC is said to be "faster" than another if it has lower operation count.
We now determine the software complexity of the CRC algorithms, which refers to the operation count per input message byte required for computing the check h-tuple. Let us examine Algorithms 1-4 (shown in Figs. [1][2][3][4]. For each algorithm, the check tuple P (X) is computed by using a loop that computes B(X) for n times, where B(X) is given in Definition 1 for the basic CRC and in Theorem 1 for the fast CRC. In addition to B(X), we also need to compute all the other terms inside the loop (which include the loop overhead). Let r and x be the operation counts required for computing B(X) and the other terms inside the loop, respectively. Let y be the operation count required for computing the terms outside the loop. Further, for each algorithm, let t be the total operation count required for computing the CRC check tuple from the input message that consists of n tuples. We then have t = (x + r)n + y.
Let e be the operation count per input byte required for computing the check h-tuple. Each byte has 8 bits. Because t is the operation count for computing the check h-tuple from the ns input message bits, we have e = 8t/(ns) = 8[(x + r)n + y]/(ns), i.e., In the following, we consider h, s, and n to be independent variables, and our goal is to compute e in terms of h, s, and n for both the basic CRCs and the fast CRCs. That is, we can write e = e(s, h, n). To compute e, we need to determine r, x, and y, to which we add the subscripts b and f when they refer to the basic CRCs and the fast CRCs, respectively. That is, r b , x b , y b , and e b refer to the basic CRCs, while r f , x f , y f , and e f refer to the fast CRCs. We present CRC implementation with and without table lookup. Our software programs are for w-bit computers that satisfy s ≤ w and h ≤ w (however, we allow the possibility that h + s > w). For example, 32-bit computers are for s, h ≤ 32 bits, while 64-bit computers are for s, h ≤ 64 bits (future 128-bit computers are for s, h ≤ 128 bits). To be specific, we implement the CRC algorithms in C, which is a highly portable general-purpose computer programming language (certainly, they can also be implemented in other computer languages). We use the following 2 simple rules to count the number of software operations [15]: The operation count of a program statement is defined as the number of operations, other than the equal sign (=), that appear in that statement.
(R2) For an if-statement, we average the operation count of the if-statement and the operation count of its alternative (e.g., an else-statement).
Let us consider examples on how to use rule (R1). The statement C = (A<<1)∧F will count as 2 operations (<< and ∧ ). Note that "=" does not count as an operation. Next, consider the statement for(i=0; i<n; i=i+1){ }. This implements a (null) loop of n iterations, each iteration has 2 operations (< and +). Thus, the total operation count for this loop statement is 2n. The for-loop above is equivalent to the while-loop i=0; while(i<n){i=i+1;} which, of course, also has 2n operations.
The above 2 statements are equivalent to the the following 2 statements: C = A<<1; if ((A&K) != 0) C = C∧F; Here, the first statement has 1 operation, and the second statement has 2.5 operations. Thus, the 2 statements together also have 3.5 operations as expected. Note that (A&K)∈ {0, 1}, because K = 1. Here, for simplicity, we assume that (A&K) takes the values 0 and 1 with equal probability of 1/2. Suppose now that K = 3. We then have(A&K)∈ {0, 1, 2, 3}. By assuming that (A&K) takes the values 0, 1, 2, and 3 with equal probability of 1/4, the above if-statement (which has 4 operations) is executed with probability 3/4 and the elsestatement (which has 3 operations) is executed with probability 1/4. Thus, these if-else statements can be considered as a single statement that has 4 × 3/4 + 3 × 1/4 = 3.75 operations. Remark 5. Rules (R1) and (R2) serve as a simple technique for comparing the complexity of different CRCs, i.e., they will be used to obtain a first-order estimation of the ratio e b /e f . These rules are intended only for CRC algorithms that are implemented in C, and not for other types of algorithms or other programming languages. As seen in the following, our CRC software implementation uses only a small number of elementary C operators (namely, +, <<, >>, =, ==, !=, <, <=, &, and ∧) and C keywords (namely, char, short, int, long, unsigned, if, else, for, while, and return). Our following C programs (using the big-endian convention) for the CRCs are written in a style that is intended to be simple and straightforward. See also Remark 6.
Other techniques for counting operations are also possible. For example, consider rule (R1 ′ ), which is defined as rule (R1) but also counts the equal sign (=) as an operation. Let e ′ b and e ′ f denote the resulting operation counts under (R1 ′ ). We must have e ′ b > e b and e ′ f > e f . Although the difference between e b and e ′ b (as well as between e f and e ′ f ) can be significant, the difference between the ratios e b /e f and e ′ b /e ′ b /e ′ f ≈ e b /e f . Note that rule (R1), which is used in this paper, is slightly simpler to use than rule (R1 ′ ). Thus, our technique for counting software operations is reasonable for the purpose of complexity comparison, i.e., we are more interested in the ratio e b /e f , rather than in e b and e f .
Here, for simplicity, we assign the same unit cost to each operation. A more elaborate technique would assign different costs to different operations. However, this assignment depends on many factors (such as computer hardware, operating system, processor architecture, and memory organization), which are outside the focus of this paper.
⊔ ⊓ Let us now compute x and y in (32). The computation of r is deferred to later subsections. First, consider Fig. 11, which shows the C program for bitwise implementation of the basic CRC for the case s < h. As indicated in Fig. 10, this program is based on Algorithm 1. In this program, we assume that h ∈ {8, 16, 32, 64}, i.e., h is the size (in bits) of one of the natural unsigned types of C: unsigned char, unsigned short int, unsigned int, or unsigned long int. The input is the n message s-tuples Q[0], Q [1], . . . , Q[n − 1], and the output is the CRC check h-tuple P .
We then apply rules (R1) and (R2) to the program shown in Fig. 11 to obtain the desired operation counts. The non-zero operation count for each program statement is recorded between the comment quotes (/* */). Recall that the total operation count for computing the check tuple P from the n input tuples is Here, r b is the operation count required for computing B(X), which is inside the loop indexed by i, x b is the operation count required for computing all the other terms in the loop besides B(X), and y b is the operation count required for computing all the terms outside the loop. From Fig. 11, we have x b = 4 and y b = 0.
To summarize, for h ∈ {8, 16, 32, 64} and s < h, we have x b = 4 and y b = 0, which are recorded in Fig. 13. For illustration, we let h = 16, s = 8 and M (X) = X 16 + X 15 + X 2 + 1 (which generates the well-known CRC-16) in Fig. 11. When h / ∈ {8, 16, 32, 64} and s < h, the computational complexity is slightly higher, namely, x b = 4 and y b = 1. Fig. 7 shows the C program for the basic CRC when s = h. Next, consider Fig. 12, which shows the C program for the fast CRC when h ∈ {8, 16, 32, 64} and s < h − 1. It can be shown that x f = 6 and y f = 0 for this case. Again, for illustration, we let h = 16 and s = 8 in Fig 12. Similarly, we can compute the values of x and y for all the cases for both the basic CRCs and the fast CRCs. The results are summarized in Fig. 13.
Using Fig. 13, the expression (32) can be simplified as follows. Let z be the ratio of the 2 terms on the right-hand side of (32), i.e., Fig. 13, we have 0 ≤ y ≤ 1 and x ≥ 3, which implies that z ≥ (x + r)n ≥ (3 + r)n ≥ 3n. Thus, 8y/(ns) is much smaller than 8(x + r)/s, because we assume in this paper that n is not too small (i.e., we assume that n > 4). Thus, the term 8y/(ns) can be dropped from (32). The operation count per input byte required for computing the CRC check h-tuple then simplifies to where x is determined from Fig. 13, which depends only on s and h, i.e., x = x(s, h). Recall that r denotes the operation count required for computing B(X), which also depends only on s and h [see (11)], i.e., r = r(s, h). It follows from (33) that e now also depends only on s and h, i.e., e = e(s, h). From (33), we also have where x b and x f are given in Fig. 13. In the following, using rules (R1) and (R2), we compute r b and r f for both the bitwise and the  A.1 CRC Software Implementation: Bitwise Technique (Without Table Lookup) According to Fig. 10, the bitwise implementation of the the basic CRCs uses Algorithm 1 for s < h, and Algorithm 4 for s ≥ h. From Fig. 13, we then have where r b denotes the operation count required for computing B(X) of the basic CRCs. According to Fig. 10, the bitwise implementation of the the fast CRCs uses Algorithm 3 for s < h, and Algorithm 4 for s ≥ h. From Fig. 13 where r f denotes the operation count required for computing B(X) of the fast CRCs. Both r b and r f are computed in the following subsections.

A.1.1 Basic CRCs
Recall that B(X) for the basic CRCs is given in Definition 1. First, consider the case s < h, and let us revisit Fig. 11. This figure contains the loop (indexed by j) for computing B(X), which is based on Remark 3. The figure shows that the operation count required for computing B(X) is r b = 5.5s. Next, for the case s ≥ h, it can also be shown that r b = 5.5s (see Fig. 7). To summarize, we have Note that (36) is derived from the C programs that do not use loop unrolling (which is also the case for the C programs presented in [2]). If loop unrolling is used, (36) reduces to r b = 3.5s.
Here, our software implementations of the basic CRCs are general, i.e., they are applicable to all generator polynomials M (X) and to a wide range of processor architectures. For some specific generator polynomials that have some desirable properties, alternative implementations (such as shift and add [5], and on the fly [17,18]) may have lower complexity. Thus, we concentrate on the general nature of the algorithms rather than attempting to deal with specific types of generator polynomials. Also, for our C programs, we are more concerned with their readability and less concerned with optimization techniques such as loop unrolling and use of register variables (see Remark 4).

A.1.2 Fast CRCs
Recall that B(X) of the fast CRCs is given in Theorem 1. First, assume that s < h − 1. The C program for this case is shown in Fig. 12, which contains the procedure for computing B(X). Applying rules (R1) and (R2) to Fig. 12, we observe that the operation count required for computing B(X) is r f = 4. Next, assume that s = h. The C program for this case is shown in Fig. 8, which yields r f = 9. The C programs for all the other cases can also be written, and the resulting software complexity can also be determined. Following is the list of the operation counts for all the cases: The operation count per input byte e f for the fast h-bit CRC given in (39) is a function of s, which is the size of each input tuple Q i (X). We now determine the value of s that minimizes e f . These optimal values are denoted by s * and e * f .
which is achieved when Thus, (41) and (43) show that the complexity of the fast h-bit CRCs is minimized (i.e., e f is minimized) at either s = h or s = h − 2, where s is the number of bits in each input tuple Q i (X).
For example, by letting h = 16, the optimal size for each input tuple Q i (X) is s * = h − 2 = 14 [by (41)], and the corresponding minimum operation count is e * f = 80/(h − 2) = 80/14 = 5.71 [by (40)]. Information on computers is typically organized in bytes or words. Thus, it is of interest to determine the optimal value of e f when s is restricted to a multiple of byte size and word size, i.e., when s is a multiple of 8, 16, 32, 64. These optimal values, which are obtained from (39), are shown in Fig. 14.
Recall that e f = e f (s, h), i.e., e f is a function of s and h. In Fig. 14    When s is small, we can compute B(X) = R M(X) A(X)X h , where degree(A(X)) < s, using a series of if-else statements as follows. For example, suppose that s = 2 and M (X) = F h (X) = X h +X 2 +X+1. Then A(X) ∈ {0, 1, X, X + 1}, and it can be shown that Note that polynomials can also be represented as integer numbers, e.g., the polynomial X 3 + X 2 + X is equivalent to the decimal number 14. Thus, B(X) can be computed using the C program segment shown in Fig. 17. Applying rules (R1) and (R2) to this C program segment, the operation count for computing B(X) is 1, 2, 3, or 3 if A(X) is 0, 1, 2, or 3 (in integer representation), respectively. We now assume that the bits 0 and 1 of the input message occur equally likely. Thus, A(X) assumes one of the values 0, 1, 2, 3 with equal probability of 1/4. Then, on the average, the operation count for computing B(X) is (1 + 2 + 3 + 3)/4 = 2.25. In general, this technique for computing B(X) can be applied to any generator polynomial M (X). Let k denote the operation count required for computing B(X) = R M(X) A(X)X h using this if-else technique, where degree(A(X)) < s. Note that k depends on s, i.e., k = k(s). As shown above, we then have k(2) = 2.25, which is smaller than both r b and r f given in (36) and (38). In general, it can be shown that k(s) = 2 s−1 + 2 −1 − 2 −s for s ≥ 1. In particular, k(1) = 1. Thus, this if-else technique is effective for small s, such as s = 1, 2, or 3. However, in this paper, we are mainly concerned with the case s ≥ 8, which is more commonly used in practice. For this case, k(s) is much greater than both r b and r f . Thus, when s ≥ 8, the if-else technique is much more expensive than the basic and the new techniques, and it will not be discussed further in this paper. Note also that this if-else technique is different from the table-lookup technique (which will be discussed later). ⊔ ⊓ Remark 8. Consider an input message U (X), which is protected by an h-bit CRC. Recall that we implement this CRC by first dividing the input message into n s-tuples Q i (X), i.e., we have U (X) = (Q 0 (X), Q 1 (X), . . . , Q n−1 (X)). These s-tuples Q i (X) then become the input to one of the CRC algorithms. Fig. 9 shows that the complexity of the basic CRCs is rather insensitive to the values of s, whereas the complexity of the fast CRCs is very sensitive to the values of s. Recall that the operation count per input byte e f in (39) is a function of s and h, i.e., e f = e f (s, h). For example, Fig. 9 shows that e f (8, 16) = 10 and e f (16, 16) = 6, i.e., e f (16, 16) < e f (8,16). So far, we do not address the cost of obtaining the tuples Q i (X). We now address the impact of this cost by considering the fast 16-bit CRC, i.e., h = 16. Suppose that the input message U (X) originally consists of m bytes, m ≥ 4, denoted by I 0 (X), I 1 (X), . . . , I m−1 (X). Each I i (X) is an 8-tuple. Thus, we need to organize the bytes I j (X) into the s-tuples Q i (X). One technique is to simply set Q i (X) = I i (X), i.e., each Q i (X) is an 8-tuple. Let e be the operation count per input byte required for CRC encoding. We then have s = 8, and hence e = e f (8, 16) = 10.
An alternative technique is first to pair 2 adjacent input bytes to form 16-bit tuples from which the check bits are then computed. More precisely, we now let s = 16 and define the new 16-tuples Q i (X) by The algorithm for pairing the bytes and then computing the fast 16-bit CRC is shown in Fig. 18. Using this algorithm, it can be shown that the operation count per input byte is e = 7.5, which is lower than 1 if (m is even) where r b is the operation count required for computing B(X) via table lookup. The required tables are defined below. First, we write s = t 1 + t 2 + · · · + t m for some m and t i such that 1 ≤ m ≤ s and 1 ≤ t i ≤ s (i = 1, 2, . . . , m). Next, we decompose A(X) into m polynomials A 1 (X), A 2 (X), . . . , A m−1 (X), A m (X) such that with degree(A i (X)) < t i , i = 1, 2, . . . , m. We then have where the tables T i [ ] are defined by where A i denotes the t i -tuple that is composed of the binary coefficients of A i (X To summarize, for a given polynomial A(X) of degree less than s, let m, t 1 , t 2 , ..., t m be such that s = can then be computed using the m tables defined by (46). The total number of entries for these tables is Further, regardless of whether s < h or s ≥ h, it can be shown that, using the m tables, the number of operations required for computing B(X) is We now consider the special case t 1 = t 2 = · · · = t m = s/m. The m tables defined in (46) then becomes Equations (48) and (49) show tradeoffs between the operation count r b and the table size g b . That is, to decrease the table size, we must increase m in g b = m2 s/m , and this in turn will increase the operation count r b = 3(m − 1). Thus, smaller (larger) table size g b will yield larger (smaller) operation count r b . In particular, when m = 1, we have r b = 0 and g b = 2 s . When m = s, we have r b = 3(s − 1) and g b = 2s. Substituting r b = 3(m − 1) into (44), we have Note that our formulation is a straightforward generalization of [18], which contains the results for the special cases h = 16, s ∈ {8, 16}, and m ∈ {1, s}. Our results [e.g., (49)] also resemble those of [11], which presents in-depth studies of the case h = 32.
Note that the function f (x) = 2 x is convex. Given s = m i=1 t i , from Jensen's inequality, it can then be shown that m −1 m i=1 2 ti ≥ 2 s/m , i.e., m i=1 2 ti ≥ m2 s/m . This implies that, for a given m, the table size g b in (47) is minimized when t 1 = t 2 = · · · = t m . Thus, we focus on only this special case (t i = s/m) in this paper.
For example, let h = 16, s = 8, and m = 1. That is, we use a basic 16-bit CRC to protect a message consisting of input bytes (s = 8). This CRC is implemented using one lookup table (m = 1), which has g b = m2 s/m = 2 8 entries. Using (50) with s < h, we have e b = (24m + 24)/s = 6. That is, 6 operations are required for computing the check tuple per input byte. These results are recorded in the first row of Fig. 19. Note that, because each table entry has h = 16 bits, the total storage is hg b = 16 × 2 8 bits = 512 bytes (which is not shown in the figure). The results for other values of h, s, and m are shown in Fig. 19.
From Fig. 19, we observe the followings. First, the results for the cases h = 8 and h = 16 are identical for s = 32, 64, i.e., they differs only for s = 8, 16. This follows directly from (50). Similarly, the results for the cases h = 16 and h = 32 are identical for s = 8, 64, i.e., they differs only for s = 16, 32. Although the number of table entries g b = m2 s/m depends on only s and m, the total storage is hg b = hm2 s/m , which also depends on h.
Recall from Fig. 9 that the complexity results for bitwise implementation of the basic CRCs vary little over a wide range of s values. In contrast, as seen in Fig. 19, those for table-lookup implementation vary greatly with s. These results can also be used to optimize CRC table-lookup implementation. For example, suppose that h = 16. Let us compare the 2 cases: (s = 8, m = 1) and (s = 16, m = 4) in Fig. 19. In both cases, the required operation count per input byte is e b = 6. However, the first case requires one table of 2 8 entries (= 16 × 2 8 = 512 bytes), while the second case requires 4 tables totaling only 2 6 entries (= 16 × 2 6 = 128 bytes), which is 75% less than the first case. More generally, Fig. 19 shows that, for a given e b , the total number of table entries g b is minimized when s = h.

A.2.2 Fast CRCs
Recall from Section 2.1 that, when implementing an h-bit CRC, we are free to choose the value of s, which is the size of each input tuple Q i (X). That is, we can choose s < h, s = h, or s > h. Fig. 9 shows that, under bitwise implementation, the fast CRCs are much faster than the basic CRCs for s ≤ h, in the sense that e f is much smaller than e b . Further, by comparing Fig. 9 with Fig. 19, we see that the bitwise implementation of the fast CRCs (i.e., g f = 0) is even faster than the table-lookup implementation of the basic CRCs (i.e., g b > 0) in many cases. For example, consider the case s = h = 32. Fig. 19 shows that e b = 6 when g b = 2 7 (at m = 8), and e b = 12 when g b = 2 6 (at m = 16). On the other hand, Fig. 9 shows that e f = 3 when g f = 0. The same figures also show that, although the fast CRC requires no table lookup (i.e., g f = 0) and the basic CRC requires a table of g b = 2 10 entries (at m = 4), both CRCs have the same operation count e f = e b = 3.
Recall from (41) and (43) that, under bitwise implementation, e f is minimized either at s = h − 2 or at s = h. Thus, by choosing s to be at (or near) these optimal values, the fast CRCs require no table lookup (i.e., g f = 0) and still have low operation count (i.e., e f is small).
We now discuss table-lookup techniques for the fast CRCs generated by F h (X) = X h + X 2 + X + 1. An obvious technique is to apply the table-lookup technique in Section A.2.1 for the basic CRCs to the fast CRCs by simply letting M (X) = F h (X). The required total number of table entries is then given by (49), i.e., g f = g b = m2 s/m . In the following, for the case s ≥ h, we present another table-lookup technique (which is similar to the mixed technique in Remark 10 with m = 2) that exploits the special structure of F h (X) to yield g f = 2 s−h+2 , which is small when s ≈ h , e.g., g f = 4 when s = h.
Recall that r f denotes the operation count required for computing B(X). Without using tables (i.e., when g f = 0), r f is given by (38), i.e., r f = 9 + 5.5(s − h) for s ≥ h. We show below that r f is slightly reduced by using a small lookup table.
Assume that s ≥ h. According to Fig. 10, we use Algorithm 2 to implement the table-lookup technique for the fast CRCs when s ≥ h. From Fig. 13, we then have where r f , which denotes the operation count required for computing B(X) via table lookup, is determined in the following. First, we decompose A(X) into A 1 (X) and A 2 (X) such that where degree(A 1 (X)) < s − h + 2 and degree(A 2 (X)) < h − 2. Using (11) with M (X) = F h (X), we have where A 1 denotes the (s − h + 2)-tuple that is composed of the binary coefficients of the polynomial A 1 (X) of degree less than s − h + 2. The These entries in hexadecimal are shown in Fig. 21.
The table-lookup algorithm for the fast CRC (when s ≥ h) is given in Fig. 22, where the 2 s−h+2 entries of the table T f [ ] defined by (53) are stored in the top part of the algorithm. The C program for the special case s = h = 16, which is based on Fig. 22, is given in Fig. 23.   Fig. 21 Four-entry tables for the fast h-bit CRCs generated by F h (X) = X h + X 2 + X + 1 (s = h).
} 10 P = B; 11 return P ;  Table-lookup algorithm for the fast h-bit CRC generated by F h (X) = X h + X 2 + X + 1 (s ≥ h). Remark 11. Based on the suggestion by Y. Sawada, the C program in Fig. 23 can be improved to yield the C program shown in Fig. 24. This improvement follows from the observation that A1 and A2 are the left and right parts of A, respectively, i.e., A2 can be determined from A1 and A. Thus, by modifying the table T[A1] as shown in Fig. 24, we can replace A2 by A, i.e., A2 is now no longer needed.
Using the above improvement, it can be shown in general that the table given in (56) can now be simplified to become the new table defined by  ⊔ ⊓

APPENDIX B OTHER FAST ERROR-DETECTION CODES
So far, we apply the new technique (15) to F h (X) = X h + X 2 + X + 1 to yield the fast h-bit CRCs. We now apply this same technique to binomials and trinomials to yield even faster (but weaker) CRCs. We then construct some non-CRC error-detection codes, which are not only fast but also have optimal guaranteed error-detecting capability. Recall from Section 3.3 that the maximum length of an error-detection code is defined to be the total bit length at or below which its minimum distance is d ≥ 3, i.e., beyond which its minimum distance will reduce to d = 2. Theorem 2 shows that the maximum length of a CRC is the period of its generator polynomial. In the following, n b denotes the total bit length of a code.

B.1 Fast CRCs Generated by Binomials
Consider the h-bit CRC generated by the binomial M (X) = X h + 1, which has period h. To avoid triviality, we assume that this CRC includes at least one input bit, i.e., n b > h. From Theorem 2, this CRC then has the minimum distance d = 2, i.e., it is a weak code for error detection. This CRC can be implemented via Fig. 3 (for s < h) or Fig. 4 (for s ≥ h). Applying the new technique (15) to M (X) = X h + 1, the term B(X) in these figures is given by where N (X) = (X h + 1)X s−h . Note that by choosing s ≤ h, we have B(X) = A(X), i.e., the polynomial division is eliminated.
Suppose now that s = h. The CRC generated by X h + 1 can then be implemented by Fig. 6 with B(X) = A(X). Fig. 6 can be further simplified to yield the following pseudocode for computing the check h-tuple P (X): i.e., the CRC generated by M (X) = X h + 1 is identical to the bock-parity checksum [5]. From the above pseudocode, it can be shown that computing the check tuple P (X) for this checksum requires e = 24/s operations per input byte. Recall from Section 4 that e b = 8(3 + 5.5s)/s and e f = 96/s. We then have e f /e = 96/24 = 4 and e b /e = 8(3 + 5.5s)/24 = (3 + 5.5s)/3. For example, if s = h = 16, then computing the check tuple P (X) for the 16-bit bock-parity checksum requires e = 24/16 = 1.5 operations per input byte. We then have e f /e = 4 and e b /e = (3 + 5.5 × 16)/3 = 30.33. Thus, as expected, the bock-parity checksum (which has minimum distance d = 2) is substantially faster than the fast and basic CRCs (both of which have minimum distance d = 4).

B.2 Fast CRCs Generated by Trimomials
Let C be the CRC generated by the trinomial T h (X) = X h + X + 1. The periods t of the trinomials are given in Fig. 25 for h ≥ 3. Note that the periods t for the important cases h = 8, 16, 32, 64, 128, are unusually small. In fact, Fig. 25 shows that the period is t = h 2 − 1 when h is a power of 2. Because T h (X) is a codeword of weight 3, the minimum distance d of this CRC must satisfy d ≤ 3. From Theorem 2, we then have d = 3 if n b ≤ t, and d = 2 if n b > t. This CRC can be implemented via Fig. 3 (for s < h) or Fig. 4 (for  s ≥ h). Applying the new technique (15) to M (X) = T h (X), the term B(X) in these figures is given by where N (X) = (X h + X + 1)X s−h . Remark 1 implies that it is simpler to compute the B(X) in (58) than the B(X) in (16). Thus, the CRC generated by the trinomial T h (X) = X h + X + 1 is faster than the fast CRC generated by F h (X) = X h + X 2 + X + 1. However, the former has minimum distance only d = 3, whereas the latter has minimum distance d = 4. Further, for the important cases of h = 8, 16, 32, 64, 128, the maximum length of the faster CRC generated by the trinomial T h (X) is much shorter than that of the fast CRC generated by F h (X). For example, the faster 16-bit CRC generated by T 16 (X) has d = 3 and the maximum length of only 255 bits (see Fig. 25 Fig. 25 The period of trinomial T h (X) = X h + X + 1.

B.3 Fast and Optimal Error-Detection Codes
In the following, we construct codes that are not only fast but also have optimal error-detecting capability.
The h-bit CRC in Section B.2, which is denoted by C and has minimum distance d = 3, can be extended to yield a code that has d = 4 by adding an overall parity bit to the h-bit CRC. Note that this extended code, denoted by C * , has h * = h + 1 check bits and is not a CRC. The h-bit CRC has burst-error-detecting capability b = h. The following theorem shows that the extended code C * has burst-error-detecting capability b = h * = h + 1. Theorem 4. Let C be an h-bit CRC generated by a polynomial M (X) of degree h. Assume that M (X) is not a multiple of X, i.e., gcd(X, M (X)) = 1, and that M (X) has odd weight, i.e., it has an odd number of terms. Let C * be the non-CRC code that is obtained by adding an overall parity check bit to C, i.e., C * has h * = h + 1 check bits. Then C * detects all error bursts of length h + 1 or less, i.e., its burst-error-detecting capability is b = h + 1.
Proof. Let V * (X) be a codeword of C * . By definition of C * , we have V * (X) = V (X)X + parity(V (X)), where V (X) is a codeword of C. Because V (X) is a codeword of the CRC generated by M (X), we have V (X) = K(X)M (X) for some polynomial K(X) (see the proof of Theorem 2). We then have V * (X) = K(X)M (X)X + parity(K(X)M (X)) Let E * (X) be an error burst of length h + 1 or less, which has the form where i ≥ 0, and E(X) is a polynomial such that E(X) = 1 and degree(E(X)) ≤ h. Using proof by contradiction, we now show that E * (X) cannot be a codeword of C * . Thus, assume that E * (X) is a nonzero codeword of C * , i.e., This implies that parity(K(X)M (X)) = 1. Thus, K(X) = 0, which implies that degree(K(X)M (X)X) > h. But we also have E(X) = K(X)M (X)X, which implies that degree(K(X)M (X)X) ≤ h, which is a contradiction to the previous statement. Case 2: i > 0. We then have parity(K(X)M (X)) = 0. Thus, X i (E(X) + 1) = K(X)M (X)X. Because gcd(X, M (X)) = 1, we must have X i = K(X)X. Thus, K(X) = X i−1 . We then have parity(K(X)M (X)) = parity(M (X)) = 1, which is a contradiction to the previous statement that parity(K(X)M (X)) = 0.
⊔ ⊓ Let t be the period of the polynomial M (X) in Theorem 4. The extended code C * in Theorem 4 then has h * = h + 1 check bits, the burst-error-detecting capability b = h * = h + 1, the minimum distance d = 4, and the maximum length of t + 1 bits. In the following, we show that C * becomes fast by choosing M (X) = T h (X) = X h + X + 1, i.e., M (X) is a trinomial.
Thus, let M (X) = X h + X + 1, and P CRC (X) be the check h-tuple for the CRC generated by this particular M (X). Suppose that s = h + 1. Because s > h, the check tuple P CRC (X) can be computed by Algorithm 4 (see Fig. 4), in which the term B(X) is computed by (58), i.e., where N (X) = (X h + X + 1)X, and degree(A(X)) < s = h + 1.
Recall from Theorem 4 that the non-CRC code C * is obtained by adding an overall parity check bit to the above CRC. The overall parity bit of C * is computed as follows. First, we define where Q 0 (X), . . . , Q n−1 (X) are the input s-tuples. The overall parity bit of C * is also the parity bit of W (X). The check polynomial of C * is then P (X) = P CRC (X)X + parity(W (X)) which is a polynomial of degree < h + 1. Fig. 26 shows an implementation of C * , which is based on Fig. 4 (with s = h * = h + 1 and M (X) = X h + X + 1) and includes the calculation of the overall parity bit of C * . Let e * be the operation count per input byte required for computing the check tuple P (X) for the code C * . By ignoring the negligible complexity due to the terms outside the loop indexed by i in Fig. 26, it can be shown that e * = 96/h * . It is shown in (39) of Appendix A that the complexity for the fast h * -bit CRC is also given by e f = 96/h * (when s = h * ). Thus, e * = e f , i.e., the (non-CRC) h * -bit code C * is as fast as the fast h * -bit CRC.
Let M (X) be a primitive polynomial of degree h, i.e., the period of M (X) is t = 2 h − 1. Let us now compare the capability and complexity for the following 2 codes, each of which has h * = h + 1 check bits. The first code is the familiar basic CRC generated by (X + 1)M (X), which has d = 4, b = h + 1, and the maximum length of 2 h − 1 bits. An example is the well-known CRC-16, which is generated by M (X) = (X + 1)(X 15 + X + 1) = X 16 + X 15 + X 2 + 1. Under bitwise implementation, this basic CRC requires e b = 45.5 operations per input byte for computing its check tuple, provided that the input message is composed of 16-tuples, i.e., s = h = 16 (see Fig. 9).
The second code is the non-CRC code C * as described in Theorem 4, which has d = 4, b = h + 1, and the maximum length of t + 1 = 2 h bits (which is 1 bit longer than the basic (h + 1)-bit CRC above). It is well-known that any code that has h + 1 check bits and the minimum distance d = 4 must satisfy the following 2 constraints: (1) the burst-error detecting capability b ≤ h + 1 and (2) the maximum length ≤ 2 h . Thus, the non-CRC code C * is optimal for error detection in the sense that, with h * = h + 1 check bits and d = 4, it has the optimal b = h * and the optimal maximum length 2 h . In fact, at the maximum length of 2 h bits, the code C * is a (2 h , 2 h − h − 1, 4) extended Hamming perfect code with the optimal burst-error-detecting capability b = h + 1. Also, it is well-known that the undetected error probability of this perfect code is bounded above by 2 −(h+1) .
As shown in Fig. 26, the code C * is fast when M (X) = T h (X) = X h + X + 1, i.e., M (X) is a trinomial. It is known that T h (X) is primitive for some values of h [22], including h = 3, 7, 15, 63, and 127 (i.e., h + 1 = 4, 8, 16, 64, and 128). For example, let h = 15 and s = h * = h + 1 = 16. Using Fig. 26, it can be shown that the operation count per input bye required for computing the check tuple for the (non-CRC) 16-bit code C * is e * = 96/16 = 6 (which is much smaller than e b = 45.5 of the basic CRC-16 above). To summarize, the (non-CRC) h * -bit code C * (e.g., with h * = 4, 8, 16, 64, or 128 check bits) constructed from a primitive trinomial and an overall parity check bit has (a) the optimal error-detection capability and (b) a fast bitwise implementation. Note that, as discussed later in Section C.2, other fast and optimal codes can also be constructed from polynomials different from trinomials.
10 P = B + parity(W ); 11 return P ; Fig. 26 Algorithm for computing the fast (h + 1)-bit non-CRC code from the h-bit CRC (generated by X h + X + 1) and an overall parity bit.

APPENDIX C APPLICATION OF THE NEW TECHNIQUE TO GENERAL CRC GENERATOR POLYNOMIALS
So far, we apply the new technique (15) to the polynomials X h + X 2 + X + 1, X h + X + 1, and X h + 1 to yield fast CRCs. In this appendix, we apply the same technique to more general generator polynomials, and then determine the conditions under which the new technique is faster than the basic technique. In particular, we show later in Section C.1.2.1 that, when applied to the CRC-64-ISO generated by X 64 + X 4 + X 3 + X + 1, the new technique is 15 times faster than the basic technique. This appendix presents only bitwise algorithms.
The h-bit CRC generated by (59) can be computed either by the basic technique (see Definition 1) or by the new technique (15). Recall that CRC complexity refers to the operation count per input byte (denoted by e b and e f for the basic and the fast CRCs, respectively) required for computing the CRC check tuple. Again, we assume that the CRCs are implemented in C, and the operations are counted according to rules (R1) and (R2) stated in Appendix A.

C.1 General CRC Generator Polynomials
First, suppose that the basic technique is used to compute the check tuple of the CRC generated by (59), i.e., B(X) is computed as in Definition 1 with M (X) = F (X) in (11). From (37), we have Next, suppose that the new technique is used to compute the check tuple of the CRC generated by (59). By letting M (X) = F (X) in (15), we have where N (X) = F (X)X s−h and degree(A(X)) < s. Substituting (59) into (62), we have To briefly illustrate the main idea, consider the special case s = h. Then B(X) = R F (X) A(X)X h under the basic technique, and B(X) = R F (X) A(X)(X i k + X i k−1 + · · · + X i1 + 1) under the new technique. Intuition suggests that computing B(X) via the new technique is faster than the basic technique if i k is sufficiently small. More precise conditions on i k are given in the following.
Let e be the operation count per input byte required for computing the CRC check tuple under the new technique (63). We have e = e f for the special case F (X) = F h (X) = X h + X 2 + X + 1. Although Fig. 9 shows that e f < e b , it may not be the case that e < e b for the more general polynomial F (X). Thus, in the following, we determine the conditions on F (X) so that e < e b or e b /e > 1 (i.e., the conditions under which the new technique is faster than the basic technique). Thus, the new technique serves as a faster alternative to the basic technique when e b /e > 1. The computation of e b /e for many CRCs are given later in Sections C.2-C.4. Before continuing, we present the following remarks, which contain some results that will be used later to determine the operation count required for computing B(X). Remark 12. Let r ′ be the number of operations required for computing where n ≥ 1, and we assume that the tuple A(X)X ji can be stored in a single computer word. Computing A(X)X ji is then equivalent to shifting A(X) to the left by j i bits, which can be done by a single operation on most computers. Thus, for a given A(X), we can compute B ′ (X) by using n left-shift operations and n addition operations. We then have r ′ = 2n.

⊔ ⊓
Recall that, given the CRC generated by (59), our goal here is to determine the complexity for computing the check h-tuple P (X) for an input message that consists of n tuples Q 0 (X), Q 1 (X), . . . , Q n−1 (X). Each tuple Q i (X) has s bits. As shown in Figs. 1-4, the check tuple P (X) is computed by using a loop that computes B(X) for n times, where B(X) can be computed by the basic technique (see Definition 1) or by the new technique (15). In the following, we compare the complexity between these 2 techniques. We consider 2 cases: s ≥ h and s < h.

C.1.1 Case: s ≥ h
In this case, according to Fig. 10, the new technique uses Algorithm 4 (shown in Fig. 4), which contains the computation of B(X). From (60) and (63), we have where A * (X) = A(X)X s−h . Using Remark 3, it can be shown that R N (X) [A * (X)] = R N (X) A(X)X s−h can be computed with r 0 = 5.5(s − h) operations (see Appendix C). Applying Remark 13 with M * (X) = N (X), n = k, j n = i k , q = 1, and r 0 = 5.5(s − h), the tuple B(X) can be computed with r = 5.5(s − h + i k ) + k operations. Fig. 13  Thus, the new technique is faster than the basic technique when e b /e > 1, i.e., 3+5.5s > 3+5.5(s−h+i k )+k, which is equivalent to where i k = degree(H(X)) and k = weight of (H(X) + 1). Remark 15. Suppose that F (X) is either X h + X 2 + X + 1 or X h + X + 1. Then i k ≤ 2, i.e., i k is a very small value. Thus, it is appropriate to use loop unrolling in the calculation of C m (X) above. Then (64) reduces to e = 8[3 + 5.5(s − h) + 3.5i k + k]/s, and then Note that it is common to choose s, h ∈ {8, 16, 32, 64}, i.e., the typical values of s and h are not very small, even when i k is very small. For example, suppose now that s = h and F (X) = F h (X) = X h + X 2 + X + 1, i.e., k = i k = 2 and e = e f . Substituting s = h and k = i k = 2 into (66), we have Applying Remark 12, we then have r = 2k, which is substituted into (67) where i k = degree(H(X)) and k = weight of (H(X) + 1). For example, consider the CRC-64-ISO generated by the primitive polynomial F (X) = X 64 + X 4 + X 3 + X + 1 Here, we have h = 64, k = 3, and i k = 4. Assume that s ≤ h − i k = 60. Under the new technique, we then have i.e., the polynomial division is eliminated. Substituting k = 3 into (70), we have e b e = 4 + 5.5s 12 For the special case s = 32, we have e b /e = 15, i.e., the new technique is 15 times faster than the basic technique for the CRC-64-ISO. We also have e b /e = 15 when s = 32 for a 64-bit CRC generated by a polynomial that has the following more general form For the CRC-64-ISO, the value e b /e shown above is based on the implementation for which B(X) is computed directly by the single statement B(X) = A(X)X 4 + A(X)X 3 + A(X)X + A(X). An alternative implementation, suggested by Y. Sawada, is to compute B(X) via 2 statements: first, compute B ′ (X) = A(X)X + A(X), and then compute B(X) = B ′ (X)X 3 + B ′ (X). ⊔ ⊓ C.1.2.2 Case: s < h and i k > h − s As seen below, the computation of B(X) requires the polynomial division in this case. The assumption i k > h − s implies that there exists m * such that 1 ≤ m * ≤ k , i m * > h − s, and i j ≤ h − s for all j < m * . There are 3 subcases to consider. Case 1: 1 < m * < k. By letting m = m * − 1, we have By letting A * (X) = A(X)X im+1 , we can write and B 2 (X) = A(X)X im + · · · + A(X)X i1 + A(X) operations for a given A(X). Using Remark 13, B 1 (X) can be computed with operations. Using Remark 12, B 2 (X) can be computed with r 2 = 2m operations. Overall, the number of operations required for computing B(X) is which is substituted into (68) to yield where i k = degree(H(X)) and k = weight of (H(X) + 1). Recall that we also assume that h > i k > i m+1 > i m ≥ i 1 > 0, i m+1 > h − s, and i m ≤ h − s. For example, consider the CRC-32-IEEE 802.3 generated by the following primitive polynomial: F (X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + X + 1 (74) i.e., h = 32, k = 13, i k = 26. Assume that s = 16. We then have m = 10. Substituting these values into (73) yields e b /e = 92/85, i.e., the new technique is slightly faster than the basic technique. Case 2: m * = 1. We then have where A * (X) = A(X)X i1 and Case 3: m * = k. We then have where i k > h − s, and i n ≤ h − s for all n < k. We have

C.2 CRC Generator Polynomials of Weight 3
We now consider the special case k = 1, i.e., F (X) is a polynomial of weight 3: F (X) = X h + X i1 + 1. By where h > i > 0. Note that F (X) = T h (X) = X h + X + 1 for the special case i = 1. Fig. 27 lists some weight-3 polynomials along with their periods, for h ≤ 32. In Section B.2, the fast h * -bit perfect codes are constructed from the CRCs generated by T h (X) for h * = 4, 8, 16, 64, 128, where h * = h + 1. In the following, we show that other fast perfect codes can also be constructed from CRCs generated by weight-3 polynomials. Let C be the h-bit CRC generated by F (X) in (77). Recall from Theorem 2 that the maximum length of C equals the period of F (X). Assume that s ≤ h − i. Using the new technique, we have B(X) = R F (X) A(X)(X i + 1) = A(X)(X i + 1), i.e., the polynomial division is eliminated. Let e be the operation count per input byte required for computing the check tuple P (X) of the h-bit CRC C. Then e is given by (69).
Let C * be the non-CRC code that is constructed by adding an overall parity bit to the h-bit CRC C, and P * (X) be the check tuple of C * . Let e * be the operation count per input byte required for computing P * (X). Note that P * (X) has h + 1 bits, which can be computed by an algorithm that is similar to Fig. 26. Using (69) and Fig. 26 Let us now compare the speed of the (h + 1)-bit code C * with that of the fast (h + 1)-bit CRC generated by F h+1 (X) = X h+1 + X 2 + X + 1.
for s ≤ h − i. Thus, (81) shows that the (h + 1)-bit non-CRC code C * is at least as fast as the fast (h + 1)-bit CRC generated by F h+1 (X), i.e., C * is also a fast code for s ≤ h − i. Further, at its maximum length, the code C * is the (2 h , 2 h − h − 1, 4) extended Hamming perfect code, provided that F (X) = X h + X i + 1 is a primitive polynomial (i.e., its period is 2 h − 1).
For example, let F (X) = X 11 + X 2 + 1, i.e., h = 11 and i = 2. Fig. 27 shows that F (X) is primitive. Let C be the 11-bit CRC generated by F (X). The non-CRC code C * , which is constructed by adding an overall parity bit to C, is the (2048, 2036, 4) extended Hamming perfect code. Note that both C and C * are fast if we choose s ≤ h − i = 9. Suppose that we choose s = 8. From (79) and (80), we then have e * = 80/8 = 10 and e f = 88/8 = 11, i.e., e * < e f . Thus, for s = 8, the non-CRC 12-bit code C * is faster than the fast 12-bit CRC generated by F 12 (X) = X 12 + X 2 + X + 1. Further, the maximum length of the non-CRC code (which is 2,048 bits) is also much longer than that of the fast CRC generated by F 12 (X) (which is 595 bits), and 2 bits longer than that of the CRC generated by F (X) = X 12 + X 3 + X + 1 (which is 2,046 bits, as discussed later in Section C.3).
Similarly, we can construct a 32-bit extended Hamming perfect code C * by adding an overall parity bit to the CRC C generated by F (X) = X 31 + X 3 + 1 (see Fig. 27). We have h = 31 and i = 3. Both C and C * are fast if we choose s ≤ h − i = 28.

C.3 CRC Generator Polynomials of Weight 4
We now consider the special case k = 2, i.e., F (X) is a polynomial of weight 4: where h > i 2 > i 1 > 0. In particular, F (X) = F h (X) = X h + X 2 + X + 1 when i 2 = 2 and i 1 = 1. Fig. 28 lists some weight-4 polynomials F (X) = X h + X i2 + X i1 + 1, which have periods that are greater than those of F h (X), for h ≤ 32. Recall from Theorem 2 that the maximum length of a CRC equals the period of its generator polynomial. In the following, we consider the application of the new technique to weight-4 generator polynomials for CRCs such as CRC-16 and CRC-CCITT. For brevity, we only present the results for s < h (the case s ≥ h can be handled similarly). There are 3 cases to consider.
Case 1: Using the new technique, we have B(X) = R F (X) A(X)(X i2 + X i1 + 1) = A(X)(X i2 + X i1 + 1), i.e., the polynomial division is eliminated. Substituting k = 2 into (69) For example, let F (X) = X 32 + X 4 + X + 1, i.e., h = 32 and i 2 = 4. It follows from (83) that the new technique is faster the basic technique when 2 ≤ s ≤ 28. Under this condition, we have i.e., the polynomial division is eliminated. Fig. 28 shows that the 32-bit CRC generated by F (X) has the maximum length of 2,147,483,647 = 2 31 − 1 bits (≈ 268,435,456 bytes). Recall from Fig. 5 that the original fast 32-bit CRC, generated by F 32 (X) = X 32 + X 2 + X + 1, has the maximum length of 2,097,151 ≈ (2 31 − 1)/1024 bits (≈ 262,143 bytes). Thus, the maximum length of the CRC generated by F (X) is substantially larger than that of the fast CRC generated by F 32 (X). However, (83) shows that these 2 CRCs have identical complexity when s ≤ 28. Consider the 12-bit CRC generated by F (X) = X 12 + X 3 + X + 1. Fig. 28 shows that this CRC has the maximum length of 2,046 bits, which is much larger than that of the fast CRC generated by F 12 (X) = X 12 + X 2 + X + 1, which has the maximum length of only 595 bits (see Fig. 5). However, (83) shows that these 2 CRCs have identical complexity when s ≤ 9.

C.4 CRC Generator Polynomials of Weights Greater Than 4
We now consider the case k ≥ 3, i.e., the CRC generator polynomial has weight greater than 4, i.e., it contains more than 4 terms. Our goal here is to find generator polynomials for CRCs that (a) have minimum distance d min > 4 and (b) can be efficiently implemented by the new technique (15), i.e., they have low complexity. Codes with minimum distance d min detect all patterns of less than d min errors. For example, the fast CRCs generated by F h (X) = X h + X 2 + X + 1, which have d min = 4, detect all patterns of 1, 2, and 3 errors.
An error pattern E(X) is detected by the CRC generated by F (X) if E(X) is not a multiple of F (X), i.e., R F (X) [E(X)] = 0 (see the proof of Theorem 2). This fact can be used to search for CRCs that can detect specified sets of error patterns.
In the following, for a given m > 0, we search for h-bit CRCs of length l that can detect all patterns of m errors: where l > a m−1 > a m−1 > · · · > a 1 > a 0 ≥ 0. There are l m such m-error patterns. Let l m be the maximum length of a CRC that can detect all patterns of m errors. A CRC with d min = m + 1 detects all patterns of m errors or less, and fails to detect some patterns of m + 1 errors. Thus, a CRC will have d min = m + 1 if its total code length = min{l 1 , l 2 , . . . , l m } bits, and d min ≥ m + 1 if its total code length ≤ min{l 1 , l 2 , . . . , l m } bits. Note that l 2 of a CRC is also its period. If F (X) in (86) has even weight, then all patterns of odd number of errors are detected, i.e., l m = ∞ for odd m. Thus, for odd m, the CRC has d min = m + 1 if its total code length = min{l 2 , l 4 , . . . , l m−1 } bits. For example, suppose that k is even, i.e., F (X) in (86) has even weight. The CRC generated by F (X) then has d min = 6 if its total code length = min{l 2 , l 4 } bits. Further, this CRC has d min = 8 if its total code length = min{l 2 , l 4 , l 6 } bits.
A straightforward technique to show that a CRC of length l will detect all m-error patterns is to verify that each of such l m m-error patterns is not a multiple of the CRC generator polynomial. This brute-force technique has computational complexity O(l m ) [10]. A faster technique, which has computational complexity O(l m−1 ), is presented in Remark 17. As an example, Fig. 29 shows some h-bit CRC generator polynomials of weight 6, for h = 16, 24, 32, and 64. These CRCs and their l 2 and l 4 are found by computer search. For each value of h, these CRC generator polynomials are arranged according to increasing l 4 (see Remark 18). As discussed above, these CRCs detect all odd numbers of errors because their generator polynomials have even weights. Further, these CRCs have d min = 6 when their total code lengths l = min{l 2 , l 4 }.
In the following examples, we discuss the performance and implementation of some CRCs that are generated by the polynomials shown in Fig. 29. Here, we have k = 4 and F (X) = X h + X i4 + X i3 + X i2 + X i1 + 1. We assume that the input message is divided into n tuples Q 0 (X), Q 1 (X), . . . , Q n−1 (X). Each tuple Q i (X) has s bits (e.g., s = 8, 16, 32 and 64). Recall that the h-bit CRC generated by (86) can be computed either by the basic technique (see Definition 1) or by the new technique (15).    Thus, under the new technique, using s = 16 is much faster than using s = 8 and 32 for this CRC. The C program for computing the CRC check bits using s = 16 is shown in Fig. 31. s = 16 for the 32-bit CRC generated by X 32 + X 12 + X 8 + X 4 + X 3 + 1.
⊔ ⊓ Example 5. Consider the 32-bit CRC generated by F (X) = X 32 + X 18 + X 17 + X 15 + X 14 + 1 (= 10006c001 in hexadecimal notation). From Fig. 29 i.e., for bitwise implementation, the 32-bit CRC generated by F (X) is 3.43 times faster than basic 32-bit CRCs. The C program for bitwise implementation and s = 8 for this CRC is shown in Fig. 32 We now discuss table-looup implementation for the CRC generated by F (X) = X 32 + X 18 + X 17 + X 15 + X 14 + 1. We can implement the table lookup for this CRC by imitating the table-lookup implementation presented in Section A.2.2 for the fast CRCs generated by F h (X) = X h + X 2 + X + 1. Using the new technique (15), we have We now decompose A(X) into 2 simpler polynomials A 1 (X) and A 2 (X): where degree(A 1 (X)) < 2 and degree(A 2 (X)) < 14. We then have where A 1 is a 2-tuple. Thus, table T [ ] has 4 entries, which can be shown to be: In hexadecimal notation, we have T [1] = 8006c001, T [2] = b4003, and T [3] = 800d8002. The C program, which includes the table of 4 entries, for this CRC is shown in Fig. 33. Recall from Appendix A that r denotes the operation count required for computing B(X). From Fig. 33 Thus, under the new technique, using s = 32 is much faster than using other values of s for the CRC generated by X 64 + X 5 + X 3 + X 2 + X + 1.
In Fig. 35, we present CRC generator polynomials of weight 5, i.e., k = 3. These polynomials generate CRCs that have d min = 5 if their total code length ≤ min{l 2 , l 3 , l 4 } bits. Let us compare the CRCs in Fig. 35 with those in Fig. 29. First, the largest values of l 4 for h = 16 and 32 in Fig. 35 are almost twice of those in Fig. 29. Next, while l m = ∞ for the CRCs in Fig. 29 for odd m, we have l m < ∞ for those in Fig. 35. The CRC generator polynomials of odd weights greater than 5 are given in Fig. 36. In particular, l 4 for X 24 + X 14 + X 13 + X 12 + X 11 + X 10 + 1 in Fig. 36 is almost twice that for X 24 + X 17 + X 12 + X 7 + 1 in Fig. 35.
In Fig. 37, we present fast h-bit CRCs that are generated by primitive polynomials of weight 5, i.e., F (X) = X h + X i3 + X i2 + X i1 + 1. We have l 2 = 2 h − 1, because the polynomials are primitive. These CRCs have fast implementation when s is chosen such that s ≤ h − i 3 or i 3 ≤ h − s (see Section C.1.2.1). Note that Fig. 37 includes some polynomials in Fig. 35, as well as the CRC-64-ISO polynomial X 64 + X 4 + X 3 + X + 1.
So far, we present polynomials that generate CRCs that have d min = 5 (see Figs. 35 and 36) and d min = 6 (see Figs. 29 and 34). Generator polynomials for CRCs that have d min > 6 can also be found. For example, Fig. 38 shows polynomials of weight 8, which generate CRCs that have d min = 8 if their total code lengths ≤ min{l 2 , l 4 , l 6 } bits, because l m = ∞ for odd m. Note that these same CRCs have d min ≥ 4 and d min ≥ 6 if their total code lengths ≤ l 2 and ≤ min{l 2 , l 4 } bits, respectively. Similar to the CRCs presented in Examples 1-6, many CRCs in Fig. 38 also have fast implementation. However, they are usually not as fast as the CRCs in those examples, because they are generated by polynomials that have greater weights (see Figs. 29 and 38).
Case 1: n is even. Then l 1 = l 3 = l 5 = ∞ because F (X) has even weight. The h-bit CRC generated by F (X) then has minimum distance d min = 6 when its total length = min(l 1 , l 2 , l 3 , l 4 , l 5 ) = min(l 2 , l 4 ) = l 4 = h + 1 bits. This CRC has d min ≥ 4 when its total length ≤ min(l 1 , l 2 , l 3 ) = l 2 bits. Recall that l 2 is also the period of F (X).
Case 2: n is odd. The h-bit CRC generated by F (X) then has d min = 5 when its total length = min(l 1 , l 2 , l 3 , l 4 ) = l 4 = h + 1 bits. This CRC has d min ≥ 3 when its total length ≤ min(l 1 , l 2 ) = l 2 bits. ⊔ ⊓ Remark 17. Consider a CRC that is generated by F (X) and has total length of l bits. When a CRC codeword of length l is transmitted, it is affected by errors. Let us focus on the patterns of m errors. There are l m such patterns of m errors. A straightforward technique to show that the CRC detects all the m-error patterns is to verify that it detects each of the l m m-error patterns. However, we show below that, to verify that this CRC detects all the m-error patterns, it is sufficient to verify that it detects all the error patterns from a subset of only l−1 m−1 patterns of m errors. First, let E(X) be an error polynomial. We can write where a ≥ 0 and E * (X) is a polynomial whose least significant bit is 1, i.e., E * (0) = 1. For example, let E(X) = X 5 + X 2 . We then have a = 2 and E * (X) = X 3 + 1, because E(X) = X 2 (X 3 + 1). Next, we show that E(X) is undetected iff E * (X) is undetected. Thus, suppose that the error pattern E(X) is undetected, i.e., it is a codeword of the CRC generated by F (X). We then have E(X) = K(X)F (X) for some polynomial K(X), which implies X a E * (X) = K(X)F (X). Because we assume that F (X) is not a multiple of X, i.e., gcd(X, F (X)) = 1, we must have E * (X) = K * (X)F (X) for some polynomial K * (X). Thus, E * (X) is also a codeword, i.e., it is an undetected error pattern. Suppose now that E * (X) is undetected, i.e., E * (X) is a multiple of F (X). Then E(X) = X a E * (X) must also be undetected, because E(X) is also a multiple of F (X). To summarize, E(X) is undetected iff E * (X) is undetected. This fact can be used to speed up the search for CRCs that can detect specified sets of error patterns.
Let A be a set of error patterns. As seen above, each E(X) ∈ A can be written as E(X) = X a E * (X), for some a ≥ 0 and E * (0) = 1. Let A * be the set of all such E * (X), i.e., We must have |A * | ≤ |A|. However, in general, it is not necessarily that A * ⊆ A. In particular, consider a CRC having total length of l bits, and let A be the set of all patterns of m errors. We then have |A| = l m = O(l m ). Because A * is the set of all patterns of m errors, under the restriction that the least significant bit of each of these error patterns is 1 [i.e., E * (0) = 1], we must have |A * | = l−1 m−1 = O(l m−1 ). A straightforward technique to show that a CRC of length l will detect all the m-error patterns is to verify that each m-error pattern in A is not a multiple of the CRC generator polynomial [10]. More specifically, for each m-error pattern E(X) = X am−1 + X am−2 + · · · + X a1 + X a0 The computation can also be implemented by table lookup [3]. We then have Overall, this brute-force technique has computational complexity l m = O(l m ). As seen above, E(X) ∈ A is undetected iff E * (X) ∈ A * is undetected. Recall that |A| = l m and |A * | = l−1 m−1 . Thus, an alternative technique to show that a CRC of length l will detect all the m-error patterns is to verify that each m-error pattern in A * is not a multiple of the CRC generator polynomial.
This alternative technique has computational complexity l−1 m−1 = O(l m−1 ), and is faster than the brute-force technique by the factor l m / l−1 m−1 = l/m = O(l). ⊔ ⊓ Remark 18. Here, we explain how the CRC generator polynomials shown in Figs. 29 and 34-39 are found. We restrict our search of h-bit CRC generator polynomials to a subset of polynomials S = {F 0 (X), F 1 (X), . . . , F n−1 (X)}, for some n, where each F j (X) is a polynomial of the form (86), i.e., it has degree h and weight k + 2 (i.e., F j (X) has k + 2 terms). For example, if we restrict S to be the set of polynomials of degree h and weight 6 (i.e., k = 4), we then have n = |S| = h−1 4 . Note that each polynomial F j (X) can also be represented by a binary integer F j whose digits are the coefficients of F j (X), i.e., F j ≡ F j (X). The polynomials in S are arranged in increasing order, i.e., F j1 < F j2 when j 1 < j 2 .
Consider a CRC generated by F j (X) that has the form (86). Because any undetected error must be a multiple of F j (X), it follows that l i ≥ h for all i ≥ 1. In particular, l k+2 = h, because the error E(X) = F j (X), which has weight k + 2 and length h + 1, is undetected. We also have l 1 = ∞. Recall that l 2 is also the period of the polynomial. Here, we are only interested in l m for 2 ≤ m ≤ k + 1. For example, when k = 3, i.e., F j (X) is a polynomial of weight 5, we are only interested in l 2 , l 3 , and l 4 (see Fig. 35). When k is even, i.e., F j (X) is a polynomial of even weight, we have l m = ∞ for odd m. In this case, we are only interested in l m for even m, i.e., for m = 2, 4, . . . , k. For example, when k = 4, i.e., F j (X) is a polynomial of weight 6, we are only interested in l 2 and l 4 (see Fig. 29).
(a) Consider Fig. 29, which shows polynomials of weight 6, i.e., k = 4 and F j (X) = X h + X i4 + X i3 + X i2 + X i1 + 1. Here, we show l 2 and l 4 . Each F j (X) generates a CRC that has minimum distance d min = 6 when its total length ≤ min{l 2 , l 4 } bits. The polynomials are shown in increasing values of their binary representation and increasing l 4 , i.e., the l 4 of F j1 (X) is smaller than the l 4 of F j2 (X) for j 1 < j 2 . Although these CRCs can be implemented by the familiar basic technique, they can be much faster implemented by the new technique (15). Using the new technique, an h-bit CRC with smaller l 4 is at least as fast as an h-bit CRC with larger l 4 . Thus, as expected, there are tradeoffs between code capability and speed, i.e., CRCs with smaller l 4 is faster than CRCs with larger l 4 .
(b) As seen in Fig. 29, where we impose the condition k = 4 (i.e., the generator polynomials have weight exactly 6), the generator polynomial X 16 + X 14 + X 11 + X 5 + X 2 + 1 yields the largest l 4 = 130 for the case of h = 16. Can l 4 be improved if we allow k > 4? Consider Fig. 34, which shows the CRC generator polynomials with even k and k > 4, i.e., each F j (X) is a polynomial of even weight greater than 6. Our purpose here is to find out if there are other CRCs that have values of l 4 that are larger than those in Fig. 29. Such a CRC generator exists for the case h = 16, namely, X 16 + X 13 + X 12 + X 10 + X 9 + X 4 + X + 1, with l 4 = 152, which is larger than the largest l 4 = 130 in Fig. 29. Note that, using the new technique (15), the CRCs in Fig. 29 are usually faster than those in Fig. 34, because they are generated by polynomials that have lower weights.
(c) Figs. 35 and 36 show generator polynomials that have odd weights and generate CRCs that can detect 1, 2, 3, and 4 errors. We now show l 2 , l 3 and l 4 . In Fig. 35, we require k = 3 (i.e., the generator polynomials have weight exactly 5). In Fig. 36, we require that k is odd and k > 3 (i.e., the generator polynomials have odd weights greater than 5).
(d) Figs. 38 and 39 show generator polynomials that have even weights and generate CRCs that can detect 1, 2, 3, 4, 5, 6, and 7 errors. We now show l 2 , l 4 and l 6 . In Fig. 38, we require k = 6 (i.e., the generator polynomials have weight exactly 8). In Fig. 39, we require that k is even and k > 6 (i.e., the generator polynomials have even weights greater than 8).

⊔ ⊓
We have w m = |B m |. Thus, a direct technique for computing w m is to count the number of polynomials in A m that are multiples of F (X) (cf. [3]). Because |A m | = l m = O(l m ), this direct technique has computational complexity O (|A m |) = O(l m ) (cf. [3]). A faster technique for computing w m , which has computational complexity O(l m−1 ), is presented in Remark 19. Using this faster technique, we obtain the values of w m for h-bit CRCs as shown in Figs. 40-43 for m = 4, 6, 8, and h = 8, 16, 24, 32, 64. Note that w m = 0 for odd m and w 2 = 0, because the generator polynomials in these figures have weight 4 (i.e., even weight) and minimum distance d = 4 at the indicated code lengths. Fig. 40 shows w 4 , w 6 , and w 8 for the fast 8-bit CRC generated by X 8 + X 2 + X + 1 (which is also the ATM CRC-8) and for the 8-bit CRC generated by X 8 + X 5 + X 4 + 1 (used in 1-Wire bus). The results show that these 2 CRCs have similar w 4 , w 6 , and w 8 . Fig. 41 shows w 4 for the fast 16-bit CRC generated by X 16 + X 2 + X + 1, the CRC-CCITT generated by X 16 + X 12 + X 5 + 1, and the CRC-16 generated by X 16 + X 15 + X 4 + 1. The results show that (a) for l ≤ 1000, w 4 is smallest for the CRC-CCITT, largest for CRC-16, and in-between for the fast 16-bit CRC, and (b) for l ≥ 2000, all 3 CRCs have similar w 4 . Fig. 42 shows that w 4 for the fast 32-bit CRC generated by X 32 + X 2 + X + 1 is larger than w 4 for the 32-bit CRC generated by X 32 + X 31 + X 8 + 1 (which is proposed in [5]). Fig. 43 shows that, for l ≥ 200, w 4 for the fast 64-bit CRC generated by X 64 + X 2 + X + 1 is smaller than w 4 for the 64-bit CRC generated by X 64 + X 63 + X 2 + 1 (which is proposed in [5]).
We now consider a first-order estimate for the undetected error probability by assuming that the first term of (87), w dmin p dmin (1 − p) l−dmin , is much larger than all the other terms. A simple estimate, which is reasonable when lp << 1, for the undetected error probability for a BSC is then For example, suppose that the fast 32-bit CRC generated by X 32 + X 2 + X + 1 is used to protect a 3000-bit codeword over a BSC with transition probability p. Because d min = 4 and l = 3000, Fig. 42 yields w dmin = w 4 = 1.855 × 10 5 . Using (90), we then have p u ≈ 1.855 × 10 5 p 4 . In particular, p u ≈ 1.855 × 10 −19 when p = 10 −6 , and p u ≈ 1.855 × 10 −15 when p = 10 −5 . The undetected error probability p u for the BSC can be greatly further reduced by using CRCs with d min > 4. These CRCs are presented in Section C.4, e.g., Fig. 29 shows many generator polynomials for 32-bit CRCs that have d min = 6 when l ≤ l 4 . Although these CRCs can be efficiently implemented by the fast technique (15), they are not as fast as the fast CRC generated by X 32 + X 2 + X + 1. Note that the undetected error probability p u given in (87) Fig. 40 w 4 , w 6 , and w 8 for the CRCs generated by X 8 + X 2 + X + 1 and X 8 + X 5 + X 4 + 1 (w m = number of codewords of weight m). Thus, Because E * (X) is not a multiple of X, it can be shown that C E * (X) ∩ C E * (X) ′ = ∅ when E * (X) = E * (X) ′ . That is, {C E * (X) : E * (X) ∈ B * m } is a partition of B m . Thus, Because w m = |B m | and |C E * (X) | = l − degree(E * (X)), we have

APPENDIX E CRC PARALLEL IMPLEMENTATION
Given a CRC, which is generated by a polynomial M (X) of degree h, our goal is to compute the check h-tuple P (X) to protect an input message U (X) = (Q 0 (X), . . . , Q n−1 (X)), where Q i (X) is an s-tuple. So far, it is implicitly assumed that the CRC algorithms are for sequential implementation. That is, the entire input message U (X) is supplied to a single processor of a computer, and the output P (X) is then computed by this same processor. Following the technique in [7], we can modify these CRC algorithms for parallel implementation on k different processors of a computer, k > 1, as follows.
First, the input message U (X) is divided into k sub-messages E 0 (X), . . . , E k−1 (X), i.e., U (X) = (E 0 (X), . . . , E k−1 (X)) where E i (X) consists of n i s-tuples. Thus, n = n 0 + · · · + n k−1 . Define W i (X) = R M(X) X (ni+1+···+n k−1 )s for 0 ≤ i ≤ k − 2, and W k−1 (X) = 1. Note that W i (X) is computed from X (ni+1+···+n k−1 )s , which is used to determine the relative position of sub-message E i (X) in U (X) (see Remark 20). Next, for each i = 0, 1, . . . , k − 1, input sub-message E i (X) is supplied to processor i, which is used to compute the following h-tuples: P i (X) = R M(X) E i (X)X h (92) where W i (X) is defined by (91). Note that P i (X) is the CRC check tuple computed by processor i for submessage E i (X). For each i = 0, 1, . . . , k − 1, we assume that processor i computes P i (X) and Z i (X) in (92) and (93), independent of other processors, i.e., the computation is done in parallel by the k processors. Theorem 5. The tuples Z i (X), 0 ≤ i < k, which are computed in parallel by the k processors, are combined to yield the final CRC check h-tuple P (X) for the entire input message U (X), i.e., Proof. In polynomial notation, we have E i (X)X (ni+1+···+n k−1 )s + E k−1 (X) The CRC check tuple P (X) for U (X) then becomes We now determine the total CRC computation time, denoted by t total , for the parallel technique. First, let t Wi , t Pi , and t Zi be the times for processor i to compute W i (X), P i (X), and Z i (X), respectively. Let t P be the time for the computer to compute the summation (94). We can consider t Wi , t Zi , and t P as the overhead costs for the CRC parallel implementation. Because the k processors compute (92) and (93) in parallel, the total time for the computer to compute the final CRC check tuple P (X) is We now determine the speedup factor for the parallel technique under the following ideal conditions: (a) the k processors have identical computational capability, (b) the sub-messages E i (X) have the same length, i.e., n i = n/k, and (c) the overhead costs t Wi , t Zi , and t P are negligible compared to t Pi , i.e., t Wi + t Pi + t Zi + t P ≈ t Pi (see Remark 20). From (95), we then have t total ≈ t Pi ≈ t U /k, where t U denotes the time for a single processor to compute the CRC check tuple P (X) for the entire message U (X), i.e., t U is the CRC computational time for sequential implementation. Thus, under the ideal conditions, the speedup factor is approximately k for parallel implementation.
Remark 20. Under the CRC parallel implementation, processor i computes W i (X), P i (X), and Z i (X) as given in (91)-(93), i = 1, . . . , k − 1. These tuples can be computed as follows. First, it can be shown from (91) that W i (X) = R M(X) [X ni+1s W i+1 (X)] with W k−1 = 1. Thus, once W i+1 (X) is known, W i (X) can be computed in O(n i+1 s) steps (by Remark 1). We can also write W i (X) = R M(X) X ni+1s−h W i+1 (X)X h , i.e., we can view W i (X) as the output check tuple of the CRC generated by M (X) when X ni+1s−h W i+1 (X) is the input tuple. Thus, W i (X) can be computed by either the CRC basic technique or the CRC new technique. Suppose now that n 0 , . . . , n k−1 are known and fixed. The tuples W 0 (X), W 1 (X), . . . , W k−1 can then be stored in a table defined by T [i] = W i (X), i = 0, 1, . . . , k − 1 (cf. [7]). Next, processor i can use either the basic technique or the new technique to compute the (partial) CRC check tuple P i (X). Further, using the technique "Mimic long multiplication as done by hand" in [13, p. 90], it can be shown that the tuple Z i (X) = R M(X) [P i (X)W i (X)] can be computed in O(h) steps. Finally, once Z 0 (X), . . . , Z k−1 (X) are computed by the k processors, their summation in (94) can be quickly computed. Thus, for a sufficiently long sub-message E i (X) along with the use of table lookup for determining W i (X), the computational complexity of P i (X) is much greater than that of W i (X), Z i (X), and the summation (94), i.e., t Pi >> t Wi , t Zi , t P . ⊔ ⊓

ACKNOWLEDGMENT
This work was supported in part by the US Office of Naval Research.