03-12-2012, 01:36 PM
CYCLIC REDUNDANCY CHECK
CYCLIC REDUNDANCY.pdf (Size: 101.67 KB / Downloads: 77)
Cyclic Redundancy Check
The cyclic redundancy check, or CRC, is a technique for detecting errors in digital
data, but not for making corrections when errors are detected. It is used primarily
in data transmission. In the CRC method, a certain number of check bits, often
called a checksum, are appended to the message being transmitted. The receiver
can determine whether or not the check bits agree with the data, to ascertain with
a certain degree of probability whether or not an error occurred in transmission. If
an error occurred, the receiver sends a “negative acknowledgement” (NAK) back
to the sender, requesting that the message be retransmitted.
The technique is also sometimes applied to data storage devices, such as a
disk drive. In this situation each block on the disk would have check bits, and the
hardware might automatically initiate a reread of the block when an error is
detected, or it might report the error to software.
The material that follows speaks in terms of a “sender” and a “receiver” of a
“message,” but it should be understood that it applies to storage writing and reading
as well.
Background
There are several techniques for generating check bits that can be added to a message.
Perhaps the simplest is to append a single bit, called the “parity bit,” which
makes the total number of 1-bits in the code vector (message with parity bit
appended) even (or odd). If a single bit gets altered in transmission, this will
change the parity from even to odd (or the reverse). The sender generates the parity
bit by simply summing the message bits modulo 2—that is, by exclusive or’ing
them together. It then appends the parity bit (or its complement) to the message.
The receiver can check the message by summing all the message bits modulo 2
and checking that the sum agrees with the parity bit. Equivalently, the receiver can
sum all the bits (message and parity) and check that the result is 0 (if even parity
is being used).
Theory
The CRC is based on polynomial arithmetic, in particular, on computing the
remainder of dividing one polynomial in GF(2) (Galois field with two elements)
by another. It is a little like treating the message as a very large binary number, and
computing the remainder on dividing it by a fairly large prime such as
Intuitively, one would expect this to give a reliable checksum.
Hardware
To develop a hardware circuit for computing the CRC checksum, we reduce the
polynomial division process to its essentials.
The process employs a shift register, which we denote by CRC. This is of
length r (the degree of G) bits, not as you might expect. When the subtractions
(exclusive or’s) are done, it is not necessary to represent the high-order bit,
because the high-order bits of G and the quantity it is being subtracted from are
both 1.