METHOD FOR PACKET-LEVEL FEC ENCODING, IN WHICH ON A SOURCE PACKET-BY-SOURCE PACKET BASIS, THE ERROR CORRECTION CONTRIBUTIONS OF A SOURCE PACKET TO A PLURALITY OF WILDCARD PACKETS ARE COMPUTED, AND THE SOURCE PACKET IS TRANSMITTED THEREAFTER

[0002] This application claims the benefit of U.S. Provisional Application No. 60/128,163, filed Apr. 6, 1999.

[0003] 1. Field of the Invention

[0004] 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.

[0005] 2. Description of the Related Art

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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. 1B. Of course, as the files become larger, the number of shares will increase.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] 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 host computer may start receiving data from a source in midstream, such as in “live” video/audio transmissions.

[0014] Accordingly, it would be desirable to provide a method that encodes streams of source packets directly that overcomes the above-described problems. To accomplish this, a method is provided in which, when a packet of data arrives from a source, or a packet is formed from arriving source data bits or octets, the packet's error-correcting contribution to a group of wildcard packets is computed. Once that computation is done, the packet can then be transmitted to the subscriber computer without waiting for the arrival of any other source packet, thus making the encoding process nearly instantaneous. In particular, advantage is taken of the identity submatrix of the encoding generator matrix described in U.S. patent application Ser. No. 08/785,443, which causes the encoded source packets to be identical to the original source packets. Thus no actual encoding of the source packets is required, and the source packets may be transmitted as soon as the computation of its wildcard contributions has been completed. The contributions from the source packets to each wildcard packet of the group are summed, and when all of the contributions have been computed for all of the wildcard packets associated with the group of source packets, the wildcard packets are transmitted. At the receiver, the source packets may be reconstructed from the received packets using the packet-level decoding techniques set forth in U.S. patent application Ser. No. 08/785,443.

[0015] In another aspect of the invention, if a timeout occurs at the host computer because no further stream data is forthcoming, or a signal is received from the source indicating that the data stream has ended, an appropriate set of wildcard packets is transmitted, thus preventing the data stream information from becoming stale. Optionally, the number of wildcards sent, as compared to the total number of wildcards normally computed for the group, may be proportional to the number of source packets actually received by the host computer, as compared to the number of source packets normally received by the host computer when no timeout occurs.

[0016] The various aspects of the present invention can be best understood by reference to the detailed description of the preferred embodiments set forth below taken with the drawings, in which:

[0017] FIG. 1A depicts an example of a file of packets including original packets and wildcard packets;

[0018] FIG. 1B depicts an example of a file with shares of interleaved packets;

[0019] FIG. 2 depicts a block of 12 packets received from a source by a host computer;

[0020] FIG. 3 shows the formula for computing the contributions for each source packet to the wildcard packets in accordance with the general case of the present invention;

[0021] FIG. 4 depicts a block of 9 packets received from a source by a host computer; and

[0022] FIG. 5 shows the formula for computing the contributions for each source packet to the wildcard packets in accordance with the timeout case of the present invention.

[0023] A typical input to the host computer is video or audio data in the form of (1) an octet, byte, or bit-stream (hereinafter collectively referred to as “bit-stream”), (2) a file, or (3) a packet stream. If the source is a bit-stream, the data is formed into packets, preferably of equal-size, thus creating a packet stream. Similarly, if the source is a file, the host computer may treat that file as a bit-stream, and packetize the same, preferably in equal size packets, to create a packet stream. Accordingly, regardless of the type of input source data, the host computer will encode source (or “original”) data packets, and will transmit encoded packets comprising both source packets and wildcard packets to one or more subscriber computers. In the general case, it is preferred that for a given packet stream, there is a small standard deviation in source packet size and that the average source packet size is very close to the actual maximal packet size (relatively large variations in packet size will be discussed below). This provides a method that is efficient from both information-theoretic and performance point-of-views. A typical block of source packet data input to the host computer is shown in FIG. 2.

[0024] Although the computations are performed on a per-source packet basis, it is assumed that the wildcard packets are computed over a group of k source packets, for example, 12 source packets (s₁through s₁₂). The number n-k of error correcting wildcard packets required for each group of k source packets is selected by the host computer operator based on the expected number of packets to be lost during transmission due to interfering noise, as explained in U.S. patent application Ser. No. 08/785,443. For example, it may be expected that a maximum 4 packets will be lost during transmission out of every n=16 packets transmitted (a 25% loss), and thus n-k=4 wildcard packets (e₁through e₄) will have to be computed for every k=12 source packets. It should be appreciated that these numbers have been chosen to more easily demonstrate the present invention, as actual loss rates are usually much smaller on average (0 to 5%).

[0025] The error correcting contribution of every source packet “s” to the error-correcting wildcard packets “e” is computed as shown in FIG. 3. Each original source packet s₁is prefixed with a data field of a few bytes indicating the length of the packet. The resulting packet (containing length and information data of s_i) will be denoted X_i. Using the terminology of U.S. patent application Ser. No. 08/785,443, “X_ij” and “Y_ij” represent respectively the jth byte of the ith unencoded source packet X_iand the ith encoded packet Y_i, wherein Y_i=X_ifor i=1, . . . , k, and Y_k+1, Y_k+2, . . . , Y_nare the error correcting wildcard packets (for example “e₁, e₂, e₃, and e₄”). The error correcting contributions are calculated for each byte j of source packet i. The kxn encoding generator matrix G is computed as set forth in U.S. patent application Ser. No. 08/785,443, wherein the first kxk rows and columns form the identity matrix I (see FIG. 5 of U.S. patent application Ser. No. 08/785,443). Accordingly, the first k encoded packets are identically the k source packets, and thus no actual encoding computations, save for the wildcard contributions, need be performed for those packets. Accordingly, the host computer may transmit each source packet of a group immediately after computing its contribution to the wildcard packets of the group. By doing this, encoding delays at the host computer may be minimized, and there is no need to write and read the source packet into and out of memory. The predominant computational and memory costs required at the host computer are related to the wildcard packets, which are relatively minor compared to what would have been required for the source packets had they been first converted into a virtual file.

[0026] If the number of bytes in any given packet s is less than the predefined maximal packet size of the block, than the remaining bytes of that packet are padded with zeroes. In other words, any blank spaces in the block shown in FIG. 2 are treated as zeroes for encoding purposes. For example, s₁, and s₂have a length equal to the actual maximal packet size for data stream, while both are smaller than the predefined maximal packet size for the block. The blank space to the right of s₁and s₂, as well as the other source packets, are thus treated as zeroes when the wildcard contributions are computed. It should be noted that none of the extra zeroes are transmitted by the host computer.

[0027] For example, when a frame of video is packetized by the source, it is divided into approximately equal-sized packets, each packet having a size of about 1500 bytes. If the predefined maximal packet size of the data block is 1600 bytes, then 100 bytes are filled with zeroes for encoding purposes. The predefined maximal packet size of the block is chosen to greater than the expected actual maximal packet size so as to minimize the need to repacketize the incoming packet stream to fit the block. Although zero-filling results in a small loss of information-theoretic efficiency, it is compensated by better performance efficiency for not having to repacketize data.

[0028] Each transmitted source packet has in its header information indicating to which group of encoded packets it belongs, so it may be associated with other source and wildcard packets of that group upon reception. In addition, each source packet's header has a timestamp so the packet's data may be put back into a time-ordered data stream upon reception.

[0029] In addition, each source packet has a data field consisting of approximately a few bytes, outside of the header, which indicates the length of the packet. This field precedes the actual information data (for example, video or audio data) of the source packet. This length data is treated like the actual information data in that it is encoded as part of source packet X_i. The encoding of the length data is required because when a source packet is lost and recovered, it is recovered with possibly all of the zeroes that were added during the encoding process. Thus, the decoder also needs to recover the packet's length to determine which of those zeroes are actually part of the information data or are merely zero-fill data to be ignored.

[0030] The contribution from each of the source packets to each of the wildcard packets of the group are continuously summed as the processing for each source packet is completed. For each wildcard packet, the running summation is performed in a bank of accumulators, one accumulator for each wildcard packet byte, from the first byte to the last byte corresponding to the predefined maximal packet size. The actual maximal packet size shown in FIG. 2 is not actually known until the last of the 12 source packets have been received, and thus each accumulator must be set up to receive a contribution from a source packet as large as the predefined maximal packet size. Accordingly, the wildcards will all be of the same length, that being the actual maximal packet size. In this regard, none of the extra zeroes corresponding to those bytes beyond the actual maximal packet size are transmitted with the wildcard packets.

[0031] After the k source packets have been received (or formed) by the host computer from the source and their respective contributions to the wildcard packets have been computed and summed, the n-k wildcard packets are complete and may now be transmitted. The header of each wildcard packet contains information indicating that it is a wildcard packet and to which group of encoded packets it belongs. This allows the received wildcard packets to be correctly associated with the received source packets of the same group at the subscriber computer. In addition, each of the wildcard headers contain information indicating that all k source packets contributed to them. (See below for the timeout case, wherein less than k source packets contributed to the wildcard packets.)

[0032] At the subscriber computer, some, if not all, of the n total source and wildcard packets for a given encoding group are successfully received. For that encoding group, if the k source packets have been successfully received, then no decoding is necessary. If the at least k successfully received packets are instead a combination of source and wildcard packets, then one of the wildcard packet's header is checked to see whether or not the wildcard packets were encoded using all k source packets. If so, then any k packets of the at least k successfully received packets may be used to reconstruct the k source packets. The decoding techniques for accomplishing this are explained in detail in U.S. patent application Ser. No. 08/785,443 (see FIG. 3B and accompanying text). (See timeout case below if it is determined from the wildcard header that less than all k source packets contributed to the encoded wildcard packets.)

[0033] If less than k packets were successfully received for a given packet encoding group, that is, more than n-k packets were deemed “lost” by the subscriber computer, then all k source packets cannot be reconstructed without error. The subscriber computer must then request retransmission of the missing source packets, if possible, or otherwise make do with whichever source packets were successfully received (for example, the data of the unreconstructable missing source packets may in certain circumstances be replaced with, or estimated from, data of successfully received source packets). However, careful selection of the number of wildcard packets by the host operator should greatly minimize the occurrence of this event.

[0034] It should be noted that the entire process described above is repeated for arriving source packets (e.g., s₁₃, s₁₄, s₁₅, . . . ) until the data stream ends.

[0035] Unfortunately, unlike well-defined files, when working with data streams the host computer does not know at any given point in time if or when future data will arrive. The “timeout case” extends the above-described general case to those instances when less data has been received than was originally expected, as follows.

[0036] As shown in FIG. 4, the first 9 of k=12 source packets, denominated s₁to s₉, arrive in the host computer, and are processed as discussed above in the general case. However, the last 3 packets, s₁₀, s₁₁, and s₁₂, never arrive. Eventually, a timeout condition in the host computer occurs. A timeout occurs when no data has been received by the host computer from the source within a predetermined time interval since receipt of the last packet. Alternatively, a signal may be sent from the source and received by the host computer, the signal indicating that the data stream has ended.

[0037] In either situation, since s₁₀, s₁₁, and s₁₂, never arrived at the host computer, they are treated as zero (they need not be transmitted). Thus, X₁₀, X₁₁, and X₁₂in the formula shown in FIG. 3 are zero, and the error correction contributions resulting therefrom are also zero.

[0038] Instead of sending all of the wildcard packets, the number of wildcard packets sent may be adjusted proportionally. This is because the other wildcard packets are not required for error-free reconstruction. In this example, since only 75% (9 of 12) of the source packets of the group arrived and contributed to the computations of the wildcard packets, only 75% (3 of 4) of the wildcard packets need be transmitted. Thus, only wildcard packets e₁, e₂and e₃are transmitted in this example. Further, the respective headers of these wildcard packets contain information indicating that only 9 source packets contributed to their formation. Although in this example only one wildcard is not sent, reducing the number of transmitted wildcard packets generally can result in a substantial savings when dealing with groups of large numbers of packets. For example, assuming the number of source packets in a group is 2000 and the number of wildcard packets for that group is 500, if a timeout occurs after only 20 source packets (1%) have been received by the host computer, it is preferable to send only 5 wildcard packets (1%) than all 500 wildcard packets.

[0039] Because s₁₀, s₁₁, and s₁₂are treated as zero, the formula in FIG. 3 may be rewritten as shown in FIG. 5. In the formula shown in FIG. 5, G′ is a 9×12 matrix comprising the concatenation of a 9×9 identity matrix I with a 9×3 submatrix consisting of the first 9 rows and first three columns of the 12×4 submatrix shown in FIG. 3. G′ is a row-reduced form of a Vandermonde matrix, and thus the encoding/decoding techniques of U.S. patent application Ser. No. 08/785,443 can be applied to the transmitted packets s₁, s₂, . . . , s₉, e₁, e₂, e₃. One skilled in the art will appreciate that G′ is not the same as the encoding (generating) matrix that would normally be used to create 3 wildcards from 9 source packets, but differs therefrom only in an arbitrary choice of constants used to pick a Vandermonde matrix.

[0040] In summary, in the general case an encoding/decoding technique is used in which all of the packets s₁, s₂, . . . , s₁₂can be perfectly reconstructed from any 12 packets taken from the set {s₁, s₂, . . . ,s₁₂, e₁, e₂, e₃, e₄}. But in the timeout case, the host computer timed out before receiving s₁₀, s₁₁, and s₁₂, so the host computer pretends that there are imaginary source packets s₁₀, s₁₁, s₁₂consisting of all zeroes and sends out only s₁, s₂, . . . , s₉, e₁, e₂, e₃, wherein each wildcard packet e₁, e₂, e₃contains information in its header that s₁₀, s₁₁, s₁₂are imaginary all-zero packets. Thus, s₁, s₂, . . . , s₉may be reconstructed from any 9 of the packets that were sent:

[0041] subcase 1: s₁, . . . , s₉are successfully received, and no decoding is required.

[0042] subcase 2: at least nine packets are received, including at least one of the wildcard packets. The header of any of the received wildcard packets tells the subscriber computer that it was formed with less than all k=12 source packets, and in particular, that it was formed with source packets s₁to s₉, and thus the subscriber computer knows that s₁₀, s₁₁, s₁₂are imaginary all-zero packets, that is, that s₁, s₂, . . . , s₉, e₁, e₂, e₃satisfy the relationship set forth in FIG. 5. Thus, s₁, . . . , s₉may be reconstructed using any nine of the received packets with the decoding technique set forth in detail in U.S. patent application Ser. No. 08/785,443 detail (see FIG. 3B and the accompanying text thereof).

[0043] It should be noted that in subcase 1, the subscriber computer does not actually know that all of the transmitted source packets have been received, because source packets s₁, . . . , s₉were transmitted before the host computer knew that there was not going to a real source packet s₁₀. Thus, the subscriber computer must either wait for the receipt of additional source packets s₁₀to s₁₂, which would indicate the general, non-timeout case, or the receipt of one of the wildcard packets, the header of which would indicate how many source packets were used to create it.

[0044] In the general case, it is preferred that the packet-based data stream input to the host computer has a small standard deviation in source packet size and that the average source packet size is very close to the actual maximal packet size, which in turn must be smaller than the predefined maximal packet size (see FIG. 2). In this case, the source packet sizes will be same or about the same as the wildcard packet size (i.e., the actual maximal packet size), which provides nearly the most efficient coding from an information-theoretic point of view. However, given the variation of packet sizes among the different types of sources and conditions, the preferred data stream is not always provided to the host computer. The host computer can handle these variations in packet sizes as follows.

[0045] In one case, the source packets are generally uniform, such as shown in FIG. 2, but occasionally a very large source packet arrives that is either greater than the predefined maximal packet size or the average size of previously-arriving packets. In this situation, the host computer simply breaks that very large source packet into two or more smaller packets, each of whose size is less than the predefined maximal packet size and preferably close to the sizes of the previously-arriving packets.

[0046] In another case, the data stream generally consists of many very large packets (beyond the predefined maximal packet size), and/or packets of widely variable or unpredictable size. Accordingly, the source packets either cannot be encoded because they are too large, or the encoding becomes greatly inefficient from an information-theoretic point-of-view. In this situation, it would be preferable to “repacketize” the packets to ensure that their sizes are less than the predefined maximal packet size and/or to reduce their variability in size. To accomplish repacketizing, the packet stream is converted into a bit-stream, which is then reconverted into a packet stream with packets of approximately equal size. Repacketizing, however, adds a delay into the encoding process.

[0047] Wildcard and source packets may be sent, in parallel, on separate transmission channels. For example, it may be desirable to send a digital television signal (or digital audio signal) which can be used by traditional equipment (which would suffer in terms of quality when outages due to noise occurred) as well as by high-quality systems which could make use of the error-correction wildcard information. The error-correction wildcard information could be sent on a separate channel on the satellite network, or with a separate packet identifier (PID) in the case of a digital video broadcast (DVB) system. To accomplish this, a channel multiplexer would be required.

[0048] In addition, the above-described data stream encoding method may be extended so that the packets are interleaved, by utilizing the file interleaving methods described in detail in U.S. patent application Ser. No. 08/785,443. One share of interleaved packets may be transmitted to the subscriber computer at the same time as several other shares of interleaved packets, as shown in FIG. 1B for two interleaved shares.

[0049] Of course, it will be appreciated that the invention may take forms other than those specifically described, and the scope of the invention is to be determined solely by the following claims.