WikiPatents - Community Patent Review
Create Free Account  |  License or Sell Your Patent  |  WikiPatents Marketplace  |  WikiPatents Blog
Username:  Password:  
    
Advanced Search
Method and apparatus for transmitting MPEG data at an adaptive data rate    
United States Patent5881245   
Link to this pagehttp://www.wikipatents.com/5881245.html
Inventor(s)Thompson; Kenneth M. (Altanta, GA)
AbstractA method and device for communicating encoded data (such as MPEG encoded data for example) from a server to a decoder via a buffer. The rate at which the server provides the encoded data are adjusted based on a state of the buffer such that the buffer does not overflow or run dry, even when the communication of the data is subject to drift. Specifically, when the buffer is below a predetermined level, the rate at which the server provides the encoded data is increased. On the other hand, when the buffer is above a predetermined level, the rate at which the server provides the encoded data is decreased.
   














 Title Information Submit all comments and votes
 
Patent Text Patent PDF Print Page Summary File History
Plain text PDF images Print Summary File History
Inventor     Thompson; Kenneth M. (Altanta, GA)
Owner/Assignee     Digital Video Systems, Inc. (Los Gatos, CA)
Patent assignment
All assignments
Publication Date     March 9, 1999
Application Number     08/711,827
PAIR File History     Application Data   Transaction History
Image File Wrapper   Patent Term   Fees
Litigation
Filing Date     September 10, 1996
US Classification     709/219 725/146 725/147 725/148
Int'l Classification     H04N 007/16
Examiner     Flynn; Nathan
Assistant Examiner    
Attorney/Law Firm     Sawyer & Associates
Address
Parent Case    
Priority Data    
USPTO Field of Search     348/419 348/423 348/500 348/6 348/7 348/12 370/412 370/545 370/230 455/6.1 455/3.1 455/4.1 455/5.1 455/4.2 395/200.49 395/200.48 395/200.47
Patent Tags     transmitting mpeg data adaptive data rate
   
Enter a comma (,) or semicolon (;) between multiple tag words/phrases.
Describe this patent:
 Amusing   
 Clever   
 Complex   
 Efficient   
 Historic   
 Important   
 Innovative   
 Interesting   
 Practical   
 Simple   
[no votes]
Patent WIKI

Share information and news about this patent, including information and news about the technology, inventors, company, ligation and licensing.

 References Submit all comments and votes
 
*references marked with an asterisk below are user-added references
 U.S. References
 
Add a new US reference:  
ReferenceRelevancyCommentsReferenceRelevancyComments
5720037
Biliris
725/92
Feb,1998

[0 after 0 votes]
5677969
Auyeung

Oct,1997

[0 after 0 votes]
5598213
Chung
375/240.04
Jan,1997

[0 after 0 votes]
5586264
Belknap
725/115
Dec,1996

[0 after 0 votes]
5566208
Balakrishnan
375/240
Oct,1996

[0 after 0 votes]
5543853
Haskell
375/240.28
Aug,1996

[0 after 0 votes]
 Foreign References
 Other References
 Market Review Submit all comments and votes
   
Market Size
Estimate the gross annual revenues of the relevant market sector:
> $10B
$5B - $10B
$2B - $5B
$500M - $2B
$100M - $500M
$10M - $100M
$1M - $10M
$500K - $1M
$100K - $500K
< $100K
[No votes]
$0
 
$0   $2.5B   $5B   $7.5B   $10B
Market Share
Estimate the percentage of the relevant market sector this invention will capture:
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%
Reasonable Royalty
What percentage of gross sales should the inventor or assignee be paid?
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%
Public's "Guesstimation" of Royalty Value
Market SizeN/A[No votes]
xMarket ShareN/A[No votes]
xReasonable RoyaltyN/A[No votes]

N/A

License Availablity
If you are NOT the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
License Availablity
If you ARE the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
Competitive Advantage
Does this invention have a significant competitive advantage over similar technologies?
Yes

No



[No votes]
Most helpful competitive advantage comment
[No comments]

Commercial Alternatives
Are there viable commercial alternatives for this invention?
Yes

No



[No votes]
Most helpful commercial alternative comment
[No comments]

 Technical Review Submit all comments and votes
 Claims Submit all comments and votes
 


What is claimed is:

1. In a system having a server, upto M*N decoders, each having a decoder buffer memory, and upto M expanders, each having a buffer memory partitioned into upto N queues, a method for transmitting encoded data from the server to one of the upto M*N decoders, the method comprising steps of:

a) transmitting the encoded data from the server to the one of the upto M*N decoders, via one of the upto M expanders associated with the one of the upto M*N decoders, until its decoder buffer memory is filled to a predetermined level;

b) transmitting, at a first rate, the encoded data from the server to one of the N queues of the buffer memory of the one of the upto M expanders associated with the one of the upto M*N decoders;

c) determining a state of the one of the N queues of the buffer memory of the one of the upto M expanders; and

d) adjusting the first rate at which the encoded data is transmitted from the server to the one of the N queues of the buffer memory of one of the upto M expanders associated with the one of the upto M*N decoders based on the state determined in step (c) to form an adjusted rate.

2. The method of claim 1 wherein the step of determining a state includes sub-steps of:

i) determining a state of the one of the N queues of the buffer memory at the one of the upto M expanders, and

ii) transmitting the determined state from the one of the upto M expanders to the server.

3. The method of claim 1 further comprising steps of:

e) determining whether the adjusted rate is greater than a predetermined maximum rate;

f) setting the adjusted rate to the predetermined maximum rate if it has been determined to be greater than the predetermined maximum rate in step (e);

g) determining whether the adjusted rate is less than a predetermined minimum rate; and

h) setting the adjusted rate to the predetermined minimum rate if it has been determined to be less than the predetermined minimum rate in step (g).

4. The method of claim 1 further comprising steps of:

e) determining whether the system is in a start-up state; and

f) setting the adjusted rate to a predetermined maximum rate if it has been determined that the system is in a start-up state.

5. A system for distributing encoded data, the system comprising:

a) a server for retrieving files of the encoded data and outputting streams of the encoded data at a determined rate;

b) an expander having an input receiving the streams of encoded data output by the server, a storage device for buffering the streams of encoded data received at the input of the expander, a first output for providing, upon request, the streams of encoded data buffered in the storage device, and a second output for providing storage device state data to the server, wherein the determined rate of the server is adjusted based on the storage device state data; and

c) a plurality of decoders, each of the plurality of decoders having an input for receiving the streams of encoded data provided from the first output of the expander and an output for providing data requests to the expander.

6. The system of claim 5 wherein the storage device is segmented into a number of queues such that each of the plurality of decoders has an associated queue.

7. The system of claim 6 wherein the stream server directs the streams of the encoded data to a particular one of the number of queues of the storage device based on which of the plurality of decoders the stream is destined for.

8. The system of claim 5 wherein the input and second output of the expander share a common port.

9. The system of claim 8 wherein the input and second output of the expander are facilitated by a communications channel supporting the SCSI-2 fast and wide protocol.

10. The system of claim 5 wherein the expander includes:

i) a first interface defining the input of the expander;

ii) an internal bus, the internal bus being coupled with the first interface;

iii) a second interface defining the first output of the expander and being coupled with the internal bus;

iv) a first microprocessor, coupled with the internal bus, for moving the streams of encoded data received at the first interface to the storage device and for moving buffered data from the storage device to the second interface; and

v) an arbiter for arbitrating access to the internal bus of the expander.

11. The system of claim 10 wherein the first microprocessor further determines the storage device state data and provides the storage device state data to the first interface via the internal bus.

12. The system of claim 6 wherein each of the plurality of decoders includes:

i) a transport demultiplexer having an input for accepting the stream of encoded data, and at least two outputs, the transport demultiplexer separating different types of encoded data from the stream of encoded data and providing these different types of encoded data to associated ones of the at least two outputs;

ii) a first memory device, associated with the transport demultiplexer, for buffering the stream of encoded data;

iii) a first decoder, having an input coupled with one of the at least two outputs of the transport demultiplexer, for decoding the encoded data provided to it; and

iv) a second memory device, associated with the first decoder, for buffering the encoded data provided on the one of the at least two outputs of the transport demultiplexer,

wherein, the second memory device is filled with the encoded data provided on the one of the at least two outputs of the transport demultiplexer before the first memory device is filled, to a predetermined level, with the stream of encoded data.

13. The system of claim 12 wherein a queue of the storage device of the expander is only filled when the first and second memory devices of the associated one of the plurality of decoders are filled to a predetermined level.

14. The system of claim 5 wherein the server includes:

i) a file storage device for storing files of the encoded data;

ii) a timing and control unit for accessing one of the files of the encoded data stored in the file storage device;

iii) a transfer buffer for buffering the one of the files of the encoded data stored on the file storage device and accessed by the timing and control unit;

iv) an interface unit for formatting data buffered in the transfer buffer for output, wherein the timing and control unit selects the determined rate at which data are requested by the interface unit from the transfer buffer; and

v) a rate adjustment device for adjusting the determined rate based on the storage device state data.

15. The system of claim 5 wherein the expander includes:

i) a first interface defining the input of the expander;

ii) an internal bus, the internal bus being coupled with the first interface;

iii) a second interface defining the first output of the expander and being coupled with the internal bus;

iv) a first microprocessor, coupled with the internal bus, for moving the streams of encoded data received at the first interface to the storage device and for moving buffered data from the storage device to the second interface;

v) a second microprocessor, coupled with the internal bus, for determining the storage device state data;

vi) a control bus interface coupled with the internal bus; and

vii) an arbiter for arbitrating access to the internal bus of the expander.

16. The system of claim 15 wherein the second microprocessor communicates the storage device state data to the stream server via the second output.
 Description Submit all comments and votes
 


BACKGROUND OF THE INVENTION

a. Field of the Invention

The present invention concerns the communication, or distribution, of encoded data, such as MPEG (i.e., Motion Pictures Expert Group) or MPEG-2 encoded video data for example, from a server (such as an MPEG transport stream server for example) to one or more decoders.

b. Related Art

The MPEG-2 standard focuses on the encoding and transport of video and audio data. In general, the MPEG-2 standard uses compression algorithms such that video and audio data may be more efficiently stored and communicated.

The International Organisation for Standardisation (or the Organisation Internationale De Normalisation) (hereinafter referred to as "the ISO/IEC") has produced drafts of the MPEG-2 standard for the coding of moving pictures and associated audio. This standard is set forth in four documents. The document ISO/IEC 13818-1 (systems) specifies the system coding of the specification. It defines a multiplexed structure for combining audio and video data and means of representing the timing information needed to replay synchronized audio and video sequences in real-time. The document ISO/IEC 13818-2 (video) specifies the coded representation of video data and the decoding process required to reconstruct pictures. The document ISO/IEC 13818-3 (audio) specifies the coded representation of audio data and the decoding process required to reconstruct the audio data. Lastly, the document ISO/IEC 13818-4 (conformance) specifies procedures for determining the characteristics of coded bitstreams and for testing compliance with the requirements set forth in the ISO/IEC documents 13818-1, 13818-2, and 13818-3. These four documents, hereinafter referred to, collectively, as "the MPEG-2 standard" or simply "the MPEG standard", are incorporated herein by reference.

A bit stream, multiplexed in accordance with the MPEG-2 standard, is either a "transport stream" or a "program stream". Both program and transport streams are constructed from "packetized elementary stream" (or PES) packets and packets containing other necessary information. A "packetized elementary stream" (or PES) packet is a data structure used to carry "elementary stream data". An "elementary stream" is a generic term for one of (a) coded video, (b) coded audio, or (c) other coded bit streams carried in a sequence of PES packets with one and only stream identifier (or "ID"). Both program and transport streams support multiplexing of video and audio compressed streams from one program with a common time base.

Transport streams permit one or more programs with one or more independent time bases to be combined into a single stream. Transport streams are useful in instances where data storage and/or transport means are lossy or noisy. The rate of transport streams, and their constituent packetized elementary streams (PESs) may be fixed or variable. This rate is defined by values and locations of program clock reference (or PCR) fields within the transport stream.

FIG. 1 illustrates the packetizing of compressed video data 106 of a video sequence 102 into a stream of PES packets 108, and then, into a stream of transport stream packets 112. Specifically, a video sequence 102 includes various headers 104 and associated compressed video data 106. The video sequence 102 is parsed into variable length segments, each having an associated PES packet header 110 to form a PES packet stream 108. The PES packet stream 108 is then parsed into segments, each of which is provided with a transport stream header 114 to form a transport stream 112. Each transport stream packet of the transport stream 112 is 188 bytes in length.

Although the syntax of the transport stream 112 and transport stream packets is described in the MPEG-2 standard, the fields of the transport stream packet pertaining to the present invention will be described below with reference to FIG. 2 for the reader's convenience. As shown in FIG. 2, a transport stream 112 includes one or more 188 byte transport stream packets 200, each of the transport stream packets 200 having a header 114 and an associated payload 216.

Each header 114 includes an eight (8) bit synch byte field 218 and a packet identification (or PID) field 220. The synch byte field 218 has a value of "01000111" (or 47 hex) and identifies the start of a 188 byte transport stream packet 200. The PID field 220 indicates the type of data (e.g., audio, video, secondary audio program (or "SAP"), private, etc.) stored in the payload 216 of the 188 byte transport stream packet. Certain PID values are reserved.

The payloads 216 of one or more transport stream packets 200 may carry "packetized elementary stream" (or PES) packets 300. To reiterate, a "packetized elementary stream" (or PES) packet 300 is a data structure used to carry "elementary stream data" and an "elementary stream" is a generic term for one of (a) coded video, (b) coded audio, or (c) other coded bit streams carried in a sequence of PES packets with one and only stream ID.

FIG. 3 is a diagram which illustrates the syntax of a PES packet 300. As FIG. 3 shows, a PES packet 300 includes a 24 bit start code prefix field 302, an eight (8) bit stream identifier field 304, a sixteen (16) bit PES packet length field 306, an optional PES header 308, and a payload section 106. Each of these fields is described in the MPEG-2 standard. However, for the reader's convenience, the fields particularly relevant to the present invention are described below.

The sixteen (16) bit PES packet length field 306 specifies the number of bytes in the PES packet 300 following this field 306. A value of 0 in this field 306 indicates that the PES packet length is neither specified nor bounded. Such an unspecified and unbounded PES packet 00 is only allowed in PES packets whose payload is a video elementary stream contained in transport stream packets. As can be deduced from the description of the PES packet length field 306, the PES packet 300 can be much longer (e.g., 4000 bytes) than the length of the payload 216 of a 188 byte transport stream packet. Thus, as shown in FIG. 1, a PES packet 300 is typically carried in consecutive payloads 216 of a series of transport stream packets. The payload 106 of a PES packet 300 may carry a sequence of video frames or audio frames, for example.

FIG. 4 is a high level block schematic showing a system 400 for communicating and decoding video and audio data in accordance with the MPEG-2 standard. This system 400 basically includes a MPEG stream server 402 which provides data to an MPEG decoder 404 via a communications link 406.

The MPEG stream server 402 includes a storage system 408, a timing and control unit 410, a transfer buffer 412, and an interface unit 414. The storage system 408 stores files of packetized encoded data, such as PES or transport stream packets of MPEG data for example. The encoded data has been encoded, by an MPEG encoder for example, at an encoder rate. The storage system 408 may include a disk or array of disks which are well-known in the art. The timing and control unit 410 controls a reading out of one or more files stored in the storage systems 408 based on a clock signal CLK. The files of packetized encoded data read out from the storage system 408 are buffered in the transfer buffer 412. Under the control of the timing and control unit 410, the interface unit 414 provides data, stored in the transfer buffer 412, to the communications link 406. The interface unit 414 multiplexes packets of encoded audio and video data to form a program stream or a transport stream 112. The control signals provided by the timing and control unit 410 to the interface unit 414 may be based on the clock signal CLK or may be based on an independent clock signal.

At a remote end of the communications link 406, the MPEG decoder 404 includes a transport stream demultiplexer 416, a video decoder 418, an audio decoder 420, and clock control unit 422. The transport stream demultiplexer 416 receives the output of the stream server 402 in the form of a transport stream 112. Based on the packet identification (or PID) number 220 of a particular transport stream packet 200, the transport stream demultiplexer 416 separates the encoded audio and video packets and provides the video packets to the video decoder 418 and the audio packets to an audio decoder 420. The transport stream demultiplexer 416 also provides timing information to a clock control unit 422. The clock control unit 422 provides timing signals to both the video decoder 418 and the audio decoder 420 based on the timing information provided by the transport stream demultiplexer 416. The video decoder 418 provides decoded video data which corresponds to the video data originally encoded. Similarly, the audio decoder 420 provides decoded audio data which corresponds to the audio data originally encoded.

In any real-time system utilizing a digital source to derive an analog signal, the requisite number of data bits must be provided to analog generation circuitry in a timely manner so that the analog signal may be generated and transmitted to preserve the real-time characteristics of the system. In the current digital art, each video channel is derived from a single storage medium and a concomitant storage controller. In a system having mismatches in capacity between the digital source and the analog generation circuitry, such as will occur when digital data must be retrieved from local storage and transmitted as a digital stream over a transport medium, the real-time operation is aided by the use of intermediate buffer memory. The buffer memory ensures the requisite bits are available to the analog generation circuitry when needed.

It is important to provide a buffer memory of the proper size. Too little memory will cause lost analog frames, and too much memory is costly. As shown in FIG. 4, encoded data, such as encoded video data for example, may be buffered in the decoder 404 at a point "A" before the transport demultiplexer 416 and/or at a point "B" between the transport demultiplexer 416 and the video decoder 418.

Similarly, decoding encoded data involves the timely delivery of the encoded data (which comprise a video program for example) from a storage system (e.g., server 402) to the decoder 404. Of particular importance to the timely delivery of encoded data are two, sometimes unavoidable characteristics of the delivery process itself; namely "drift" and "jitter".

Drift is a monotonic error in the rate of data transfer from the server 402 to the decoder 404. Drift occurs when, on average, the rate at which a decoder (e.g., video decoder 418) consumes encoded data differs from the rate at which encoded data are provided (e.g., by the transport demultiplexer 416). Drift may cause a decoder buffer to run dry or overflow, particularly during extended transfers of data. If the decoder buffer runs dry, the decoder has no data to decode. Thus, for example, a video decoder would have to display the same frame for two or more consecutive frame periods. If, on the other hand, the decoder buffer overflows, data are lost. Drift is of particular concern when relatively long transfers of encoded data are provided to a relatively small decoder buffer.

Jitter is a random variation in the rate of data transfer from the server to the decoder. Jitter may cause variations in the level of decoder input buffers. However, since jitter tends to average out over time, it typically does not cause a decoder buffer to run dry or overflow.

In the known system 400, the MPEG digital source (i.e., the stream server 402) is the master of downstream circuitry (i.e., the decoder 404). That is, the downstream circuitry must be arranged to process the incoming data bits without the ability to control the rate at which incoming bits arrive. In operation, the MPEG stream server 402 provides the MPEG data to the MPEG decoder 404 (or video decoder 418) at a constant output rate that matches an original MPEG encode rate. This encode rate is either provided by the encoder or may be calculated from the size of the file containing the MPEG data and the number of frames contained within that data file. Thus, in the known system 400, the stream server 402 and the communications link 406 must provide the packets of encoded data at a fixed rate.

Small buffers located at "A" or "B" usually suffice to avoid random variances in the provision of encoded data, due to jitter for example. Unfortunately, even if the MPEG encode rate, the MPEG stream server output rate and the MPEG decoder rate are equal, problems can occur in the system 400 nonetheless, due to data transmission anomalies which alter the data transmission rate. In particular, as discussed above, drift of the transmitted MPEG data may cause the decoder buffers to overflow or run dry, particularly with relatively long transfers and relatively small buffers. Such anomalies obviously impact the overall quality and reliability of transmitted MPEG data and ultimately, viewers of a transmitted program,

Although the probability of queue overflow can be reduced by increasing the size of the decoder buffers, this solution increases the cost of the decoder 404. If multiple decoders 404 are needed, this increased memory cost is exacerbated.

An additional transmission-rate related problem which limits the prior art system 400 occurs when different programs are MPEG encoded at different encode rates and then transmitted as concatenated programs. To reiterate, a transport stream 112 may include one or more programs. In particular, video programs which comprise a sequence of video data are MPEG encoded and then stored as files in the storage system 408 of the stream server 402. Due to inherent differences in the video data from one program to another, not all of the programs are MPEG encoded at the same encode rate, however. Thus, during operations of the stream server 402, it may be necessary to transmit a first encoded program at a given rate (the program encode rate) and then transmit another, concatenated program at a different rate. Oftentimes, the stream server 402 cannot compensate for the variations in the transmission rates. This may lead to "garbled" or unintelligible transmissions of encoded data.

In view of the above described problems with known systems 400, a method and apparatus for preventing buffer(s) arranged between a server and a decoder from running dry or overflowing, due to drift for example, while, at the same time, compensating for variations in encoding rates in more than one program, are needed.

SUMMARY OF THE INVENTION

The present invention advantageously compensates for the data transfer rate problems associated with known systems. The present invention does so by providing a control back channel from the decoder and to the stream server.

First, the control back channel of the present invention allows the stream server to compensate for transmission problems such as drift. Further, the control back channel of the present invention automatically compensates for variations in stream rates which occur when programs, which are encoded at different rates, are played consecutively. Finally, the control back channel of the present invention facilitates compensation for rate anomalies due to errors in decoding which may result in short term slow down or speed up of the decoder data consumption.

During operation, any transfer rate adjustments necessitated by transmission anomalies, by successive programs having varying encoding rates, or by decoder anomalies, are all performed upstream of the decoder (e.g., by the stream server) without burdening the decoder. Advantageously, the present invention is applicable to configurations where the decoder and stream server are not directly connected, i.e., when the decoder and stream server communicate over a long-haul network. Moreover, the present invention permits the size of the buffers arranged between the server and the decoder(s) to be minimized.

The method of the present invention accomplishes these goals by (i) transmitting the encoded data from the server to the decoder, via a buffer, at a first rate,(ii) determining a state of the buffer, and (iii) varying the first rate based on the state of the buffer. The step of determining a state of the buffer preferably includes determining whether a level of buffer utilization is above or below a predetermined threshold or "high water mark". In a preferred embodiment of the method of the present invention, this may further involve determining a state of the utilization of the buffer, e.g., high, medium, or low. The buffer utilization can be divided into a greater number of states which permits the rate to be more accurately adjusted but increases processing complexity. The number of buffer utilization states introduces quantization effects.

In a preferred embodiment of the method of the present invention, when the level of buffer utilization is high, the first rate is decreased and when the level of buffer utilization is low, the first rate is increased. When the level of buffer utilization is medium, the first rate is increased, although not to the extent as when the buffer utilization is low. In a preferred embodiment of the method of the present invention, the minimum and maximum rates are bounded.

In a preferred embodiment of the present invention, the encoded data from the server is transmitted to the buffer over a communications channel in accordance with the SCSI-2 fast and wide protocol.

The method of the present invention is preferably employed in a system having a server, up to M*N decoders, each having a decoder buffer memory, and up to M expanders, each having a buffer memory partitioned into up to N queues. In such a system, the method (i) transmits the encoded data from the server to one of the decoders, via one of the expanders associated with the decoder, until its decoder buffer memory is filled to a predetermined level, (ii) transmits, at a first rate, the encoded data from the server to one of the queues of the buffer memory of the expander associated with the decoders, (iii) determines a state of the queue of the buffer memory, and (iv) adjusts the first rate at which the encoded data are transmitted from the server to the queue based on the determined state to form an adjusted rate. The state of the queue may be determined at the expander and transmitted to the server.

In a preferred embodiment of the method of the present invention, if the system is in a start-up or error recovery state, the adjusted rate is limited to a predetermined maximum rate. In the start-up rate, the stream server begins to transmit the encoded data before the scheduled playtime to pre-charge the memories of the proper decoder and the corresponding queue of the buffer memory of the expander.

A system for implementing the method of the present invention includes (i) a server for retrieving files of the encoded data and outputting streams of the encoded data at a determined rate, (ii) an expander having an input receiving the streams of encoded data output by the server, a storage device for buffering the streams of encoded data received at the input of the expander, a first output for providing, upon request, the streams of encoded data buffered in the storage device, and a second output for providing storage device state data to the server, wherein the determined rate of the server is adjusted based on the storage device state data, and (iii) decoders, each of which has an input for receiving the streams of encoded data provided from the first output of the expander and an output for providing data requests to the expander.

The storage device is preferably segmented into a number of queues such that each of the plurality of decoders has an associated queue. In such a case, the stream server directs the streams of the encoded data to a particular queue of the storage device based on which of the decoders the stream is destined for.

In a preferred embodiment of the present invention, the input and second output of the expander share a common port. This common port can be facilitated by a communications channel supporting the SCSI-2 fast and wide protocol.

In a preferred embodiment of the present invention, the expander includes (i) a first interface defining the input of the expander, (ii) an internal bus coupled with the first interface, (iii) a second interface defining the first output of the expander and being coupled with the internal bus, (iv) a first microprocessor, coupled with the internal bus, for moving the streams of encoded data received at the first interface to the storage device and for moving buffered data from the storage device to the second interface, and (v) an arbiter for arbitrating access to the internal bus of the expander. The first microprocessor preferably determines the storage device state data and provides the storage device state data to the first interface via the internal bus.

In a preferred embodiment of the present invention, each of the decoders includes a transport demultiplexer, a first decoder, a first memory device and a second memory device. The transport demultiplexer has an input for accepting the stream of encoded data, and at least two outputs. The transport demultiplexer separates different types of encoded data from the stream of encoded data and provides these different types of encoded data to associated ones of its outputs. The first memory device is associated with the transport demultiplexer and buffers the stream of encoded data. The first decoder has an input coupled with one of the outputs of the transport demultiplexer and decodes the encoded data provided to it. The second memory device is associated with the first decoder and buffers the encoded data provided on the output of the transport demultiplexer. The second memory device is filled with the encoded data provided before the first memory device is filled, to a predetermined level, with the stream of encoded data. A queue of the storage device of the expander is only filled when the first and second memory devices of the decoders are filled to a predetermined level.

In a preferred embodiment of the present invention, the server includes a file storage device, a timing and control unit, a transfer buffer, an interface unit, and a rate adjustment device. The file storage device stores files of the encoded data. The timing and control unit accesses one of the files of the encoded data stored in the file storage device. The transfer buffer buffers the files of encoded data stored on the file storage device and accessed by the timing and control unit. The interface unit formats data buffered in the transfer buffer for output. The timing and control unit selects the determined rate at which data are requested by the interface unit from the transfer buffer. Finally, the rate adjustment device adjusts the determined rate based on the storage device state data.

In an alternative embodiment of the present invention, the expander may include (i) a first interface defining the input of the expander, (ii) an internal bus coupled with the first interface, (iii) a second interface defining the first output of the expander and being coupled with the internal bus, (iv) a first microprocessor, coupled with the internal bus, for moving the streams of encoded data received at the first interface to the storage device and for moving buffered data from the storage device to the second interface, (v) a second microprocessor, coupled with the internal bus, for determining the storage device state data, (vi) a control bus interface coupled with the internal bus, and (vii) an arbiter for arbitrating access to the internal bus of the expander. In this alternative embodiment, the second microprocessor communicates the storage device state data to the stream server via the second output.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram which illustrates the packetizing of encoded data in accordance with the MPEG-2 standard.

FIG. 2 is a diagram illustrating the syntax of an MPEG-2 transport stream.

FIG. 3 is a diagram illustrating the syntax of an MPEG-2 PES packet.

FIG. 4 is a high level block diagram of a known MPEG video delivery system.

FIG. 5 is a high level block diagram of a system in which the method and device of the present invention may operate.

FIG. 6 is a block diagram of a playback card of the system of FIG. 5.

FIG. 7 is a block diagram of a system interface card of the system of FIG. 5.

FIG. 8 is a block diagram of the stream server of the present invention.

FIGS. 9a and 9b illustrate states of a buffer (or queue) monitored by the method of the present invention.

FIG. 10 is a flow diagram of the general operation of the method of the present invention.

FIG. 11 illustrates a compressed data bus and a control bus which may be used in the system of FIG. 5.

FIG. 12 is a graph which illustrates buffer (or queue) states and buffer (or queue) level trajectories monitored by the method of the present invention.

FIG. 13, which consists of FIGS. 13a and 13b, is flow diagram of the operation of the present invention.

FIG. 14 is a table showing an example of rate weights which may be used with the present invention.

DETAILED DESCRIPTION

1. HIGH LEVEL DESCRIPTION OF OUR SYSTEM

1.1 Basic function of the overall system

FIG. 5 is a high level block diagram of a system 500 in which the device and method of the present invention may operate. Basically, the system 500 distributes compressed video and audio data from a source to a group of decoders, each decoder being associated with a particular channel of a subscription television service. Each of the decoders provide an analog output. These analog outputs are combined into a broadband signal, which is then distributed to subscribers of the television service.

1.2 Basic structure of the overall system

As shown in FIG. 5, the system 500 includes a stream server 502, a plurality M of interface cards 530, a plurality of up to M*N playback cards 504, a plurality of up to M*N modulators 536, and a channel combiner 538. A first communications means 532 permits communication between the stream server 502 and the M system interface cards 530. A second communications means 534 permits communication between each of the M system interface cards 530 and up to N associated playback cards 504. The output of each of the playback cards is coupled with the input of an associated modulator 536. The outputs of the each of the up to M*N modulators 536 are provided to inputs of the channel combiner 538.

1.3 Basic operation of the overall system

Basically, the stream server 502 provides packetized encoded data, such as MPEG-2 encoded video data for example, to the up to N*M playback cards 504 via first communications means 532, M (e.g., 10 to 15) system interface cards 530, and second communications means 534. Each of the M system interface cards 530 is coupled with up to N (e.g., up to 8) playback cards 504 via an associated backplane bus 544 which is a part of the second communications means 534. Each of the playback cards 504 outputs decoded data to an associated modulator 536. Each of the modulators 536 modulate the decoded data at a particular carrier frequency. Thus, the modulators 536 collectively provide a number (e.g., up to N*M) of narrowband signals. These narrowband signals are combined (i.e., frequency division multiplexed) by channel combiner 538 into a broadband signal. The broadband signal is provided to subscribers 542 via a distribution network 540, such as a co-axial cable distribution network for example.

Of particular relevance to the present invention are the stream server 502, the first communications means 532, the M system interface cards 530, the second communications means 534, and the up to N*M playback cards 504. The details of each of these components, as well as their operation, are explained below.

Basically, the present invention distributes buffer memories throughout the system 500 to buffer the compressed audio and video data before it is decoded at the playback cards 504. The present invention prevents these buffers memories from overflowing or running dry by facilitating back channel communication, from the playback cards 504 to an associated system interface card 530, and from the system interface cards 530 to the stream server 502. The details of the buffer memory distribution and back channel communication will be described below.

2. COMPONENTS OF THE SYSTEM

2.1 THE STREAM SERVER

2.1.1 Functions of the Stream Server

Basically, the stream server 502 of the present invention provides compressed data to be decoded at each of the up to M*N playback cards 504. More importantly, the stream server 502 provides the compressed data at such a rate to prevent the distributed buffer memories from overflowing or running dry.

2.1.2 Structure of the Stream Server

FIG. 8 is a block diagram of the stream server 502 of the system 500. The stream server 502 includes a storage system 808, a timing and control unit 810, a transfer buffer 812, an interface unit 814, a back channel interface unit 816, and a rate adjustment module 818.

The storage system 808 stores files of packetized encoded data, such as PES or transport stream packets of MPEG-2 data for example. The encoded data has been encoded, by an MPEG-2 encoder for example, at an encode rate. The storage system 808 may include a disk or array of disks which are well-known in the art. The timing and control unit 810 controls a reading out of one or more files residing on the storage system 808 based on a clock signal CLK. The files of packetized encoded data read out from the storage system 808 are buffered in the transfer buffer 812. Under the control of the timing and control unit 810, the interface unit 814 provides data, stored in the transfer buffer 812, to the first communications means 532. The interface unit 814 multiplexes packets of encoded audio and video data to form a transport stream 112. The interface unit 814 also includes appropriate output device drivers. The control signals provided by the timing and control unit 810 to the interface unit 814 may be based on the clock signal CLK or may be based on an independent clock signal, as adjusted by the rate adjustment module 818. More specifically, based on signal(s) from the interface unit 814 (or from the back channel interface unit 816), the rate adjustment module 818 varies the control signal(s) output by timing and control unit 810 to the interface unit 814. The operation of the rate adjustment module 818 will be described in more detail below. Although the elements of the MPEG stream server 502 were described as "devices" or "units", the elements are not necessarily implemented with hardware. Rather, some of the elements of the MPEG stream server 502 may be implemented by processor executed instructions.

The MPEG stream server 502 may be a work station (executing a stored program), such as a Silicon Graphics Challenge DM or Challenge S server for example. The MPEG stream server 502 should include a processor (or processors) having (1) adequate processing speed for processing the packets, for performing the timing and control, as well as rate adjustment functions, for responding to the control signals, and for providing indicator signals (e.g., 100 MHz R4600 or 150 MHz R4400 CPUs); (2) an adequate amount of memory to store audio, video, and private application data being processed (e.g., 32 Mbytes to 2 Gbytes of RAM); and (3) a system bus having adequate throughput (e.g., 267 Mbytes to 1.2 Gbyte bandwidth). The MPEG stream server 502 should also include appropriate input/output ports and interfaces for accepting the packetized data and for transmitting the transport stream and for accepting and providing appropriate control and indicator signals (e.g., Ethernet, SCSI (or "Small Computer Standard Interface"), SCSI-2 fast and wide, FDDI (or "Fibre Distributed Data Interface"), and others).

2.2 THE SYSTEM INTERFACE CARDS

2.2.1 Function of the System Interface Cards

Each of the M interface cards 530 can be thought of as performing two functions; namely, (1) pumping transport stream data received from the stream server 502 to appropriate ones of the up to N playback cards 504, and (2) controlling the communication (e.g., scheduling, managing, and rate control) of the transport stream data. The communication of the transport stream data are controlled in two ways. First, within the interface card 530, the delivery of transport stream data to the up to N playback cards is controlled based on back channel control and status signals from the up to N playback cards associated with that playback card. Second, the rate at which the stream server 502 provides the transport stream data to a particular one of the M interface cards 530 is based on control and status signals sent by the interface card 530 to the stream server 502. Thus, the system interface card 530 is arranged to control the flow of the transport stream propagated by the stream server 502 in response to flow control information passed from the playback card(s) 504 to the system interface card 530, as well as to the status of the buffer memory 710 of the system interface card 530.

2.2.2 Structure of the System Interface Cards

FIG. 7 is a block diagram of one of the M system interface cards 530. A SCSI-2 fast and wide interface 702, a data bus interface 706, a pump microprocessor 708 and a buffer memory 710 perform the pumping function. These elements may also perform the rate control function. A control microprocessor 712 and a control bus interface 714 may perform some or all of the communications control functions. Each of these components are connected via a bus 704.

A bus arbiter 716 arbitrates control of the bus 704. Specifically, the data and address buses comprising bus 704 are subject to being mastered by three different devices, namely, the SCSI-2 fast and wide interface 702, the control microprocessor 712, and the pump mic