Let *T'(x) = T(x)+E(x)*, be the incorrectly received message created
by adding the original message *T(x)* to an error polynomial *E(x)*.
To represent a 2-bit error in a pair of adjacent bits, error polynomial *E(x)*
must have the form *x ^{i+1}+x^{i}*, which factors into

To pass undetected, the expression *T'(x)/G(x)* must give remainder
0. This expression is a sum of two terms:

The first term is *T(x)/G(x)*. By definition of polynomial *T(x)*,
it leaves remainder 0 when divided by *G(x)*. Therefore expression
T'(x)/G(x) has remainder 0 if and only if *E(x)/G(x)* has remainder 0.
In other words, to pass undetected, *G(x)* must evenly divide E(x),
leaving remainder 0.

Does *G(x)=x ^{3}+1* evenly divide

This is because all such error polynomials factor into the form *x ^{i}(x^{r-1}+
... +1)* where

CRC-12

*x ^{12}+x^{11}+x^{3}+x^{2}+x+1*

CRC-16

*x ^{16}+x^{15}+x^{2}+1*

CRC-CCITT

*x ^{16}+x^{12}+x^{5}+1*

Having 1 as the last term of *G(x)* also helps detection of error
bursts, *E(x)*, with degree equal to or greater than *G(x)*'s.
This is because a burst can only pass undetected, when all *r* bits of
the remainder of *E(x)/G(x)* are 0. According to the definition of a
burst, the first and last bits of *E(x)* are defined to be 1, while the
last bit of *G(x)* is chosen to be 1. The next-to-last *r* bits
of *E(x)/G(x)*'s remainder have 50% chance of matching, assuming that
the error altered them randomly. Only when all *r* bits match does the
burst escape detection, and this event has probability ½^{r}.

In the special case when *E(x)* has degree exactly *r*, then
because its first bit is defined to be 1, as well as its last bit, divisor *G(x)*
matches in both first and last bit positions. This leaves only *r-1*
other bits unknown. This case therefore escapes detection with probability ½^{r-1}.

The modulo-2 polynomial division used for CRC Polynomials is conveniently
implemented using a shift register of *r* bits, where *r* is the
degree of the CRC polynomial. The following C fragment illustrates such an
implementation:

BOOLEAN morebits(void);

BIT nextbit(void);

BITREGISTER shiftreg, crc;

while (morebits())

{

if (FIRSTBIT(shiftreg) == 1) shiftreg ^= crc;

shiftreg= (shiftreg << 1) | nextbit();

}

In the fragment above, the input shifts left (operator `<<`

) 1
bit at a time. When a 1 appears in the first bit of the shift register the
post-CRC-division remainder is determined (exclusive-or operator `^=`

) for all
bits in parallel, at each step of the division.

The corresponding hardware shift register depends on a circuit which has a
shift register stage for the low order *r* bits of the CRC polynomial.
Each stage which represents a 1 polynomial coefficient is preceded by an
exclusive-or gate. The exclusive-or gates are connected to sense the first
shift register bit. This corresponds to the first bit of the dividend. When the
first bit is 0, the shift register shifts each bit into the stage to its left.
However, when the first bit is 1, bits which pass through an exclusive-or gate
are inverted as they are shifted. This determines the post-CRC-division
remainder for all bits in parallel, at each step of the division.

In both software and hardware, after the message polynomial has passed
through the input, the shift register contains the remainder which should be 0
for a correctly received message. This remainder can be shifted out of the
first shift register bit by shifting *r* 0 bits into the input.