Past exam question: 2078 Kartik, Q4
Open in the Padhaiko appExplain the operation of CRC-4 with example of error detection.
Solution
Principle of Cyclic Redundancy Check (CRC-4): Cyclic Redundancy Check (CRC) is a polynomial-based block error detection code. In CRC-4:
- The generator polynomial has degree . A standard CRC-4 polynomial is:
- Let the source dataword be bits long (e.g., , ).
- The transmitter appends zeros to the dataword: .
- Modulo-2 division (XOR subtraction without borrow) of this augmented data by produces an -bit remainder .
- The transmitted codeword is:
Transmitter Encoding via Modulo-2 Division: Let data and generator (). Append zeros to : . Perform modulo-2 long division:
110000 (Quotient)
----------
10011 ) 1101010000
10011
-----
10011
10011
-----
00000000
Let us trace step-by-step:
1.
2. Bring down next bit `1`
3.
4. Bring down `0`, `0`, `0`, `0` Remainder .
To demonstrate a non-zero remainder, let us use data : Augmented data: .
101110
10011 ) 1010010000
10011
-----
01111
00000
-----
11110
10011
-----
11010
10011
-----
10010
10011
-----
00010 -> Remainder R = 0010
- Remainder .
- Transmitted Codeword: .
Receiver Verification in Error-Free Case: The receiver divides the incoming bits by :
101110
10011 ) 1010010010
10011
-----
011110
10011
-----
11011
10011
-----
10001
10011
-----
00100
00000
-----
010010
10011
-----
0000 -> Remainder = 0000
Because the remainder is strictly , the receiver accepts the frame as error-free.
Error Detection Example with Corrupted Transmission: Suppose transmission noise induces a 1-bit flip at the least significant bit:
Dividing by at the receiver: Modulo-2 division yields a non-zero remainder:
Because the remainder is non-zero, the receiver immediately detects the error and discards the damaged frame, requesting retransmission (ARQ).
CRC-4 uses an order-4 polynomial generator (such as , bit string 10011).
- Transmitter: Appends 4 zeros to the dataword, divides modulo-2 by , and appends the 4-bit remainder to form codeword .
- Receiver: Divides the received word by . A remainder of zero signifies an error-free transmission, while any non-zero remainder confirms a detected bit error.