METHOD OF CORRECTING MESSAGE ERRORS USING CYCLIC REDUNDANCY CHECKS

• US 20080040644A1
• Filed: 08/09/2007
• Published: 02/14/2008
• Est. Priority Date: 08/11/2006
• Status: Active Grant

• Current Assignee: Aclara Technologies LLC (Hubbell, Inc.)
• Original Assignee: Aclara Power-Line Systems Incorporated (Hubbell, Inc.)
• Inventors: Spencer, Quentin
• Granted Patent: US 7,831,884 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms

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.

Claims

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. In a digital communications network, a method of correcting errors in a message transmitted through the network to improve reliability of communications within the network, comprising:

directing the message to a message passing decoder;

processing the message by the message processing decoder to detect an error in the message and to correct the error; and

,

the message passing decoder employing both a linear block code and a multiple bit cyclic redundancy check for error detection and correction, the message passing decoder combining the linear block code and a cyclic redundancy check together to form a parity check matrix with which the message is processed whereby more than one error in the message processed by the message passing decoder, if more than one error is present, is detected and corrected.

6. The method of claim 5 further including extending the parity-check matrix using a sparsification algorithm.

7. The method of claim 5 in which the linear block code comprises one of a Hamming code, a BCH code, a Reed-Muller code, or a Reed-Solomon code.

8. The method of claim 5 in which the cyclic redundancy check is a 16 or 32 bit cyclic redundancy check.

9. In an electrical distribution system having a two-way automatic communications system for sending outbound messages through the system to a customer'"'"'s facility and for receiving an inbound message from the facility in response thereto, a method of correcting errors in an inbound message to improve reliability of communications within the system, comprising:

directing the inbound message to a message passing decoder;

the message processing decoder processing the message to detect an error in the message and to correct the error; and

,

the message passing decoder employing both a linear block code and a multiple bit cyclic redundancy check for error detection and correction, the message passing decoder combining the linear block code and a cyclic redundancy check together to form a parity check matrix with which the message is processed whereby more than one error in the inbound message processed by the message passing decoder, if more than one error is present, is detected and corrected.

10. The method of claim 9 in which the electrical distribution system is a multi-phase system in which messages are concurrently transmitted on more than one phase, and the method includes the message passing decoder performing a parity check on each inbound message on each phase to detect and correct multiple bit errors in each message, if more than one bit error is present.

11. The method of claim 10 in which the linear block code comprises one of a Hamming code, a BCH code, a Reed-Muller code, or a Reed-Solomon code.

12. The method of claim 10 in which the cyclic redundancy check is a sixteen bit cyclic redundancy check.

13. In a multi-phase electrical distribution system having a two-way automatic communications systems for sending outbound messages through the system to a customer'"'"'s facility and for receiving an inbound message from the facility in response thereto, outbound and inbound messages being concurrently sent and received on different phases of the distribution system, a method of correcting errors in an inbound message to improve reliability of communications within the system, comprising:

directing each inbound message to a message passing decoder;

processing the message by the message processing decoder to detect an error in the message and to correct the error; and

,

the message passing decoder employing both a linear block code and a multiple bit cyclic redundancy check for error detection and correction, the message passing decoder combining the linear block code and a cyclic redundancy check together to form a parity check matrix with which the message is processed whereby more than one error in the inbound message processed by the message passing decoder, if more than one error is present, is detected and corrected.

14. The method of claim 13 in which the linear block code is one of a Hamming code, a BCH code, a Reed-Muller code, or a Reed-Solomon code.

15. The method of claim 13 in which the cyclic redundancy check is a 16 or 32 bit cyclic redundancy check.