CRC - Cyclic Redundancy Check
By: Preethi Ramkumar
Meaning of CRC – “Cyclic Redundancy Check”, is based on division in a commutative ring, namely the ring of polynomials over the integers modulo 2. In simpler terms, this is the set of polynomials where each coefficient is only one bit, and arithmetic operations wrap around. For example:(x2 + x) + (x + 1) = x2 + 2x + 1 = x2 + 1
Two becomes zero because 2 is 10 in binary, and we discard all bits except the last one. Multiplication is similar: (x2 + x)(x + 1) = x3 + 2x2 + x = x3 + x
We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x3 + x2 + x by x + 1. We would find that
x3 + x2 + x = (x + 1)(x2 + 1) - 1 = (x + 1)(x2 + 1) + 1.
In other words, the division yields a quotient of x2 + 1 with a remainder of -1, which, since it is odd, has a last bit of 1.
Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide by another fixed polynomial. The coefficients of the remainder polynomial are the CRC, and there are simple, efficient algorithms for computing this remainder, such as the one shown below. CRCs are often referred to as "checksums," but such designations are not strictly accurate since, technically, a checksum is calculated through addition and not through division as is the case with CRCs.
There are two variations which can be applied to the above implementation; applying one or both gives a total of four equivalent ways to compute a checksum:
The shiftRegister can be reversed, so its least-significant bit is tested and it is shifted to the right by 1 bit each step. This requires a polynomial with its bits reversed, and produces a bit-reversed result. This variant is actually the one most commonly in use.
Instead of changing multiple bits in the shiftRegister based on the xor of one bit of the shiftRegister and one bit of the bitString, it is possible to xor (compute the parity of) all the bits of the shiftRegister selected by the polynomial and the bitString and add that single bit to the shiftRegister. With suitable adjustments to the polynomial, this also produces the same remainder. This variation is difficult in software, but used in some hardware implementations, and is often used when describing the close relative to a CRC, the linear feedback shift register
The specific CRC is defined by the polynomial used. To produce an n-bit CRC requires a degree-n polynomial, of the form xn + … + 1. This is naturally expressed as an n+1-bit string, but the leading (xn) term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the standard CRC-16, x16+x15+x2+1, will be represented as the hexadecimal number 0x8005 or as 0xa001.
One of the most commonly encountered is known as CRC-32, used by (among others) Ethernet, (FDDI) , PKZIP, WinZip, and PNG. Its polynomial can be written 0x04C11DB7 or 0xEDB88320.
Other Related Definitions:
“…The CRC is a very powerful but easily implemented technique to obtain data reliability. The CRC technique is used to protect blocks of data called Frames. Using this technique, the transmitter appends an extra n- bit sequence to every frame called Frame Check Sequence (FCS). The FCS holds redundant information about the frame that helps the transmitter detect errors in the frame.” [RAD Data Communications]
“…CRC has been an integral part of the computer industry for quite some time. The actual implementation of CRC is quite simple, especially from within 4th Dimension. However, the concept behind CRC is less straightforward. CRC is rarely explained in a manner that is less than daunting. The aim of this technical note is to present the theory of CRC from the ground up, and enable the reader to understand CRC, without having a background in computer science. It explains how CRCs work and presents 4D code that makes CRCs easy to use in your applications.”
[ 4D, Inc]
“… CRC Short for Cyclic Redundancy Check, CRC is a method of detecting errors in data transmission. A CRC is data that is sent with a block of data, that when received by where the information is being sent to, the CRC can be used to verify if data was all received correctly.
“…A method to detect and correct errors by adding bits derived from a block or string of bits to the block. (2) An algorithm to compute bits characteristic of a block based on the algebra of polynomials over the integers, modulo 2. (3) The characteristic bits of a block.
” [National Institute of Standards and Technology's]
- cyclic redundancy check(algorithm)
-32 bit Cyclic Redundancy Check Source Code for C++
Macs - Cyclic Redundancy Check Polynomials Tutorial
Techtarget - cyclic redundancy checking
- Cyclic redundancy check
- CYCLIC REDUNDANCY CHECKS IN USB
Cyclic Redundancy Check
- A powerful method for detecting errors
Rad - How the CRC algorithm works
Products and Solutions:
Blogs, News, Feeds, Discussion Lists:
CRC Standard Mathematical Tables and Formulae by Daniel Zwillinger
Distributed Sensor Networks (Chapman & Hall/Crc Computer and Information Science) by S. Sitharama Iyengar
CRC Concise Encyclopedia of Mathematics by Eric W. Weisstein
Other CRC Related Resources