Past exam question: 2076 Ashwin, Q5
Open in the Padhaiko appExplain with example how CRC-5 work to detect 3 burst errors.
Solution
Theoretical Foundation of CRC Burst Error Detection: A burst error of length is a contiguous block of received bits where the first bit and the last bit are corrupted, and zero or more intermediate bits may also be corrupted. Mathematically, the received word is , where is the error polynomial:
where:
- represents the position of the burst error,
- is a polynomial of degree with (the first and last bits are ).
CRC Error Detection Theorem for Burst Errors: If a CRC generator polynomial has degree :
- All burst errors of length are detected with 100% certainty.
- Reason: For to be undetected, must be divisible by . Since degree of is , and has a non-zero constant term (, not divisible into ), cannot divide . Therefore, the remainder cannot be zero.
For CRC-5, the generator degree is . Since , all 3-bit burst errors are guaranteed to be detected.
Concrete Example of Detecting a 3-Bit Burst Error: Let generator (). Let data .
- Transmitter Encoding:
- Append 5 zeros: .
- Modulo-2 division of by yields quotient and remainder .
- Transmitted codeword:
- Injection of a 3-Bit Burst Error: Suppose channel noise creates a 3-bit burst error in positions 6, 7, and 8 from the left:
Received corrupted word:
Receiver Verification: The receiver performs modulo-2 division of by :
101001
100101 ) 10110100000
100101
------
010000
000000
------
100000
100101
------
001010
000000
------
010100
000000
------
101000
100101
------
01101 --> Remainder != 00000
Because the syndrome remainder is non-zero (), the receiver reliably detects the 3-bit burst error and rejects the corrupted frame.
CRC-5 has degree . Since any burst error of length produces an error polynomial with , the generator cannot divide . Consequently, any 3-bit burst error () produces a non-zero syndrome remainder at the receiver, ensuring 100% detection.