Cyclic redundancy check

A Cyclic redundancy check (often shortened to CRC) is a way to calculate a checksum, based on a polynomial. In computer science, CRCs are used to check that no errors occurred transmitting the data. The transmitted messages are divided into predetermined lengths which, used as dividends, are divided by a fixed divisor. The remainder of the calculation is appended onto and sent with the computer recalculates the remainder. If it does not match the transmitted remainder, an error is detected. At this point, the data is re-sent. Ethernet packets have a (CRC) code.  

For example: 

If 'm' is your message of 16 bits, and you are calculating a CRC of 8 bits (CRC-8), then let 'x' be message 'm' appended by 7 zeroes. Let 'y' be a "magic" number. Divide 'x' by 'y', until you obtain a remainder that is not divisible further. Take this remainder and subtract it from the "magic" number 'y' and add this result to 'x' to obtain 'z'. 'z' is now a multiple of the "magic" number 'y' and dividing 'z' by 'y' will give a zero remainder. 'z' can now be transmitted to the receiver. The receiver will perform this division and check if the remainder is zero to confirm that there were no errors in transmission. The message can be recovered by simply reading the most significant 16 bits in the 24 bit transmission. 

In real world systems, these long division operations are performed in hardware by bit-shifting and XORing, a feat which is trivial for digital electronics to perform at extremely high speeds. 

Category:Information theory
Category:Binary arithmetics
Category:Algorithms