Past exam question: 2075 Chaitra, Q6
Open in the Padhaiko appDemonstrate how CRC-4 works to trace two burst errors.
Solution
Mathematical Formulation of CRC-4: In CRC-4:
- The generator polynomial has degree .
- Standard CRC-4 polynomial:
- Let the dataword be ( bits).
- Append zeros: .
- Modulo-2 division of by gives remainder .
- Transmitted codeword is .
Transmitter Encoding Modulo-2 Division:
110111
10011 ) 1100100000
10011
-----
10100
10011
-----
01110
00000
-----
11100
10011
-----
11110
10011
-----
11010
10011
-----
1001 --> Remainder R = 1001
- Remainder .
- Transmitted Codeword:
Tracing Two Distinct Burst Errors at the Receiver: A burst error of length is a sequence of bits starting and ending with bit flips. By CRC mathematical properties, any burst error of length ( for CRC-4) produces an error polynomial with . Since cannot divide , the remainder is guaranteed to be non-zero.
- Trace 1: A 2-Bit Burst Error (): Suppose noise flips 2 adjacent bits at positions 4 and 5 from the left (
0110):
Received corrupted word:
Dividing by : Modulo-2 division produces:
Because the remainder is non-zero, the receiver successfully detects and flags Burst Error 1.
- Trace 2: A 3-Bit Burst Error (): Suppose noise flips bits across a 3-bit span (bits 8 and 10 corrupted):
Received corrupted word:
Dividing by : Modulo-2 division yields:
Because the remainder is non-zero, the receiver successfully detects and flags Burst Error 2.
CRC-4 using () generates a 4-bit check code.
- Because the generator degree is , all burst errors of length are guaranteed to produce a non-zero syndrome remainder.
- In both demonstrated traces—a 2-bit burst () yielding remainder
1010, and a 3-bit burst () yielding remainder0101—the receiver detects the non-zero remainder and rejects the corrupted frame.