The essential mathematical operation in the calculation of a CRC is binary division, and the remainder from the division determines the CRC. The main portion of the algorithm in pseudocode is as follows:
shiftregister = initial value (commonly 0x0000... or 0xFFFF...) while bits remain in string: if MSB of shiftregister is set: shiftregister = (shiftregister leftshift 1) xor polynomial ("leftshift" assumes bigendian architecture) else: shiftregister = shiftregister leftshift 1 xor next bit from the string into LSB of shiftregister output shiftregister
Note: Use of a lookup table containing the CRC's of all 256 possible bytes allows for an eightfold increase in the speed of the algorithm.
CRC types are often identified by "polynomial," which is the number used as the divisor (given in hexadecimal format). One of the most commonly encountered of the CRC types is that used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. It uses the polynomial 0x04C11DB7, and is known as "CRC32."
CRC's are often referred to as "checksums," but such designations are not accurate since, technically, a checksum is calculated through addition, not division.
Search Encyclopedia

Featured Article
