Research in Mathematics and Computer Science: Calculation of the Probability of Undetected Error for Certain Error Detection Codes. Phase 1
Abstract
Cyclic redundancy check codes (or CRC codes) have become the standard means for insuring the integrity of messages that have been transmitted over a noisy communications channel. The sole purpose of these codes is to detect transmission errors (in contrast to error correction codes (or ECC codes) which attempt to correct transmissions in errors). Sometimes both CRC and ECC codes are utilized and in that case the burden is on the CRC code to detect errors that were not correctly decoded by the ECC code. Unfortunately, even the very best CRC codes cannot detect all transmission errors. The probability of CRC failure is called the probability of undetected error. The thrust of this study was concerned with finding an efficient method of calculating this probability of undetected error and then to use this method to find good (or even the best) CRC codes. A new algorithm was implemented to find good choices for the generator polynomial of CRC codes, that is, generator polynomials for which the probability of undetected error was less than a given bound for all shortened block lengths and for all values of the binary symmetric channel error rate. Results are given for generator polynomials corresponding to 8, 16, 24 and 32 parity bits. All possible generator polynomial corresponding to 8 and 16 parity bits and some of the generator polynomials corresponding to 24 and 32 parity bits were tested.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 31, 1989
- Accession Number
- ADA210302
Entities
People
- Andrew J. Viterbi
- Jack K. Wolf
- Lyle J. Fredrickson
Organizations
- Qualcomm