Method of correcting message errors using cycle redundancy checks

Abstract

A method of correcting errors in a message transmitted over a digital communication channel, where the message was encoded using a CRC for purposes of error detection. A parity-check matrix representation of the CRC is computed for any fixed-length message, and that parity-check matrix is combined with the parity-check matrix for any error correcting code that used in conjunction with the CRC. The combined parity-check matrix is extended using sparsification algorithms to allow it to work well under a message passing decoder (MPD). Received messages are decoded using the message passing decoder, making it possible to correct more errors than if the CRC were decoded in a conventional manner.

1 . A method of using cyclic redundancy checks (CRCs) in messages transmitted over a digital communications link to correct errors that may have occurred during transmission in order to improve overall reliability of the communication link, the method comprising:
 computing a parity-check representation of a CRC;   extending the parity-check matrix using a sparsification algorithm; and,   directing the received message to a message passing decoder, the message processing decoder processing the message using the extended parity-check matrix of the CRC to correct the errors in the message.   
   
   
       2 . The method of  claim 1  in which the CRC matrix is combined with a parity-check matrix from an error correcting code to create a single, combined parity-check matrix. 
   
   
       3 . The method of  claim 2  in which the error correcting code is a general linear block code, including, but not limited to, a Hamming code, a BCH code, a Reed-Muller code, or a Reed-Solomon code. 
   
   
       4 . The method of  claim 2  further including removing all cycles of length  4  from the combined parity-check matrix representing the CRC and error correcting code. 
   
   
       5 - 15 . (canceled)