Research in Mathematics and Computer Science: Calculation of the Probability of Undetected Error for Certain Error Detection Codes. Phase 1
Final technical rept. 1 Aug 1988-31 Jan 1989
QUALCOMM INC SAN DIEGO CA
Pagination or Media Count:
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.
- Computer Programming and Software