Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-11-07
2004-02-17
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S752000, C714S762000, C714S776000, C370S394000, C370S412000, C710S030000
Reexamination Certificate
active
06694478
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of error correcting codes for data transmission and more particularly to a packet loss recovery technique for use in data packet-based networks providing real-time multimedia communications.
BACKGROUND OF THE INVENTION
One of the most significant issues that must be dealt with in data packet-based communications networks such as, for example, the Internet, is the problem of error correction due to packet loss. Since each data packet is transmitted through the network independently (and potentially via entirely different network routes), it is common for a destination location to fail to receive an occasional sequence of one or more data packets, and to receive some such packets after an atypically substantial delay. And when such a network is employed to provide real-time multimedia communications such as, for example, voice communications, receiving some data packets after a substantial delay may be tantamount to not receiving them at all, since the receiver cannot typically wait to proceed with the processing of subsequent data packets.
A number of techniques, invariably involving some sort of redundancy coding, have been employed to address the general problem of error correction including the packet loss problem. Typically, the packet loss channel is recognized as an erasure channel using a channel coding language. Classical error correcting codes such as binary block codes, convolutional codes, and Reed Solomon codes, each familiar to those of ordinary skill in the art, can then be employed in an erasure correcting mode. (See, e.g., E. Ayanoglu et al., “Diversity Coding for Transparent Self-Healing and Fault-Tolerant Communication Networks,” IEEE Transactions on Communications, vol. 41, no. 11, pp. 1677-1685, November, 1993; and R. Urbanke et al., “Methods and Apparatus for Packetizing Data for Transmission Through an Erasure Broadcast Channel,” co-pending U.S. patent application, Ser. No. 08/892,855, filed Jul. 15, 1997 and assigned to the assignee of the present invention. U.S. patent application, Ser. No. 08/892,855, now U.S. Pat. No. 6,175,944, is hereby incorporated by reference as is fully set forth herein.) However, it is in fact considerably simpler to correct an erasure than to correct other types of errors (such as, for example, “random” modifications of one or more symbols). In the case of an error, the location of the error must first be determined, while in the case of an erasure (e.g., an unreceived data packet), the location is known.
Typically, a random error correcting code can correct about twice as many erasures as errors in a given block. However, in the context of a transmission of a sequence of data packets across a network, a packet loss effectively causes a continuous string (a “burst”) of erased symbols. Since most classical channel codes are designed for the correction of random errors (or random erasures), prior art approaches to dealing with the packet loss problem typically perform some form of interleaving (permuting) on a relatively long sequence of packets. In this manner, a packet loss channel with correlated erasures (i.e., a continuous string of erased symbols) is transformed into an apparently random erasure channel. Unfortunately, performing such an interleaving process necessarily results in a significant delay at the destination, since the decoder must de-interleave the received data in order to recreate the original sequence of data packets.
Therefore, the use of channel codes such as, for example, Reed Solomon codes, when effectively applied across many packets in sequence, will necessarily require that relatively long delays be incurred at the receiver. As pointed out above, however, such delays may be prohibitive for real-time applications such as, for example, voice communication over networks based on the Internet protocol (IP). Recently, however, in U.S. Pat. No. 5,870,412 (“Forward Error Correction System for Packet Based Real Time Media”) issued to G. M. Schuster et al. on Feb. 9, 1999 (hereinaiter, “Schuster et al.”), a method for data recovery in a bursty packet network which incurs a relatively short delay (as compared to other prior art techniques) has been presented.
Specifically, Shuster et al. performs forward error correction by appending checksum information to each data packet, wherein the checksum information is defined by taking a bit-by-bit exclusive-or sum of the information portion (the “payload”) from a preceding specified number of data packets. (Bit padding on the shorter payloads is used if the information payloads from the preceding packets are of unequal length.) By way of illustration,
FIG. 1
shows an organization of an encoded data packet in accordance with the prior art packet loss recovery techniques as employed in Shuster et al. The illustrated data packet comprises coded information followed by checksum information which has been appended to the data packet for purposes of forward error correction. As described above, in the case of the Shuster et al. technique, the checksum information specifically comprises an exclusive-or sum of the information payload from a preceding specified plural number of data packets.
Thus, using the Shuster et al. technique, a single bit erasure correction code of length w+1 packet instances is formed, enabling for the correction of a burst of up to w lost data packets (provided such a burst is followed by a string of w correctly received data packets), with a maximum decoding delay of 2w−1 packets. Clearly, the Shuster et al. method incurs an overhead in bit volume of at least 100% (more if bit padding is required), as compared to the bits of the information payloads alone. In addition, it can be seen that the method of Shuster et al. requires the solution of w exclusive-or equations.
In co-pending U.S. patent application Ser. No. 09/425,143, “Packet Loss Control Method For Real-Time Multimedia Communications” by H-L. Lou and C-E. W. Sundberg, filed on Oct. 21, 1999 and commonly assigned to the assignee of the present invention (hereinafter, “Lou et al.”), a significantly improved technique over that of Shuster et al. was provided. U.S. patent application Ser. No. 09/425,143 is hereby incorporated by reference as if fully set forth herein. By way of illustration,
FIG. 2
shows an organization of an encoded data packet in accordance with the prior art packet loss recovery techniques as employed in Lou et al.
In particular, while Shuster et al. generates checksum information by “combining” (e.g., by performing exclusive-or operations on) the payload information from a plurality of preceding data packets, Lou et al. simply “repeats” information content from a particular one of the previous data packets in a later packet. More specifically, according to the technique of Lou et al , the information payload associated with a given data packet k, for example, might be identically copied and appended to data packet k+w. (That is, the information payload would be repeated with a delay of w transmitted packets.) Such an improved approach advantageously can correct for a burst of up to w lost data packets (as does the method of Shuster et al.) while improving the decoding delay to w packets as compared to the 2w−1 decoding delay required by the method of Shuster et al. In fact, it can be shown that the decoding delay required by the technique of Lou et al., relative to the number of consecutive lost packets that can be properly corrected, is in fact optimal. (Note that each of these prior art approaches append forward error correcting data to the existing packets without adding any additional packets.)
Both of the above-described prior art approaches (i.e., those of both Shuster et al. and the improved method of Lou et al.), however, are limited to providing rate 1/2 convolutional forward error correcting codes (FEC). (As is fully familiar to those of ordinary skill in the art, the “rate” of an error correcting code is determined based on the ratio between the total number of bit
Martinian Emin
Sundberg Carl-Erik W.
Agere Systems Inc.
Botos Richard J.
Brown Kenneth M.
Moise Emmanuel L.
LandOfFree
Low delay channel codes for correcting bursts of lost packets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Low delay channel codes for correcting bursts of lost packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low delay channel codes for correcting bursts of lost packets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331113