Computation of cyclic redundancy checks

As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character "W", which is binary 01010111₂, decimal 87₁₀, or hexadecimal 57₁₆. For illustration, we will use the CRC-8-ATM (HEC) polynomial ${\displaystyle x^{8}+x^{2}+x+1}$. Writing the first bit transmitted (the coefficient of the highest power of ${\displaystyle x}$) on the left, this corresponds to the 9-bit string "100000111".

The byte value 57₁₆ can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial ${\displaystyle M(x)}$. Msbit-first, this is ${\displaystyle x^{6}+x^{4}+x^{2}+x+1}$ = 01010111, while lsbit-first, it is ${\displaystyle x^{7}+x^{6}+x^{5}+x^{3}+x}$ = 11101010. These can then be multiplied by ${\displaystyle x^{8}}$ to produce two 16-bit message polynomials ${\displaystyle x^{8}M(x)}$.

Computing the remainder then consists of subtracting multiples of the generator polynomial ${\displaystyle 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 the subtractions borrow "from infinity" instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.

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 blue shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left.

In the msbit-first example, the remainder polynomial is ${\displaystyle x^{7}+x^{5}+x}$. Converting to a hexadecimal number using the convention that the highest power of x is the msbit; this is A2₁₆. In the lsbit-first, the remainder is ${\displaystyle x^{7}+x^{4}+x^{3}}$. Converting to hexadecimal using the convention that the highest power of x is the lsbit, this is 19₁₆.

Writing out the full message at each step, as done in the example above, is very tedious. Efficient implementations use an ${\displaystyle n}$-bit shift register to hold only the interesting bits. Multiplying the polynomial by ${\displaystyle x}$ is equivalent to shifting the register by one place, as the coefficients do not change in value but only move up to the next term of the polynomial.

Here is a first draft of some pseudocode for computing an n-bit CRC. It uses a contrived composite data type for polynomials, where x is not an integer variable, but a constructor generating a Polynomial object that can be added, multiplied and exponentiated. To xor two polynomials is to add them, modulo two; that is, to exclusive OR the coefficients of each matching term from both polynomials.

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial := polynomialForm(bitString[1..n])   // First n bits of the message
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0   // Define bitString[k]=0 for k>len
        if coefficient of xn of remainderPolynomial = 1 {
            remainderPolynomial := remainderPolynomial xor generatorPolynomial
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

Code fragment 1: Simple polynomial division

Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; 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 ${\displaystyle x}$ could be a left or right shift, and the addition of bitString[i+n] is done to the ${\displaystyle x^{0}}$ 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 ${\displaystyle x^{n}}$ 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 ${\displaystyle x^{n-1}}$ coefficient of the remainderPolynomial before it is multiplied by ${\displaystyle x}$.

The second problem could be solved by doing the last n iterations differently, but there is a more subtle optimization 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; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor (bitstring[i] * xn−1)
        if (coefficient of xn−1 of remainderPolynomial) = 1 {
            remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
        } else {
            remainderPolynomial := (remainderPolynomial * x)
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

Code fragment 2: Polynomial division with deferred message XORing

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 ${\displaystyle x^{n}}$ 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; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn−8
        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; see § Post-invert below
    return remainderPolynomial
}

Code fragment 3: Polynomial division with bytewise message XORing

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

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 ${\displaystyle x}$, and the last ${\displaystyle n}$ bits transmitted are the CRC remainder ${\displaystyle R(x)}$, starting with the coefficient of ${\displaystyle x^{n-1}}$ and ending with the coefficient of ${\displaystyle x^{0}}$, 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 bit ordering (endianness) of the data; which bit in each byte is considered "first" and will be the coefficient of the higher power of ${\displaystyle 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 ${\displaystyle 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 (serial port) standards specify least-significant bit first (little-endian) transmission, so a software CRC implementation to protect data sent across such a link should map the least significant bits in each byte to coefficients of the highest powers of ${\displaystyle x}$. On the other hand, floppy disks and most hard drives write the most significant bit of each byte first.

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

So far, the pseudocode has avoided specifying the ordering of bits within bytes by describing shifts in the pseudocode as multiplications by ${\displaystyle x}$ and writing explicit conversions from binary to polynomial form. In practice, the CRC is held in a standard binary register using a particular bit-ordering convention. In msbit-first form, the most significant binary bits will be sent first and so contain the higher-order polynomial coefficients, while in lsbit-first 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 ${\displaystyle x^{16}+x^{12}+x^{5}+1}$:

// Most significant bit first (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 rem and 0x8000 {   // if leftmost (most significant) bit is set
                rem  := (rem leftShift 1) xor 0x1021
            } else {
                rem  := rem leftShift 1
            }
            rem  := rem and 0xffff      // Trim remainder to 16 bits
        }
    }
    // A popular variant complements rem here
    return rem
}

Code fragment 4: Shift register based division, MSB first

// Least significant bit first (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 rem and 0x0001 {   // if rightmost (most significant) bit is set
                rem  := (rem rightShift 1) xor 0x8408
            } else {
                rem  := rem rightShift 1
            }
        }
    }
    // A popular variant complements rem here
    return rem
}

Code fragment 5: Shift register based division, LSB first

Note that the lsbit-first form avoids the need to shift string[i] before the xor. In either case, be sure to transmit the bytes of the CRC in the order that matches your chosen bit-ordering convention.

When appending a CRC to a message, it is possible to detach the transmitted CRC, recompute it, and verify the recomputed value against the transmitted one. However, a simpler technique is commonly used in hardware.

When the CRC is transmitted with the correct byte order (matching the chosen bit-ordering convention), a receiver can compute an overall CRC, over the message and the CRC, and if they are correct, the result will be zero.[14] This possibility is the reason that most network protocols that include a CRC do so before the ending delimiter; it is not necessary to know whether the end of the packet is imminent to check the CRC. In fact, a few protocols use the CRC *as* the ending delimiter -- CRC-based framing.

In practice, most standards specify presetting the register to all-ones and inverting the CRC before transmission. This has no effect on the ability of a CRC to detect changed bits, but gives it the ability to notice bits that are added to the message.

General category

• Error correcting code
• List of hash functions
• Parity is equivalent to a 1-bit CRC with polynomial x+1.

Non-CRC checksums

• Adler-32
• Fletcher's checksum

• JohnPaul Adamovsky. "64 Bit Cyclic Redundant Code – XOR Long Division To Bytewise Table Lookup".

• Andrew Kadarch, Bob Jenkins. "Efficient (~1 CPU cycle per byte) CRC implementation". GitHub.