Cyclic redundancy check

From open-encyclopedia.com - the free encyclopedia.

A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum which is a small integer from a large block of data, such as network traffic or computer files, in order to detect errors in transmission or duplication. CRCs are calculated before and after transmission or duplication, and compared to confirm that they are the same. The most widely used CRC calculations are constructed in ways such that certain types of errors, such as those due to noise in transmission channels, are almost always detected.

Contents

1 Introduction

2 Polynomials and types

3 CRCs and data integrity

4 See also

5 External links

Introduction

The essential mathematical operation in the calculation of a CRC is modulo 2 division, and the remainder from the division determines the CRC. CRC's are often referred to as "checksums," but such designations are not accurate since, technically, a checksum is calculated through addition, not division. The main portion of the algorithm in pseudocode is as follows:

The following is wikicode, a proposed pseudocode for use in many articles:

 function crc(bit array bitString[1..len], int polynomial) {
     shiftRegister := initial value // commonly all 0 bits or all 1 bits
     for i from 1 to len {
         if most significant bit of shiftRegister xor bitString[i] = 1
             shiftregister := (shiftregister left shift 1) xor polynomial
         else
             shiftRegister := shiftregister left shift 1
     }
     return shiftregister
 }

Note: Use of a lookup table containing the CRC's of all 256 possible bytes allows for an eight-fold 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 CRC-32.

Polynomials and types

CRC-8	x^8 + x^2 + x + 1
CRC-CCITT	x^16 + x^12 + x^5 + 1
IBM-CRC-16	x^16 + x^15 + x^2 + 1
802.3-Frames	x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

CRCs and data integrity

While useful for error detection, CRCs cannot be safely relied upon to verify data integrity (that no changes whatsoever have occurred), since it's possible to intentionally change data without modifying its CRC. Cryptographic hash functions can be used to verify data integrity.

External links

A Painless Guide to CRC Error Detection Algorithms (dead link ?)
A Painless Guide to CRC Error Detection Algorithms (dead link ?)
Understanding Cyclic Redundancy Check
Jacksum (a program with various message verification functions)
checksums, CRCs, and their source code http://www.netrino.com/Connecting/1999-11/ , http://www.netrino.com/Connecting/1999-12/ , http://www.netrino.com/Connecting/2000-01/

de:Zyklische Redundanzprüfung ja:巡回冗長検査