Follow us on Twitter
twitter icon@FreshPatents

Browse patents:

Method of correcting message errors using cycle redundancy checks

Title: 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. ...

USPTO Applicaton #: #20090259917
Inventors: Quentin Spencer

The Patent Description & Claims data below is from USPTO Patent Application 20090259917, Method of correcting message errors using cycle redundancy checks.


- Top of Page

The present application is a divisional of U.S. application Ser. No. 11/836,381 filed on Aug. 9, 2007, which claims priority from U.S. Provisional Patent Application Ser. No. 60/837,349 filed on Aug. 11, 2006, all of which is herein incorporated by reference.


Not Applicable.


- Top of Page


This invention relates to a method of error detection and correction in messages sent over a digital communications channel. Specifically, the method uses cyclic redundancy checks (CRCs), which previously have only been used for error detection, to provide a certain amount of correction in messages where errors are detected. One practical application of the method described herein relates to error detection in messages sent over a power distribution system employing a TWACS® communication system to send and receive messages over electrical power lines to acquire information on the status of power users, including current power usage. In particular, the method of error detection is described for inbound TWACS communications; i.e., messages sent from a user's location back to a utility in response to a message (an outbound communication) sent from the utility to the user.

In recent years, there has been substantial progress in the area of error correction codes. Most of the gains have been achieved using iterative coding techniques and new classes of codes designed to perform well with such coding methods. These new classes of codes include, for example, Turbo-codes and Low-Density Parity-Check (LDPC) codes. While these codes are being incorporated into standards for next-generation communication systems, there remain many “legacy” communication systems and protocols that use more traditional methods of error detection and correction, and are likely to be used well into the foreseeable future. These systems and protocols would benefit from the use of iterative decoding techniques. In particular, message passing decoders (MPDs), which are also referred to as belief-propagation decoders, used with LDPC codes could theoretically be used with any linear block code. In practice, an MPD performs best when the parity-check matrix block code is sparse (i.e., there are very few 1s compared to the number of 0s). Thus the need for a low-density parity-check matrix. However, most commonly used block codes, such as Hamming, BCH, and Reed-Solomon codes, do not have sparse parity check matrices. Because of this, they have not usually been thought of as candidates for using an MPD. There are, however, methods for extending dense parity-check matrices so they have a sparse structure better suited for message passing decoding. Using these sparsification methods, it has been shown that improved performance can be achieved with these older classes of codes; although this comes at the cost of computational complexity, and the performance does not surpass that of good LDPC codes.

CRCs are widely used in digital communication systems for error detection. Typically, a CRC of a fixed length (most commonly 16 or 32 bits, although other lengths are also used) is computed and appended to a message to be transmitted. The receiver of the transmitted message recomputes the CRC to determine if an error has occurred in transmission. Depending upon the application, a detected error often results in a request for a retransmission of the message. In many applications, CRC based error detection is also combined with some form of error correction. The choice of an error correcting code, the CRC used, and the protocol for handling detected errors, are all design decisions that are determined for each application, and depend upon such factors as the expected probability of an error, tolerance for errors in a received message, and the costs of bandwidth and latency in the system.

In some communication systems, errors are relatively rare, and the bandwidth is sufficiently high that retransmission of a message does not have a significant impact (the Ethernet protocol is an example of this). Conversely, some communications are quite noisy and error prone, and retransmissions are commonplace. Reducing the frequency of retransmissions can save valuable bandwidth, particularly in systems whose underlying data rates are low. An example of this is a TWACS powerline communications system, which will be used hereafter as an example of how the method of the invention functions. In a TWACS outbound communications, each message is encoded using a Hamming code and a 16 bit CRC. Since a Hamming code is only able to correct one error, the CRC is used to detect whether more than one error has occurred, so a retransmission can be requested. In practice, however, it is theoretically possible for some errors to go undetected.

In order to improve performance, an LPDC code has been designed for TWACS (see cross referenced U.S. patent application Ser. No. 11/232,072) which should help to overcome some of these shortcomings. However, improving the error detection and correction capability of the Hamming/CRC error control scheme would also benefit the large, currently installed base of TWACS transponders. The scope of the present invention is a method of using CRC bits to correct errors, thereby improving overall error rates. As described hereinafter, the method can be used with a message with only a CRC, or with messages that combine a CRC with a block error correcting code.



- Top of Page


The present invention is directed to a method of correcting errors in a message of a fixed length that includes CRC parity check bits for error detection. The method includes generating a parity check matrix representation of the CRC which can be applied to any type of CRC regardless of its size or generator polynomial. If a message is also encoded with a block error correcting code such as a Hamming, BCH, Reed-Muller, or Reed-Solomon code, the parity-check matrix is combined with the parity check matrix for the error correcting code to comprise a single parity-check matrix. Because the resulting matrix is not expected to be a sparse matrix, sparsification techniques are utilized to improve its performance for message passing decoding. The result is a reduction in the packet error rate of the communications channel.

Other objects and features will be in part apparent and in part pointed out hereinafter.


The objects of the invention are achieved as set forth in the illustrative embodiments shown in the drawings, which form a part of the specification.

FIG. 1 is a representation of a linear feedback shift register;

FIG. 2 is a simplified representation of an electrical distribution network including a two-way communications capability; and,

FIG. 3 is a representation of an outbound or inbound communications signal sent over the network.

Corresponding reference characters indicate corresponding parts throughout the several views of the drawings.


The following detailed description illustrates the invention by way of example and not by way of limitation. This description will clearly enable one skilled in the art to make and use the invention, and describes several embodiments, adaptations, variations, alternatives and uses of the invention, including what I presently believe is the best mode of carrying out the invention. As various changes could be made in the above constructions without departing from the scope of the invention, it is intended that all matter contained in the above description or shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

Traditionally, a CRC has been implemented using a linear feedback shift register (LFSR) such as the 16 bit register R shown in FIG. 1. This is because of the shift register\'s very low cost when implemented in hardware. However, the serial nature of the register is not sufficiently fast for some applications. As is known in the art, alternate designs have been proposed that compute a CRC for an entire block in parallel. The first step in using the CRC to create errors is to create a parity check matrix representation of the CRC using methods similar to those for parallelization.

One way of viewing parallelization algorithms is to consider the CRC as a linear filter which, because it has feedback, functions similarly to an infinite impulse response (IIR) filter. As with any linear IIR filter, its impulse response can be calculated for finite length responses. For example, a CRC-16 is to be computed for messages of a 32 bit length. The message comprises mostly 0s, having 1 bits only at locations 2, 17, 30, and 31, so to appear as: 01000000000000001000000000000110

← Previous       Next →
Advertise on - Rates & Info

You can also Monitor Keywords and Search for tracking patents relating to this Method of correcting message errors using cycle redundancy checks patent application.


Keyword Monitor How KEYWORD MONITOR works... a FREE service from FreshPatents
1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored.
3. Each week you receive an email with patent applications related to your keywords.  
Start now! - Receive info on patent apps like Method of correcting message errors using cycle redundancy checks or other areas of interest.

Previous Patent Application:
Data accessing method, controller and storage system using the same
Next Patent Application:
Structured low-density parity-check (ldpc) code
Industry Class:
Error detection/correction and fault detection/recovery
Thank you for viewing the Method of correcting message errors using cycle redundancy checks patent info.
- - -

Results in 0.19013 seconds

Other interesting categories:
Medical: Surgery Surgery(2) Surgery(3) Drug Drug(2) Prosthesis Dentistry  


Data source: patent applications published in the public domain by the United States Patent and Trademark Office (USPTO). Information published here is for research/educational purposes only. FreshPatents is not affiliated with the USPTO, assignee companies, inventors, law firms or other assignees. Patent applications, documents and images may contain trademarks of the respective companies/authors. FreshPatents is not responsible for the accuracy, validity or otherwise contents of these public document patent application filings. When possible a complete PDF is provided, however, in some cases the presented document/images is an abstract or sampling of the full patent application for display purposes. Terms/Support
Browse patents:

stats Patent Info
Application #
US 20090259917 A1
Publish Date
Document #
File Date
Other USPTO Classes
International Class

Message Passing Sparsification

Follow us on Twitter
twitter icon@FreshPatents

Error Detection/correction And Fault Detection/recovery   Pulse Or Data Error Handling   Digital Data Error Correction   Forward Correction By Block Code   Error Correcting Code With Additional Error Detection Code (e.g., Cyclic Redundancy Character, Parity)  

Browse patents:
20091015|20090259917|correcting message errors using cycle redundancy checks|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 |