Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-07-15
2001-01-16
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S752000
Reexamination Certificate
active
06175944
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data transmission over a channel which is subject to losses. More particularly, the invention relates to methods and apparatus for transmitting a data set which will be transmitted with a first higher level of transmission quality if a first level of losses occur and with a second lower level of quality having an acceptable level of degradation if a second higher level of losses occur, without the necessity for retransmitting lost data.
BACKGROUND OF THE INVENTION
Digital data transfer has been an important technology for many years. Traditionally, digitally transferred data has been packaged as files. When a file is transferred, the loss of data is often critical, because the data contained in the file defines not only the information of the file, which can often be reconstructed, but the structure of the file, which informs the reading device where the file begins and ends, and which data is to be viewed as part of the file. Moreover, digital data transfers have traditionally been accomplished by a server connected more or less directly to a client through a telephone line or similar device. While such a connection is susceptible to losses, the losses are usually not excessive.
Traditional digital data transfer, because of the need to transfer a file with its complete data and structure, and because of the relatively low losses introduced by traditional transfer methods, has typically been intolerant of losses. Typically, data transfers were monitored for losses, and any lost data was retransmitted. The need to retransmit data naturally increased the time required for a data transfer, but the additional time required was usually not great, and the added time was required because the data needed to be transmitted without errors.
More recently, data transfers have increasingly taken place over networks lacking a dedicated connection between server and client, with the leading such network being the Internet. Data is transmitted over the Internet through routings which may differ from the transmission of one packet to the next. This contributes significantly to the likelihood that data will be lost. Moreover, a substantial portion of the data transmitted over the Internet consists of graphics and sounds. An acceptable transmission of such items may be highly tolerant of losses, but less tolerant of delay.
Many Internet users would be only too glad to sacrifice a certain amount of picture quality in order to have a picture display faster. Even more importantly, real-time voice communication is increasing in importance as an Internet application. If data losses occur during a real-time voice communication, the degradation in quality caused by these losses may be imperceptible, while the time lost in retransmitting lost packets in order to reconstruct the data without error would adversely cause an interruption in the conversation. Thus, while in such an environment, a loss-free transmission is ideal and preferable so that no packets would be lost, in a real world transmission in which packets are lost, an imperfect transmission of the data would be highly preferable to the delays which would be occasioned by the retransmission of the lost packets.
There exists, therefore, a need in the art for a way to transmit data by means of digital packets such that a reduced quality reconstruction of the data is possible if a certain number of packets are lost, with a finer reconstruction being achieved with the loss of fewer packets.
SUMMARY OF THE INVENTION
The present invention preferably employs Reed-Solomon codes to transfer data; however, it will be recognized that other codes may be suitably employed. Each block of data is divided into two or more portions. With two portions, by way of example, one portion is being represented by Reed-Solomon codewords and defines basic coarse data to be transmitted even in the event of data losses, and the other portion is represented by additional data bytes appended to the codewords and defining additional fine detail to be transmitted when no data losses occur. If each codeword is of length n, dimension k and distance d=n−k+1, the code corrects any pattern of d-1 erasures.
Each block of data to be transmitted is divided into n packets, where n is the length of the codeword. Each packet contains i bytes, where i is the number of codewords used to convey the coarse information of the data block. Each packet contains an additional k bytes, where k is the number of additional fine bytes required to fully describe the data block.
In another aspect, a set of codewords representing a data block to be transmitted may be broadcast over a plurality of channels. Each channel may have a different erasure probability. Thus, varying numbers of packets will arrive successfully at the receiver depending on which of the various channels is traversed. The coarse or fine version of the data block will be decoded at each receiver, depending on whether or not all packets successfully arrive. At least the coarse version of the data block will be able to be decoded, so long as at least d packets arrive successfully. Other aspects of the invention provide the ability to decode the data block with varying levels of refinement in the case where more than d but less than all of the packets arrive successfully. It will be recognized that multiple levels of basic data may be transmitted employing codes designed to correct for varying levels of erasure.
A more complete understanding of the present invention, as well as further features and advantages of the invention, will be apparent from the following Detailed Description and the accompanying drawings.
REFERENCES:
patent: 5233629 (1993-08-01), Paik et al.
patent: 5577134 (1996-11-01), Westerink
patent: 5586200 (1996-12-01), Devaney et al.
patent: 5617541 (1997-04-01), Albanese et al.
patent: 5671156 (1997-09-01), Weerackody et al.
patent: 5691992 (1997-11-01), Molnar et al.
patent: 5757821 (1998-05-01), Jamal et al.
patent: 5781561 (1998-07-01), Machida et al.
patent: 5828788 (1998-10-01), Chiang et al.
Christopoulos et al., “A Hybrid Method For Image Partitioning In Low Bit Rate Segmented Image Coding”, Jun. 1997 IEEE, pp. 845-848.
Park et al., “Efficient Hierarchcal Segmentation Based on PSNR for Low Bit Rate Coding”, Jun. 1996 IEEE, pp. 157-160.
A. Albanese, J. Blomer, J. Edmonds, M. Luby and M. Sudan, “Priority Encoding Transmission”, IEEE Transactions on Information Theory, vol. 42, No. 6, pp. 1737-1745, 1996.
S.G. Mallat, “Multifrequency Channel Decompositions of Images and Wavelet Models”, I.E.E.E. Transactions on Acoustics, Speech and Signal Processing, vol. 37, No. 12, pp. 2091-2210, 1998.
P.J. Burt and E.H. Adelson, “Laplacian Pyramid as a Compact Image Code”, I.E.E.E. Transactions on Communication, vol. 33, No. 4, pp. 532-540, 1983.
Richard E. Blahut, “Theory and Practice of Error Control Codes”, Ch. 7, pp. 161-191, 1983.
Urbanke Rudiger L.
Wyner Aaron Daniel
Cady Albert De
Law Offices of Peter H. Priest, PLLC
Lucent Technologies - Inc.
Ton David
LandOfFree
Methods and apparatus for packetizing data for transmission... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for packetizing data for transmission..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for packetizing data for transmission... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500829