Cyclic Redundancy Check (CRC)

Lec-30: Cyclic Redundancy Check(CRC) for Error Detection and Correction

Cyclic Redundancy Check (CRC)

Overview and Capabilities

CRC is an extremely powerful and widely used method for error detection in real-world applications. It is highly reliable because it can detect:

• All single-bit errors, provided the generator polynomial has at least two non-zero terms.
• All double-bit errors, provided the generator polynomial does not divide x^k + 1 for any k less than the frame length.
• All odd numbers of bit errors, if the generator polynomial contains the factor (x + 1).
• All burst errors of length ≤ r, where r is the degree of the generator polynomial.
• Most burst errors of length r + 1 are detected.

In short CRC detects:

1. All single-bit errors.
2. All double-bit errors.
3. All odd number of errors (if G(x) has factor (x+1)).
4. All burst errors of length ≤ r.

Why CRC with (x+1) is similar to parity check ?

• CRC does much more than parity check.
• If the generator polynomial G(x) contains the factor (x+1), CRC implicitly performs a parity check in addition to its other checks.
• Any odd number of bit errors changes the parity of the received message.
• Therefore, such an error pattern cannot be divisible by G(x), and CRC always detects it.
• Hence, CRC with (x+1) factor ⇒ Detects all odd number of bit errors.

2. Key Terminology To successfully detect errors, pure data cannot be sent alone; it must be accompanied by redundant bits.

• $m$: Number of bits in the original message.
• $r$: Number of redundant bits (CRC bits) to be generated and appended.
• Total Transmitted Data: $(m + r)$ bits.

Demonstration: The CRC Process

Step 1: Finding the Divisor

The divisor is often provided as a polynomial. You must extract its coefficients to convert it into a binary string.

Visual Example of Polynomial to Binary Conversion: If the given polynomial has a maximum degree of 4 (e.g., $x^4 + x^3 + 1$):

• $x^4$ is present $\rightarrow$ 1
• $x^3$ is present $\rightarrow$ 1
• $x^2$ is missing $\rightarrow$ 0
• $x^1$ is missing $\rightarrow$ 0
• $x^0$ (or 1) is present $\rightarrow$ 1

Divisor = 1 1 0 0 1.

Step 2: Appending Zeros to the Dividend (Message)

Before dividing, you must append zeros to the end of your original message.

For Example Dividend is 1 0 1 0 1 0 1 0 1 0

• Rule A (Polynomial Given $x^4 + x^3 + 1$): Append zeros equal to the highest degree of the polynomial. For example, if the highest degree is 4, append four 0s (0000).

• Rule B (Binary Divisor Given): If the divisor is given directly as a binary string, count the number of bits and subtract 1. For example, if the divisor is 5 bits long (11001), append $5 - 1 = 4$ zeros, append four 0s (0000). ⭐

Step 3: The Division Process (Sender Side)

The sender performs Binary Division using the XOR operation to find the remainder. The quotient is ignored; only the remainder is useful.

XOR Logic Rule (Same values = 0, Different values = 1):

• 0 XOR 0 = 0
• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1

Division Strategy:

• Always start the division from a leading ‘1’ to save time and reduce the length of the calculation.
• Perform the XOR operation down the line, carrying down bits from the dividend as needed so your working string matches the length of the divisor.
• Once the division finishes, extract the remainder. If the remainder has more bits than the appended zeros, pick only the bits starting from the Least Significant Bit (LSB) (e.g., the last 4 values like 0010).

Example:

• Given:

$$\text{Dividend} = 1010101010$$ $$\text{Divisor} = 11001$$

In CRC, binary division is done using XOR instead of subtraction. ⭐

Perform modulo-2 division:

        111010
       ___________
11001 ) 1010101010
        11001
        -----
         11011
         11001
         -----
            1010
            ↓ bring down 1 → 10101
            11001
            -----
             1100
             ↓ bring down 0 → 11000
             11001
             -----
                 1
                 ↓ bring down 1 → 11
                 ↓ bring down 0 → 110

After completing the division, the remainder & quotient is:

• Remainder (CRC): $\boxed{0011}$
• also, Quotient: $\boxed{111010}$

Since the divisor has degree (4) (length (=5)), the remainder always has (4) bits. ⭐

Step 4: Transmitting the Data

Replace the appended zeros with the calculated remainder (CRC bits) to create the valid code word.

• Visual: [ 10 Message Bits ] + [ 4 Remainder Bits (0010) ] = [ 14-Bit Code Word Transmitted ].

Step 5: Error Checking (Receiver Side)

The receiver takes the incoming 14-bit code word and divides it by the exact same divisor (11001) using the exact same XOR division method.

• If Remainder == 00000: No error occurred during transmission; all bits arrived exactly as sent.
• If Remainder != 00000 (contains any 1s): An error is detected, meaning at least one bit flipped (e.g., a 0 became a 1) during transmission.

Efficiency Calculation

Efficiency measures how much of the transmitted data is actual useful information versus redundant checking data.

Formula: $\text{Efficiency} = \left( \frac{\text{Message Bits } (m)}{\text{Total Transmitted Bits } (m + r)} \right) \times 100$

Example based on the demonstration: If 10 bits of data are sent with 4 redundant bits, the total sent is 14 bits. Efficiency = $(10 / 14) \times 100$. This represents the channel utilisation for sending the message.