HK1156770A - Fast channel zapping and high quality streaming protection over a broadcast channel - Google Patents

Description

Fast channel switching and high quality stream protection on a broadcast channel

This application claims benefit of U.S. provisional application No.61/051,325 entitled "Fast Channel Zapping and High Quality Streaming Protection over a Broadcast Channel", filed on 7.5.2008.

Technical Field

The present invention relates generally to stream and object delivery and more particularly to delivering streams and objects over less reliable channels using FEC to protect the quality of the delivered streams.

Background

It has been a common practice to consider transmitting streaming data (typically audio and/or video data but also other types of data such as telemetry data) over a channel. One major consideration is to ensure that the quality of the delivered stream is high enough, e.g. so that all or most of the original stream data is delivered to the receiver or group of receivers, or so that the video quality played out at the receiver or group of receivers is high enough. For example, the channel used to deliver the streaming data may not be completely reliable, e.g., a portion of the data is lost or corrupted in transmission. Other measures to overcome the delivery degradation to achieve high quality delivery are typically required in such cases, where the measures may include, for example, applying FEC to the original data stream at the physical layer to prevent packet corruption, or applying FEC to the original data stream at the link, transport, or application layers to prevent packet loss. Other measures include using retransmission strategies to retransmit lost or corrupted data, such as link layer retransmission protocols or application layer retransmission protocols.

Another major consideration in designing the system is, for example, the amount of time it takes from the end user first requesting to start viewing a video stream to start displaying the video stream, or the amount of time it takes to stop displaying the current video stream and start displaying a new video stream as triggered by the user request. This amount of time is commonly referred to as the channel switch time. Typically, the smaller the channel switch time, the better the end user experience and thus the more valuable the overall service. For example, a common requirement is that the channel switching time be as small as possible, e.g., less than one second.

Such channel switching times and high quality stream delivery are typically possible when streams are delivered over highly reliable channels without a back channel, or when streams are delivered over less reliable channels and when there is a back channel available to request retransmission of lost data, but are typically challenging when streams are delivered over less reliable channels and when a back channel cannot be used to enhance reliability, and it may be more appropriate to use FEC instead.

Recently, it has become a common approach to consider FEC codes for streaming media protection during transmission. When transmitted over a packet network (examples of which include the internet and those wireless networks standardized by groups such as 3GPP, 3GPP2, and DVB), the source stream is placed in packets as it is generated or obtained, so the packets can carry the source stream to the receivers in the order in which the source stream was generated or obtained. In a typical application of FEC codes to these types of situations, FEC codes are used to add additional repair packets to the original source packets containing the source stream, the repair packets having the property that when a source packet loss occurs, the received repair packets can be used to recover the data contained in the lost source packet. In other instances, partial packet loss may occur, i.e., a receiver may lose a portion of a packet while receiving other portions of the packet, so in these instances, receiving a repair packet in whole or in part may be used to recover the lost source packet in whole or in part. In other instances, other types of corruption of the transmitted data may occur, for example, the bit values may flip, and thus, repair packets may be used to correct such corruption and recover the source packet as accurately as possible. In other instances, the source streams are not necessarily transmitted in discrete packets, but may be transmitted, for example, as a continuous bit stream.

There are many examples of FEC codes that can be used to provide protection for a source stream. Reed-Solomon codes are well known codes for error correction in communication systems. For erasure on, for example, packet data networks, a well-known efficient implementation of Reed-Solomon codes is to use a Cauchy-Vandermonde matrix such as l.rizzo in Computer Communication Review, 27 (2): "Effective Erasure Codes for replaceable Computer Communication Protocols" (hereinafter referred to as "Rizzo") and J.Bluemer, M.Kalfane, R.Krp, M.Karpinski, M.Luby and D.Zuckerman of "An XOR-Based measure-Resilience Coding Scheme" (hereinafter referred to as "XOR-Reed-Solomon") of Technical Report TR-95-48, International Computer Science Institute, Berkeley, California, (1995). Other examples of FEC codes include LDPC codes, chain reaction codes, and multilevel chain reaction codes, such as those described in U.S. patent No.6,307,487 (hereinafter "Luby I") and U.S. patent publication No.2003/0058958 (hereinafter "Shokrollahi I"), respectively, which are incorporated herein for all purposes.

Examples of FEC decoding processes for variants of Reed-Solomon codes are described in "Rizzo" and "XOR-Reed-Solomon". In these examples, decoding is applied once enough source and repair data packets are received. This decoding process can be computationally intensive and, depending on available CPU resources, can take a considerable amount of time to complete relative to the length of time spanned by the media in the packetized block.

In many applications, the packet is further divided into symbols, and the FEC process is applied on the symbols. The symbols may have any size, but the size of the symbols is typically at most equal to the size of the packet. In the following, we will refer to the symbols comprising the coding blocks as "source symbols" and the symbols generated during the FEC process as "coded symbols". For some FEC codes, particularly Reed-Solomon codes, the encoding and decoding time grow impractically as the number of coded symbols per source block grows. Thus, in practice, there is typically an upper limit to the total number of code symbols that can be generated for each source block, e.g., 255. Since symbols are usually placed in different packet payloads, this sometimes sets a practical upper limit on the maximum length of encoding of the source block, e.g. 255KB (kilobytes) at most if the packet payload is 1024 bytes at most, and of course the size of the source block itself if each symbol is sent in a separate packet.

Since applying FEC codes to data blocks transmitted over a larger time interval generally provides better protection for the same bandwidth overhead than applying FEC codes to data blocks transmitted over a smaller time interval, it is generally desirable to apply FEC encoding and decoding to data blocks in a stream transmitted over a larger time period. This is because many channels suffer from time-dependent loss and/or corruption characteristics, e.g., data is likely to be lost in bursts, or there are likely to be some short periods of time, the channel characteristics of which are much worse than over other short time intervals.

A challenge with using FEC coding applied to data blocks transmitted over a large time interval is that it may adversely affect the channel switching time. For example, at the receiver, it is not possible to recover and play the encoded data block in its entirety until sufficient data for the entire encoded data block has been received. Thus, if FEC encoded data blocks are sent over a large time interval, the channel switching time may be unacceptably high.

One way to achieve short channel switching times while transmitting FEC encoded data blocks over a large time interval is to order the data in the following order: the most important data and the least important data in the FEC encoded data are transmitted last and first. For example, U.S. patent application No.11/423,391 entitled "Forward Error Correcting (FEC) Coding and Streaming" (hereinafter "FEC stream"), which is incorporated herein for all purposes, describes a method for transmitting FEC repair data prior to transmitting source data of a source block, such that even if a receiver joins the stream in the middle of the source block, the receiver is able to receive a portion of the source data of the source block and begin transmitting it to, for example, a media player for playback, thereby minimizing channel switching time.

Another consideration is to minimize the amount of channel resources used by the header data to identify the actual data to be transmitted. In general, header data is typically overhead, which negatively impacts the amount of capacity available to transfer data. For example, if 4 bytes of header data are used to identify every 100 actual data bytes, then the header overhead is up to 4%. It is desirable to minimize header overhead as much as possible, particularly for stream and object delivery applications, but more generally for any data delivery application.

Methods, processes, and apparatus are described that allow high quality streams to be delivered over less reliable channels when reverse channels are not used to enhance reliability, requiring short channel switching times. It is also of paramount importance to minimize the physical resources (e.g., header overhead and FEC headers) required to achieve a given level of reliability.

Disclosure of Invention

Embodiments present novel methods and processes for transmitting and receiving streaming data over a channel using FEC codes to provide high quality delivery and allow short channel switching times. A novel signaling method is described that minimizes the required header overhead in a system for both streaming and object delivery. Novel configurations for transmitting and protecting streams are also described.

The following detailed description and the accompanying drawings will provide a better understanding of the nature and advantages of the present invention.

Drawings

Fig. 1 is a block diagram of a communication system according to one embodiment of the present invention.

Fig. 2 is a diagram illustrating components of receiver delay for a known system.

Fig. 3 is a diagram illustrating components of receiver delay when transmitting FEC repair symbols generated from corresponding source symbols before transmitting the corresponding source symbols.

Fig. 4 is a block diagram illustrating how one embodiment prioritizes data into sub-blocks and maps the sub-blocks to a prioritized transmission order.

Fig. 5 is a block diagram illustrating how one embodiment maps sub-blocks to physical layer blocks based on mapping the entire sub-block to each physical layer block.

Fig. 6 is a block diagram illustrating how an embodiment maps sub-blocks to physical layer blocks, where an equal amount of sub-block data is mapped to each physical layer block and the sub-blocks are sometimes partitioned over multiple physical layer blocks.

Detailed Description

The embodiments described herein provide a novel method of signaling source blocks among multiple physical layer blocks for both streaming and object delivery applications. These signaling methods include transmitting interleaved source blocks in physical layer blocks with minimal and in some cases no overhead, transmitting an indication of how symbols relate to the source block from which the symbol originated, and transmitting an indication of prioritized data for the source block. Other methods of organizing and transmitting streams over one or more channels are described that improve the quality of the delivered streams while minimizing or improving the amount of channel resources and receiver power resources required.

In the following, the network carrying the data is assumed to be packet-based in order to simplify the description herein, and it can be appreciated that a person skilled in the art can readily see how the processes and methods described herein can be applied to other types of transport networks, such as continuous bit stream networks. In the following, assuming that FEC codes are used to provide protection for lost packets or lost portions of data in packets in order to simplify the description herein, it can be appreciated that one skilled in the art can readily see how the processes and methods described herein can be applied to other types of data transmission impairments such as bit flipping.

Fig. 1 is a block diagram of a communication system 100 using chain reaction coding. In the communication system 100, an input file 101 or an input stream 105 is provided to an input symbol generator 110. Input symbolThe number generator 110 generates one or more sequences of input symbols (IS (0), IS (1), IS (2), … …) from the input file or stream, where each input symbol has a value and a position (represented in fig. 1 as a bracketed integer). The possible value of an input symbol, i.e. its symbol system (alphabet), is typically 2^MA symbol system of symbols such that each input symbol encodes an M-bit input file. The value of M is typically determined using communication system 100, but a general system may include a symbol size input for input symbol generator 110, such that M is different for different uses. The output of the input symbol generator 110 is provided to an encoder 115.

The key generator 120 generates a key for each output symbol to be generated by the encoder 115. Each key is generated according to one of the following methods: luby I or Shokrollahi I, or any other similar method that can ensure that a large portion of the keys generated for data blocks in the same input file or stream are unique regardless of whether they are generated using this or another key generator. For example, key generator 120 may generate each key using a combination of the output of counter 125, unique stream identifier 130, and/or the output of random generator 135. The output of the key generator 120 is provided to the encoder 115. In other instances, such as in some streaming applications, the set of keys may be fixed and may be reused for each data block in the stream.

The encoder 115 generates output symbols having values b (I) from the input symbols provided by the input symbol generator, based on each key I provided by the key generator 120. The value of each output symbol is generated based on its key and based on some function of one or more input symbols (referred to herein as the "associated input symbol" of the output symbol or simply its "association"). M is typically, but not always, the same for the input symbol and the output symbol, i.e. they both encode the same number of bits.

In some embodiments, the encoder uses K input symbols to select the association. K may be just an estimate if K is not known in advance, such as the input is a stream and K may vary between each block in the stream. The value K may also be used by the encoder 115 to allocate memory for the input symbols.

The encoder 115 provides the output symbols to a transmit module 140. The key for each of the output symbols is also provided from the key generator 120 to the transmission module 140. The transmitting module 140 transmits the output symbols and depending on the key method used, the transmitting module 140 may also transmit some data on the channel 145 to the receiving module 150 regarding the key of the transmitted output symbols. It is assumed that channel 145 is a drop channel, but this is not a requirement for normal operation of communication system 100. Modules 140, 145, and 150 may be any suitable hardware components, software components, physical media, or any combination thereof, as long as transmitting module 140 is operable to transmit output symbols and any required data regarding their keys to channel 145 and receiving module 150 is operable to receive symbols and possibly some data regarding their keys from channel 145. The value of K may be sent on channel 145 if used to determine association, or may be pre-set by encoder 115 and decoder 155 negotiation.

Channel 145 may be a real-time channel, such as a path through the internet, or a broadcast link from a television transmitter to a television receiver, or a telephone connection from one point to another, or channel 145 may be a storage channel, such as a CD-ROM, disk drive, website, etc. Channel 145 may even be a combination of a real-time channel and a stored channel, e.g., a channel formed when a person sends an input file from a personal computer to an Internet Service Provider (ISP) over a telephone line, the input file being stored on a web server and then sent to the recipient over the internet.

Where channel 145 comprises a packet network, communication system 100 may not be able to assume that the relative order of any two or more packets can be maintained in transmission over channel 145. Thus, the key for the output symbol may be determined using one or more of the above-described key schemes, and not necessarily by the order in which the output symbols left receiving module 150.

The receiving module 150 provides the output symbols to the decoder 155 and provides any data received by the receiving module 150 regarding the keys of these output symbols to the key regenerator 160. The key regenerator 160 regenerates the keys for the received output symbols and provides these keys to the decoder 155. Decoder 155 uses the keys provided by key regenerator 160 and the corresponding output symbols to recover the input symbols (again IS (0), IS (1), IS (2), … …). Decoder 155 provides the recovered input symbols to input file reassembler 165. input file reassembler 165 generates a copy 170 of input file 101 or a copy 175 of input stream 105.

When used in media streaming applications, the source packets that form the source media stream are sometimes grouped together, referred to as source blocks. For example, the source blocks may be a set of source packets spanning a fixed length of time, and, for example, a Reed-Solomon erasure code may be independently applied to the source blocks to produce repair packets that are transmitted to the receiver along with the original source packets of the source blocks.

At the receiver, the source stream may be successively segmented into source blocks as the source packets arrive, and repair packets are then generated for each source block and transmitted. Preferably, especially for live or interactive streaming applications, the total end-to-end delay added due to the use of FEC codes is minimized, and it is preferred if the overall design of the FEC scheme is such that the delay of source packets is as small as possible at the sender before sending them and that all source packets and repair packets of a source block are sent with as small a total delay as possible. It is also preferable if the rate of the FEC encoded stream is as smooth as possible, i.e. the fluctuation in the rate of the FEC encoded stream is as small as possible or at least not amplified by the fluctuation already in the original source stream, as this makes the bandwidth usage of the FEC encoded stream more predictable and will minimize the impact on the network and on other possible competing streams. It is also preferable if the data sent in the packets of a source block is distributed as evenly as possible over the period of time when the packets of the source block are sent, as this provides the best protection against burst loss.

At the receiver, if a packet is lost or received in error (e.g., checked or discarded using a CRC check), the repair packet can be used to recover one or more lost source packets, assuming that enough repair packets have been received.

In some applications, the packet is further partitioned into symbols to which FEC procedures are applied. For some FEC codes, particularly Reed-Solomon codes, the encoding and decoding time grow impractically with the number of coded symbols per source block, and there is usually an upper limit on the total number of coded symbols that can be generated per source block. Since symbols are usually put into different packet payloads when used at the application layer, this sets a practical upper limit on the maximum length of encoding of the source block, and it is of course also an upper limit on the size of the source block itself.

For many applications, when protection is to be provided over a long period of time or when the media stream rate is high, it is advantageous to provide protection over a source block size that is larger than what can be supported by carrying one symbol per packet. In these cases, using shorter source blocks and interleaving source packets from different source blocks provides a scheme that enables source packets from a single source block to be distributed over a larger period of time. Another related approach is to form longer symbols that cannot fit into a packet into a larger source block and to split the symbols into sub-symbols that can be placed into successive packets. By using this approach, larger source blocks can be supported, at the expense of possibly having different sub-symbol loss or corruption patterns for the symbols. However, in many cases where the channel exhibits bursty or strongly correlated impairments, the loss or corruption of the sub-symbols making up a symbol is highly correlated, so that the FEC protection provided sometimes has only little degradation when using this approach.

Term(s) for

FEC code

In the description herein, we assume that the data to be encoded (source data) has been decomposed into equal length "symbols", which can be of arbitrary length (as small as a single bit). The symbols may be carried over the data network in packets, where the total number of symbols is explicitly carried or implied in each packet. In some cases, the source packet may not be a multiple of the symbol length, in which case the last symbol in the packet may be truncated. In this case, for FEC coding purposes, it is implicitly assumed that the last symbol is elongated with a fixed bit pattern (e.g., zero valued bits), so that the receiver can fill the punctured symbol into a complete symbol even if these bits are not carried in the packet. In other embodiments, the fixed bit pattern may be placed in the packet, effectively stretching the symbol to a length equal to the packet length. The size of a symbol can be measured in bits, where the symbol size is M bits and the symbol is from 2^MSelected from a symbol system of symbols. Non-binary data are also contemplated, however, binary bits are preferred as they are more commonly used.

The FEC code we consider for the stream in this context is typically a systematic FEC code, i.e. the source symbols comprising the source block are transmitted as part of the source block encoding. The systematic FEC code then generates some repair symbols from the source block of source symbols, and the combination of the source symbols and repair symbols then becomes the coded symbols sent for that source block. Some FEC codes have the ability to efficiently generate the required number of repair symbols. Such codes are called "information adding codes" and "fountain codes", and examples of these codes include "chain reaction codes" and "multilevel chain reaction codes".

Other FEC codes, such as Reed-Solomon codes, can only actually produce a limited number of repair symbols from a limited number of source symbols. For these types of codes, the source block may still be relatively large, where the source block is partitioned into symbols of a size long enough so that the number of source symbols of the source block is at most an upper bound on the actual number of source symbols, and the expected number of repair symbols generated from the source block is at most an upper bound on the actual number of repair symbols. In case the symbols are larger than the appropriate size for physical layer packet transmission, the symbols may be further split into sub-symbols, which may be carried separately in such packets. To simplify the description that follows, symbols are typically described as indivisible units, however in many cases in this specification symbols may be divided into sub-symbols and the resulting methods and processes are quite similar to those described using symbols.

There are many other ways to carry symbols in packets and although the following description uses this example for simplicity, it is not meant to be limiting or comprehensive. In the context of the following description, the term "packet" is not intended to be limited to being literally represented as just a single unit of data. But is intended to encompass a broader concept to define a logical collection of symbols or portions of symbols that may or may not be transmitted as a single data unit.

In addition to symbol loss, there may be other forms of data corruption, for example, symbols in transmission changing their value or otherwise being corrupted, and the methods described below apply equally to these forms. Thus, although the following description generally describes symbol loss, the method is equally well applicable to other types of corruption and other types of FEC codes other than FEC erasure codes, such as FEC error correction codes and FEC checksum codes and FEC verification codes.

Flow of

To provide FEC protection for the source stream, the source stream may be a combination of one or more logical streams, examples of which are a combination of an audio RTP stream and a video RTP stream, a MIKEY stream and an RTP stream, a combination of two or more video streams, and a combination of a control RTCP traffic and an RTP stream. As the source stream arrives at the transmitter in a format such as a source bit stream, a source symbol stream, or a source packet stream, the transmitter may buffer the stream into source blocks and generate a repair stream from the source blocks. The transmitter arranges the source and repair streams, for example, in packets to be transmitted over a packet network and transmits them. The FEC encoded stream is a combined source and repair stream. The receiver receives the FEC encoded stream, which may be corrupted, for example, by loss or bit flipping. The receiver attempts to reconstruct some or all of the original source blocks of the source stream and makes these reconstructed portions of the original source stream available at the receiver, for example, to a media player.

For streaming applications, there are several key parameters that are input when designing how FEC codes are used to protect the source stream and several key metrics that are important for optimization.

Two key input parameters in this design are the guard period and the amount of protection. The transmitter guard period of a source block is the duration of time during which symbols generated from the source block are transmitted. The amount of protection for a source block is the number of FEC repair symbols sent for that source block, expressed as a fraction or percentage of the number of source symbols in that source block. For example, if the guard period is 2 seconds and the amount of protection is 20% and there are 10000 source symbols in a source block, then 10000 source symbols and 2000 repair symbols for that source block are sent over a time window of 2 seconds. Both the guard period and the amount of protection for each source block may vary from source block to source block. For example, when the source blocks preferably do not span between certain source packets in the source stream, e.g., when the first packet is the last packet of a group of pictures (GOP) in an MPEG2 video stream and the second consecutive packet is the first packet of the next GOP, then the source blocks may terminate after the first packet and before the second packet, even though this occurs before the end of the protection period. This allows the FEC protection block to be aligned with the video coding block, which may have many advantages, including minimizing receiver latency due to video buffering and FEC buffering. In other applications, it is advantageous to maintain the same guard period and/or source block size for each successive source block at all times for a number of reasons. In many of the descriptions below, both the guard period and the amount of guard are assumed to be the same for each subsequent source block for simplicity. It should be clear to those skilled in the art that this is not limiting, as one can readily determine after reading this specification how to apply the processes and methods described herein when the amount of protection or the period of protection, or both, varies from source block to source block, and when the source block size varies.

To simplify some of the subsequent description, it is generally assumed that the source symbols of the original stream arrive at the transmitter that is to perform FEC encoding at a steady rate, and that the receiver makes the subsequent source symbols available at the same steady rate as soon as the receiver makes the source symbols available at the receiver for the first time, assuming that there is no source symbol loss in the first source block from which the source symbols are received and that the loss of encoded symbols in each subsequent source block is at most the maximum possible amount to allow successful FEC decoding. This simplifying assumption is not inherent in the operation or design of the processes and methods described hereinafter, and it is in no way intended to limit these processes to this assumption, which is merely introduced as a tool to simplify the description of some of the characteristics of the processes and methods. For example, for a variable rate stream, the corresponding condition is that the rate at which the receiver obtains the source symbols is the same or nearly the same as the rate at which the source symbols arrive at the transmitter.

Some key metrics that are critical to minimization include transmitter delay, which is the delay introduced by the transmitter. For some applications, such as live video streaming or interactive applications (e.g., video conferencing), it is desirable to minimize transmitter latency. One solution to the overall design that helps minimize transmitter latency is to have the transmitter transmit the source symbols in the same order they arrive at the transmitter. Other designs for minimizing transmitter delay are described later.

Another important metric is channel switching time. This is the time between when the receiver joins or requests the stream and first begins receiving encoded symbols from the stream until the time when the receiver first obtains source symbols from the stream. In general, it is desirable to minimize the channel switching time because it minimizes the memory requirements at the receiver for storing the symbols before they are decoded and delivered by the decoder, and this also minimizes the amount of time between the incoming stream and the stream first becoming available (e.g., for video stream playback).

For many known systems, an important scheme for minimizing channel switching time is for the transmitter to maintain the original transmission order of the source symbols. In the following paragraphs, we describe a novel method for ordering and encoding the source symbols in a block, to apply FEC codes, and to transmit the encoded data for each source block in a manner that minimizes the channel switching time.

As we now describe, for many known systems, the channel switch time typically includes multiple components. An example of these components of a stream partitioned into sequential source blocks is shown in fig. 2. Fig. 2 shows a design that may be used in a typical IPTV deployment where there is a single source block per protection period, the repair symbols for each source block are sent immediately after the source symbols for that source block, and the example shows the case where the receiver joins the stream at the beginning of the source block. In this example, the two components of the channel switching time are the guard period and the decoding delay. The receiver guard period is the time during which the receiver buffers the received code symbols from the source block. Note that the transmitter protection period and the receiver protection period are the same if the channel between the transmitter and the receiver does not have any change in the amount of time it takes for each bit, byte, symbol, or packet to arrive at the receiver from the transmitter. Thus, in practice, the transmitter guard period may be different from the receiver guard period due to variations in network timing at the time of delivery. For simplicity of description, we assume hereinafter that the transmitter protection period and the receiver protection period are the same for each source block, and we use the term "protection period" synonymously for transmitter protection period and receiver protection period, i.e., we assume that the network delivery time is the same for all data, and we note that one skilled in the art can make the necessary changes to the methods and apparatus described herein to account for differences in transmitter protection period and receiver protection period due to network delivery fluctuations.

In these known systems, the guard period component of the receiver delay is mandatory because even if no source symbols are lost in the first source block, the source symbols must be made available at least after the guard period, in order to ensure smooth source symbol delivery for all subsequent source symbols when there is a loss of coded symbols in the subsequent source block. During this guard period, part or most or all of the FEC decoding of the source block may occur concurrently with the reception of the coded symbols. At the end of the guard period there may be additional FEC decoding that occurs before the first source symbol of the source block can be obtained from the receiver, and this time period is marked as decoding delay in fig. 2. In addition, even after the first source symbol is available, there may be additional FEC decoding before the second and subsequent source symbols of the source block are available. For simplicity, the additional FEC decoding is not shown in fig. 2, and it is assumed in this example that there is sufficient available CPU resources to decode all source symbols after the first source symbol at a sufficiently fast rate.

In these known systems, when the receiver joins the stream just in the middle of the source block, the channel switching time may be as small as the guard period plus the decoding delay when the source symbols from the first partial source block are not lost, as long as the transmitter maintains the original transmission order of the source packets. Therefore, for these known systems, it is desirable for the transmitter to maintain the original transmission order of the source symbols.

Another objective of the streaming approach is to minimize the FEC end-to-end delay, which is the worst total delay introduced by using FEC, between the time when the source packets are ready to be sent at the sender before applying FEC encoding and the time when the source packets are available for playback at the receiver after FEC decoding has been applied.

Another object of the streaming method is to minimize the fluctuation of the transmission rate when FEC is used. One reason for this is because in packet networks, at some point in a network with limited capacity, flows with fluctuating sending rates may be more susceptible to packet loss due to congestion or buffer overload caused by peaks in the sending rate of the flow coinciding with peaks in other traffic. The rate fluctuation of the FEC encoded stream should at least not be worse than the rate fluctuation of the original source stream and preferably the more FEC protection applied to the original source stream, the smaller the rate fluctuation of the FEC encoded stream becomes. As a special case, if the original stream is sent at a constant rate, the FEC encoded stream should also be sent at a rate as close to constant as possible.

Another object of the streaming method is to be able to use as simple logic as possible at the receiver. This is important in many cases because the receiver may be built into a device with limited computational, memory and other resource capacities. Also, there may be significant symbol loss or corruption in the transmission in some cases, and thus the receiver may have to recover from a catastrophic loss or corruption situation where there is little or no context to understand where reception of the stream should continue as conditions improve. Thus, the simpler and more robust the logic of the receiver will be the faster and more reliable the receiver will be able to start recovering the source symbols of the source stream from the received stream and making them available again.

When FEC encoded data to be transmitted for one source block is transmitted interleaved with data transmitted for other source blocks over a larger period of time, the transmission of FEC encoded data for that source block should be transmitted as evenly as possible over time to ensure that loss and corruption in the channel are best protected as possible.

The data transmission of the source blocks should be such that the receiver can timely recover the source data of the source blocks in a predetermined priority order.

The data sent for a flow should be sent with as little header information associated with the flow as possible in order to minimize header overhead. Preferably no header information is sent with the stream and some or all of the header information is derived or already available from other information embedded in the system and/or may be inferred from other information (e.g., the time at which the information arrived at the receiver).

In the following paragraphs, we describe methods, processes and apparatus that meet some or all of these objectives.

Improved transmitting and receiving method and apparatus

In some cases, data to be passed as blocks may be prioritized. In other cases, the data to be passed as blocks need not be prioritized. In any case, the original data stream is divided into source blocks, FEC repair data is generated for each such source block, and then the encoded data for each such source block (including the original source block data and the FEC repair data generated from that source block) is spread over a longer time than the original playout time of the source block (and thus, the encoded data for subsequent source blocks are interleaved with one another). In these cases, the applied FEC code may be an erasure code that protects the data in the stream against data loss by as much as desired, but other types of FEC codes are also envisaged, for example, FEC codes that are error correcting codes or FEC codes that can be used to verify the integrity of the data. In these cases, the longer the time for transmitting the encoded data for each source block of the stream (referred to as the guard period) and the more uniform the distribution of the encoded data over the guard period, the better the level of protection provided by the application layer FEC code against packet loss.

In one embodiment of the invention, encoded data is transmitted in equal-sized tiles (e.g., 120 bytes per tile), referred to herein as physical layer packets, in a physical channel. The physical layer packets may have a physical layer FEC code applied to the physical layer packets to protect each physical layer packet from damage. In some cases, a large number of physical layer packets are partitioned into slots, each slot having the same number of physical layer packets, e.g., 512 physical layer packets. The physical layer protocol may sometimes be used to distinguish and uniquely identify the physical layer packet in each time slot. In these cases, the FEC symbols may be mapped directly to the physical layer packets and the identification of which symbol is carried in which physical layer packet may be determined largely or entirely by the method used to determine the identity of the physical layer packet, which reduces or entirely eliminates the need to carry symbol identification data with the symbol data in each physical layer packet. In some cases it is preferable to carry part of the symbol identification data or some information about which part of the stream or which source block the symbol was generated from in the physical layer packet along with the symbol. For example, for a 121 byte physical layer packet, there may be 1 byte of such symbol identification data and the symbol size may be the remaining 120 bytes, however, it may be determined entirely how the symbols were generated from the original source symbol stream from a combination of the symbol identification data carried with the symbols in the physical layer packet and the method for uniquely identifying the physical layer packet, which may be identified, for example, by the location of the physical layer packet in the frame and/or by the identifier of the frame containing the physical layer packet and/or by the timing of receipt of the physical layer packet and/or the frame containing the physical layer packet. For example, the 1-byte identifier may identify the portion of the source block from which the symbol came, where different portions of the source block are marked, e.g., by which priority the data of the source block portion is in, and/or by which stream of the plurality of streams the source symbol came from.

Some improvements to the above process may be made if the repair packets are sent before the source packets, for example, as described in "FEC streaming". The cost of this approach is the introduction of additional delay at the transmitter, since the source packets are typically held in a buffer for transmission after the repair packets. As another example, repair data may be generated from all or a portion of the source blocks. For example, partial repair data may be generated from the entire source block, and other portions may be generated from one or more other priority layers of the source block. If the symbol identification data is carried with the symbol in a physical layer packet or an application layer packet (which may extend multiple physical layer packets), then a portion of the symbol identification data of the repair symbol may identify from which portion of the source block it was generated.

Signal transmitting method

In some embodiments, for each symbol, information about the symbol may be transmitted using header data (e.g., one byte of header data) associated with the symbol, e.g., a stream identifier when there are multiple streams, a segment identifier when the source block is to be transmitted over multiple physical layer blocks, a sub-block identifier when the source block includes multiple sub-blocks, a location of the symbol in the source block according to a symbol order of the symbol in the source block, etc. In some embodiments, some or all of this header data may be sent with each symbol in the physical layer packet. In other embodiments, most or all of the header data for each symbol is derived from other information, and little or no header data is sent with each symbol in the physical layer packet.

Symbols in source blocks

Preferably, the symbol order of the source blocks is determined explicitly or implicitly and the order is the same at the transmitter and receiver. For streaming or object delivery applications, some other preferred property of this order is beneficial. For example, one preferred characteristic may be that the symbol order of the source block is such that all source symbols are arranged foremost followed by all repair symbols. Another example is that the symbols are arranged in an order determined by the sub-block structure of the source block, e.g. all symbols associated with the first sub-block of the source block are arranged first, all symbols associated with the second sub-block of the source block are arranged in the second order, and so on. As previously mentioned, a symbol may also include multiple sub-symbols.

ESI in source block

The ESI (encoding symbol identifier) is an arbitrary identifier used to determine how to generate symbols from source blocks, in some cases in combination with other information such as the number of source symbols in the source block. ESI can be used explicitly to generate symbols at a sender or to identify and/or recover symbols at a receiver, or ESI can be used implicitly. Preferably, the symbols of each source block are ordered in such a way that the sender and receiver can determine the ESI of a given symbol based on its position in the symbol order. For example, if for a source block the symbol is the jth symbol in the symbol order, then it may be the case that the ESI of the symbol is j, where j is a positive integer.

Preferably, but not exclusively, the mapping between ESI of symbols and symbol order can be easily calculated by both the sender and the receiver. For example, consecutive ESIs of an ordered set of symbols may be 0, 1, 2, 3, … …, j +1, and so on, i.e., ESIs are consecutive integers starting from zero, and thus, in this case, the symbol positions are the same as ESIs. As another example, consecutive ESIs of an ordered set of symbols may be 5, 10, 15, 20, … …, 5 x j, 5 x (j +1), and so on. There are many other methods for determining the mapping of ESIs to ordered symbol sets that allow both the sender and receiver to determine the ESI of a given symbol, given the symbol position in the symbol order. Preferably, the sequence of ESI's that are easily computed by both the sender and the receiver can be used to represent the symbol order of the symbols associated with the source block.

Physical layer grouping in physical layer blocks

When sending physical layer packets in a physical layer block, the order of the physical layer packets in the physical layer block can be determined, typically by the characteristics of the overall architecture. Also, the difference of one physical layer block from another physical layer block may be determined by the transmitter and the receiver, e.g., based on timing information and physical layer signaling. The ordered symbols may be mapped to physical layer packets using a number of different methods, including linear congruential mapping, or using a mapping that ensures that consecutive symbols are mapped to physical layer packets to be transmitted in a time-diverse manner in the transmission of a physical layer block, e.g., each consecutive symbol is mapped to a physical layer packet transmitted in a different time quadrant in the transmission of a physical layer block, or consecutive symbols are mapped to physical layer packets transmitted using largely diverse sets of frequencies. The ordered set of symbols to be sent in the physical layer block may include: the symbol associated with the first segment identifier, followed immediately by the symbol associated with the second segment identifier, followed immediately by the symbol associated with the third segment identifier, and so on, where the total number of segment identifiers may be one or more. Among the symbols associated with each segment identifier, the symbols may be ordered by successively increasing ESI. A preferred property is to make the mapping between the ordered symbols and the physical layer packets in the physical layer block (explicitly or implicitly) known and easily determined by the transmitter and receiver.

As previously described, a symbol may include multiple sub-symbols, where each physical layer packet may be capable of carrying one or more sub-symbols, but may not be long enough to carry one symbol. In these cases, the aforementioned methods and procedures for mapping symbols to physical layer packets can be readily modified to further account for this problem. For example, the ESI may be modified to identify not only the symbol but also a particular sub-symbol in the symbol, e.g., the ESI is an identifier of both the symbol and the sub-symbol. As another example, the mapping may be such that the sub-symbols of the symbol are always sent consecutively, and the mapping from the ordered symbols to the physical layer packet identifies the physical layer packet carrying the first sub-symbol of the symbol.

In some cases, a large amount of signaling data is available in the physical layer block, e.g., the ability to derive the ESI of a symbol or the position of a symbol in the symbol order from the position of the physical layer packet in the physical layer block, the physical layer block identifier, and other information carried in the physical layer block header information.

In some embodiments of the invention, a symbol, which may be a source symbol or a repair symbol, is carried with a minimal amount of header identification data in each physical layer packet. The ordered set of symbols of the source block is sequentially mapped to physical layer packets in the physical layer block using a process well known to both the transmitter and the receiver. For example, an ordered set of 512 symbols may be mapped sequentially to 512 physical layer packets. The order of the symbols may be determined at the transmitter and transmitted explicitly out-of-band to the receiver, or is preferably implicitly communicated between the transmitter and the receiver by a predetermined process for determining the order of the symbols for each block. When symbols from multiple source blocks are to be mapped to a physical layer packet in the same physical layer block, the order of the symbols with respect to each source block, along with the order of the source blocks, may be used to determine the order of all symbols to be mapped to a physical layer packet in a physical layer block, if the source blocks are already ordered. In other embodiments, multiple symbols are carried in each physical layer packet. In other embodiments, the symbols may span multiple physical layer packets, for example, when the symbols are partitioned into sub-symbols and each sub-symbol is carried in a physical layer packet. Those skilled in the art will recognize that the processes and methods described herein may also be applied to other embodiments.

In some embodiments, the physical layer blocks may be blocks at different layers, such as logical blocks or data, or application-defined data blocks or transport block or media layer blocks. Also, the physical layer packet may be a transport packet or a logical packet or an application packet or a media layer packet. Those skilled in the art will recognize that these embodiments may have many substantially equivalent variations.

Segment of

Source symbols and repair symbols associated with a source block may be transmitted in multiple physical layer blocks. The segment identifier of the source symbol or repair symbol may be used to indicate in which physical layer block the symbol is carried relative to the first physical layer block carrying any symbol of the source block, preferably in reverse order. For example, all symbols associated with a source block carried in the last physical layer block carrying any symbol of the source block may have a segment identifier of 0, while the segment identifiers of all symbols associated with a source block in each preceding physical layer block may be 1 greater than the segment identifiers in subsequent physical layer blocks carrying any symbol of the source block. Note that not all consecutive physical layer blocks among the physical layer blocks carrying symbols of a particular source block may carry symbols of the source block, e.g., a first physical layer block may carry symbols of a source block, a next second physical layer block may not carry any symbols of the source block, and a still next third physical layer block may carry symbols of the source block. In other cases, the segment structure of a source block may be conveyed by indicating, for example, the physical layer packet position in the physical layer packet order or a physical layer block as a segment boundary indicator (which is used to indicate the end of a segment of one source block and the start of a new segment of another source block). For example, for a physical layer block having 2000 physical layer packets, where the first 500 physical layer packets correspond to segments from a first source block, the next 600 physical layer packets correspond to segments from a second source block, and the remaining 900 physical layer packets correspond to segments from a third source block, the segment boundary indicators 500, 600 may be used to indicate that the segments of the first source block correspond to the first 500 physical layer packets, the segments of the second source block correspond to the next 600 physical layer packets, and the segments of the third source block correspond to the remaining 900 physical layer packets. Alternatively, the segment boundary identifier may be expressed in units of symbols and may be determined with respect to the order of symbols in the physical layer block.

In some preferred embodiments there is at most one source block associated with each segment identifier in each physical layer block, and so the symbol can be uniquely distinguished from different source blocks using the segment identifier, and so in these cases the segment identifier is also used as a source block identifier for distinguishing symbols carried in the physical layer blocks. In other embodiments, the source block identifiers of the symbols are carried by other means, for example by including the source block identifiers in header data associated with each symbol or by including the source block identifiers in header data associated with each physical layer block. There are other variations in which the source block identifier need not be carried in the header of a physical layer block, but may instead be carried elsewhere in a separate physical layer block (e.g., in a control data stream) containing header information for multiple physical layer blocks, or sent via other networks. Those skilled in the art will recognize many other similar variations.

Sub-blocks

The encoded or unencoded source block may include a plurality of sub-blocks, e.g., sub-blocks corresponding to different source symbols and repair symbols associated with the source block, where the source symbols and repair symbols correspond to logically associated portions of the symbols. For example, a first set of source and/or repair symbols comprising a first sub-block may correspond to a portion of a source block that may be used to present lower resolution video to a portion of video associated with the source block, while a second set of source and/or repair symbols comprising a second sub-block, when used in conjunction with some or all of the first sub-block, may present higher resolution video to the portion of video associated with the source block. As another example, the sub-block identifier may identify some or all of the repair symbols associated with the source block, or the sub-block identifier may identify some or all of the source symbols associated with the source block. In some cases, the sub-block identifier may be represented by explicitly marking each sub-block with a number. For example, a first sub-block of a source block may have a sub-block identifier of 0, while a second sub-block of the source block may have a sub-block identifier of 1. In other cases, the sub-block structure may be represented by indicating, for example, ESI or a symbol position in symbol order as a sub-block boundary indicator indicating the end of one sub-block and the start of a new sub-block in ESI or symbol order. For example, for a source block with 900 source symbols and 100 repair symbols, where the ESI of the symbols is a continuous integer starting from zero, and where a first sub-block includes the source symbols and a second sub-block includes the repair symbols, a sub-block boundary indicator 900 may be used to indicate that the first sub-block corresponds to symbols for ESI from 0 to 899, and the second sub-block starts with symbols for ESI of 900. The subblock identifier of the source or repair symbol indicates which subblock the symbol is a part of.

Method for transmitting header data together with each symbol

In one embodiment, the header data associated with each symbol to be sent with the symbol in the physical layer packet includes a segment identifier, a sub-block identifier, and an ESI. For example, if the number of possible segment identifiers is 8 and the number of possible sub-block identifiers is 8 and the number of ESIs is 1024, then 16 bits or equivalently 2 bytes of header data is sufficient for each symbol. In each physical layer packet in the physical layer block, the contents of the physical layer packet include a symbol and header data associated with the symbol, where the header data includes a segment identifier and a sub-block identifier.

In this embodiment, the receiver may process the physical layer packets in the received physical layer blocks as follows. After receiving the physical layer packets in the physical layer block, the receiver makes a determination based on the header data associated with the symbols in each physical layer packet it can read. From the header data, the receiver may determine the segment identifier, sub-block identifier, and ESI of the symbols contained in the physical layer packet. From the segment identifier, the receiver can determine which source block the symbol is associated with from among the possible source blocks. From the sub-block identifier, the receiver may determine which sub-block the symbol is associated with from the possible sub-blocks of the source block. Based on the ESI, which can be used to determine the symbol position in the source block and/or to recover lost source symbols from received repair symbols and other source symbols at FEC decoding, the receiver can determine the relationship of the symbols to the source block and to the sub-blocks of the source block.

The receiver may then decide on certain actions based on this information. For example, the receiver may use the sub-block data associated with the symbol for different purposes. For example, the sub-block data may be used in part to determine how to FEC decode to recover some or all of the source blocks. The sub-block data may also be used, for example, to determine which part of the data should be passed to an upper layer application (e.g., a multimedia player process in the receiver) in order to support higher level functionality in the receiver, e.g., to determine which part of the recovered source block to pass to the multimedia player as a whole for multimedia play. For example, when a receiver receives a first physical layer block, the portion of the symbol associated with the first segment identifier may be associated with a first sub-block that may be passed to a multimedia player to play the portion of the low quality video associated with the source block associated with the first segment identifier. The receiver may also decide to save the extracted and/or recovered symbols associated with source blocks having segment identifiers other than the first segment identifier, to combine them with symbols of the same source block received in a subsequent physical layer block, and to combine these symbols for FEC encoding and/or delivery to the media player, possibly in units of symbol sub-blocks or symbol sub-block sets.

Those skilled in the art will recognize that there are numerous variations and combinations of the above-described embodiments. For example, the symbol header data sent with the symbol may include the segment identifier and the sub-block identifier without the ESI. As an example of another variation, the ESI is sent with only the symbol in the header data, and other data such as a segment identifier or sub-block identifier may be determined from other data, if used.

As an example of another variation, the header data associated with each symbol may not include a sub-block identifier. In this case, the sub-block identifier may be determined implicitly, e.g., by derived ESI, or the sub-block identifier coincides with a segment of the source block, or no sub-block is used.

As an example of another variation, the header data associated with each symbol may not include a segment identifier. In this case, for example, the segment identifier may be determined implicitly by allocating a fixed number of physical layer packets in each physical layer block, or the sub-blocks coincide with the segment, or the segment is not used.

As another example variation, the header data associated with each symbol may also include a stream identifier. In this case, the stream identifier may determine which of several streams a symbol is associated with, for example, an audio stream or a video stream. Note that the stream identifier may be governed by other identifiers (scope), e.g., if the streams are logically connected, such as audio and video streams for the same program segment, then the sub-block identifier may govern some or all of the stream identifiers, for example. Note that the stream identifier may also govern other identifiers, for example, if the streams are logically independent, such as audio/video streams for different program segments, then the stream identifier may govern some or all of the sub-block identifiers, for example.

Method for transmitting without header data with each symbol

In another embodiment, there is no header data associated with the symbols carried in the physical layer packet. Instead, some minimal data may be carried in the header data of the physical layer block instead. The minimum data may include, for example, a segment table, wherein each row of the segment table corresponds to a segment identifier including a number of symbols of a source block segment carried in the physical layer block and an ESI of a first symbol in a symbol order of the source block segment among all symbols of the source block segment carried in the physical layer block. The number of symbols in a segment may not be included in some embodiments, for example, because the number of symbols in each segment is always the same in all physical layer blocks.

In some embodiments, where the same segment identifier is used for two or more source blocks in the same physical layer block, the segment table may instead be a source block table.

The minimum data may also include, for example, a sub-block table indicating which sub-block of each source block's symbols are carried in the physical layer block. The sub-block table may take many forms, for example, sub-block information may be appended to each appropriate segment identifier row in the segment table, or as another example, sub-block information may be stored in a separate table. In some embodiments, the sub-block table may not be included, for example because sub-blocks are not used or because sub-block signaling is handled at a higher application layer.

In this embodiment, the receiver may process the physical layer packets in the received physical layer blocks as follows. The receiver reads the segment table and/or sub-block table from the physical layer block header data and stores it. The receiver may determine from the segment table the number of symbols and initial ESI associated with each segment of the source block (where the symbols of the segment are carried with the physical layer block). From the physical layer identification of the location of the physical layer packet carrying the symbol, from the segment table containing the number and initial ESI associated with each segment, and from the mapping of the combined ordered set of symbols in all segments of the source block contained in the physical layer block to the physical layer packet, the receiver can determine the ESI of the symbol and which source block the symbol is associated with. From the sub-block table, the receiver may determine which sub-block of the source block the symbol is associated with in a similar manner.

Based on the ESI, the receiver can determine the relationship of the symbol to the source block and to the sub-blocks of the source block, wherein the ESI can be used to determine the symbol position of the symbol in the source block and/or to recover the non-received source symbols and other source symbols from the received repair symbols upon FEC decoding.

The receiver may then decide, based on this information, certain actions, including those described above for the "header data sent with each symbol" method described herein.

Those skilled in the art will recognize that there are numerous variations of the above. As a variant example, the header data associated with each symbol may include a sub-block identifier, e.g., a portion of one byte of each physical layer packet is used for this purpose. In some cases, this may be preferable since the sub-block structure spans the entire source block, while the transmission of data for the source block may be over several physical layer blocks, and thus carrying the sub-block identifier in the header data transmitted with each symbol may allow a receiver joining the channel in the middle of the source block transmission to quickly understand the sub-block structure of the source block.

As another example, sub-blocks may not be used.

As another example, the header data associated with each physical layer packet may be sent, for example, as separate data in the same physical layer block, or may be transmitted to the receiver by other means, such as in a control channel available to the receiver, or, as another example, in a separate physical layer block containing header information for multiple physical layer blocks, or, as another example, via another network.

As another example, the header data associated with each symbol may include a stream identifier. In this case, the stream identifier may determine which of several streams a symbol is associated with, for example, an audio stream or a video stream. Note that the stream identifier may be governed by other identifiers, for example, if the streams are logically connected, such as audio and video streams for the same program segment, then for example, the sub-block identifier may govern some or all of the stream identifiers. Note that the stream identifier may also govern other identifiers, for example, if the streams are logically independent, such as audio/video streams for different program segments, then the stream identifier may govern some or all of the sub-block identifiers, for example. The flow identifier may also be included in the header data of the physical layer block in a format similar to that described above for the segment identifier and the sub-block identifier, in which case the flow identifier does not have to be included in the header data associated with each symbol in order to communicate the flow structure to the receiver.

As an example, assume that the number of segments per source block is 4, the number of sub-blocks is 3, the number of physical layer packets per physical layer block is 512, and three symbols of size 100 bytes are included in each physical layer packet of 300 bytes, and thus, the physical layer block contains 3 × 512-1536 symbols. Then, a first segment table for a particular first physical layer block and a second segment table for a second physical layer block may be as shown in fig. 3, wherein the second physical layer block is transmitted consecutively after the first physical layer block. In this example, the segment identifier may not be explicitly carried in the segment table, but instead is implied by a row number in the table, i.e., row j corresponds to segment identifier j.

In the first segment table, the segment with identifier 0 has a number of symbols of 450, which is carried by 150 physical layer packets, where the first 450 symbols are mapped according to the mapping of the sorted symbols to the physical layer packets. In this example, the ESI of a symbol with a segment identifier of 0 is a consecutive integer from 0 to 449. The number of symbols of segment with identifier 1 is 300, which is carried by 100 physical layer packets after the first 150 physical layer packets, the 300 symbols being mapped according to the mapping of the ordered symbols to physical layer packets. In this example, the ESI of a symbol with a segment identifier of 1 is a consecutive integer from 420 to 719.

In the second segment table, the number of symbols of the segment with identifier 0 is 420, which is carried by 140 physical layer packets, the first 420 symbols being mapped according to the mapping of the sorted symbols to the physical layer packets. Note that for j ═ 0, 1, 2, the source block with segment identifier j in the first segment table may be the same as the source block with segment identifier j +1 in the second segment table. Thus, under this mapping, the initial ESI of the segment in the first segment table with identifier j is the sum of the initial ESI and the number of symbols of the segment in the second segment table with identifier j + 1.

There are other variations that do not require data to be carried in the headers of the physical layer blocks, but instead carry data elsewhere, such as in a control data stream, in a separate physical layer block containing header information for multiple physical layer blocks, or via other networks. Those skilled in the art will recognize many other variations of the above-described method.

Mapping to and from FEC payload IDs

For many application layer FEC codes described in the standards, for example, as described in IETF RFC 5052 (internet engineering task force requirements annotation 5052) and IETF RFC 5053 (internet engineering task force requirements annotation 5053), typically, the FEC payload ID (identifier) is associated with a symbol or group of symbols or sub-symbols sent in an application layer packet. For the simplest case, when the FEC payload ID is associated with a symbol, the FEC payload ID includes the source block number used to generate the symbol, the ESI of the symbol, and in some cases also the initial ESI of the repair symbol with the smallest associated ESI (and this initial ESI may be considered a sub-block identifier identifying that the source symbol is part of a first sub-block and the repair symbol is part of a second sub-block).

In some of the above methods and processes, the FEC payload ID is not transmitted with each symbol, but rather describes other means of minimizing the amount of header data transmitted with each symbol in order to maximize channel capacity. In some cases it may be useful at the transmitter to convert the transmission format from one using the FEC payload ID to one using the above-described means for conveying this information to the receiver. In some cases it may also be useful at the transmitter to convert the transmission format from one using the above-described means for conveying this information to the receiver to one using the FEC payload ID. For example, software may have been developed that uses the FEC payload ID to identify symbols, and it is convenient to use the output symbol stream and associated header data produced by the software to produce an output symbol stream and associated data that is compatible with the transmission format using the above-described means.

The mapping method to and from the FEC payload ID format can be easily derived from the description provided above.

Transmitting configuration to optimize channel switching

For a prioritized stream to be transmitted over a channel, where the data to be transmitted is partitioned into different physical layer blocks, e.g., frames or superframes, the symbol data to be transmitted for the source block may be interleaved over a plurality of such physical layer blocks in a prioritized manner in reverse order of their priority. For example, as described in "FEC streaming", repair data for a source block may be sent before source data for the source block in order to reduce channel switching time in the context of these descriptions. Data comprising data at a given priority level of the source block may be aggregated together into sub-blocks. For example, continuing the above example, the repair symbols may be considered a lower priority sub-block and the source symbols may be considered a second highest priority sub-block, and thus, the lower priority sub-block may be transmitted before the higher priority sub-block.

Fig. 4 shows an example of how an embodiment may prioritize data into sub-blocks and map the sub-blocks to prioritized transmission orders. In fig. 4, data stream 470 is represented by various data blocks and data sub-blocks. For example, data stream 470 is shown having audio block 450 and various video blocks (e.g., I-frame (ZI)410) and various sub-blocks of symbol data (e.g., P)₁-P_x 420-422、b₁-b_z430, 435 and B₁-B_y440-442). In FIG. 4, P₁420 denotes the highest priority sub-block in the stream followed by b respectively₁-b_z 430-435、B₁-B_y 440-442、P₂-P_x421-. Given these priority levels, the blocks and sub-blocks of the stream may be arranged as shown in transmit configuration 480. The lowest priority block (ZI 410) may be sent to the receiver at the beginning of the transmission and the highest priority data (P) may be sent last₁420). In addition, when creating prioritiesThe hierarchical transmission order may also take into account dependencies between the various sub-blocks. For example, according to some embodiments, sub-block b₁、B₁And b₂Can depend on P₁. In these embodiments, P is sent₁It is advantageous to send these dependent sub-blocks before. Thus, upon receipt of P₁，P₁All of the data in and all of its dependent sub-blocks may quickly become available at the receiver. After the transmit configuration is determined, the transmit configuration may be used to divide the data into different physical layer blocks accordingly.

One method for mapping prioritized sub-blocks into physical layer blocks is to map sub-blocks into each physical layer block. Fig. 5 shows an embodiment of the method. Fig. 5 shows a data set 500 that is decomposed into various physical layer blocks 501-504. The blocks in fig. 5 are shown as being transmitted in the direction indicated by arrow 509. For example, physical layer block 501 is sent before physical layer block 504 (and, therefore, before physical block 504), and in physical layer block 501, section 580 is sent before section 520. As shown in fig. 5, some data 500 is placed into each of the physical layer blocks 501-504. For clarity, each data segment in data 500 is shown as being placed into only one of physical layer blocks 501-504, even though each segment is placed into a corresponding section of each physical layer block. FEC data 510 is placed in the physical layer block at 520 and 523; p₁Data 420 is placed in physical layer block 540-; b₁-b_zThe data 430 and 435 are placed in the physical layer block at 530 and 533; b is₁-B_yData 440-442 is placed to physical layer block 550-553; p₂-P_xData 421 + 422 is placed into physical layer block 560 + 563; audio data 450 is placed into physical layer block at 570-; the I-frame (ZI)410 is placed at 580-583 of the physical layer block. One advantage of mapping sub-blocks to physical layer blocks in the manner shown in fig. 5 is that the play-out behavior at the receiver will be more predictable, since the segments of each priority group will be contained in each physical layer block. However, the segments in each physical layer block will typically have different sizes, since the priorities are differentThe level classes will typically contain different amounts of data. This can lead to potential performance problems at the receiver due to the more complex process of unpacking the data at the receiver, and can present a sta-mixing (stat-muxing) problem due to the different segment sizes.

Another approach is to distribute the symbol data across the different physical layer blocks as uniformly as possible, since this approach generally provides the best protection against channel impairments. An example of one embodiment of the method is shown in fig. 6. Fig. 6 shows a data set 600 that is broken down into various physical layer blocks 601-604. The blocks in fig. 6 are shown as being transmitted in the direction indicated by arrow 609. For example, physical layer block 601 is sent before physical layer block 604 (and thus, before physical block 604), and in physical layer block 601, section 640 is sent before section 610. As shown in fig. 6, the various data priorities in the symbol data are aggregated together into block 605-608. These blocks 650-608 are in turn mapped to an equal amount of physical layer blocks 601-604. For clarity, each segment of data 600 is shown as being placed into only one of physical layer blocks 601-604, even though each segment is placed into a corresponding section of each physical layer block. For example, block 605 is mapped to 610-; block 606 is mapped to 620 and 623; block 607 is mapped to 630-633; block 608 is mapped 640-643. The mapping shown in fig. 6 results in some sub-blocks being partitioned between multiple clusters. For example, data segment B₁-B_y440, 442 may be included in both blocks 606 and 607. In addition, a given physical block may not contain any data from a particular priority. For example, block 601 may not contain any FEC 510 data at 610, while block 604 may not contain data from P at block 613₁420, or any other data. One advantage of the method shown in fig. 6 is that since the segments of the physical layer block have the same size, the receiver will require less processing to unpack the segments. This may result in improved receiver performance. In addition, uniform segment size makes the stara mixing easier. However, since there may not be any guarantee of the exact priority to be contained in any given physical layer block, the play-out behavior at the receiver will be less predictableAnd (6) measuring.

One concern when mapping data is to send enough high priority data of the source blocks in the first physical layer block to allow the receiver to start playing as soon as possible after receiving the high priority data. In the case where high priority data for some source blocks should be available after the receiver receives the first physical layer block, one way to achieve this concern is to prioritize the data in the encoded or unencoded source blocks such that the amount of high priority data is at most 1/N of the total number of data to be transmitted for the source block, where N is the number of physical layer blocks to which data is to be transmitted for the source block. In general, if it is required that data of the first J priorities must be available for some first source blocks after the receiver receives K physical layer blocks, this is achievable if the fraction of data in the first J priorities is at most K/N.

An example of a preferred segmentation strategy, which can be used regardless of whether the above-described method is applied, is as follows. It is assumed that transmitted source block data is to be transmitted in N physical layer blocks, where the transmitted data includes source symbols of the source blocks and FEC repair symbols (if any) generated from the source blocks to be transmitted. It is assumed that the transmitted source block data is divided into K priorities, where for j ═ 1, … …, K, the portion transmitted with priority j is P _ j.

As described above, data transmitted with priority j may be aggregated into a sub-block, referred to as sub-block j. The part of the transmitted data that is transmitted in the last physical layer block may then be the maximum of P1 and 1/N, i.e. all data in the highest priority sub-block 1 and possibly some remaining data is transmitted in the last physical layer block N. Let M _1 be the maximum value, and let L _ 1-M _1 be the remaining part of data to be sent in the physical layer blocks N-1, … …, 1 after the M _1 part of data was transmitted in the last physical layer block N. The portion of the transmit data transmitted in physical layer block N-1 may then be the maximum of P _1+ P _2-M _1 and 1/N-1, i.e., all of the highest priority and next highest priority sub-blocks and possibly some of the remaining data are transmitted in the last two physical layer blocks. This assumes that the first two priority data are to be played at the receiver after the two physical layer blocks are received.

The method can be extended to determine which transmit data to send in each physical layer block. The method can also be extended to a case where the receiver requirements for the receiver to play the transmission source block data are different, e.g., playing the transmission data of priority 2 after receiving 3 physical layer blocks instead of 2 physical layer blocks. The above method can be modified as needed to multiplex many different streams or streams of streams on the same physical channel, where the amount of space available in each physical layer block is used to determine how much of each priority of transmitted data of each stream or stream of streams is to be transmitted in each block.

Note that the above priorities do not necessarily describe a complete order, i.e. the priorities may be partial orders, in which case there are a number of options in which to place prioritized data, and indeed prioritized data that cannot be compared in terms of priority may be mixed together in the order of transmission in some embodiments.

As noted above, any of the proposed transmission configurations may be implemented using any of the improved transmission and reception methods and processes described herein, e.g., ESI, including header data transmitted with each symbol or no header data transmitted with each symbol, etc.

Partial FEC encoding of source blocks

FEC repair data may be generated from the entire source block and may provide the ability to recover all or most of the source block if enough source symbols are received from the source block plus repair symbols generated from the source block. The FEC repair data may be generated from only a portion of the source blocks, e.g., one set of FEC repair data may be generated from a first portion of the source blocks and a second set of FEC repair data may be generated from a second portion of the source blocks. As an example, the second portion of the source blocks may include the first portion of the source blocks plus some additional portions of the source blocks. It is assumed that the source symbols of a source block are divided into low priority source sub-blocks and high priority source sub-blocks. Then a first sub-block of FEC repair symbols may be generated from the high priority source sub-block and a second sub-block of FEC repair symbols may be generated from the combination of the low priority source sub-block and the high priority source sub-block. Then, the order of transmission of the sub-blocks may be: a second sub-block of FEC repair symbols, a low priority source sub-block, a first sub-block of FEC repair symbols, a high priority source sub-block. In this case, if the receiver receives only all or part of the high priority source sub-blocks, it may attempt to play it out immediately, as long as there is not much corruption. If the receiver receives all or part of the first sub-block of FEC repair symbols and the high priority source sub-block, the receiver may attempt to recover the high priority source sub-block using the first sub-block of FEC repair symbols as long as there is not much corruption. If the receiver receives all or part of the low priority source sub-block, the first sub-block of FEC repair symbols, and the high priority source sub-block, the receiver may attempt to recover the corrupted portion of the high priority source sub-block using the first sub-block of FEC repair symbols and then send the received portion of the low priority source sub-block and the recovered portion of the high priority source sub-block to the media player. If the receiver receives all or a portion of all 4 sub-blocks, the receiver may use all FEC repair symbols to recover all source symbols.

Note that it may be more preferable that the above method is used to provide FEC protection on each sub-block separately, e.g. it may be more preferable to instead have the second sub-block of FEC repair symbols protect the entire source block and not just the low priority source sub-block. For example, assume that each of two source sub-blocks includes 100 source symbols, respectively, and each of two FEC repair sub-blocks includes 50 repair symbols, respectively. Using the above method, it is possible to allow recovery of the entire source block even when 60 source symbols in the high priority source sub-block are lost and 30 source symbols in the low priority source sub-block are lost, however, if the two source sub-blocks are independently protected by two FEC repair sub-blocks, recovery of the high priority sub-block is not possible (60 source symbols of the source sub-block are lost, only 50 repair symbols protect the sub-block). For example, the FEC protection may be implemented using Reed-Solomon codes, which experiments show that they exhibit near-ideal recovery characteristics when used to protect overlapping sub-blocks in the manner described above.

Protection by these methods is also useful in cases where protection over a long period of time results in occasional exceedance of the entire data reception time period. It may be more preferable to provide FEC protection on shorter blocks instead, and then on longer blocks that include the shorter blocks. Thus, if the excess does not cause too many losses in adjacent time periods, then FEC protection across shorter blocks may allow those short blocks to be recovered, whereas additional FEC protection across longer blocks allows more losses over longer time periods.

Receiving multiple physical layer block streams

For streaming applications where logically contiguous streams are sent on a single stream of physical layer blocks, the entire physical channel may include multiple such physical layer block streams. For example, there may be 256Kbps or 1Mbps per physical layer block stream, however, there may be 50 such streams, so that the entire available physical channel may be 12.5 to 50Mbps in this example.

Typically, a receiver can receive one of the physical layer block streams at a time for a variety of different reasons, including power issues and memory issues. However, it may be advantageous for the receiver to receive multiple physical layer block streams. For example, if the receiver receives all of the stream, a channel switch from one stream to another can occur almost immediately, and the new stream to which the receiver is moving can be played from the beginning of the highest priority because all of the data for the new stream has already arrived for some time before the receiver changes channels to the stream. This is true even if the stream is protected using FEC protection with a long protection period, or if the stream is video encoded in a highly compressed manner, for example, when update frames (sometimes called I-frames, sometimes called IDR-frames (independent data update frames)) in the video stream are sent infrequently due to their excessive size. This typically means that the time spanned by a GOP (group of pictures) in a highly compressed video stream can be quite large. For example, the GOP duration of the video stream may be 10 seconds, and FEC protection may be provided to protect the entire GOP for 10 seconds. In this case, instead of using some of the above methods, where high priority data from the stream is displayed as quickly as possible, and then lower and lower priority data is also displayed to enhance the play-out quality, the channel switching time may be up to 10 seconds if the receiver receives only one channel at a time, whereas the channel switching time may be almost instantaneous if the receiver receives all channels.

When considering a solution where the receiver receives multiple physical layer packet streams simultaneously, there may be some optimizations. For example, the receiver only needs to FEC decode the stream currently being transmitted to, for example, a media player for playing, e.g., perform error correction decoding or erasure protection decoding. The data of the other streams can be stored and FEC decoded only when the receiver changes channels, and then FEC decoding can occur very quickly on the data already received for the new channel to start media playback almost immediately.

As another possible optimization, when a receiver receives only one stream at a time, there may be redundant data included in a stream that is not needed if the receiver already has a previous portion of the stream available for playback when the receiver first joined the stream. An example of this redundant data may be low quality video IDR frames, which are very often included alone in a video stream so that a receiver can add streams and can play some streams almost immediately, even at reduced quality. If the receiver has a previous portion of the stream that includes a high quality IDR frame and all subsequent frames sent earlier, then the often low quality IDR frame may not need to be included. Low-quality IDR frames may use a significant amount of available bandwidth, for example, if each low-quality IDR frame is 3KB and is sent once per second in a 256Kbps stream, the low-quality IDR frames use more than 9% of the available bandwidth. A low quality IDR frame is not necessary if the receiver is receiving data of the stream before the channel is changed to the stream to which the receiver is going to change.

One drawback of listening to multiple streams of a physical layer block is that more power is used at the receiver than listening to a single stream. In addition, more memory and other resources are required to store data received from multiple streams than a single stream. There are some ways to minimize these disadvantages. One such approach is to globally organize logic and/or data over available streams in a manner in which a receiver need only receive a small number of streams at a time to achieve the above benefits.

For example, if there is logic to predict which stream the receiver is most likely to change the channel to, the logic may cause the receiver to receive the channel before actually changing to those possible channels.

As another example, the data in the physical layer block streams may be organized such that there is one physical layer block stream carrying all IDR frames for all other video streams, referred to as IDR streams, and then each other physical layer block stream carries all data of one of the video streams except the IDR frame of that video stream. In this example, the receiver may be receiving the current physical layer block stream of the video stream currently being played by the media player, while (always or immediately at the appropriate time) receiving the IDR stream. Accordingly, the receiver may make available IDR frames of all or some of the video streams, where the receiver may use them for playback when displaying information about all or some of the video streams available in thumbnail channel guide mode, or for starting to display a new video stream when a channel change is made at the receiver. The IDR stream may be received all the time or may be received intermittently, e.g., only physical layer blocks from the IDR stream containing IDR frames for the currently playing video stream. In all cases, FEC protection may be provided on each physical layer block stream if desired. One advantage of these methods is that the receiver receives at most two physical layer block streams at any point in time and still obtains all or most of the advantages of receiving all physical layer block channels simultaneously.

While the invention has been described with respect to exemplary embodiments, those skilled in the art will recognize that numerous modifications are possible. For example, the processes described herein may be implemented using hardware components, software components, and/or combinations thereof. For example, the methods described herein may be embodied on a computer-readable medium, such as a CD-ROM, DVD, or the like, that includes computer-executable code for directing a processor of a computer to perform the methods. Therefore, while the invention has been described with respect to exemplary embodiments, it will be understood that the invention is not intended to cover all modifications and equivalents falling within the scope of the appended claims.

Claims (20)

1. An electronic delivery system for delivering a data stream over a broadcast channel, wherein the broadcast channel is a channel for transmitting signals from one or more sources to a plurality of receivers, wherein each receiver attempts to receive substantially the same signal, the electronic delivery system comprising:

a transmitter system that transmits data of the data stream in a physical layer packet of a physical layer block, wherein the indication indicating how the transmitted data relates to the data stream is based at least in part on the physical layer block.

2. The electronic delivery system of claim 1, wherein the indication of how the transmitted data relates to the data stream is based at least in part on information in a header in the physical layer block, wherein the transmitter system configures the header of the physical layer block to include the indication.

3. The electronic delivery system of claim 1, wherein the indication of how the transmitted data relates to the data stream is based at least in part on information in a header in the physical layer packet.

4. The electronic delivery system of claim 1, wherein the transmitted data is organized into symbols in a data block source, and wherein the indication comprises an indication of how to generate symbols from the source blocks and an indication of an association between symbols and source blocks.

5. The electronic delivery system of claim 4, wherein the indication is a coded symbol identifier, wherein the coded symbol identifier is carried at least in part in a header of a physical layer block.

6. The electronic delivery system of claim 4, wherein the indication is a code symbol identifier, wherein the code symbol identifier is carried in a control data channel.

7. The electronic delivery system of claim 4, wherein the association between the symbol and the source block is determined largely from a header of the physical layer block.

8. The electronic delivery system of claim 4, wherein the transmitted data symbols comprise FEC repair data generated from a source block.

9. The electronic delivery system of claim 4, wherein the plurality of logical data streams are transmitted in a single stream of physical layer blocks.

10. The electronic delivery system of claim 4, wherein the transmitted data symbols are transmitted on a stream of multiple physical layer blocks.

11. The electronic delivery system of claim 4, wherein the indication indicating how the transmitted data symbols relate to the stream or object data is carried at least in part in a physical layer packet carrying the transmitted data symbols.

12. The electronic delivery system of claim 4, wherein the data transmitted for a source block is organized into different sub-blocks having different priorities.

13. The electronic delivery system of claim 12, wherein the indication of the sub-block structure of the source block is determined largely from a header of the physical layer block.

14. The electronic delivery system of claim 12, wherein the indication of the sub-block structure of the source block is determined largely from a header of a physical layer packet carried in the physical layer block.

15. The electronic delivery system of claim 12, wherein the transmitted data symbols comprise FEC repair data generated from different sub-blocks and combinations of sub-blocks.

16. The electronic delivery system of claim 12, wherein sub-blocks having priorities are used to determine the order of transmission of the sub-blocks.

17. The electronic delivery system of claim 12, wherein the sub-blocks are mapped to the physical layer block using sub-blocks having priorities.

18. The electronic delivery system of claim 17, wherein the prioritized sub-blocks mapped to the physical layer block are partitioned between different physical layer blocks.

19. A method of transmitting data from a transmitter to a receiver in an electronic delivery system for delivering a data stream over a broadcast channel, wherein the broadcast channel is a channel for conveying signals from one or more sources to a plurality of receivers, wherein each receiver attempts to receive substantially the same signal, the method comprising:

transmitting data of the data stream from the transmitter in a physical layer packet of a physical layer block, wherein the indication indicating how the transmitted data relates to the data stream is based at least in part on the physical layer block.

20. A computer readable medium comprising computer readable code for performing the method of claim 19.