Cyclic Redundancy Check (CRC) is a fundamental error-detection code used in the Data Link Layer to detect accidental bit corruption in frames before they are accepted by the receiver.2 In network protocols such as Ethernet and HDLC, the sender computes a short Frame Check Sequence (FCS) from the outgoing frame and appends it to the transmitted bits.2 The receiver repeats the same computation or, equivalently, divides the received codeword by the same generator polynomial; a zero remainder indicates that no detectable error has occurred.2

CRC is called a cyclic code because bit strings are interpreted as polynomials over $GF(2)$, where addition and subtraction are both implemented as XOR, with no carries or borrows.2 This algebraic structure makes CRC both mathematically analyzable and highly efficient in hardware, especially with shift registers and XOR gates.2 Compared with simple parity or additive checksums, CRC provides much stronger detection of common line errors, especially burst errors that affect adjacent bits in a frame.2

Within Network Theory, CRC should be understood as a practical instance of cyclic codes used for link-level integrity, not for cryptographic security. Its goals are to detect noise-induced corruption, framing faults, and many multi-bit error patterns at line speed.2

Footnotes

1. Cyclic redundancy check - Wikipedia - Overview of CRC theory, $GF(2)$ arithmetic, burst-error detection, and generator selection. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Lesson 5 - The Data Link Layer - Explains CRC encoding and decoding in the Data Link Layer using polynomial division. ↩ ↩² ↩³

3. Data Link Layer PDF - Lists common CRC polynomials and notes properties such as odd-bit and burst-error detection. ↩

4. Lecture 3: Framing and Error Detection - Presents CRC goals, modulo-2 division, and the burst-error guarantee for degree-$r$ generators. ↩ ↩² ↩³

5. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks - Discusses polynomial selection, Hamming distance, hardware taps, and detection strength for given frame lengths. ↩ ↩²

6. What Is a Cyclic Redundancy Check? | Everpure - Summarizes practical CRC operation and notes efficiency in hardware implementations. ↩

Mathematical Model of CRC

A binary message can be represented as a polynomial whose coefficients are either $0$ or $1$.2 For example, the bit string $10011010$ corresponds to

$$D(x) = x^7 + x^4 + x^3 + x$$

if the leftmost bit is the coefficient of the highest power. Likewise, a generator bit pattern such as $1101$ corresponds to

$$G(x) = x^3 + x^2 + 1$$

The degree of $G(x)$ is $r$, so the CRC field has exactly $r$ bits.2 To form the transmitted codeword, the sender computes a remainder $R(x)$ such that

$$T(x) = x^r D(x) + R(x)$$

is exactly divisible by $G(x)$ over $GF(2)$.2 Since arithmetic is modulo $2$, subtraction is identical to addition:

$$1 - 1 = 0,\quad 1 + 1 = 0$$

which is why modulo-2 long division uses XOR rather than ordinary subtraction.2

A compact way to express CRC encoding is

$$R(x) = \left(x^r D(x)\right) \bmod G(x)$$

and then

$$T(x) = x^r D(x) + R(x)$$

At the receiver, the test is simply

$$T'(x) \bmod G(x)$$

If the remainder is nonzero, an error is detected.2

Key technical ideas in this section include polynomial code, GF(2), remainder, and degree.2

Footnotes

1. Cyclic redundancy check - Wikipedia - Overview of CRC theory, $GF(2)$ arithmetic, burst-error detection, and generator selection. ↩ ↩² ↩³

2. Lesson 5 - The Data Link Layer - Explains CRC encoding and decoding in the Data Link Layer using polynomial division. ↩ ↩² ↩³ ↩⁴

3. Lecture 3: Framing and Error Detection - Presents CRC goals, modulo-2 division, and the burst-error guarantee for degree-$r$ generators. ↩ ↩² ↩³ ↩⁴

4. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks - Discusses polynomial selection, Hamming distance, hardware taps, and detection strength for given frame lengths. ↩ ↩²

Worked Example: Binary Modulo-2 Division

Consider the dataword $D = 100100$ and generator $G = 1101$, which represents $x^3 + x^2 + 1$. Since the degree is $3$, append $3$ zeros:

$$100100000$$

Now divide $100100000$ by $1101$ using XOR-based long division. The remainder is $001$. Therefore, the transmitted codeword is

$$T = 100100001$$

because the sender replaces the appended zeros with the remainder.

To verify at the receiver, divide $100100001$ by $1101$ again. The remainder is $000$, so the frame is accepted as error-free under the CRC test.

A compact summary is shown below.

This example illustrates modulo-2 division, codeword, syndrome, and FCS.2

Footnotes

1. Cyclic Redundancy Check and Modulo-2 Division - GeeksforGeeks - Provides a worked binary division example with dataword $100100$ and generator $1101$. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Lesson 5 - The Data Link Layer - Explains CRC encoding and decoding in the Data Link Layer using polynomial division. ↩

Hardware Implementation of CRC

CRC is especially attractive because the same polynomial logic maps naturally onto linear feedback shift register (LFSR) hardware.2 In a typical implementation, incoming bits are shifted through a register, and XOR feedback taps correspond to the nonzero coefficients of the generator polynomial. Each clock cycle updates the register state, so the final register contents after the last data bit represent the CRC remainder.2

This makes CRC computation suitable for line-rate implementation in network interface hardware and storage controllers.2 Historically, many practical polynomials were chosen partly because they required relatively few feedback taps, making early hardware simpler. Modern systems may also provide instruction-level acceleration for some standardized CRCs.

In conceptual terms, the encoder and checker are almost identical circuits: one computes the remainder before transmission, while the other verifies that the received codeword produces the expected zero remainder or known residue, depending on the implementation convention.2

Footnotes

1. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks - Discusses polynomial selection, Hamming distance, hardware taps, and detection strength for given frame lengths. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. What Is a Cyclic Redundancy Check? | Everpure - Summarizes practical CRC operation and notes efficiency in hardware implementations. ↩ ↩² ↩³ ↩⁴

3. Cyclic redundancy check - Wikipedia - Overview of CRC theory, $GF(2)$ arithmetic, burst-error detection, and generator selection. ↩

Error Detection Capability and the Role of the Generator Polynomial

The quality of CRC depends heavily on the choice of generator polynomial.2 All CRC polynomials detect all single-bit errors, but stronger guarantees for double-bit, odd-bit, and burst errors depend on algebraic properties of $G(x)$.2

Several widely cited design rules are important in link-layer CRC selection:3

1. If $G(x)$ has at least two nonzero terms, all single-bit errors are detected.
2. If $G(x)$ does not divide $x^k + 1$ for relevant frame lengths, many double-bit errors are also detected.2
3. If $(x + 1)$ is a factor of $G(x)$, then all error patterns with an odd number of flipped bits are detected.
4. If the generator has degree $r$, then all burst errors of length $\leq r$ are detected, and for longer bursts the undetected fraction is approximately $2^{-r}$, so the detected fraction is approximately $1 - 2^{-r}$.2

This burst-error property is especially important in the Data Link Layer because real channels often exhibit correlated disturbances rather than isolated random bit flips. For example, a 32-bit CRC can detect every burst error up to length $32$ bits, which is why CRC-32 is widely used in LAN technologies such as Ethernet.2

The choice of polynomial also affects Hamming distance over a given maximum frame length, which in turn determines guaranteed detection of certain multi-bit error patterns. Research by Koopman and others has shown that some newer polynomials outperform older legacy choices for specific packet sizes, meaning the “best” generator depends on both degree and protected message length.2

Footnotes

1. Cyclic redundancy check - Wikipedia - Overview of CRC theory, $GF(2)$ arithmetic, burst-error detection, and generator selection. ↩ ↩² ↩³ ↩⁴

2. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks - Discusses polynomial selection, Hamming distance, hardware taps, and detection strength for given frame lengths. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Lecture 3: Framing and Error Detection - Presents CRC goals, modulo-2 division, and the burst-error guarantee for degree-$r$ generators. ↩ ↩² ↩³ ↩⁴

4. Data Link Layer PDF - Lists common CRC polynomials and notes properties such as odd-bit and burst-error detection. ↩ ↩² ↩³

5. Double Burst Error Detection Capability of Ethernet CRC - IEEE 802 - Notes the Ethernet CRC-32 polynomial and its guaranteed burst-detection capability up to $32$ bits. ↩

6. What Is a Cyclic Redundancy Check? | Everpure - Summarizes practical CRC operation and notes efficiency in hardware implementations. ↩

Standard CRC Polynomials in Networking Context

Several generator polynomials appear frequently in communication systems.2 Examples include CRC-16, CRC-CCITT, and CRC-32. Their names typically refer to the degree of the polynomial, which equals the number of CRC bits appended to the frame.

The practical lesson is that a larger CRC degree generally improves random error detection probability, but the exact protection depends on polynomial structure and frame length, not only on the number of bits in the checksum.2

Footnotes

1. Data Link Layer PDF - Lists common CRC polynomials and notes properties such as odd-bit and burst-error detection. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Untitled Document - Gives standard networking CRC polynomials such as CRC-16, CRC-CCITT, and CRC-32. ↩ ↩²

3. Double Burst Error Detection Capability of Ethernet CRC - IEEE 802 - Notes the Ethernet CRC-32 polynomial and its guaranteed burst-detection capability up to $32$ bits. ↩

4. Cyclic redundancy check - Wikipedia - Overview of CRC theory, $GF(2)$ arithmetic, burst-error detection, and generator selection. ↩

5. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks - Discusses polynomial selection, Hamming distance, hardware taps, and detection strength for given frame lengths. ↩

Exam-Oriented Problem-Solving Strategy

When asked to compute a CRC by hand in a Network Theory course, use a disciplined procedure.2

1. Convert the generator bits into its polynomial form only if conceptual explanation is required.
2. Let the generator length be $m$; then append $m-1$ zeros to the dataword.
3. Perform XOR long division from left to right, only when the current leading bit is $1$.
4. The final $m-1$ bits are the CRC checksum.
5. Append that checksum to the original dataword, not to the padded one.
6. To verify, divide the full transmitted codeword by the same generator; the remainder should be all zeros.2

A common source of mistakes is using decimal subtraction, forgetting to append the correct number of zeros, or appending the remainder incorrectly.

Footnotes

1. Lesson 5 - The Data Link Layer - Explains CRC encoding and decoding in the Data Link Layer using polynomial division. ↩ ↩² ↩³

2. Cyclic Redundancy Check and Modulo-2 Division - GeeksforGeeks - Provides a worked binary division example with dataword $100100$ and generator $1101$. ↩ ↩² ↩³ ↩⁴ ↩⁵