next up previous contents index Search
Next: CRC-16 Up: 0.12.3 Cyclic Redundancy Checks Previous: 0.12.3 Cyclic Redundancy Checks CRC-CCIT

The CRC-CCIT is used by the Xmodem-CRC telecommunication protocol and   takes its name from the CCIT worldwide standards organization. This     flavor of CRC is used on single bytes of data. The divisor polynomial for this CRC flavor is:

x16 + x12 + x5 + 1

The CRC-CCIT value, for an 8-bit number, is the remainder of the division of the CRC polynomial by the above divisor polynomial. For instance, for the previously examined bit pattern 10011011 the CRC-CCIT fraction would look like this:

CRC-CCIT = remainder of $\frac{x^7 + x^4 + x^3 + x^1 + 1}
{x^{16} + x^{12} + x^5 + 1}$

This may look like a difficult expression to simplify, especially with the speed demanded by limited buffer size and high bandwidth communications. However, by carefully choosing the value of x so as to make division possible using only bitwise operations, the value can be computed very rapidly. This value is 0x1021.

An even faster alternative to calculating the remainder of the above division is to create a lookup table of values. Since the denominator   of the division is a constant and the numerator can have only 256 possible values (one for each possible bit combination), a table of 256 remainders can provide instant access to the CRC-CCIT value of a particular byte. Such a table can be generated easily by repeatedly calling the get_crc_ccit function below in a loop with values ranging from zero to 255 and a crc seed value of zero.

unsigned short table[256];

for (i = 0; i < 256; i++) {

  /* the implementation of get_crc_ccit is given below */
  table[i] = get_crc_ccit(i, 0);

Here's the table (all CRC values are hexadecimal):

(0) 0x0000 0x1021 0x2042 0x3063 0x4084 0x50a5 0x60c6 0x70e7
(8) 0x8108 0x9129 0xa14a 0xb16b 0xc18c 0xd1ad 0xe1ce 0xf1ef
(16) 0x1231 0x0210 0x3273 0x2252 0x52b5 0x4294 0x72f7 0x62d6
(24) 0x9339 0x8318 0xb37b 0xa35a 0xd3bd 0xc39c 0xf3ff 0xe3de
(32) 0x2462 0x3443 0x0420 0x1401 0x64e6 0x74c7 0x44a4 0x5485
(40) 0xa56a 0xb54b 0x8528 0x9509 0xe5ee 0xf5cf 0xc5ac 0xd58d
(48) 0x3653 0x2672 0x1611 0x0630 0x76d7 0x66f6 0x5695 0x46b4
(56) 0xb75b 0xa77a 0x9719 0x8738 0xf7df 0xe7fe 0xd79d 0xc7bc
(64) 0x48c4 0x58e5 0x6886 0x78a7 0x0840 0x1861 0x2802 0x3823
(72) 0xc9cc 0xd9ed 0xe98e 0xf9af 0x8948 0x9969 0xa90a 0xb92b
(80) 0x5af5 0x4ad4 0x7ab7 0x6a96 0x1a71 0x0a50 0x3a33 0x2a12
(88) 0xdbfd 0xcbdc 0xfbbf 0xeb9e 0x9b79 0x8b58 0xbb3b 0xab1a
(96) 0x6ca6 0x7c87 0x4ce4 0x5cc5 0x2c22 0x3c03 0x0c60 0x1c41
(104) 0xedae 0xfd8f 0xcdec 0xddcd 0xad2a 0xbd0b 0x8d68 0x9d49
(112) 0x7e97 0x6eb6 0x5ed5 0x4ef4 0x3e13 0x2e32 0x1e51 0x0e70
(120) 0xff9f 0xefbe 0xdfdd 0xcffc 0xbf1b 0xaf3a 0x9f59 0x8f78
(128) 0x9188 0x81a9 0xb1ca 0xa1eb 0xd10c 0xc12d 0xf14e 0xe16f
(136) 0x1080 0x00a1 0x30c2 0x20e3 0x5004 0x4025 0x7046 0x6067
(144) 0x83b9 0x9398 0xa3fb 0xb3da 0xc33d 0xd31c 0xe37f 0xf35e
(152) 0x02b1 0x1290 0x22f3 0x32d2 0x4235 0x5214 0x6277 0x7256
(160) 0xb5ea 0xa5cb 0x95a8 0x8589 0xf56e 0xe54f 0xd52c 0xc50d
(168) 0x34e2 0x24c3 0x14a0 0x0481 0x7466 0x6447 0x5424 0x4405
(176) 0xa7db 0xb7fa 0x8799 0x97b8 0xe75f 0xf77e 0xc71d 0xd73c
(184) 0x26d3 0x36f2 0x0691 0x16b0 0x6657 0x7676 0x4615 0x5634
(192) 0xd94c 0xc96d 0xf90e 0xe92f 0x99c8 0x89e9 0xb98a 0xa9ab
(200) 0x5844 0x4865 0x7806 0x6827 0x18c0 0x08e1 0x3882 0x28a3
(208) 0xcb7d 0xdb5c 0xeb3f 0xfb1e 0x8bf9 0x9bd8 0xabbb 0xbb9a
(216) 0x4a75 0x5a54 0x6a37 0x7a16 0x0af1 0x1ad0 0x2ab3 0x3a92
(224) 0xfd2e 0xed0f 0xdd6c 0xcd4d 0xbdaa 0xad8b 0x9de8 0x8dc9
(232) 0x7c26 0x6c07 0x5c64 0x4c45 0x3ca2 0x2c83 0x1ce0 0x0cc1
(240) 0xef1f 0xff3e 0xcf5d 0xdf7c 0xaf9b 0xbfba 0x8fd9 0x9ff8
(248) 0x6e17 0x7e36 0x4e55 0x5e74 0x2e93 0x3eb2 0x0ed1 0x1ef0

In order to arrive at a CRC for the entire range of data to be verified, a running CRC value is used. This is to say, the CRC of the first byte of data is used to somehow affect the CRC value of the second byte, and so on...

for (i = 0; i < data_size; i++) {
  crc = get_crc_ccit(crc, buffer[i]);

Here is the code to calculate the CRC of a byte, based on source from Rex and Binstock. The initial value of crc should be zero on the first call to this routine.

#include <stdio.h>
#include <stdlib.h>

unsigned short get_crc_ccit (unsigned short crc, unsigned short data) {
  static unsigned int i;

  /* move to most significant bit */
  data <<= 8;

  /* for each bit in the character... */
  for (i = 8; i > 0; i--) {

    /* calculate */
    if ((data ^ crc) & 0x8000) crc = (crc << 1) ^ 0x1021;
    else crc <<= 1;

    /* next bit please */
    data <<= 1;

Scott Gasch