Past exam question: 2076 Chaitra, Q5
Open in the Padhaiko appDemonstrate how CRC-5 works to detect errors in data communication.
Solution
Mathematical Definition of CRC-5: In CRC-5 (Cyclic Redundancy Check with degree 5):
- The generator polynomial has degree , consisting of 6 bits.
- A standard CRC-5 polynomial (e.g., ITU-T / USB) is:
- Let source dataword ( bits).
- Transmitter appends zeros to :
- Modulo-2 division of by yields quotient and a 5-bit remainder .
- Transmitted codeword is .
Transmitter Modulo-2 Division: Divide by :
1100100 (Quotient)
----------
100101 ) 110101100000
100101
------
100001
100101
------
001000
000000
------
010000
000000
------
100000
100101
------
001010
000000
------
010100
000000
------
10100 --> Remainder R = 10100
- Remainder (5 bits).
- Transmitted Codeword:
Receiver Verification and Error Detection:
- Error-Free Case: The receiver divides received word by . Modulo-2 division produces Quotient and Remainder . Since the remainder is all zeros, the frame is accepted as valid and error-free.
- Corrupted Case (Single or Burst Error): Suppose channel noise flips the 4th bit from the right:
The receiver divides by :
Because the remainder is non-zero, the receiver immediately detects the error and drops the corrupted frame, triggering an automatic repeat request (ARQ). CRC-5 is mathematically guaranteed to detect all single-bit errors, all double-bit errors, all odd numbers of errors (if is a factor), and any burst error of length bits.
CRC-5 appends a 5-bit remainder computed by dividing the 5-zero-padded dataword by a degree-5 generator polynomial (). The receiver divides the received word by ; a remainder of confirms valid data, whereas any non-zero remainder detects errors (including all burst errors of length ).