Computation of CRC - Bit Ordering (Endianness)

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 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 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 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, int len) { rem := 0 // A popular variant complements rem here for i from 1 to len { rem := rem xor (string 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, int len) { rem := 0 // A popular variant complements rem here for i from 1 to len { rem := rem xor string 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 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.