01-02-2013, 11:24 AM
Cyclic redundancy check (CRC) codes
Cyclic redundancy.pdf (Size: 281.07 KB / Downloads: 924)
Overview of Cyclic Redundancy Check Codes
Cyclic redundancy check (CRC) codes
– Invented by W. Wesley Peterson, and published in 1961
– A type of linear block codes
• Generally, not cyclic, but derived from cyclic codes
– A systematic error detecting code
• a group of error control bits (which is the remainder of a
polynomial division of a message polynomial by a generator
polynomial) is appended to the end of the message block
• with considerable burst-error detection capability
– The receiver generally has the ability to send
retransmission requests back to the data source through a
feedback channel.
Error Detection Capability
Binary (N, k) CRC codes (with N-k appended bits)
can detect the following error patterns:
1. All error bursts of length N-k or less
2. A fraction of error bursts of length equal to N-k+1; the
fraction equals (1-2-(N-k-1))
3. A fraction of error bursts of length greater than N-k+1;
the fraction equals (1-2-(N-k))
4. All combinations of dmin- 1 or fewer errors, where dmin is
the minimum distance
5. All error patterns with an odd number of errors if the
generator polynomial g(X) has an even number of
nonzero coefficients