# CRC

### Bách khoa toàn thư mở Wikipedia

CRC (cyclic redundancy check) là một loại hàm băm, được dùng để sinh ra giá trị kiểm thử, của một chuỗi bit có chiều dài ngắn và cố định, của các gói tin vận chuyển qua mạng hay một khối nhỏ của tệp dữ liệu. Giá trị kiểm thử được dùng để dò lỗi khi dữ liệu được truyền hay lưu vào thiết bị lưu trữ. Giá trị của CRC sẽ được tính toán và đính kèm vào dữ liệu trước khi dữ liệu được truyền đi hay lưu trữ. Khi dữ liệu được sử dụng, nó sẽ được kiểm thử bằng cách sinh ra mã CRC và so khớp với mã CRC trong dữ liệu.

CRC rất phổ biến, vì nó rất đơn giản để lắp đặt trong các máy tính sử dụng hệ cơ số nhị phân, dễ dàng phân tích tính đúng, và rất phù hợp để dò các lỗi gây ra bởi nhiễu trong khi truyền dữ liệu.

Bài này đang được dịch từ tiếng Anh, nếu bạn có đủ khả năng xin góp sức dịch bài này. Nếu không tiếp tục được quan tâm, phần ngoại ngữ của bài sẽ bị xóa sau khoảng 1 tháng. Xin tham khảo Hướng dẫn cách biên soạn bài để biết thêm chi tiết.

## [sửa] Giới thiệu

A CRC "checksum" is the remainder of a binary division with no bit carry (XOR used instead of subtraction), of the message bit stream, by a predefined (short) bit stream of length n + 1, which represents the coefficients of a polynomial with degree n. Before the division, n zeros are appended to the message stream.

CRCs are based on division in the ring of polynomials over the finite field GF(2) (the integers modulo 2). In simpler terms, this is the set of polynomials where each coefficient is either zero or one (a single binary bit), and arithmetic operations wrap around. For example:

Note that 2x becomes zero in the above equation because addition of coefficients is performed modulo 2:

Multiplication is similar:

We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x3 + x2 + x by x + 1. We would find that

In other words,

The division yields a quotient of x2 + 1 with a remainder of -1, which, since it is odd, has a last bit of 1.

Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide by another fixed polynomial, after first multiplying by xn where n is the degree of the fixed polynomial. The coefficients of the remainder polynomial are the CRC.

In the above equations, x2 + x + 1 represents the original message bits `111`, x + 1 is the generator polynomial, and the remainder 1 (equivalently, x0) is the CRC. The degree of the generator polynomial is 1, so we first multiplied the message by x1 to get x3 + x2 + x.

In general form:

Here M(x) is the original message polynomial and G(x) is the degree-n generator polynomial. The bits of are the original message with n zeros added at the end. R(x) is the remainder polynomial, which is the CRC 'checksum'. The quotient polynomial Q(x) is uninteresting. In communication, the sender attaches the n bits of R after the original message bits of M and sends them out (in place of the zeros). The receiver takes M and R and checks whether is divisible by G(x). If it is, then the receiver assumes the received message bits are correct. Note that is exactly the string of bits the sender sent; this string is called the codeword.

A CRC is a checksum in a strict mathematical sense, as it can be expressed as the weighted modulo-2 sum of per-bit syndromes, but that word is generally reserved more specifically for sums computed using larger moduli, such as 10, 256, or 65535.

CRCs can also be used as part of error-correcting codes, which allow not only the detection of transmission errors, but the reconstruction of the correct message. These codes are based on closely related mathematical principles.

## [sửa] Endianness

When implemented in bit serial hardware, the generator polynomial uniquely describes the bit assignment; the first bit transmitted is always the coefficient of the highest power of x, and the last n bits transmitted are the CRC remainder R(x), starting with the coefficient of xn − 1 and ending with the coefficient of x0, a.k.a. the coefficient of 1.

However, when bits are processed a byte at a time, such as when using parallel transmission, byte framing as in 8B/10B encoding or RS-232-style asynchronous serial communication, or when implementing a CRC in software, it is necessary to specify the endianness of the data; which bit in each byte is considered "first" and will be the coefficient of the higher power of x.

If the data is destined for serial communication, it is best to use the bit ordering the data will ultimately be sent in. This is because a CRC's ability to detect burst errors is based on proximity in the message polynomial M(x); if adjacent polynomial terms are not transmitted sequentially, a physical error burst of one length may be seen as a longer burst due to the rearrangement of bits.

For example, both IEEE 802 (ethernet) and RS-232 standards specify little-endian (least-significant bit first) transmission, so a software CRC implementation to protect should map the least significant bits in each byte to coefficients of the highest powers of x. On the other hand, floppy disks and most hard drives write the most significant bit of each byte first.

The little-endian CRC is slightly simpler to implement in software, so is somewhat more commonly seen, but many programmers find the big-endian bit ordering easier to follow. Thus, for example, the XMODEM-CRC extension, an early use of CRCs in software, uses a big-endian CRC.

## [sửa] Ví dụ

Suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character "W", which is decimal 8710 or hexadecimal 5716. For illustration, we will use the CRC-8-ATM polynomial x8 + x2 + x + 1. Writing the first bit transmitted (the coefficient of the highest power of x) on the left, this corresponds to the 9-bit string "100000111".

The byte value 5716 can be transmitted in two different orders, depending on the endianness convention used. Each one generates a different message polynomial M(x). Big-endian, this is x6 + x4 + x2 + x + 1 = 01010111, while little-endian, it is x7 + x6 + x5 + x3 + x = 11101010. These can then be multiplied by x8 to produce two 16-bit message polynomials x8M(x).

Computing the remainder then consists of subtracting multiples of the generator polynomial G(x). This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1. And because we do not care about the quotient, there is no need to record it.

Big-endian example | Little-endian example
--- | ---

| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
- | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
|  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
|  |  | - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0
|  |  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0
|  |  |  |  | - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0
|  |  |  |  |  | - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0
|  |  |  |  |  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0

| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
- | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0
|  | - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0
|  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0
|  |  |  | - | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0
|  |  |  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0
|  |  |  |  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0
|  |  |  |  |  |  | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
= | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0

Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero, at the end, a group which is unchanged from the original, and a shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the zero group becomes one bit longer and the unchanged group becomes one bit shorter, until only the final remainder is left.

In the big-endian example, the remainder polynomial is x7 + x5 + x. Converting to a hexadecimal number using a big-endian convention, this is A216. In the little-endian example, the remainder is x7 + x4 + x3. Converting to hexadecimal using a little-endian convention, this is 1916.

## [sửa] Thực hiện

Writing out the full message at each step, as done in the example above, is very tedious. Efficient implementations use an n-bit register to hold only the interesting bits. Here is a first draft of some pseudocode for computing an n-bit CRC:

     function crc(bit array bitString[1..len+n], int len) {
         remainderPolynomial := polynomialForm(bitString[1..n])   // First n bits of the message
         // A popular variant complements remainderPolynomial here
         for i from 1 to len {
             remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0
             if coefficient of xn of remainderPolynomial = 1 {
                 remainderPolynomial := remainderPolynomial xor generatorPolynomial
             }
         }
         // A popular variant complements remainderPolynomial here
         return remainderPolynomial
     }

Note that this example code refrains from specifying an endianness preference; the input `bitString` is already in the form of a bit array, and the `remainderPolynomial` is manipulated in terms of polynomial operations; the multiplication by x could be a left or right shift, and the addition of `bitString[i+n]` is done to the x0 coefficient, which could be the right or left end of the register.

This code has two disadvantages. First, it actually requires an n+1-bit register to hold the `remainderPolynomial` so that the xn coefficient can be tested. More significantly, it requires the `bitString` to be padded with n zero bits.

The first problem can be solved by testing the xn − 1 coefficient of the `remainderPolynomial` before it is multiplied by x.

The second problem could be solved by doing the last n iterations differently, but there is a more subtle optimzation which is used universally, in both hardware and software implementations.

Because the XOR operation used to subtract the generator polynomial from the message is commutative and associative, it does not matter in what order the various inputs are combined into the `remainderPolynomial`. And specifically, a given bit of the `bitString` does not need to be added to the `remainderPolynomial` until the very last instant when it is tested to determine whether to `xor` with the `generatorPolynomial`.

This eliminates the need to preload the `remainderPolynomial` with the first n bits of the message, as well:

     function crc(bit array bitString[1..len], int len) {
         remainderPolynomial := 0
         // A popular variant complements remainderPolynomial here
         for i from 1 to len {
             if (coefficient of xn-1 of remainderPolynomial xor bitString[i]) = 1 {
                 remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
             } else {
                 remainderPolynomial := (remainderPolynomial * x)
             }
         }
         // A popular variant complements remainderPolynomial here
         return remainderPolynomial
     }

This is the standard bit-at-a-time hardware CRC implementation, and is well worthy of study; once you understand why this computes exactly the same result as the first version, the remaining optimizations are quite straightforward. If `remainderPolynomial` is only n bits long, then the xn coefficients of it and of `generatorPolynomial` are simply discarded. This is the reason that you will usually see CRC polynomials written in binary with the leading coefficient omitted.

In software, it is convenient to note that while one may delay the `xor` of each bit until the very last moment, it is also possible to do it earlier. It is usually convenient to perform the `xor` a byte at a time, even in a bit-at-a-time implementation like this:

     function crc(byte array string[1..len], int len) {
         remainderPolynomial := 0
         // A popular variant complements remainderPolynomial here
         for i from 1 to len {
             remainderPolynomial := remainderPolynomial xor polynomialForm(string[i])
             for j from 1 to 8 {    // Assuming 8 bits per byte
                 if coefficient of xn-1 of remainderPolynomial = 1 {
                     remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
                 } else {
                     remainderPolynomial := (remainderPolynomial * x)
                 }
             }
         }
         // A popular variant complements remainderPolynomial here
         return remainderPolynomial
     }

This is usually the most compact software implementation, used in microcontrollers when space is at a premium over speed.

So far, the pseudocode has avoided specifying an endianness by describing shifts in the pseudocode as multiplications by x and writing explicit conversions from binary to polynomial form. In practice, the CRC is held in a standard binary register using a particular endianness. In big-endian form, the most significant binary bits contain the higher-order polynomial coefficients (sent first), while in little-endian form, the least-significant binary bits contain the higher-order coefficients. The above pseudocode can be written in both forms. For concreteness, this uses the 16-bit CRC-16-CCITT polynomial x16 + x12 + x5 + 1:

     // Big-endian, x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
     function crc(byte array string[1..len], int len) {
         rem := 0
         // A popular variant complements rem here
         for i from 1 to len {
             rem := rem xor string[i] leftShift (n-8)   // n = 16 in this example
             for j from 1 to 8 {    // Assuming 8 bits per byte
                 if leftmost (most significant) bit of rem is set {
                     rem := (rem leftShift 1) xor 0x1021
                 } else {
                     rem := rem leftShift 1
                 }
             }
         }
         // A popular variant complements rem here
         return rem
     }

     // Little-endian, x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408
     function crc(byte array string[1..len], int len) {
         rem := 0
         // A popular variant complements rem here
         for i from 1 to len {
             rem := rem xor string[i]
             for j from 1 to 8 {    // Assuming 8 bits per byte
                 if rightmost (least significant) bit of rem is set {
                     rem := (rem rightShift 1) xor 0x8408
                 } else {
                     rem := rem rightShift 1
                 }
             }
         }
         // A popular variant complements rem here
         return rem
     }

Note that the little-endian form avoids the need to shift `string[i]` before the `xor`. Also, when converting `rem` to bytes and appending it to the message, follow the chosen endianness convention.

Another common optimization uses a lookup table indexed by highest order coefficients of `rem` to perform the inner loop over 8 bits in fewer steps. A 256-entry lookup table is a particularly common choice, although using a 16-entry table twice per byte is very compact and still faster than the bit at a time version. This replaces the inner loop over `j` with

             // Big-endian
             rem = (rem leftShift 8) xor big_endian_table[(leftmost 8 bits of rem) rightShift (n-8)]

             // Little-endian
             rem = (rem rightShift 8) xor little_endian_table[rightmost 8 bits of rem]

One of the most commonly encountered CRC algorithms is known as CRC-32, used by (among others) Ethernet, FDDI, ZIP and other archive formats, and PNG image format. Its polynomial can be written big-endian as 0x04C11DB7, or little-endian as 0xEDB88320. The W3C webpage on PNG includes an appendix with a short and simple table-driven implementation in C of CRC-32. You will note that the code corresponds to the little-endian byte-at-a-time pseudocode presented here, and the table is generated using the bit-at-a-time code.

Despite its popular acclaim, the polynomial in question was arbitrarily chosen and generally exhibits very poor error detection properties (in terms of Hamming distance per given block size) compared to polynomials selected by algorithmic means[1] [2].

## [sửa] Variations

There are several standard variations on CRCs. One or more of the variations may be used with any CRC.

- To check the CRC, instead of calculating the CRC on the message and comparing it to the CRC, a CRC calculation may be run on the entire codeword. If the result is zero, the check passes. This works because the codeword is , which is always divisible by G(x).

- The shift register may be initialized with ones instead of zeroes. Equivalently, the first n bits of the message may be inverted before feeding them into the algorithm. The reason to do this is because an unmodified CRC does not distinguish between two messages which differ only in the number of leading zeros. When this inversion is done, the CRC does distinguish between such messages.

- The CRC may be inverted before being appended to the message stream. This is because an unmodified CRC does not distinguish between two messages that differ only in the number of trailing zeros. When this is done, the CRC does distinguish. With this modification, the CRC of a full codeword that already includes a CRC is no longer zero. The CRC may be checked either by the straightforward method of computing the CRC on the message, inverting it, and comparing with the CRC in the message stream, or by calculating the CRC on the entire codeword and comparing it with an expected fixed value called the check polynomial `C(x)`. This result is sometimes called the corresponding magic number, and may be computed as .

When using the CRC-32 polynomial and the CRC-16-CCITT polynomial, by convention both inversions are performed.

- The check polynomial for CRC-32 is C(x) = x31 + x30 + x26 + x25 + x24 + x18 + x15 + x14 + x12 + x11 + x10 + x8 + x6 + x5 + x4 + x3 + x + 1.

## [sửa] Reversed representations and reciprocal polynomials

### [sửa] Polynomial representations

All the well-known CRC generator polynomials of degree n have two common hexadecimal representations:

- The big-endian representation is a hexadecimal number with n bits, the least significant bit of which is always 1. The most significant bit represents the coefficient of xn − 1 and the least significant bit represents the coefficient of x0.

- The little-endian representation is a hexadecimal number with n bits, the most significant bit of which is always 1. The most significant bit represents the coefficient of x0 and the least significant bit represents the coefficient of xn − 1.

The big-endian form is referred to in the literature as the normal representation, while the little-endian is called the reversed representation, because it is the bitwise reverse of the normal representation. It is essential to use the correct form when implementing a CRC. If the coefficient of xn − 1 is zero, the forms can be distinguished at a glance by seeing which end has the bit set.

In both these representations the xn coefficient is omitted and understood to be 1.

To further confuse the matter, the excellent paper by P. Koopman and T. Chakravarty [2][3] converts CRC generator polynomials to hexadecimal numbers in yet another way: big-endian, but including the xn coefficient and omitting the x0 coefficient. This "Koopman" representation has the advantage that the degree can be determined from the hexadecimal form and the coefficients are easy to read off in left-to-right order. However, it is not used anywhere else and is not recommended due to the risk of confusion.

### [sửa] Reciprocal polynomials

A reciprocal polynomial is created by assigning the xn through x0 coefficients of one polynomial to the x0 through xn coefficients of a new polynomial. That is, the reciprocal of the n bit polynomial G(x) is xnG(x − 1). Example: The reverse of x16 + x15 + x2 + 1 is x16 + x14 + x1 + 1. The most interesting property of reciprocal polynomials, when used in CRCs, is that they have the exact same error-detecting strength as the polynomials they are reciprocals of. The reciprocal of a polynomial generates the same codewords — that is, the bit strings consisting of a valid CRC appended to a message — as the original polynomial, only bit reversed. But the reciprocal polynomial is not the same as the original polynomial, and the CRCs generated using it are not the same (even modulo bit reversal) as those generated by the original polynomial.

Another interesting property of reciprocal polynomials is related to their representation. Consider again the CRC-16-IBM polynomial x16 + x15 + x2 + 1 and its reciprocal. These are its representations

- Normal original: 0x8005
- Reversed original: 0xA001
- Koopman original: 0xC002
- Normal reciprocal: 0x4003
- Reversed reciprocal: 0xC002
- Koopman reciprocal: 0xA001

Note that the Koopman representation of the reciprocal polynomial is the same as the reversed representation of the original polynomial. This means that if you mistakenly use the Koopman representation of a polynomial in a right-shift algorithm, you get a CRC that is just as strong as (but different from) the one you intended. This holds only for polynomials with a degree which is a multiple of 4.

## [sửa] Error detection strength

The error-detection ability of a CRC depends on the degree of its key polynomial and on the specific key polynomial used. The "error polynomial" E(x) is the exclusive-or of the received message codeword and the correct message codeword. An error will go undetected by a CRC algorithm if and only if the error polynomial is divisible by the CRC polynomial.

- Because a CRC is based on division, no polynomial can detect errors consisting of a string of zeros prepended to the data, or of missing leading zeros. However, see Variations.
- All single bit errors will be detected by any polynomial with at least two terms with non-zero coefficients. The error polynomial is xk, and xk is divisible only by polynomials xi where .
- All two bit errors separated by a distance less than the order of the polynomial will be detected. The error polynomial in the two bit case is . As noted above, the xk term will not be divisible by the CRC polynomial, which leaves the xi − k + 1 term. By definition, the smallest value of i − k such that a polynomial divides xi − k + 1 is the polynomial's order. The polynomials with the largest order are called primitive polynomials, and for polynomials of degree n with binary coefficients, have order 2n − 1.
- All errors in an odd number of bits will be detected by a polynomial which is a multiple of x + 1. This is equivalent to the polynomial having an even number of terms with non-zero coefficients.
- All burst errors of length n will be detected by any polynomial of degree n or greater which has a non-zero x0 term.

(as an aside, there is never reason to use a polynomial with a zero x0 term. Recall that a CRC is the remainder of the message polynomial times x^n divided by the CRC polynomial. A polynomial with a zero x0 term always has x as a factor. So if K(x) is the original CRC polynomial and , then

That is, the CRC of any message with the K(x) polynomial is the same as that of the same message with the K'(x) polynomial with a zero appended. It is just a waste of a bit.)

The combination of these factors means that good CRC polynomials are often primitive polynomials (which have the best 2-bit error detection) or polynomials whose factors are a primitive polynomial of degree n − 1 and x + 1 (which detects all odd numbers of bit errors, and has half the two-bit error detection ability of a primitive polynomial of degree n)[2].

### [sửa] Error detection strength (Bitfilters)

Analysis Technique using bitfilters (see weblink "CRC-Analysis with Bitfilters") allows to determine quite more efficient the properties of a given generator polynomial. The results are the following:

1. All burst errors (but one) with length no longer than the generator polynomial can be detected by any generator polynomial 1 + ... + Xn. This includes 1-bit errors (burst of length 1). The maximum length is n + 1, when n is the degree of the generator polynomial (which itself has a length of n + 1). The exception to this result is a bit pattern the same as that of the generator polynomial.
2. All uneven bit errors are detected by generator polynomials with even number of terms.
3. 2-Bit errors in a (multiple) distance of the longest bitfilter of even parity to a generator polynomial are not detected; all others are detected. For degrees up to 32 there is an optimal generator polynomial with that degree and even number of terms; in this case the period mentioned above is 2n − 1 − 1. For n = 16 this means that blocks of 32767 bits length do not contain undiscoverd 2-Bit errors. For uneven number of terms in the generator polynomial there can be a period of 2n − 1; however, these generator polynomials (with odd number of terms) do not discover all odd number of errors, so they should be avoided. A list of the corresponding generators with even number of terms can be found in the link mentioned at the beginning of this section.
4. All single bit errors within the bitfilter period mentioned above (for even terms in the generator polynomial) can be identified uniquely by their residual. So CRC method can be used for error correction as well (within those limits, e.g. 32767 bits with optimal generator polynomials of degree 16). Since all odd errors leave an odd residual, all even an even residual, 1-bit errors and 2-bit errors can be distinguished, however not necessarily 1-bit errors and 3-bit errors. Thus bit error correction might be erroneous itself and produce more errors.

## [sửa] CRC polynomial specifications

The following table below omits "Initial value", "Reflected value" and "Final XOR value".

- These hex values are important for some more complicated checksums (like most forms of CRC-32 and CRC-64). CRCs less than CRC-16 do not tend to use these values.
- Very often custom versions of checksums are created by changing these values, as it does not alter the mechanics of the checksum algorithm.

CRC standardization issues

- The definition of CRC-12 is disputed, as there are 3 forms of CRC-12 in common use.
- Both forms of CRC-8 in use have notable weaknesses mathematically.
- It is assumed that at least 10 forms of CRC-16 and CRC-32 exist, but no form of CRC-16 or CRC-32 is mathematically optimal.
- CCITT CRCs differ from ITU CRCs (of the same size), as the same entity has standardized checksums more than once but in different eras.

## [sửa] CRC polynomials in common use (in ITU-IEEE syntax)

Name | Polynomial | Representations: Normal or Reverse (Normal of Reciprocal)
--- | --- | ---
CRC-1 | x + 1 (use: hardware; also known as parity bit) | 0x1 or 0x1 (0x1)
CRC-5-CCITT | x5 + x3 + x + 1 (ITU G.704 standard) | 0x0B or 0x1A (0x15)
CRC-5-USB | x5 + x2 + 1 (use: USB token packets) | 0x05 or 0x14 (0x9)
CRC-7 | x7 + x3 + 1 (use: telecom systems, MMC) | 0x09 or 0x48 (0x11)
CRC-8-ATM | x8 + x2 + x + 1 (use: ATM HEC) | 0x07 or 0xE0 (0xC1)
CRC-8-CCITT | x8 + x7 + x3 + x2 + 1 (use: 1-Wire bus) | 0x8D or 0xB1 (0x63)
CRC-8-Dallas/Maxim | x8 + x5 + x4 + 1 (use: 1-Wire bus) | 0x31 or 0x8C (0x19)
CRC-8 | x8 + x7 + x6 + x4 + x2 + 1 | 0xD5 or 0xAB (0x57)
CRC-8-SAE J1850 | x8 + x4 + x3 + x2 + 1 | 0x1D or 0xB8
CRC-10 | x10 + x9 + x5 + x4 + x + 1 | 0x233 or 0x331 (0x263)
CRC-12 | x12 + x11 + x3 + x2 + x + 1 (use: telecom systems) | 0x80F or 0xF01 (0xE03)
CRC-15-CAN | x15 + x14 + x10 + x8 + x7 + x4 + x3 + 1 | 0x4599 or 0x4CD1 (0x19A3)
CRC-16-Fletcher | Not a CRC; see Fletcher's checksum | Used in Adler-32 A & B CRCs
CRC-16-CCITT | x16 + x12 + x5 + 1 (XMODEM,X.25, V.41, Bluetooth, PPP, IrDA; known as "CRC-CCITT") | 0x1021 or 0x8408 (0x0811)
CRC-16-IBM | x16 + x15 + x2 + 1 (USB, many others; also known as "CRC-16") | 0x8005 or 0xA001 (0x4003)
CRC-24-Radix-64 | x24 + x23 + x18 + x17 + x14 + x11 + x10 + x7 + x6 + x5 + x4 + x3 + x + 1 | 0x864CFB or 0xDF3261 (0xBE64C3)
CRC-32-Adler | Not a CRC; see Adler-32 | See Adler-32
CRC-32-MPEG2 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | 0x04C11DB7 or 0xEDB88320 (0xDB710641) Also used in IEEE 802.3
CRC-32-IEEE 802.3 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (V.42) | 0x04C11DB7 or 0xEDB88320 (0xDB710641)
CRC-32C (Castagnoli)[1] | x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18 + x14 + x13 + x11 + x10 + x9 + x8 + x6 + 1 | 0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)
CRC-64-ISO | x64 + x4 + x3 + x + 1 (use: ISO 3309) | 0x000000000000001B or 0xD800000000000000 (0xB000000000000001)
CRC-64-ECMA-182 | x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 + x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22 + x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1 (as described in ECMA-182 p.63) | 0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
CRC-128 | IEEE-ITU Standard. Use superseded by hashes MD5 & SHA-1 |
CRC-160 | IEEE-ITU Standard. Use superseded by hashes MD5 & SHA-1 |

## [sửa] CRCs and data integrity

While useful for error detection, CRCs cannot be safely relied upon to verify data integrity in the face of intelligent (rather than random) changes. Because of the linear structure of CRC polynomials, it is extremely easy to intentionally change data without modifying its CRC, as demonstrated by CRC and how to Reverse it. This is possible even if the data is encrypted. Message authentication codes can be used to verify data integrity.

### [sửa] Xung đột mã CRC

As with all hash functions, CRCs tend to have collision rates nearing 100% after a certain number of collision tests. Each additional bit added to a CRC (ie: CRC-20 vs CRC-21) cuts the number of collisions down by nearly 50%. The polynomial has an intrinsic repeat rate (i.e. when viewed as a random number generator, after a certain number of cycles it will repeat itself). The polynomial repeat rate of a CRC-8 is around 100 bits, but the CCITT-16 repeats at around 4k bytes.

- The theoretical collision rate for CRC64 is around one collision every 264 or 18Tiêu bản:E CRCs.
- A properly designed CRC (using fewer bits) can be as effective as a poorly designed CRC using more bits due to the irreducible polynomial property of CRCs. In this case CRC-32 can perform nearly as well as CRC-40.

### [sửa] Designing CRC polynomials

The selection of generator polynomial is the most important part of implementing the CRC algorithm. The polynomial must be chosen to maximize the error detecting capabilities while minimizing overall collision probabilites. The most important attribute of the polynomial is its length (the number of the highest nonzero coefficient), because of its direct influence of the length of the computed checksum.

The most commonly used polynomial lengths are

- 9 bits (CRC-8)
- 17 bits (CRC-16)
- 33 bits (CRC-32)
- 65 bits (CRC-64)

When creating a new CRC polynomial or improving an existing CRC the general mathematical advice is to use an irreducible polynomial that satisfies all polynomical irreducibility constraints from modular arithmetics.

- Irreducibility in this case means that the polynomial cannot be divided by any polynomial except itself and 1 with zero remainder.

The properties of the generator polynomial can be derived from the algorithm definition

- CRCs with more than one nonzero coefficients are able to detect all single bit errors in the input message.
- CRCs can be used to detect all double bit errors in the input message shorter than 2k, where k is the length of the longest irreducible part of the polynomial.
- If the CRC polynomial is divided by x + 1 then no polynomial with odd number of nonzero coefficients can be divided by it. Hence, it can be used to detect odd number of errors in the input message (like single bit parity function).
- CRC polynomials detect (single) burst errors shorter than the number of the position of the highest polynomial coefficient.

## [sửa] See also

- Danh sách các thuật toán kiểm thử
- Bit chẵn lẻ

Specific Technological References

- Adler-32
- Fletcher's checksum

## [sửa] Tham khảo

1. ▲ 1,0 1,1 Castagnoli, G. and Braeuer, S. and Herrman, M. (June năm 1993). “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits”. IEEE Transactions on Communications 41 (6). - Castagnoli's et al. work on algorithmic selection of CRC polynomials
2. ▲ 2,0 2,1 2,2 Koopman, P. (June năm 2002). “32-Bit Cyclic Redundancy Codes for Internet Applications”. The International Conference on Dependable Systems and Networks. - verification of Castagnoli's results by exhaustive search and some new good polynomials
3. ▲ Koopman, P. and Chakravarty, T. (2004). “Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks”. The International Conference on Dependable Systems and Networks. - analysis of short CRC polynomials for embedded applications

## [sửa] Liên kết ngoài

- Tutorial and C++ implementation of CRC
- Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-redundancy.html
- The CRC Pitstop
- Williams, R. (1993-09) A Painless Guide to CRC Error Detection Algorithms
- Understanding Cyclic Redundancy Check
- Black, R. (1994-02) Fast CRC32 in Software — Algorithm 4 is used in Linux and info-zip's zip and unzip.
- Kounavis, M. and Berry, F. (2005). A Systematic Approach to Building High Performance, Software-based, CRC generators — Slicing-by-4 and slicing-by-8 algorithms
- (1999-11, 1999-12, 2000-01) checksums, CRCs, and their source code. Embedded Systems Programming
- CRC32: Generating a checksum for a file, C++ implementation by Brian Friesen
- Online Tool to compute common CRCs (8/16/32/64) from strings
- Online CRC calculator
- Online CRC Tool: Generator of synthesizable CRC functions
- Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms
- CRC16 to CRC64 collision research
- Reversing CRC – Theory and Practice.
- 'CRC-Analysis with Bitfilters'.
- Bad CRC Reading Tool
- Another Bad CRC Reading Tool, but free

Lấy từ “http://vi.wikipedia.org../../../c/r/c/CRC_1a4b.html”

Thể loại: Bài đang dịch quá 1 tháng | Thuật toán kiểm thử

##### Views

- Bài viết
- Thảo luận
- Phiên bản hiện hành

##### Tìm kiếm

##### Ngôn ngữ khác

- Bahasa Indonesia
- Български
- Català
- Česky
- Deutsch
- English
- Español
- Français
- 한국어
- Italiano
- עברית
- Nederlands
- 日本語
- Polski
- Português
- Русский
- Suomi
- Svenska
- 中文