Let’s Get Technical
A third hardware technique that
can be used with a serial stream of
data uses multiple bits to create a
check sequence. This technique is
called a Cyclic Redundancy Check
(CRC) and can be used with bit
streams of varying lengths.
The basic method is to treat the
serial data stream as a large, binary
number. By dividing this number by a
predefined binary polynomial, we
end up with a remainder pattern (the
check sequence) that gets tacked
onto the end of the original data.
The check sequence essentially
turns the serial stream into a number
that is evenly divisible by the polynomial.
So, on the receiving end, when the
received data (which includes the
check sequence) is passed through
the CRC circuit, the resulting check
sequence will be all 0s if there are no
errors. Any 1s that show up indicate
one or more errors in the bit stream,
but we will not know where they are.
Suppose the data to transmit is
10101100 and the four-bit polynomial
is 1011. Generating the check
sequence is accomplished through
the use of Modulo-2 arithmetic (once
again using exclusive-OR). This
process is illustrated in Figure 3. A
three-bit pattern of 000 is tacked onto
the end of the original data. This is
done to reserve room for the actual
three bits of the check sequence
once they are determined.
At each step, four bits of data are
XORed with the four-bit polynomial
1011. This process repeats until there
are no more bits left in the data. The
final three bits remaining are the CRC
check sequence (011). This
sequence is now tacked onto the end
of the original data (giving us
10101100011) and transmitted.
On the receiving end, the same
process is used again, with the 011
sequence replacing the original three
0s. If there are no errors, the remainder
will be 0. Change one of the bits
yourself and verify that the remainder
The CRC generator is easily
constructed using a few XOR gates
and a shift register. Figure 4 shows
Figure 2. Using multiple parity bits to detect and correct a single bit error.
(A) Generating the check bits. (B) Determining the four-bit error code.
the schematic of the CRC generator
for the 1011 polynomial.
A four-bit divider polynomial
requires a three-bit shift register to
hold the three remainder bits that
make up the check sequence. After
all bits have been clocked into the
circuit, the shift register will contain
the three remainder bits (LSB on the
right and MSB on the left).
An eight-bit polynomial would
require a seven-bit shift register (and
seven 0s tacked onto the original data
to begin the process). In general, the
shift register has one less stage than
the number of bits in the polynomial.
Table 3 shows some typical CRC
polynomials and their uses.
Software techniques for performing
error detection and correction are
especially useful in the world of
networking and the Internet. When we
download a web page or send an
Figure 3. Generating a CRC check