Cyclic Codes and Cyclic Redundancy Check (CRC)

1. Cyclic Codes

A cyclic code is a special type of linear block code with one additional property:

If a codeword is cyclically shifted, the result is also another valid codeword.

For example:

Codeword:       1011000
Cyclic shift:   0110001

The last bit is moved to the beginning during the cyclic shift.

Table 5.3 shows an example of a CRC code. We can see both the linear and cyclic properties of this code.

---

2. Cyclic Redundancy Check (CRC)

CRC is a subset of cyclic codes used for error detection in networks such as LANs and WANs.

In CRC:

• The dataword has k bits.
• The codeword has n bits.
• n − k redundant bits are added.
• A predefined generator/divisor is used.

For example:

k = 4
n = 7

CRC bits = n − k = 3

---

3. CRC Encoder

The encoder works as follows:

Dataword
   ↓
Append n − k zeros
   ↓
Modulo-2 division
   ↓
Remainder
   ↓
Append remainder to dataword
   ↓
Codeword

Example

Suppose:

Dataword = 1001
Generator = 1011

Since the generator has 4 bits:

Number of CRC bits = 4 − 1 = 3

First, append three zeros:

1001 → 1001000

The augmented dataword is divided by 1011 using modulo-2 division.

The remainder is:

110

Therefore:

Dataword = 1001
Remainder = 110

Codeword = 1001110

---

4. Modulo-2 Division

CRC uses modulo-2 binary division.

The important rule is:

Addition and subtraction are both performed using XOR.

XOR operation:

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

During each step:

• If the leftmost bit is 1, XOR with the divisor.
• If the leftmost bit is 0, use an all-zero divisor.

The final remainder forms the CRC check bits.

---

5. CRC Decoder

The receiver performs the same division process.

Received codeword
        ↓
Divide by the same generator
        ↓
Remainder
        ↓
Syndrome

The remainder obtained at the receiver is called the syndrome.

If syndrome = 000

Syndrome = 000
       ↓
Dataword accepted

The receiver interprets this as no error detected.

If syndrome ≠ 000

Syndrome ≠ 000
       ↓
Error detected
       ↓
Codeword discarded

6. CRC Example

---

7. Generator / Divisor

The generator is a predefined divisor used by both the sender and receiver.

The  two requirements for a generator:

1. It must have at least two bits.
2. Its leftmost and rightmost bits must both be 1.

For example:

1011

satisfies these requirements.

---

8. Standard CRC Generators

Some of the standard divisors used in networking are shown in Table 5.4.

Name	Binary	Application
CRC-8	100000111	ATM header
CRC-10	11000110101	ATM AAL
CRC-16	10001000000100001	HDLC
CRC-32	100000100110000010001110110110111	LANs

The number in the CRC name represents the degree of the polynomial. Therefore, CRC-8 has 9 bits and CRC-32 has 33 bits.

---

9. CRC Error-Detection Performance

Single-bit errors

All qualified generators can detect any single-bit error.

Odd-number errors

Qualified generators can detect any odd number of errors if the generator can be evenly divided by 11 using modulo-2 arithmetic.

Burst errors

If:

• L = length of burst error
• r = length of the CRC remainder

then:

• If L ≤ r → all burst errors are detected.
• If L = r + 1 → detection probability is 1 − (0.5)^(r−1).
• If L > r + 1 → detection probability is 1 − (0.5)^r.

---

10. Advantages of Cyclic Codes

Cyclic codes:

• Can be implemented easily in hardware and software.
• Are particularly fast when implemented in hardware.
• Are therefore suitable for use in many networks.

The  division operation can be implemented using a shift register in hardware.

---

CRC — Quick Summary

             CRC

Sender                              Receiver
  │                                    │
Dataword                           Codeword
  │                                    │
Append zeros                       Divide by generator
  │                                    │
Modulo-2 division                  Syndrome
  │                              /          \
Remainder                       000        Non-zero
  │                              │             │
Append remainder               Accept        Discard
  │
Codeword

Key points to remember

Cyclic code: Cyclic shift of a valid codeword produces another valid codeword.

CRC: Practical error-detection technique based on cyclic codes.

Modulo-2 division: Uses XOR for addition and subtraction.

Encoder: Append zeros → divide → obtain remainder → append remainder.

Decoder: Divide received codeword → obtain syndrome.

Syndrome = 0: Accept.

Syndrome ≠ 0: Discard.

Main advantage: Efficient detection of transmission errors, particularly burst errors.

Example Problem: Computing CRC Code

Problem

Given the dataword = 1001 and the divisor (generator) = 1011, compute the CRC codeword using modulo-2 division.

---

Solution

Step 1: Identify the number of CRC bits

The divisor has 4 bits.

Therefore:

$$\text{Number of CRC bits}=4-1=3$$

Append three zeros to the dataword:

Dataword        = 1001
After adding 0s = 1001000

---

Step 2: Perform modulo-2 division

Divide 1001000 by 1011.

             1011
          __________
1011 ) 1001000
       1011
       ----
       0010
         100
               ↓ bring down 0
         1000
         1011
       ----
         00110

The final 3-bit remainder is:

Remainder = 110

The division is performed using XOR. When the leftmost bit is 0, an all-zero divisor is used, as described in the textbook.

---

Step 3: Form the CRC codeword

Append the remainder to the original dataword:

Dataword  = 1001
CRC       = 110
----------------
Codeword  = 1001110

Answer

CRC codeword=1001110​