Table of Contents
Cyclic Redundancy Check
A cyclic redundancy check (CRC) or polynomial code checksum is a non-secure hash function designed to detect accidental changes to raw computer data, and is commonly used in digital networks and storage devices such as hard disk drives. A CRC enabled device calculates a short, fixed length binary sequence, known as the CRC code or just CRC, for each block of data and sends or stores them both together. When a block is read or received the device repeats the calculation; if the new CRC does not match the one calculated earlier, then the block contains a data error and the device may take corrective action such as rereading or requesting the block be sent again, otherwise the data is assumed to be error free (though, with some small probability, it may contain undetected errors; this is the fundamental nature of error checking).
CRCs are so called because the check (data verification) code is a redundancy (it adds zero information to the message) and the algorithm is based on cyclic codes. The term CRC may refer to the check code or to the function that calculates it, which accepts data streams of any length as input but always outputs a fixed-length code. CRCs are popular because they are simple to implement in binary hardware, are easy to analyse mathematically, and are particularly good at detecting common errors caused by noise in transmission channels. The CRC was invented by W. Wesley Peterson in 1961; the 32-bit polynomial used in the CRC function of Ethernet and many other standards is the work of several researchers and was published in 1975.
Cyclic redundancy Checking is a method of checking for errors in data that has been transmitted on a communication link. A sending device applies a 16 or 32 bit polynomial to a block of data that is to be transmitted and appends the resulting cyclic redundancy code (CRC) to the block. The receiving end applies the same polynomial to the data and compares its result with the result appended by the sender. If they agree, the data has been received successfully. If not, the sender can be notified to resend the block of data.
What is checksum?
In check summing method, d-bits of data are treated as sequence of k-bit integers. The k-bit integers are added and the resulting (1’s complement) sum is treated as a k-bit checksum work. During checking, a similar summing of the k-bit integers is carried out. If the sum agrees with the transmitted sum, everything is assumed to be alright. Otherwise, an error is flagged. The IP-checksum uses k = 16.
We assume that the data bits 1000100100 1001000111 are broken up into two 10 bits words (i.e. k = 10). Then the checksum is calculated as follows:
| Example 01 |
Given a 10 bit sequence 1011001001 and a divisor of 1011, find the CRC.
Therefore, CRC will be 110.
| Example 02 |
Explain the operation of CRC error detection method by means of an example, show how: The error detection bits are generated The received frame is checked for transmission errors. Use the generator polynomial x3 + x + 1.
In this example, we describe CRC codes using the prime polynomial G(x) = x3 + x + 1 associated with the prime number [1011]. The checksum is the remainder after dividing the original block of bits by this prime number.
Assume that our information bit stream is I(x) = x6 + x3 + x2 + 1
The parity polynomial is then generated by
\[P\left( x \right)={{x}^{3}}\times \frac{P\left( x \right)}{G\left( x \right)}=\frac{{{x}^{9}}+{{x}^{6}}+{{x}^{5}}+{{x}^{3}}}{{{x}^{3}}+x+x}\]
This division can be found using simple binary division of [1001101] by the number [1011] as shown below:
The resulting remainder checksum is [101] with polynomial expression P(x) = x2 + 1.
The coded transmitted word is then defined as
\[C\left( x \right)={{x}^{3}}\times I\left( x \right)+P\left( x \right)\Rightarrow C=[1001101101]\]
At the receiver side, the noisy version of the transmitted code word is received as
\[R\left( x \right)=C\left( x \right)+e\left( x \right)\]
The received code word is then checked for efforts by
\[\frac{R\left( x \right)}{G\left( x \right)}=\frac{C\left( x \right)}{G\left( x \right)}+\frac{e\left( x \right)}{G\left( x \right)}\]
Apparently, the received code word is acceptable if e(x) is a multiple of G(x).
;