Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Implementing The CCITT Cyclical Redundancy Check


The CCITT-CRC error detection scheme was first employed (with some minor modifications) by IBM in its SDLC data link protocol and is used today in other modern data link protocols such as HDLC, SS7, and ISDN. Like a checksum, the CCITT-CRC does not impose any additional transmission overhead at the character level. It can detect errors in any arbitrary number of bits of data, and its error detection rate is 99.9984 percent, worse case.

Some rather powerful math stands behind the CCITT-CRC. Fortunately, the reader doesn't need to understand the math in order to use the algorithm. The basic idea is to treat the entire message as a (rather long) binary number, which both the sender and receiver divide using the same divisor. The quotient is discarded, and the remainder is sent as the CRC. If the message is received without error, the receiver's calculation will match the sender's calculation, and the CRC's will agree.

(This is a gross simplification of the process. The CRC is actually the one's complement of the remainder obtained from the modulo 2 division of the message by a generation polynomial. The CCITT-CRC uses:

x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1

for the generator polynomial. The generator is part of the standard established by the CCITT, an international standards body that publishes recommendations dealing with telephony and data communications.)

The elegance of this approach is that the division, which looks as though it ought to be a complicated process, can be implemented in hardware using a shift register and a few exclusive-OR gates.

The division can also be implemented in software, as the function crc16 (Listing One) demonstrates.

/**************************************************************************
//
// crc16.c - generate a ccitt 16 bit cyclic redundancy check (crc)
//
//      The code in this module generates the crc for a block of data.
//
**************************************************************************/

/*
//                                16  12  5
// The CCITT CRC 16 polynomial is X + X + X + 1.
// In binary, this is the bit pattern 1 0001 0000 0010 0001, and in hex it
//  is 0x11021.
// A 17 bit register is simulated by testing the MSB before shifting
//  the data, which affords us the luxury of specifiy the polynomial as a
//  16 bit value, 0x1021.
// Due to the way in which we process the CRC, the bits of the polynomial
//  are stored in reverse order. This makes the polynomial 0x8408.
*/
#define POLY 0x8408

/*
// note: when the crc is included in the message, the valid crc is:
//      0xF0B8, before the compliment and byte swap,
//      0x0F47, after compliment, before the byte swap,
//      0x470F, after the compliment and the byte swap.
*/

extern  crc_ok;
int     crc_ok = 0x470F;

/**************************************************************************
//
// crc16() - generate a 16 bit crc
//
//
// PURPOSE
//      This routine generates the 16 bit remainder of a block of
//      data using the ccitt polynomial generator.
//
// CALLING SEQUENCE
//      crc = crc16(data, len);
//
// PARAMETERS
//      data    <-- address of start of data block
//      len     <-- length of data block
//
// RETURNED VALUE
//      crc16 value. data is calcuated using the 16 bit ccitt polynomial.
//
// NOTES
//      The CRC is preset to all 1's to detect errors involving a loss
//        of leading zero's.
//      The CRC (a 16 bit value) is generated in LSB MSB order.
//      Two ways to verify the integrity of a received message
//        or block of data:
//        1) Calculate the crc on the data, and compare it to the crc
//           calculated previously. The location of the saved crc must be
//           known.
/         2) Append the calculated crc to the end of the data. Now calculate
//           the crc of the data and its crc. If the new crc equals the
//           value in "crc_ok", the data is valid.
//
// PSEUDO CODE:
//      initialize crc (-1)
//      DO WHILE count NE zero
//        DO FOR each bit in the data byte, from LSB to MSB
//          IF (LSB of crc) EOR (LSB of data)
//            crc := (crc / 2) EOR polynomial
//          ELSE
//            crc := (crc / 2)
//          FI
//        OD
//      OD
//      1's compliment and swap bytes in crc
//      RETURN crc
//
**************************************************************************/
unsigned short crc16(data_p, length)
char *data_p;
unsigned short length;
{
       unsigned char i;
       unsigned int data;
       unsigned int crc;
       
       crc = 0xffff;
       
       if (length == 0)
              return (~crc);
       
       do {
              for (i = 0 data = (unsigned int)0xff & *data_p++;
                  i < 8;
                  i++, data >>= 1) {
                    if ((crc & 0x0001) ^ (data & 0x0001))
                           crc = (crc >> 1) ^ POLY;
                    else
                           crc >>= 1;
              }
       } while (--length);
       
       crc = ~crc;
       
       data = crc;
       crc = (crc << 8) | (data >> 8 & 0xFF);
       
       return (crc);
}
Listing One.

The processor overhead involved in calculating the checksum is not too bad when you consider the large number of errors that the algorithm can detect. Two noteworthy items: the CCITT-CRC is calculated on the data bits in the order that they are sent (least significant bit first); and the 16-bit CRC is itself sent least significant byte first.

The initial value of the CRC, known as the "preset," can be either 0 or 0xFFFF. Originally, implementers used a preset of zero. This preset, however, exposed a weakness in the algorithm. A message that started with an arbitrary number of zeros would have a CRC of zero until a 1 bit was detected. Today, the predominant preset is OxFFFF, which avoids the leading zero problem.

The function main (Listing Two) illustrates the behavior of the CCITT-CRC on some test data.

/**************************************************************************
//
// main() - test driver for crc16 function
//
**************************************************************************/

#include <stdio.h>

main(argc, argv)
int argc;
char *argv[];
{
       unsigned short crc;
       static unsigned char string[40];
       string[0] = 'T';
       string[1] = (unsigned char)0xd9;
       string[2] = (unsigned char)0xe4;
       string[3] = NULL;
       
       printf ("The crc of \"T\" is 0xD9E4. crc16 returned 0x%X.\r\n\n",
                    crc16(string, (short)1))
       
       printf ("The crc of \"T 0xD9 0xE4\" is %x. The value of crc_ok is 0x%X.\r\n\n",
                    crc16(string, (short)3), crc_ok);
       
       strcpy(string, "THE,QUICK,BROWN,FOX,0123456789");
       printf("The crc of \"%s\" is 0x6E20. crc16 returned 0x%X.\r\n\n",
                    string, crc1 (string, strlen(string)));
       
       string[0] = (unsigned char)0x03;
       string[1] = (unsigned char)0x3F;
       puts("CCITT Recommendation X.25 (1984) Appendix I example:");
       printf("\tThe crc of 0x03 0x3F is 0x5BEC. crc16 returned 0x%X.\r\n\n",
                    crc16(string, (short)2));
       
       puts("strike RETURN to continue...");
       getchar();
}
Listing Two.

The first case calculates the CRC for the message T. The second case calculates the CRC for the message T and its CRC. Note that this CRC is a constant, which has been defined in crc_ok. (This is the approach usually taken when the CCITT-CRC is implemented in hardware.) The third case illustrates the CRC applied to a longer message. The final case is taken from Appendix I of CCITT Recommendation X.25.

A note about portability: I have used the code presented here on four different compilers for three different machine types (8086, 6809, and 68000). You should be able to use it without any problems.

The CCITT-CRC has other applications besides the field of data communications. I used it in an embedded system application to verify the integrity of a block of data held in non-volatile RAM. You could use it to verify any block of data on disk or in memory. And of course you can use it in message protocols of your own devising.

Other Error Detection Schemes

Anytime a message is transferred over a physical medium, the possibility exists that it may be corrupted by noise. Accordingly, since the earliest days of data communication, various mechanisms have been devised to detect when the data received was not the same as the data sent.

One of the simplest error detection schemes is parity checking. Each data byte is sent with an extra bit, which is called the parity bit. The value of the parity bit depends on the number of 1 bits in the byte, and also on the type of parity checking used. When Odd Parity is employed, the parity bit is a 1 when the number of 1 bits in the byte is odd. Otherwise, the parity bit is a 0. When Even Parity is used, a parity bit of 1 indicates an even number of 1 bits. Parity checking is easily implemented in hardware and is a feature found on most data comm chips. Its speed and ease of use make it an attractive and popular error detection mechanism.

Yet, parity checking is rather inefficient. In asynchronous communications, each eight-bit data byte is "framed" by a start bit and a stop bit, for a total of 10 bits. Adding a parity bit to the data byte increases the character size 10 percent. Furthermore, parity checking can only detect an odd number of errors per byte. If two bit errors occur in a single byte, they cancel each other. The parity is unchanged, and the error goes undetected. In an extreme case, all eight data bits in the byte could be reversed, but the parity check would not detect the error.

A more efficient method of detecting errors is the checksum. A checksum is calculated by adding together the values of all of the data bytes in the message. Checksums can be 8, 16, or 32 bits wide (overflow from the addition is ignored). In a typical application, the checksum is appended to the end of the message. The receiver verifies the message by re-calculating the checksum on the data and comparing its result to the checksum that was sent.)

Simple checksums are easy to implement in software and do not bog the processor down. When checksums are employed, data can be transmitted without the overhead of parity bits. This is a consideration that becomes more important as the size of the message increases. However, checksums fall prey to an entire class of errors that can be termed "transposition errors." Imagine that a message is sent containing the sequence 0x31 0x33. With just two bit errors, the sequence could be incorrectly received as 0x33 0x31, and yet still produce a "correct" checksum.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.