Search
Next: 0.12.3.3 CRC-32 Up: 0.12.3 Cyclic Redundancy Checks Previous: 0.12.3.1 CRC-CCIT

### 0.12.3.2 CRC-16

CRC-16's numerator polynomial is based on sixteen bits of data unlike the CCIT's which is based on eight. The divisor polynomial for the CRC-16 is also different than the CCIT's, it is:

x16 + x5 + x2 + 1

The CRC-16, like the CRC-CCIT, can be implemented with a table lookup strategy. However where the CCIT needed 256 distinct entries in the table (one for each possible numerator - 28 total) the CRC-16 can work with a much smaller table. By examining the table value of each of the four nibbles (four bits) of data in the sixteen bit numerator polynomial the CRC-16 can arrive at a value for the upper part of the fraction. The denominator is, of course, a constant. So, the CRC-16 can operate quickly with a table size of only sixteen entries.

Because it can operate quickly with a small lookup table, the CRC-16 is often used in hardware devices such as disk controllers and the like.

/*
*  this source code is based on Rex and Binstock which, in turn,
*  acknowledges William James Hunt.
*/

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

unsigned int crc_16_table[16] = {
0x0000, 0xCC01, 0xD801, 0x1400, 0xF001, 0x3C00, 0x2800, 0xE401,
0xA001, 0x6C00, 0x7800, 0xB401, 0x5000, 0x9C01, 0x8801, 0x4400 };

unsigned short int get_crc_16 (int start, char *p, int n) {
unsigned short int crc = start;
int r;

/* while there is more data to process */
while (n-- > 0) {

/* compute checksum of lower four bits of *p */
r = crc_16_table[crc & 0xF];
crc = (crc >> 4) & 0x0FFF;
crc = crc ^ r ^ crc_16_table[*p & 0xF];

/* now compute checksum of upper four bits of *p */
r = crc_16_table[crc & 0xF];
crc = (crc >> 4) & 0x0FFF;
crc = crc ^ r ^ crc_16_table[(*p >> 4) & 0xF];

/* next... */
p++;
}

return(crc);
}


Scott Gasch
1999-07-09