Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-04-06
2003-08-19
Decady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06609223
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for reliably encoding data streams to be transmitted in various types of communication and computer systems, for example, a one-way satellite broadcast system between a host computer and a subscriber computer.
2. Description of the Related Art
U.S. patent application Ser. No. 08/785,443, which is incorporated herein by reference, discloses a forward error correction (FEC) encoding method for reliably transferring packets of data between a transmitter and receiver in a computer network or communication system. In particular, that patent application provides various packet-level FEC encoding techniques to ensure that large, multimedia data files, including digitized music, still images or moving images, such as may be transmitted by a host computer to one or more receiver subscriber computers using one-way satellite broadcasting, are received error free despite the effects of various types of noise interfering with the transmitted signal.
In many computer networks or communication systems, including the aforementioned one-way satellite broadcast system, the data bits or symbols (such as octets or bytes) are organized into larger groups called packets. When a file is transmitted, uncoded header packets preceding the information-containing packets are sent. Those header packets contain the address and control information to ensure that the following information packets are received by the addressed subscriber computers. Moreover, each packet itself includes uncoded header bytes that indicate, inter alia, to which file the packet belongs and the position of the packet within that file. The remaining bytes of the packet are the body which includes the informational data, such as compressed video data. For example, a packet may be 4,096 bytes long, wherein the header portion is the first 16 bytes, and the body portion is the remaining 4,080 bytes. A large digital object is thus transmitted as a sequence of “original” or “source” packets.
In the techniques described in U.S. patent application Ser. No. 08/785,443, an extra number of error correcting “wildcard” packets are encoded and transmitted with the original packets to provide a predetermined level of protection against packet loss. For example, if a file contains 180 original packets, an extra 20 wildcard packets may be encoded and transmitted with those 180 original packets, as shown in
FIG. 1A
, to provide against a loss of 20 original packets (approximately an 11% loss). For the reasons described in that patent application, the addressed subscriber computers can successfully reconstruct the large digital object from the received packets so long as any 180 packets, of the 200 packets transmitted, are successfully received.
Additionally, as also described in U.S. patent application Ser. No. 08/785,443, a large file may be broken into smaller “chunks” or “shares”, each of which generally contains the same number of packets, to allow the large file to be more easily transmitted and received by the system. Each share is individually encoded, transmitted, received and reconstructed (decoded). The file is made whole from the individually constructed shares. As also discussed in that application, the packets of the shares may be interleaved to provide additionally protection against the effects of interfering noise. For example, a data file of 360 original packets and 40 wildcard packets may be divided into two shares of 200 interleaved packets each, as shown in FIG.
1
B. Of course, as the files become larger, the number of shares will increase.
As disclosed in U.S. patent application Ser. No. 08/785,443, packet-level error detection processing in the receiving subscriber computers provides an indication that a received packet is “good” or “bad”. Also, an indication is made if a packet has not been received at all, i.e., “lost”. The bad packets are marked as lost and are not used in further decoding. As further explained therein, as long as the number of lost packets does not exceed the number of wildcard packets, the original packets of the file or share may be completely and correctly reconstructed. Continuing the above examples, for each file or share, at least 180 packets of the 200 transmitted packets must be received as “good” packets for the successful reconstruction of the original 180 packets. The techniques for decoding the received good packets to reconstruct the original packets are described more fully in U.S. patent application Ser. No. 08/785,443.
In U.S. patent application Ser. No. 09/179,083, the above-described file-oriented packet-level encoding and decoding techniques of U.S. patent application Ser. No. 08/785,443 are extended from data files to data “streams”. In the computer network/communication system arts, a stream may be a continuous sequence of octets (or bytes) without a packet structure, as in the phrase “TCP (transmission control protocol) is a stream-based protocol”. On the other hand, a stream may be a continuous sequence of packets. For example, when those skilled in the art use the phrase “video (or audio) streaming”, they are usually referring to a stream of UDP/IP (user datagram protocol/internet protocol) or IP Multicast packets. For the present application, a stream is generally any data arriving over a period of time which must be processed and transmitted as it arrives, without waiting for the data to end. Usually, the data is generated by an independent source, and at any given point in time the transmitting system has no knowledge of if or when future data will arrive.
In U.S. patent application Ser. No. 09/179,083, data streams are assembled into “virtual files” of packets, and then the file-oriented encoding and decoding techniques of U.S. patent application Ser. No. 08/785,443 are applied thereto. That is, the host computer collects the data of the streams into packets, and the packets are collected into a virtual file. The virtual file is then encoded by the host computer using the techniques of U.S. patent application Ser. No. 08/785,443, and the encoded packets are transmitted to the subscriber computers. At the subscriber computer side, the packets are received and collected into a virtual file, which is then decoded using the techniques of U.S. patent application Ser. No. 08/785,443. Once the virtual file is decoded, it is output by the subscriber as a stream of packets, or as a stream of unpacketized data if applicable. However, the method described in U.S. patent application Ser. No. 09/179,083 has a drawback in that delays are created when the host computer waits for data to arrive from the source so it can be packetized and made into a virtual file. Another delay is created as the subscriber computer waits for the arrival of all of the packets required to reconstruct the virtual file. Further, a great deal of memory, and associated read/write operations, is required for storing the virtual file.
Accordingly, to remove these delays from the “virtual file” method of encoding data streams, and to reduce the memory requirements thereof, it would be desirable to encode and decode data streams directly, that is, without the creation of virtual files. However, there are complications when working with data streams as opposed to virtual files. It is usually desirable, or sometimes necessary, to process the data streams in a timely fashion with minimal delays. Such a restriction generally rules out the ability to request retransmission of missed data, and thus, it is important that a reliable encoding scheme for one-way transmission be used. To additionally minimize delays, the host computer should be capable of receiving stream data from the source at a rate similar to the original stream. Moreover, unlike virtual files, when data streams are encoded, there is a lack of knowledge at the host computer, at any given point in time, if and when future data will be coming. This uncertainty of future data must be accounted for in the encoding process. Further, past data may also be unknown, as the
Abraham Esaw
De'cady Albert
Kencast, Inc.
LandOfFree
METHOD FOR PACKET-LEVEL FEC ENCODING, IN WHICH ON A SOURCE... 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 PACKET-LEVEL FEC ENCODING, IN WHICH ON A SOURCE..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and METHOD FOR PACKET-LEVEL FEC ENCODING, IN WHICH ON A SOURCE... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111047