Bob is the chief engineer at Iron Horse Software, a small consulting firm which specializes in data communications and other forms of real-time software for embedded systems. He has been coding in C for over four years, using a number of different compilers.
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%, 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
x16 + x12 + x5 + 1for 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 1) demonstrates. 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 2) illustrates the behavior of the CCITT-CRC on some test data. 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 (the 1984 Red book).
A note about portability: I have used the code presented here on four different compilers (Cross Code C, Ecosoft C, Introl C and Laser C) 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.
References
1) Computer Networks: Protocols, Standards and Interfaces, Uyless Black, Prentice Hall. 1987. A comprehensive book on all aspects of data communications. Chapter 8 deals with the X.25 protocol.
2) "Calculating Checksums with Bits and Bytes," Byte Magazine, September 1986. This article presents the nuts and bolts of division by using the shift and exclusive-OR operators. Recommended reading for EEs and math majors.
3) "Generating CRCs with software," Robert Grappel, EDN, October 31, 1984. This article also gives generation polynomials for 12 and 16 bit CRCs.
See sidebar, "Other Error Detection Schemes."