Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-10-21
2004-04-27
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S713000
Reexamination Certificate
active
06728924
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 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 el al., “Methods and Apparatus for Packetizing Data for Transmission Through an Erasure Broadcast Channel,” copending U.S. patent application, Ser. No. 08/892855, filed Jul. 15, 1997 and assigned to the assignee of the present invention. U.S. patent application, Ser. No. 08/892855 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 (hereinafter, “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 a conceptual organization of a transmitted data packet in accordance with certain prior art packet loss recovery techniques, such as that employed in Shuster et al. The illustrated data packet comprises control information
11
followed by associated payload information
12
. The payload information comprises the actual data which is to be communicated across the network with use of the particular packet. In addition, and in accordance with the illustrative prior art techniques such as Shuster et al., checksum information
13
is appended to the data packet for purposes of 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+l 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 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.
SUMMARY OF THE INVENTION
We have recognized that a significant improvement over the scheme of Shuster et al. may be realized by foregoing the prior art's approach of generating checksum information by “combining” (e.g., by performing exclusive-or operations) the payload information from a plurality of preceding data packets, and rather, simply “repeating” information content from a particular one of the previous data packets. For example, and in accordance with a first illustrative embodiment of the present invention, the information payload associated with a given data packet k is identically copied and appended to data packet k+w. That is, the information payload is repeated with a delay of w transmitted packets. Such an approach can advantageously correct for a burst of up to w lost data packets (as does the prior art method of Shuster el al.), but no complex mathematical operations (such as the exclusive-or operations required by Shuster el al.) need to be performed. Moreover, and most importantly, the illustrative method of the present invention improves the decoding window (i.e., the maximum decoding delay) to w+l packets (as compared to the 2w packet decoding window required by the method of Shuster et al.
In accordance with one illustrative embodiment of the present invention, the value of the parameter w may be advantageously selected based on any desired “burst” error (i.e. the number of consecutive lost packets) correction capability, in combination with a corresponding desired “decoding window” (i.e., the maximum decoding delay), since the setting of parameter w clearly results in a direct tradeoff between these two factors. In accordance with another illustrative embodiment of the present invention, the value of the parameter w may be set or adjusted dynamically based on network feedback information.
Specifically, the present invention provides a method of coding a sequence of data packets representing a continuous stream of information, with each data
Lou Hui-Ling
Sundberg Carl-Erik Wilhelm
Brown Kenneth M.
Chaudry Mujtaba
De'cady Albert
Lucent Technologies - Inc.
LandOfFree
Packet loss control method for real-time multimedia... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet loss control method for real-time multimedia..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet loss control method for real-time multimedia... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3201150