THE VLSI HOMEPAGE

CRC-16 and CRC-32 algorithms are widely used in diverse communication protocols for robustness. The basic idea behind CRC is that the transmitter computes a string of bits called frame check sequence (or checksum) for each frame based on it’s contents and appends it to the end of the message before sending it to the receiver. The receiver then performs a similar computation and checks the checksum for any induced errors.

To detect burst errors (an error burst begins and ends with an error bit while the intermediate bits are correct), polynomial codes are more reliable than parity calculation. Polynomial codes exploit the modulo-2 arithmetic properties of binary numbers (i.e. binary arithmetic operations without any carries).

CRC computation involves appending a string of zeros to the frame equal in number to the number of FCS bits and modulo-2 divide by using a generator polynomial containing one more bit than the FCS to be generated. This division is similar to performing a bit-wise XOR opertation in the frame - the remainder is the checksum (FCS) that is transmitted. Similarly, the receiver divides the received frame using the same polynomial and checks if the remainder is zero. If the remainder is non-zero, the message has been corrupted.

We can cover CRC generation using an example - consider the message 11100110 that needs to be appended with 4-bit FCS using a generator polynomial of 11001. We need to append four 0’s to the message and modulo-2 divide it by generator polynomial.

Checksum computation

At the receiver end, the message 1 1 1 0 0 1 1 0 0 1 1 0 is modulo-2 divided by 1 1 0 0 1 to check if the remainder is zero.

The schematic is shown below for the four bit checksum computation, the FCS shift register is cleared and first octet is parallel-loaded into the parallel-in serial out shift register. This data is now shifted out MSB first and the shifted out data is XORed with X^3 and passed via feedback path to the selected inputs of FCS shift register. After the entire message has been transmitted, the fcs_ctrl changes from 1 -> 0 so that the current contents of FCS register (the remainder) follows the frame contents.

4-bit CRC schematic

Similarly on the Rx side for checking, the data is shifted into the serial-in parallel-out shift register and the serial data is XORed with X^3 and feedback path drives the FCS shift register. Once the entire message is received, the four bits of FCS register are checked to see if they hold 0s.

The choice of generator polynomial is important since it determines the number of errors it detects. A generator polynomial of N bits will detect single-bit, double-bit errors, all error bursts < N and all odd number of bit errors. The CRC-16 algorithm uses the polynomial X^16 + X^15 + X^2 + 1.

Tanenbaum goes into detail of choosing CRC polynomials in Computer Networks.

Share This