Computation of CRC
Encyclopedia
Computation of a cyclic redundancy check
is derived from the mathematics of polynomial division, modulo two
. In practice, it resembles long division
of the binary
message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that exclusive OR operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register
, and in software by a series of equivalent algorithm
s, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated
) through byte
-wise parallelism and space-time tradeoff
s.
Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final exclusive OR step and, most critically, a bit ordering (endianness
). As a result, the code seen in practice deviates confusingly from "pure" division, and the register may shift left or right.
character "W", which is binary 010101112, decimal 8710, or hexadecimal
5716. For illustration, we will use the CRC-8-ATM (HEC
) polynomial
. Writing the first bit transmitted (the coefficient of the highest power of 
) 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 bit ordering convention used. Each one generates a different message polynomial
. Msbit-first, this is 
= 01010111, while lsbit-first, it is 
= 11101010. These can then be multiplied by 
to produce two 16-bit message polynomials 
.
Computing the remainder then consists of subtracting multiples of the generator polynomial
. 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 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 becomes 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
. Converting to a hexadecimal number using the convention that the highest power of x is the msbit; this is A216. In the lsbit-first, the remainder is 
. Converting to hexadecimal using the convention that the highest power of x is the lsbit, this is 1916.
use an
-bit shift register
to hold only the interesting bits. Multiplying the polynomial by
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
generating a Polynomial object
that can be added, multiplied and exponentiated. To
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
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
return remainderPolynomial
}
Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; the input
could be a left or right shift, and the addition of 
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
coefficient can be tested. More significantly, it requires the
The first problem can be solved by testing the
coefficient of the 
.
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
This eliminates the need to preload the
function crc(bit array bitString[1..len], int len) {
remainderPolynomial := 0
// A popular variant complements remainderPolynomial here
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
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
coefficients of it and of
In software, it is convenient to note that while one may delay the
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]) * 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
return remainderPolynomial
}
This is usually the most compact software implementation, used in microcontrollers when space is at a premium over speed.
, and the last 
bits transmitted are the CRC remainder 
, starting with the coefficient of 
and ending with the coefficient of 
, 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
.
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
; 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
. On the other hand, floppy disk
s 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
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 
:
// 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
}
// 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 (least significant) bit is set
rem := (rem rightShift 1) xor 0x8408
} else {
rem := rem rightShift 1
}
}
}
// A popular variant complements rem here
return rem
}
Note that the lsbit-first form avoids the need to shift
indexed by highest order coefficients of
// Msbit-first
rem = (rem leftShift 8) xor big_endian_table[(leftmost 8 bits of rem) rightShift (n-8)]
// Lsbit-first
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 msbit-first as 0x04C11DB7, or lsbit-first 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 lsbit-first byte-at-a-time pseudocode presented here, and the table is generated using the bit-at-a-time code.
.
To maximise computation speed, an intermediate remainder can be calculated by passing the message through a 123-bit shift register. The polynomial is a carefully selected multiple of the standard polynomial such that the terms (feedback taps) are widely spaced, and no bit of the remainder is XORed more than once per byte iteration. Thus only two-input XOR gates, the fastest possible, are needed. Finally the intermediate remainder is divided by the standard polynomial in a second shift register to yield the CRC-32 remainder.
used in hardware.
When the CRC is transmitted with the correct bit order (most significant terms first), a receiver can compute an overall CRC, over the message and the CRC, and if the CRC is correct, the result will be zero. 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.
But if the message being transmitted does care about leading 0 bits, the inability of the basic CRC algorithm to detect such a change is undesirable. If it is possible that a transmission error could add such bits, a simple solution is to start with the
This does not affect CRC generation and checking in any way, as long as both generator and checker use the same initial value. Any non-zero initial value will do, and a few standards specify unusual values, but the all-ones value (−1 in twos complement binary) is by far the most common.
A similar solution can be applied at the end of the message, inverting the CRC register before it is appended to the message. Again, any non-zero change will do; inverting all the bits is simply the most common.
This has an effect on one-pass CRC checking; instead of producing a result of zero when the message is correct, it produces a fixed non-zero result. (To be precise, the result is the non-inverted CRC of the inversion pattern.) This is still straightforward to verify.
Non-CRC checksums
Cyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
is derived from the mathematics of polynomial division, modulo two
Mathematics of CRC
The cyclic redundancy check is based on division in the ring of polynomials over the finite field GF , that is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around .Any string of bits can be interpreted as the coefficients of a message...
. In practice, it resembles long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
of the binary
Binary code
A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...
message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that exclusive OR operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register
Shift register
In digital circuits, a shift register is a cascade of flip flops, sharing the same clock, which has the output of any one but the last flip-flop connected to the "data" input of the next one in the chain, resulting in a circuit that shifts by one position the one-dimensional "bit array" stored in...
, and in software by a series of equivalent algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated
Obfuscated code
Obfuscated code is source or machine code that has been made difficult to understand for humans. Programmers may deliberately obfuscate code to conceal its purpose or its logic to prevent tampering, deter reverse engineering, or as a puzzle or recreational challenge for someone reading the source...
) through byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
-wise parallelism and space-time tradeoff
Space-time tradeoff
In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution...
s.
Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final exclusive OR step and, most critically, a bit ordering (endianness
Endianness
In computing, the term endian or endianness refers to the ordering of individually addressable sub-components within the representation of a larger data item as stored in external memory . Each sub-component in the representation has a unique degree of significance, like the place value of digits...
). As a result, the code seen in practice deviates confusingly from "pure" division, and the register may shift left or right.
Example
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 ASCIIASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
character "W", which is binary 010101112, decimal 8710, or hexadecimal
Hexadecimal
In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...
5716. For illustration, we will use the CRC-8-ATM (HEC
Header Error Correction
This is a bit error detection and correction mechanism used in data transmitter and receiver.The Header Error Control is the last field in the Asynchronous Transfer Mode cell consisting of an 8-bit CRC of the cell's header only....
) polynomial
. Writing the first bit transmitted (the coefficient of the highest power of ) 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 bit ordering convention used. Each one generates a different message polynomial
. Msbit-first, this is = 01010111, while lsbit-first, it is = 11101010. These can then be multiplied by to produce two 16-bit message polynomials .Computing the remainder then consists of subtracting multiples of the generator polynomial
. 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.| Most-significant bit first | Least-significant bit first | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
EWLINE
|
EWLINE
|
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 appropriate multiple of the polynomial is subtracted to make the zero group becomes 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
. Converting to a hexadecimal number using the convention that the highest power of x is the msbit; this is A216. In the lsbit-first, the remainder is . Converting to hexadecimal using the convention that the highest power of x is the lsbit, this is 1916.Implementation
Writing out the full message at each step, as done in the example above, is very tedious. Efficient implementationsuse an
-bit shift registerShift register
In digital circuits, a shift register is a cascade of flip flops, sharing the same clock, which has the output of any one but the last flip-flop connected to the "data" input of the next one in the chain, resulting in a circuit that shifts by one position the one-dimensional "bit array" stored in...
to hold only the interesting bits. Multiplying the polynomial by
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
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
for computing an n-bit CRC. It uses a contrived composite data type
Object composition
In computer science, object composition is a way to combine simple objects or data types into more complex ones...
for polynomials, where
x is not an integer variable, but a constructorConstructor (computer science)
In object-oriented programming, a constructor in a class is a special type of subroutine called at the creation of an object. It prepares the new object for use, often accepting parameters which the constructor uses to set any member variables required when the object is first created...
generating a Polynomial object
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
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
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
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 could be a left or right shift, and the addition of bitString[i+n] is done to the 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 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
coefficient of the remainderPolynomial before it is multiplied by .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
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
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 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 byteByte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
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]) * 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
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.
Bit ordering (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, and the last bits transmitted are the CRC remainder , starting with the coefficient of and ending with the coefficient of , a.k.a. the coefficient of 1.However, when bits are processed a byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
at a time, such as when using parallel transmission, byte framing as in 8B/10B encoding
8B/10B encoding
In telecommunications, 8b/10b is a line code that maps 8-bit symbols to 10-bit symbols to achieve DC-balance and bounded disparity, and yet provide enough state changes to allow reasonable clock recovery. This means that the difference between the count of 1s and 0s in a string of at least 20 bits...
or RS-232
RS-232
In telecommunications, RS-232 is the traditional name for a series of standards for serial binary single-ended data and control signals connecting between a DTE and a DCE . It is commonly used in computer serial ports...
-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
.If the data is destined for serial communication
Serial communication
In telecommunication and computer science, serial communication is the process of sending data one bit at a time, sequentially, over a communication channel or computer bus. This is in contrast to parallel communication, where several bits are sent as a whole, on a link with several parallel channels...
, 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
; 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
IEEE 802
IEEE 802 refers to a family of IEEE standards dealing with local area networks and metropolitan area networks.More specifically, the IEEE 802 standards are restricted to networks carrying variable-size packets. IEEE 802 refers to a family of IEEE standards dealing with local area networks and...
(ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
) and RS-232
RS-232
In telecommunications, RS-232 is the traditional name for a series of standards for serial binary single-ended data and control signals connecting between a DTE and a DCE . It is commonly used in computer serial ports...
(serial port
Serial port
In computing, a serial port is a serial communication physical interface through which information transfers in or out one bit at a time...
) 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
. On the other hand, floppy diskFloppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
s 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
XMODEM
XMODEM is a simple file transfer protocol developed as a quick hack by Ward Christensen for use in his 1977 MODEM.ASM terminal program. XMODEM became extremely popular in the early bulletin board system market, largely because it was so simple to implement...
-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
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 :// 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 (least 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.Parallel computation
Another common optimization uses a lookup tableLookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
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// Msbit-first
rem = (rem leftShift 8) xor big_endian_table[(leftmost 8 bits of rem) rightShift (n-8)]
// Lsbit-first
rem = (rem rightShift 8) xor little_endian_table[rightmost 8 bits of rem]
- Code fragment 6: Cores of table based division
One of the most commonly encountered CRC algorithms is known as CRC-32, used by (among others) Ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
, FDDI, ZIP
ZIP (file format)
Zip is a file format used for data compression and archiving. A zip file contains one or more files that have been compressed, to reduce file size, or stored as is...
and other archive formats, and PNG image format. Its polynomial can be written msbit-first as 0x04C11DB7, or lsbit-first 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 lsbit-first byte-at-a-time pseudocode presented here, and the table is generated using the bit-at-a-time code.
Parallel computation without table
Parallel update for a byte or a word at a time can also be done explicitly, without a table. For each bit an equation is solved after 8 bits have been shifted in. The following tables list the equations for some commonly used polynomials, using following symbols:| ci | CRC bit 7…0 (or 15…0) before update |
| ri | CRC bit 7…0 (or 15…0) after update |
| di | input data bit 7…0 |
| ei = di + ci | ep = e7 + e6 + … + e1 + e0 (parity bit) |
| si = di + ci+8 | sp = s7 + s6 + … + s1 + s0 (parity bit) |
| Polynomial: | (x7 + x3 + 1) × x (left-shifted CRC-7-CCITT) | x8 + x5 + x4 + 1 (CRC-8-Dallas/Maxim) |
|---|---|---|
| Coefficients: | 0x12 = (0x09 << 1) (MSBF/normal) | 0x8c (LSBF/reverse) |
r0 ← r1 ← r2 ← r3 ← r4 ← r5 ← r6 ← r7 ← |
0 e0 + e4 + e7 e1 + e5 e2 + e6 e3 + e7 + e0 + e4 + e7 e4 + e1 + e5 e5 + e2 + e6 e6 + e3 + e7 |
e0 + e4 + e1 + e0 + e5 + e2 + e1 e1 + e5 + e2 + e1 + e6 + e3 + e2 + e0 e2 + e6 + e3 + e2 + e0 + e7 + e4 + e3 + e1 e3 + e0 + e7 + e4 + e3 + e1 e4 + e1 + e0 e5 + e2 + e1 e6 + e3 + e2 + e0 e7 + e4 + e3 + e1 |
| C code fragments: |
uint8_t c, d, e, f, r; … e = c ^ d; f = e ^ (e >> 4) ^ (e >> 7); r = (f << 1) ^ (f << 4); |
uint8_t c, d, e, f, r; … e = c ^ d; f = e ^ (e << 3) ^ (e << 4) ^ (e << 6); r = f ^ (f >> 4) ^ (f >> 5); |
| Polynomial: | x16 + x12 + x5 + 1 (CRC-16-CCITT) | x16 + x15 + x2 + 1 (CRC-16-ANSI) | ||
|---|---|---|---|---|
| Coefficients: | 0x1021 (MSBF/normal) | 0x8408 (LSBF/reverse) | 0x8005 (MSBF/normal) | 0xa001 (LSBF/reverse) |
r0 ← r1 ← r2 ← r3 ← r4 ← r5 ← r6 ← r7 ← r8 ← r9 ← r10 ← r11 ← r12 ← r13 ← r14 ← r15 ← |
s4 + s0 s5 + s1 s6 + s2 s7 + s3 s4 s5 + s4 + s0 s6 + s5 + s1 s7 + s6 + s2 c0 + s7 + s3 c1 + s4 c2 + s5 c3 + s6 c4 + s7 + s4 + s0 c5 + s5 + s1 c6 + s6 + s2 c7 + s7 + s3 |
c8 + e4 + e0 c9 + e5 + e1 c10 + e6 + e2 c11 + e0 + e7 + e3 c12 + e1 c13 + e2 c14 + e3 c15 + e4 + e0 e0 + e5 + e1 e1 + e6 + e2 e2 + e7 + e3 e3 e4 + e0 e5 + e1 e6 + e2 e7 + e3 |
sp s0 + sp s1 + s0 s2 + s1 s3 + s2 s4 + s3 s5 + s4 s6 + s5 c0 + s7 + s6 c1 + s7 c2 c3 c4 c5 c6 c7 + sp |
c8 + ep c9 c10 c11 c12 c13 c14 + e0 c15 + e1 + e0 e2 + e1 e3 + e2 e4 + e3 e5 + e4 e6 + e5 e7 + e6 ep + e7 ep |
| C code fragments: |
uint8_t d, s, t; uint16_t c, r; … s = d ^ (c >> 8); t = s ^ (s >> 4); r = (c << 8) ^ t ^ (t << 5) ^ (t << 12); |
uint8_t d, e, f; uint16_t c, r; … e = c ^ d; f = e ^ (e << 4); r = (c >> 8) ^ (f << 8) ^ (f << 3) ^ (f >> 4); |
uint8_t d, s, p; | uint8_t d, e, p; |
Two-step computation
As the CRC-32 polynomial has a large number of terms, when computing the remainder a byte at a time each bit depends on several bits of the previous iteration. In byte-parallel hardware implementations this calls for either multiple-input or cascaded XOR gates which increases propagation delayPropagation delay
Propagation delay is a technical term that can have a different meaning depending on the context. It can relate to networking, electronics or physics...
.
To maximise computation speed, an intermediate remainder can be calculated by passing the message through a 123-bit shift register. The polynomial is a carefully selected multiple of the standard polynomial such that the terms (feedback taps) are widely spaced, and no bit of the remainder is XORed more than once per byte iteration. Thus only two-input XOR gates, the fastest possible, are needed. Finally the intermediate remainder is divided by the standard polynomial in a second shift register to yield the CRC-32 remainder.
One-pass checking
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 commonlyused in hardware.
When the CRC is transmitted with the correct bit order (most significant terms first), a receiver can compute an overall CRC, over the message and the CRC, and if the CRC is correct, the result will be zero. 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.
CRC variants
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.Preset to −1
The basic mathematics of a CRC accepts (considers as correctly transmitted) messages which, when interpreted as a polynomial, are a multiple of the CRC polynomial. If some leading 0 bits are prepended to such a message, they will not change its interpretation as a polynomial. This is equivalent to the fact that 0001 and 1 are the same number.But if the message being transmitted does care about leading 0 bits, the inability of the basic CRC algorithm to detect such a change is undesirable. If it is possible that a transmission error could add such bits, a simple solution is to start with the
rem shift register set to some non-zero value; for convenience, the all-ones value is typically used. This is mathematically equivalent to complementing the first n bits of the message.This does not affect CRC generation and checking in any way, as long as both generator and checker use the same initial value. Any non-zero initial value will do, and a few standards specify unusual values, but the all-ones value (−1 in twos complement binary) is by far the most common.
Post-invert
The same sort of error can occur at the end of a message. Appending 0 bits to a message is equivalent to multiplying its polynomial by x, and if it was previously a multiple of the CRC polynomial, the result of that multiplication will be, as well. This is equivalent to the fact that, since 726 is a multiple of 11, so is 7260.A similar solution can be applied at the end of the message, inverting the CRC register before it is appended to the message. Again, any non-zero change will do; inverting all the bits is simply the most common.
This has an effect on one-pass CRC checking; instead of producing a result of zero when the message is correct, it produces a fixed non-zero result. (To be precise, the result is the non-inverted CRC of the inversion pattern.) This is still straightforward to verify.
See also
General category- Error correcting code
- List of checksum algorithms
- Parity
Non-CRC checksums
- Adler-32Adler-32Adler-32 is a checksum algorithm which was invented by Mark Adler in 1995, and is a modification of the Fletcher checksum. Compared to a cyclic redundancy check of the same length, it trades reliability for speed. Adler-32 is more reliable than Fletcher-16, and slightly less reliable than Fletcher-32...
- Fletcher's checksumFletcher's checksumThe Fletcher checksum is an algorithm for computing a position-dependent checksum devised by John G. Fletcher at Lawrence Livermore Labs in the late 1970s. A description of the algorithm and an analysis of the performance characteristics of a particular implementation were published in the IEEE...
External links
- 64-Bit CRC - Bitwise XOR Long-Division To Bytewise Table-Lookup: Comprehensive documentation of CRC-Math, Procedure, and C-Code.