– CRC is the short form for cyclic redundancy check and is used as an error detection code.
– CRC finds its largest use in the storage devices and digital networks for the detection of the accidental changes that might have caused to the data during its transmission.
– When the blocks of data enter in to these systems, short check value is attached to them.
– This attached value is derived from the remainder of a polynomial division carried out on the contents of the data.
– When the data blocks are retrieved, the same calculation is done.
– If this value does not match with the original value i.e., if the check values do not match, then an error is said to have occurred that has corrupted the data.
– Accordingly, appropriate action can be taken to recover the original data.
– The code has been named so because of the redundant nature of the data verification or check value.
– The message is expanded without any addition of information.
– The whole algorithm consists of cyclic codes.
What makes cyclic redundancy checks so popular?
– CRCs are very easy to implemented in binary hardware and therefore so popular.
– Their mathematical analyzation is also very simple.
– They are very effective in the detection of the common errors that are introduced by the noise that find its way in the transmission channels.
– Since the length of the check value is fixed, the function generating it can be employed as a hashing algorithm also.
– The credit for the invention of the CRCs goes to W. Wesley Peterson.
– He did so in the year of 1961 using a 32 bit polynomial in the Ethernet CRC function and other standards.
– The theory behind the CRCs is of the cyclic error correcting codes.
– Peterson was the first person to propose the use of systematic cyclic codes for detecting errors in the networks.
– Earlier, the systematic cyclic codes were used only in encoding the messages by addition of check value of fixed length.
– Apart from their simple implementation, they are most appropriate for detecting the burst errors.
– They are also used for detecting contiguous sequences of corrupt data.
– Burst errors are one of the most common types of transmission errors that occur in many communication channels such as optical and magnetic storage devices.
– The definition of what is called generator polynomial is required for specifying a CRC code.
– This polynomial is somewhat similar to the divisor in the long division.
– As per the carry less arithmetic of finite field, the coefficients of the polynomial are created.
– The length of the generator polynomial is always greater than that of the remainder and therefore it is the determining factor of the length of the result.
– In practical, the finite field GF (2) is used by almost all CRCs.
– There are two elements in this field namely 1 and 0.
– This is why it matches perfectly with the architecture of the computer.
– The parity bit which is the simplest error checking mechanism, is actually a 1 – bit CRC i.e., it uses x + 1 as generator polynomial.
– The check value is calculated by a CRC – enabled device for all the blocks of data that have to be sent and appended to the data.
– It thus forms a code word.
– When this word is received, its check value is compared with the freshly calculated one.
– Sometimes, a CRC might be performed on the whole code word.
– The two results are compared and if they match, it means no errors and if it does not, surely there is an error in that particular data block.
– The device then proceeds with the proper action such as requesting the block again or reading it again.
– The basic purpose of the CRCs is protection of the communication channels from various errors providing assurance of the integrity of the messages.