Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-05-24
2004-04-27
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S751000, C714S701000
Reexamination Certificate
active
06728920
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an error correction method for a lossy communications environment. It may readily be applied to a high traffic or high loss multipoint system. The present invention may be used in any digital communications system, including such applications as satellite communications systems, terrestrial radio systems, and cellular phone systems. The present invention is useable for Internet and Intranet broadcasting.
BACKGROUND OF THE INVENTION
Communications systems need to reliably transmit information to all users within that system. To accomplish this, data is often broken into smaller pieces called packets which can be easily managed by the communications system. Communications systems invariably suffer from corrupted bits and lost packets, resulting from a multitude of causes, including, but not limited to interference, noise, and buffer overflows.
To recover corrupted bits and lost packets, many error correcting techniques may be applied. The most common is called a Forward Error Correcting Code (FEC) which may correct single or multiple errors in a packet. An FEC works by adding error correcting bits to the transmitted packet. Unfortunately, if too many errors occur in a packet, the corrupted packet will remain corrupted or be lost, even with the use of an FEC code. Because of this, errors resulting from interference and buffer overflows are generally not correctable with an FEC code. Another disadvantage is that there is a necessary bandwidth overhead in sending the parity bits required by an FEC code.
To detect the occurrence of corrupted packets, existing systems can use an error detection algorithm. Commonly used error detection algorithms include the Cyclic Redundancy Checking (CRC) algorithm and checksum algorithm, which can detect the occurrence of multiple errors. A technique of adding parity bits can be used to detect single and odd numbers of errors.
The absence of a packet that is expected, usually resulting from strong interference or buffer overflows, can be detected by the addition of sequence information to the packet.
One method to greatly improve the probability of receiving an uncorrupted packet is to send the packet multiple times. In this case, any number of errors in a single packet, or even a lost packet, will not prohibit uncorrupted reception of the packet's information, as long as at least one packet is correctly received. Unfortunately, sending each packet R times requires R times as much bandwidth.
Another method to greatly reduce the probability of losing information is to request and retransmit a packet in the event that a packet is lost or corrupted. This method is often referred to as ARQ (automatic repeat request). To accomplish this, acknowledgments (ACKs), negative acknowledgments (NACKs), and timeout windows may be employed to identify which packets are incorrectly received or may need to be resent. These identified packets may be retransmitted as many times as necessary until the information is indicated to be successfully received. Two serious drawbacks of this method are that latency and bandwidth are increased with each retransmission. Also, the ACK and NACK messages themselves require additional bandwidth. The increased and non-deterministic latency of this protocol is not well suited to many types of traffic such as satellite communications systems. Also, the additional bandwidth required for the ACK and NACK messages make this method very poorly suited to communications systems that support broadcast of information to many or all users, as the bandwidth of the ACK and NACK messages increases with each user in the system. Broadcast of information is the transmission of identical information to multiple or all users in a communications system.
Each of these methods of packet recovery have some advantages over the others. However, the method of present invention has the advantage that information can be sent with a higher reliability, using the same amount of bandwidth, than the prior art method of repeating each packet multiple times.
The prior art methods have not been optimally effective in correcting errors in the transfer of information over some lossy mediums such as radio links, copper wires, or fiber optic cables, where the channel is randomly blocked due to interference or jamming.
SUMMARY OF THE INVENTION
The present invention relates to a method for correcting errors in the transfer of information over a lossy medium such as radio frequencies, copper wires, or fiber optic cables, where the channel is randomly blocked due to interference or jamming. However, it is not limited to lossy mediums, but may also be used in non-lossy mediums. The message is first divided into data blocks. The data blocks are then divided into data segments. The data segments of each data block are used to generate distinct combinations of data segments through a Boolean operation (such as XOR) or an arithmetic operation to form Error Correcting Segments. The Data Segments and Error Correcting Segments are transmitted. In the event that a Data Segment of the information is incorrectly received, the message can be entirely reconstructed as long as one valid subset of Data Segments is correctly received. In the case where a data block is divided into two Data Segments, three Data and Error Correcting Segments are transmitted. The retrieval of any two Data and Error Correcting Segments provides enough information to retrieve the full amount of information transmitted in the corresponding data block. In the case where a data block is divided into three data segments, seven Data and Error Correcting Segments are transmitted. The retrieval of any four good Data or Error Correcting Segments results in full retrieval of transmitted information. Furthermore, in the case where only three good Data Segment or Error Correcting Segments are received, there are only four out of the thirty five possible sets of three Data and Error Correcting Segments which will not lead to the retrieval of the complete message.
In the simplest case, after a message is divided into Data Blocks, each Data Block is further subdivided into two Data Segments A and B in which there is only one distinct combination of these Data Segments (for example, A⊕B, i.e., A XOR B). There is no acknowledge signal which is sent from the receiver to the transmitter. This reduces overhead and latency since no ACK or NACK messages need to be sent or awaited. The entire Data Block (i.e., both [A] and [B]) can be recovered if any of the following three Data or Error Correcting Segments are received: (1) [A],[B]; (2) [A],[A⊕B]; or (3) [B],[A⊕B].
The method provides significantly better performance for a fixed amount of overhead relative to simple repetition or repeat schemes. This method is particularly suitable for broadcast mediums and high latency applications such as satellite communications for which an ARQ scheme is not acceptable or practical. Lastly, this method will outperform a standard FEC code in a jamming type environment where errors are in the form of large bursts, such as frequency hopping radio that has strong interference on a percentage of frequencies. Further applications include Internet or Intranet broadcasting and may be used in any network architecture.
The present invention relates to an error correcting method for a multipoint communications system, comprising partitioning a message into Data Blocks in which each of the Data Blocks are further divided into N data segments, representing one or more bits. At least one distinct combination of N data segments is computed using a Boolean or arithmetic operator such as XOR to form Error Correcting Segments where N is equal to 2, 3, or a larger natural number. In the present invention, steps, in addition to receiving the Data or Error Correcting Segments, such as correcting bit errors and performing operations on the Data or Error Correcting Segments which have been received correctly ar
Adaptive Broadband Corporation
Chung Phung M.
Harter Secrest & Emery LLP
Salai Esq. Stephen B.
Shaw Esq. Brian B.
LandOfFree
Method for correcting errors in transfer of information does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for correcting errors in transfer of information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for correcting errors in transfer of information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254037