Cyclic Redundancy Check

Cyclic Redundancy Check (CRC)

The error-detection technique widely used in today's computer networks is based on cyclic redundancy check. CRC codes are also called polynomial codes.

CRC calculations use mod-2 arithmetic: addition has no carries and subtraction has no borrows. This means addition and subtraction are identical, and mod-2 arithmetic is equivalent to the exclusive-or (XOR) operation.

\begin{array}{cr} & 1011 \\ + & 0101 \\ \hline = & 1110 \end{array} \qquad \begin{array}{cr} & 1011 \\ - & 0101 \\ \hline = & 1110 \end{array} \qquad \begin{array}{cr} & 1011 \\ \text{XOR} & 0101 \\ \hline = & 1110 \end{array}

QUESTION

In mod-2 arithmetic, what is 1101 + 0111? And 1101 − 0111?

Sender and Receiver

Suppose the data $D$ to send is $d$ bits long. The sender and receiver must first agree on an $(r + 1)$ -bit generator polynomial $G$ .

The sender appends an $r$ -bit value R to the data $D$ , obtaining a sequence of $d + r$ bits that is exactly divisible by $G$ in mod-2 arithmetic.

The receiver divides the $d + r$ bits it receives by $G$ . If the remainder is not 0, an error has occurred.

The $d + r$ -bit sequence the sender needs can be built by shifting $D$ left by $r$ bits and adding $R$ . Since the resulting $d + r$ -bit sequence is divisible by $G$ , it is an integer multiple of $G$ :

\begin{aligned} D \cdot 2^r\ \text{XOR}\ R &= nG \\ D \cdot 2^r &= nG\ \text{XOR}\ R \end{aligned}

$R$ is the remainder of $D \cdot 2^r$ divided by $G$ :

R = \text{remainder}\left[\frac{D \cdot 2^r}{G}\right]

A Worked Example

Suppose $D$ = 101110 and $G$ = 1001. Then $r$ = 3, so three 0s are appended to $D$ before dividing.

The remainder $R$ is 011, so the sender transmits 101110011.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Why "Polynomial Code"?

A bit string can be viewed as a polynomial whose coefficients are 0 or 1, with the leftmost bit as the highest power. For example, $D = 101110$ corresponds to $x^5 + x^3 + x^2 + x$ , and $G = 1001$ to $x^3 + 1$ . Shifting left by $r$ bits multiplies by $x^r$ , and mod-2 long division is polynomial division in which coefficients are added and subtracted with XOR.

Which Errors Does CRC Detect?

Let $T$ be the transmitted bits and let the error pattern $E$ have a 1 at every corrupted position, so the receiver gets $T \oplus E$ . Because $T$ is a multiple of $G$ :

\text{remainder}\left[\frac{T \oplus E}{G}\right] = \text{remainder}\left[\frac{E}{G}\right]

So an error goes undetected only when $E$ happens to be a multiple of $G$ . This gives CRC several important properties:

Error type	Detected?	Reason
Single-bit error	Always	The first and last bits of $G$ are 1, so $x^i$ is never a multiple of $G$
Burst of length at most $r$	Always	A non-zero polynomial of lower degree than $G$ cannot be a multiple of $G$
Odd number of bit errors	Always, if $G$ has the factor $(x+1)$	Every multiple of $(x+1)$ has an even number of 1s
Random errors	Missed with probability about $1/2^r$	Only multiples of $G$ slip through

The CRC-32 used by Ethernet and 802.11 has $r = 32$ , so random errors slip through with probability about $2^{-32}$ , and every burst of length at most 32 is detected. CRC can be computed at high speed in hardware with shift registers and XOR gates, which is one reason it is so widely used.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

QUESTION

Sender and receiver agree on the generator G = 10011. How many bits R does the sender append, and which errors are guaranteed to be detected?

The data is D = 110101 and the generator is G = 101.

Compute the CRC bits R and the 8 bits the sender transmits.
The receiver gets 11000111. Is the error detected?
The receiver gets 11111111. Which bits are wrong, and what does the receiver decide? Explain.

Write Python functions mod2_remainder(bits, gen) and crc_encode(data, gen) that work on strings of 0s and 1s. Use them to (1) reproduce this section's example D = 101110, G = 1001 and check the frame at the receiver; (2) show that flipping one bit gives a non-zero remainder; (3) count how many of the 36 possible double-bit errors in the 9-bit frame go undetected with G = 1001 and with G = 1011.

Cyclic Redundancy Check