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.