Dynamic rate control

Dynamic rate control can be implemented in a television-based entertainment environment when forwarding coded data. Real-time information flows are encoded, transcoded, compressed, etc. into data streams that may be forwarded to other components within an apparatus or to other apparatuses across a network. In a described implementation, a bitcount accumulation of a data stream is monitored in multiple overlapping windows. The data stream is compared to a data limit in each window of the multiple overlapping windows to determine whether an expected bitcount accumulation has been exceeded. The data stream is modified responsive to the comparison(s). For example, if the bitcount accumulations in each window exceed the expected bit accumulations at the corresponding relative positions of each window, then the bit rate of the data stream can be modified by reducing bit rate consumption.

TECHNICAL FIELD

This disclosure relates in general to real-time rate control and in particular, by way of example but not limitation, to implementing dynamic rate control under finite bandwidth constraints in real-time.

BACKGROUND

Television-based entertainment systems are expanding the programming and services that they offer. In addition to television program content such as that found on broadcast and traditional cable networks, television service providers are adding interactive services, features, and applications. Such content and additional information are downloaded over a television-based network for display, use, and/or storage on client-side set-top boxes or similar devices. These downloads include audio and/or video information that are transmitted in real-time. To reduce the amount of data that is streamed, the information is typically compressed from a first size to a second smaller size. Because the streaming occurs in real-time, the information flow is compressed on-the-fly without knowing the ultimate data rate level and/or amount of data that will be produced and therefore streamed.

Regardless of whether the information to be transmitted is intended to be sent over a network or stored in a memory (or both), there is a finite amount of bandwidth available for the compressed data. For example, a given network has a maximum transmission capacity at which it is designed to operate, often on both an individual user level and on a total composite level. Audio and video information may be compressed by encoding it using any of many available approaches and standards, such as a Moving Pictures Expert Group(MPEG)-based standard. The encoding reduces the bandwidth needed to transmit or store the resulting data. However, the degree to which encoding compresses information varies depending on the information itself. For example, some information compresses to one-fourth of its previous size while other information compresses to only one-half of its previous size, even using the same encoding parameters.

A transmission or storage medium's bandwidth limit(s) provide a guide as to what encoding parameters should be selected for compressing audio and video information to achieve a desired data rate that meets the medium's bandwidth limits. Unfortunately, because the same encoding parameters compress different information to differing degrees, it can be difficult if not impossible to accurately predict the ultimate bandwidth limits that will be met using a given set of encoding parameters on a real-time information flow.

In fact, there are two primary options for selecting encoding parameters in concert with adhering to bandwidth limits of a given transmission or storage medium. First, aggressive encoding parameters may be selected to significantly reduce the size of the resulting compressed data stream to ensure that any bandwidth limits are satisfied, but presentation quality suffers when the overly-compressed data is decompressed and the original audio and video information is presented. Second, conservative encoding parameters may be selected so that both compression and consequential quality reductions are minimized, but then data may be dropped or otherwise lost if medium bandwidth limits are exceeded. For example, if the memory storage bandwidth limit is exceeded prior to completion of a real-time data streaming event, then any un-stored data is lost.

Accordingly, for television-based entertainment systems, there is a need for schemes and techniques to enable the real-time compression of audio and video information that will meet bandwidth constraints while not unduly reducing the resulting presentation quality of the audio and video information after decompression.

SUMMARY

Dynamic rate control can be implemented in a television-based entertainment environment when encoding, transcoding, or compressing data. Real-time information flows are encoded, transcoded, compressed, etc. into data streams that may be forwarded to other components within an apparatus or to other apparatuses across a network. In a described implementation, a bitcount accumulation of a data stream is monitored in multiple overlapping windows. The data stream is compared to a data limit in each window of the multiple overlapping windows to determine whether an expected bitcount accumulation has been exceeded. The data stream is modified responsive to the comparison(s). For example, if the bitcount accumulations in each window exceed the expected bit accumulations at the corresponding relative positions of each window, then the bit rate of the data stream can be modified by reducing bit rate consumption.

DETAILED DESCRIPTION

The following discussion is directed to television-based entertainment systems, such as interactive TV networks, cable/satellite networks, and Web-enabled TV networks. Client devices in such systems range from full-resource clients with substantial memory and processing resources, such as TV-enabled personal computers and TV recorders equipped with hard-disks, to low-resource clients with limited memory and/or processing resources, such as traditional set-top boxes. However, dynamic rate control as described herein may additionally be used in other environments such as streaming (e.g., over the Internet); real-time compression and decompression; general encoding, decoding, and transcoding; and so forth. While aspects of the described systems and methods can be used in any of these environments and for any types of client devices, they are described primarily in the context of the following exemplary environment.

Exemplary System Architecture

FIG. 1illustrates an exemplary television entertainment system100that is an architecture in which dynamic rate control may be implemented. System100facilitates distribution of content and other information to multiple viewers. System100includes one or more content providers102, zero, one or more other information providers104, a content distribution system106, and one or more data-consuming (client) devices108(1),108(2), . . . ,108(N) coupled to content distribution system106via a network110.

Content provider102includes a content server112and stored content114, such as movies, television programs, commercials, music, and similar audio and/or video content. Content server112controls distribution of stored content114from content provider102to content distribution system106. Additionally, content server112may control distribution of live content (e.g., content that was not previously stored, such as live feeds) and/or content stored at other locations to content distribution system106. Content server112may engage in dynamic rate control during the distribution of content from stored content114, live content, and/or other content.

Other information provider104includes other information database116and other information server118. Other information database116stores information that may be provided to client devices108. Such information includes software modules, files, images, text, executable programs, gaming or other interactive information, and so forth. The information may also include content, especially content of an irregular, one-of-a-kind, or similar nature, or content from smaller independent providers. Part or all of the information from other information database116may be better enjoyed or utilized when provided to client devices108in real-time, such as streamed audio and/or visual information, interactive games, and so forth. Other information server118processes the other information from other information database116prior to distribution to generate one or more files that are optimized for, or at least capable of, transmission to content distribution system106. This processing may include dynamic rate control.

Content distribution system106includes a transceiver128, one or more content processors130, and one or more other information processors132. Transceiver128can alternatively be a broadcast transmitter if bidirectional communication is not required. Transceiver128transmits (e.g., broadcasts) signals, such as cable/satellite television signals, across network110. Network110can include a cable television network, RF, microwave, satellite, and/or data network, such as the Internet, and may also include wired or wireless media using any transmission format or protocol. Additionally, network110can be any type of network (including a broadcast network), using any type of network topology and any network communication protocol, and can be represented or otherwise implemented as a combination of two or more networks.

Content processor130processes the content received from content provider102prior to transmitting the content across network110. Similarly, other information processor132processes the other information that is received from other information provider104prior to transmission of the other information across network110. A particular content processor130may encode, or otherwise process, the received content into a format that is understood by the multiple client devices108(1),108(2), . . . ,108(N) that are coupled to network110. Content processor130and/or other information processor132may engage in dynamic rate control when distributing content and other information, respectively, to the client devices108. AlthoughFIG. 1shows a single content provider102, a single other information provider104, and a single content distribution system106, the exemplary system100can include any number of content providers and/or other information providers coupled to any number of content distribution systems. Thus, content distribution system106, content provider102, and/or other information provider104are individually or jointly representative of a headend service that provides content and other information to multiple subscribers.

Client devices108can be implemented in a number of ways. For example, a client device108(1) receives content and other information from a satellite-based transmitter via a satellite dish134. Client device108(1) is also referred to as a set-top box or a satellite receiving device. Client device108(1) is coupled to a television136(1) for presenting the content and other information (e.g., audio information, video information, and/or data information) that are received by the client device108(1), as well as for presenting a graphical user interface. A particular client device108can be coupled to any number of televisions136and/or similar devices that can be implemented to display or otherwise render content. Similarly, any number of client devices108can be coupled to a single television136.

Client device108(2) is also coupled to receive content and other information from network110and to provide the received content and other information to associated television136(2). Client device108(N) is an example of a combination television138and integrated set-top box140. In this example, the various components and functionality of the set-top box are incorporated into the television, rather than using two separate devices. Set-top box140that is integrated into television138can receive signals (e.g., broadcast signals) via a satellite dish (similar to satellite dish134) and/or directly via network110. In alternate implementations, client devices108may receive signals via the Internet or any other network, especially those network mediums that are broadcast-capable. As is further described below, client devices108may also engage in dynamic rate control when forwarding information (whether content information or other information) to memory storage, other client devices, and so forth.

The exemplary system100also includes streamed information from other networks provider142, which may provide information such as information streamed over the Internet, information streamed directly from a provider of the information, and so forth. Streamed information from other networks provider142may be accessible over network110(i.e., a network that also provides content information and other information from content distribution system106). Alternatively, streamed information from other networks provider142may be accessible over a different network, including a wide area network (WAN), the Internet, a public or private telecommunications network, and so forth.

Dynamic Rate Control of a Data Stream

FIG. 2is a graph200that illustrates an exemplary data stream202on which dynamic rate control may be implemented. Data stream202is a compressed version of an information flow such as content information from stored content114(ofFIG. 1), other information from other information database116, or streamed information from streamed information from other networks provider142. When information is to be forwarded from one location or component to another location or component, it may be advantageous to compress the information into data that consumes less bandwidth than the original information. The compression can be effectuated using any of many available or customized techniques. Many such techniques comport with one or more standards promulgated by the Moving Picture Experts Group (MPEG), but other techniques may also be used.

An entire information unit such as a movie or video clip may be compressed and then forwarded. On the other hand, only part of the entire information unit may be compressed before forwarding commences. When the forwarding begins prior to compression of the entire information unit, the information flow may be considered as being streamed in real-time. As a result, the ultimate data size or data rate of the entire information unit is unknown when the forwarding commences and as the forwarding is occurring. This presents no problem if the bandwidth that maybe consumed for forwarding is unlimited. However, bandwidth is typically finite. Consequently, in such situations accommodations may be made to limit the bandwidth consumed when forwarding the compressed information flow as a data stream.

The bandwidth may be limited to comply with a maximum transmission rate, a total available memory storage, and so forth. Because the total bandwidth for the entire information unit cannot be limited as the data is being streamed, individual portion or portions may be limited to ensure that the total data rate or data size does not exceed the total available or assigned bandwidth. In other words, the data transmitted during a predetermined unit of time may be limited.

Graph200plots time along the abscissa axis from zero (0) to a predetermined unit of time that is denoted as “time-slot”. Graph200plots bitcount along the ordinate axis from zero (0) to a predetermined total accumulation of bits denoted as “target_bitcount”. An information flow that is to be forwarded in real-time is compressed into data stream202. Limits, which may be soft and/or flexible limits, are placed on data stream202according to the target_bitcount. In other words, in every elapsed time unit that is approximately equal to the time_slot, data stream202is expected to have forwarded/accumulated/consumed a bitcount that is approximately equal to the target_bitcount. A dashed line204extends diagonally from a first point (0,0) to a second point (time_slot, target_bitcount). This dashed line204represents an approximate expected bitcount of data stream202at any particular point in time. Noted on graph200are (i) a particular point206along data stream202and (ii) a current_time and a current_bitcount that correspond thereto.

As can be seen from graph200, data stream202is initially below dashed line204. During this time, data stream202is not consuming as much bandwidth as has been allotted. While there is no need to change the compression level during this initial period with respect to ensuring that data stream202does not exceed the target_bitcount limit by the end of the time_slot, it may be beneficial to reduce the compression level in order to reduce information loss from the compression. Reducing the compression level usually improves the resulting presentation quality of the information after decompression. When data stream202is above dashed line204, data stream202has/is consuming more than the allotted number of bits as of that time/position in the time_slot. In order to ensure that all of the information that is allotted to be forwarded during the given time_slot has some available bandwidth, even as the time nears the end of the time_slot, the compression level is increased so as to reduce the bit consumption of the resulting bit stream202.

In order to keep the presentation quality after decompression relatively constant, data stream202is kept relatively near dashed line204. This effectively reduces the likelihood that very few (or no) bits are left as data stream202approaches the end of the time_slot. In other words, situations where data stream202reaches a bitcount accumulation of target bitcount well before the end of the time_slot should generally be avoided. U.S. Nonprovisional Patent Application Ser. No. 09/880,243 entitled “Non-Compensated Transcoding of a Video Stream”, includes description directed to avoiding these situations. U.S. Nonprovisional Patent Application Ser. No. 09/880,243, having a filing date of Jun. 13, 2001, is hereby incorporated by reference in its entirety herein. Monitoring and adjusting data stream202during any given time_slot may enable all of the information allotted to that given time_slot to be forwarded at a relatively constant quality level. Unfortunately, especially given that different segments (e.g., time_slots or windows) of a single information unit may be compressed to differing degrees, there may be human-perceptible presentation quality fluctuations between time_slots. Data stream202may, however, be monitored and consequently adjusted over multiple overlapping time_slots or windows, while still streaming the original information flow in real-time, as is described herein.

FIG. 3illustrates exemplary apparatuses302and108for a television-based entertainment system300in which dynamic rate control units304may be implemented. A headend302is in communication with a destination306. Headend302may correspond to one or more of content provider102(ofFIG. 1), other information provider104, content distribution system106, streamed information from other networks provider142, and so forth. Destination306may correspond to a home, business, or other location that includes at least one client device108. Headend302sends content information, streamed information, and other information towards client device108A over network110. Client device108A receives the content information, streamed information, and other information via network110.

Each of headend302and client device108A includes one or more dynamic rate control units304. Dynamic rate control units304may be formed from general processor(s) and memory component(s) of the respective headend302and client device108A. Alternatively, specific processor(s) and/or memory component(s) may be used to implement dynamic rate control units304. For example, an application specific integrated circuit (ASIC) may be created and utilized as dynamic rate control units304. In any event, dynamic rate control units304may operate to dynamically control the bit rate of data streams that are being forwarded in real-time.

At headend302, dynamic rate control unit304HE performs real-time rate control prior to and simultaneously with the forwarding of a coded (e.g., encoded, transcoded, compressed, etc.) data stream to an output component308. In this case, dynamic rate control unit304HE is effectively (en)coding real-time information into a data stream. Output component308may correspond to transceiver128(ofFIG. 1), a transmitter, or any general output device suitable for interoperability with network110. The data stream is forwarded over network110from output component308. In the implementation ofFIG. 3, a cable transmission medium110(C) and a satellite transmission medium110(S) are shown. Other transmission mediums may alternatively be used to realize network110as is described above with reference toFIG. 1. The data stream is forwarded from output component308over cable transmission medium110(C) and/or satellite transmission medium110(S).

The data stream is received at destination306using an input component310of client device108A via cable transmission medium110(C) and/or satellite transmission medium110(S). Input component310may correspond to any device suitable for interoperability with network110such as a cable/satellite network interface, a TCP/IP network interface, a general receiver or transceiver, and so forth. Input component310may provide the encoded data stream to one or more decoders (not shown) and/or one or more tuners for subsequent processing, display, and/or storage. Input component310may also provide the encoded data stream to dynamic rate control unit304CD.

Dynamic rate control unit304CD receives a decoded data stream from a decoder (not shown) or an encoded data stream directly from input component310. When dynamic rate control unit304CD receives an encoded data stream, dynamic rate control unit304CD is effectively transcoding the encoded data stream into another, transcoded data stream that is compressed further and therefore consumes still fewer bits. Dynamic rate control unit304CD may forward the transcoded data stream to memory storage312and/or to local output component314. Memory storage312is capable of storing the data stream. Memory storage312may be implemented with one or more memory components, examples of which include a random access memory (RAM), a disk drive, another mass storage component, a non-volatile solid-state memory (e.g., ROM, Flash, EPROM, EEPROM, etc.), and so forth. It should be understood that dynamic rate control unit304CD may alternatively forward an encoded data stream to memory storage312and/or to local output component314when dynamic rate control unit304CD is operating on non-encoded/decoded data.

Local output component314is capable of transmitting the transcoded (or encoded) data stream over a local network316that extends over all or part of destination306. Local output component314and local network316may operate in accordance with any wired or wireless network protocol, examples of which include a local area network (LAN), a TCP/IP based network, a Bluetooth® network, an IEEE 802.11b-based network, and so forth. The transcoded (or encoded) data stream is received via local network316at one or more client devices108B, . . .108Z. Client devices108B, . . .108Z each include a local input component (not shown) for interfacing with local network316and one or more decoders for decoding the transcoded (or encoded) data stream. Client devices108B, . . .108Z may also each include a dynamic rate control unit304CD for forwarding a data stream to a memory storage located thereat or to another client device. Client devices108B, . . .108Z are capable of providing the original, non-coded information flow to an associated television136or138for presentation thereon.

Exemplary Dynamic Rate Control Implementations

An exemplary dynamic rate control algorithm is described using the ten terms (numbered (1)-(10)) in Table 1 below. The numbers in brackets in Table 1 correspond to element reference numbers fromFIG. 4, which is directed to a flow diagram of the exemplary algorithm and is described below. (1) A “data_chunk” is a logical subset of data. In an MPEG-based implementation, a data_chunk may be macroblock, a slice, a picture, a group of pictures (GOP), and so forth. (2) A “time_window” is a set of contiguous data chunks that extend for a duration of a time_slot. (3) A “time_slot” is the time length of a time_window. For example, a time_slot may be equivalent to 30 pictures. (4) A “current_time” is a point in time of a time_slot and corresponds to a particular data_chunk. (5) A “target_bitcount” is the total expected bitcount accumulation over a time_window. For example, a target_bitcount of 4,000,000 bits for a time_slot of 30 pictures results in a 4 Mb/s data stream, assuming 30 pictures are presented each second. (6) A “current_bitcount” is a number of bits accumulated at and by a particular point during a time_window.

(7) A “window_level_control_parameter” (WLCP) is used to control the number of bits consumed by a data_chunk. In other words, the WLCP is a bit rate control parameter that affects the resulting bit rate of an information flow that is coded into a compressed data stream. The WLCP may be a scalar, a vector, a matrix parameter, and so forth. In an MPEG2-based implementation, for example, the WLCP may comprise the “quant matrix”, the “quant_scale”, or both. (8) A “window_level_modifier” (WLM) is a parameter that is used to modify the WLCP on a per-data_chunk basis. (9) “Multiple overlapping time_windows” (MOTWs) are multiple time_windows that overlap such that each instant in time and each data_chunk is included in more than one time_window. Each time_window of the MOTWs includes its own target_bitcount, current_bitcount, WLM, WLCP, and mechanism(s) for adjusting the WLCP. (10) A “top_level_control_parameter” (TLCP) is a parameter that can control the bit rate. The TLCP results at least from combining the contributions of multiple WLCPs (from corresponding MOTWs) that are associated with the current time instant.

TABLE 1Terms used in exemplary dynamic rate control algorithm.TERM [FIG. 4 Element No.]ALGORITHMIC INTERPRETATION(1)data_chunk(1)logical subset of data(2)time_window(2)set of contiguous data_chunks thatextend for a duration of a time_slot(3)time_slot [404](3)length of time for a time_window(4)current_time [402](4)point in time during a time_slot(5)target_bitcount [408](5)total bitcount accumulationexpected over a time_window(6)current_bitcount [406](6)number of bits accumulated at apoint in time during atime_window(7)window_level_control_parameter(7)controls the number of bits(WLCP) [420]consumed by a data_chunk(8)window_level_modifer (WLM)(8)parameter to modify the WLCP on[416]a per-chunk basis(9)multiple overlapping time_windows(9)multiple time_windows that(MOTWs) [418]overlap such that each instant intime and each data_chunk isincluded in more than onetime_window(10)top level_control_parameter(10)parameter for controlling bit rate(TLCP) [430]that results at least fromcombining the contributions ofmultiple WLCPs fromcorresponding MOTWs

FIG. 4is a flow diagram400that illustrates an exemplary dynamic rate control algorithm. Both qualitative and quantitative perspectives on flow diagram400are presented herein. A qualitative overview of the exemplary dynamic rate control algorithm is provided next. A current_time402, a time_slot404, a current_bitcount406, and a target_bitcount408are determined in accordance with a data stream and time_window as shown inFIG. 2. Current_time402and time_slot404are used to produce a time-related ratio410. Current_bitcount406and target_bitcount408are used to produce a bitcount-related ratio412. Time-related ratio410and bitcount-related ratio412are used to generate WLM416. Generating a WLM416is described further below with reference toFIGS. 5A,5B, and5C. An original WLCP414(e.g., an immediately previous WLCP) and WLM416are used to determine a new WLCP420.

New WLCP420is determined with respect to an individual (but overlapping) time window. However, (other) multiple overlapping time windows (MOTWS) are used to produce multiple (new) WLCPs418for each given instant of time. While the absolute overall time instant and data stream point are the same, each time_window of all of the MOTWs has its own relative current_time402and current_bitcount406. Multiple (new) WLCPs418and new WLCP420are combined into a combination WLCP424to represent all of the time_windows of the MOTWs. An exemplary set of MOTWs are described further below with reference toFIG. 6. One or more previous TLCPs422and combination WLCP424, along with weighting coefficients426and a weighting coefficient428, are used to calculate a current TLCP430. Exemplary calculation methodologies are also presented below. Current TLCP430is used to set or adjust the bit rate of the data stream that results from an information flow being encoded, transcoded, or compressed.

A more quantitative view and a detailed description of the exemplary dynamic rate control algorithm is provided next. With reference now toFIGS. 2 and 4, the time_window of the graph200defines the temporal length of the window as time_slot404and the total expected accumulation of bits as target_bitcount408. Each point along data stream202, such as particular point206, is associated with a current_time402and a current_bitcount406. The ratio of current_time402to time_slot404forms time-related ratio410. The ratio of current_bitcount406to target_bitcount408forms bitcount-related ratio412. One or both of ratios410and412are used to generate WLM416.

WLM416may be generated using any of many possible mechanisms. As alluded to above, U.S. Nonprovisional patent application Ser. No. 09/880,243, entitled “Non-Compensated Transcoding of a Video Stream”, outlines one mechanism for generating WLM416. The following second and third mechanisms are additional alternatives. These two mechanisms are described algebraically as:
WLM=1/[(1−current_time/time_slot)*(1−current_bitcount/target_bitcount)]^p; and  [1]
WLM=1/[(1−current_time/time_slot)+(1−current_bitcount/target_bitcount)]^p,[2]where “p” is a user selectable parameter.

If the user desires that the rate control algorithm respond relatively rapidly to changes in the input, a large value of “p” (e.g., p>1) may be chosen. For a more damped response, relatively small values of “p” (e.g., p<=1) may be chosen.

In general under these two second and third mechanisms, WLM416increases as current_bitcount406approaches target_bitcount408. And for the same ratio412of current_bitcount/target_bitcount, WLM416becomes larger as current_time402approaches the end of the time_window (i.e., time=time_slot404). Exemplary fourth and fifth mechanisms are described below with reference toFIG. 5AandFIGS. 5B-C, respectively.

FIG. 5Ais a graph530that illustrates a fourth exemplary mechanism for generating a WLM416. This fourth mechanism is a zone-based mechanism in which the magnitude and positive/negative value of the WLM is determined responsive to the zone in which data stream202is located at the particular point in question. The graph530includes six zones: D−, S−, M−, M+, S+, and D+. The lettered zones correspond to a dramatic (D) change, a significant (S) change, and a minor (M) change. The positive/negative denotation indicates whether the WLM is positive or negative. For example, if a particular point along data stream202is located in the S− zone, then the WLM for that particular point in the time_window under consideration corresponds to the numeric value assigned to the S− zone. The numeric values assigned to the six zones may be determined empirically. As indicated by the dramatic (D), significant (S), and minor (M) designations, the absolute numeric values increase from the minor (M) zone to the significant (S) zone and from the significant (S) zone to the dramatic (D) zone. In alternative implementations, more or fewer than six zones may be utilized.

The positively-denoted zones above dashed line204represent that the WLM is positive; hence, the WLM will increase the WLCP (in this implementation as described further below). The negatively-denoted zones below the dashed line204represent that the WLM is negative; hence, the WLM will decrease the WLCP. Thus, when a particular point of data stream202is located in the M+ zone, the WLCP is increased by an amount M or an amount proportional to M. The increased WLCP, if applied directly to the quantization of the information flow that produces data stream202, results in a coarser quantization (e.g., a coarser encoding or transcoding). The coarser quantization causes a reduced bit rate consumption that “drives” data stream202back towards dashed line204. As is explained further below, an increased WLCP decreases the bit rate consumption when information is being compressed according to an MPEG standard for example. However, other standards may be employed in which an increased WLCP increases bit rate consumption. In such instances, the positive/negative denotations (and corresponding values) of the zones of graph530are swapped.

FIGS. 5B and 5Care graphs560and590that illustrate a fifth exemplary mechanism for generating a WLM416. This fifth mechanism is a function-based mechanism. The bitcount deviation of data stream202from dashed line204is mapped to a WLM value. The function may be arithmetic, geometric, exponential, and so forth. For example, the function may square the bitcount deviation to map to a WLM so that the greater the bitcount deviation of data stream202from dashed line204, the greater the WLM and the faster the data stream202may be re-directed to the expected bitcount accumulation as represented by dashed line204. A specific exemplary function is shown inFIGS. 5B and 5C.

The graph560indicates five continuous zones A, B, C, G, and H. In contrast to the discrete zones of the fourth exemplary mechanism as illustrated in the graph530(ofFIG. 5A), the five zones of the graph560map to continuously variable values of WLM. Graph590plots bitcount deviation along the abscissa axis versus WLM values along the ordinate axis. The five continuous zones A, B, C, G, and H from graph560are also noted along the bitcount deviation axis. A function592maps the bitcount deviation of data stream202to the WLM values. This function592may be implemented computationally, as a tabular data structure in a memory, and so forth.

When the bitcount deviation is slightly negative (e.g., when data stream202is located below dashed line204, as in zone G), the WLM is zero so that the WLCP is unchanged. When the bitcount deviation is more negative (e.g., located in zone H), the WLM is negative and increases in the negative direction at a predetermined rate. When the bitcount deviation is slightly positive (e.g., located in zone A), the WLM is positive and increases at a first predetermined rate. As the bitcount deviation becomes more positive (e.g., located in zone B), the WLM becomes more positive and increases at a second, higher predetermined rate. Eventually, so as to prevent the WLM from becoming too large and the WLCP from changing to quickly, the WLM value becomes saturated even as the bitcount deviation increases (e.g., when the bitcount deviation is located in zone C). Any one or more of these five exemplary mechanisms may be used in order to generate a WLM416.

Continuing again wither reference to flow diagram400ofFIG. 4, a new WLCP420is determined by using WLM416and an original (e.g., an immediately previous) WLCP414. In an exemplary MPEG implementation, the WLCP may correspond to the quant_scale, the quant_matrix, or both. The WLCP determination mechanisms described below may be used for either quantization parameter or both. The quant_scale is a parameter within an MPEG stream that enables the changing of the quantization scale of each macroblock. The quant_matrix is a matrix parameter in an MPEG stream that is constant for all macroblocks for the duration of a picture. Each element of this matrix can be changed using any of the exemplary WLCP determination functions f1defined below.

Given a WLM on a per-chunk basis, the new_quant_scale for each macroblock is determined as a function (f1) of this WLM together with the original_quant_scale of the macroblock. Other MPEG parameters may be involved in the function as well. In general,
new_quant_scale=f1 (WLM, original_quant_scale, optionally other_parameters).

Five (5) exemplary functions (f1) for determining a WLCP420in an MPEG-based implementation are presented below:
f1=original_quant_scale+WLM;  (1)
f1=original_quant_scale *WLM;  (2)
f1=mbtype==INTRA? original_quant_scale:original_quant_scale+WLM;(3)
f1=frametype==I_TYPE? original_quant_scale:original_quant_scale+WLM; and  (4)
f1=original_quant_scale+WLM*(2*gopsize−current_position_in—gop)/(2*gopsize).  (5)
Function (3) depends on the type of MPEG macroblock. Function (4) depends on the type of MPEG frame. Function (5) depends on the size of the group of pictures (GOP) and the current position in the GOP.

Determining new WLCP420therefore involves original WLCP414and WLM416. When using an MPEG-based compression/coding approach, new WLCP420may correspond to new_quant_scale (in the f1functions above) and original WLCP414may correspond to original_quant_scale. For other compression/coding standards and schemes, the applicable bit rate control parameter or parameters thereof may be substituted for the quant_scale/quant_matrix parameters of MPEG. The applicable bit rate control parameter(s) of other standards and schemes may therefore correspond to the WLCP of the algorithm of flow diagram400(ofFIG. 4).

The algorithmic aspects402-420generally apply to a single time_window, such as the one that is illustrated inFIG. 2. A particular point206corresponds to a current_time402and a current_bitcount406. WLM416is generated from this particular point along data stream202. Applying WLM416to original WLCP414determines a new WLCP420. This new WLCP420serves to govern the bit rate of data stream202relative to an expected bitcount accumulation (e.g., as indicated by the dashed line204) and a total expected bitcount accumulation as designated by target bitcount408at time_slot404. The WLCP420thus governs, or limits, the bitcount accumulation of data stream202in terms of a single time_window. This can cause the bit-rate-limiting feature of such an algorithm to, for example, reduce presentation quality within a first time_window unnecessarily because the bit rate in a succeeding time_window will be lower in any event due to information therein that is more easily compressed. Furthermore, modifying data stream202from the perspective of a single, artificially imposed time_window can create a beating effect in the information as presented aurally, visually, etc. after decoding/decompression.

This beating effect is a human-perceptible change in presentation quality between data that was compressed at a first factor in a first time_window and immediately succeeding data that was compressed at a second factor in a second, immediately succeeding time_window. This compression factor differential, and the resulting beating effects, arise because of higher quantization towards the end of time_windows followed by lower quantization at the beginning of time_windows. To mitigate this beating effect, multiple overlapping time_windows are employed.

FIG. 6illustrates an exemplary set600of multiple overlapping time_windows (MOTWs) in order to determine multiple window_level_control_parameters (WLCPs). In the MOTW set600, bitcount is illustrated as increasing in the upward direction, and time is illustrated as elapsing in the rightward direction. The MOTW set600includes three time_windows602(1),602(2), and602(3). Although only three time_windows602are shown as overlapping any given instant of time and/or position along data stream202in the MOTW set600, two, four, five, or more time_windows may alternatively be used. Also, although each time_window602of “n” time_windows in the MOTW set600is shown as overlapping the immediately previous time_window602by “(n−1)/n” of a time_window width, other overlapping distributions may alternatively be used.

Data stream202is illustrated as crossing through all three illustrated time_windows602as it reaches an intermediate or a final bitcount for the data stream as generated by the compression/coding standard that is being applied to the information flow that is to be forwarded. Each particular point along data stream202, such as particular point604at time=N, is simultaneously located in three overlapping time_windows602. Each time_window602is used to independently generate a WLM416, and each of these WLMs416is used to generate a (new) WLCP420from a respective (original) WLCP414. New WLCPs420from each time_window of the MOTW set600are then combined.

Because the multiple time_windows602are overlapping, for any given time instant, the relative “current_time=N” is different in each respective time_window602. The current_bitcount, also being relative for each time_window602, is likewise different in each respective time_window602, even for the same particular point604along data stream202. Although the target_bitcount and the time_slot values may differ between and among time_windows602, they are at least approximately equal in the MOTW set600implementation as illustrated inFIG. 6.

The use of MOTW sets provides the ability to view the same particular data point of data stream202at different phases, thus mitigating the beating effect. More specifically, because the same bitcount is viewed through MOTWs, each instant of absolute time falls in different relative time locations and positions of the different overlapping time_windows. This mitigates the problem of drastic presentation quality reduction at the end of a time_window because (at any instant of absolute time) there will be other time_windows that will be operating at the beginning, near the beginning, at the middle, etc. of their time slots.

Continuing now with reference toFIG. 4, new WLCP420is therefore determined from one time_window of a MOTW set. Similarly, multiple new WLCPs418are determined from the other time_windows of the MOTW set. To produce combination WLCP424from the MOTW set, new WLCP420is combined with each WLCP of multiple new WLCPs418. The WLCP420and the multiple WLCPs418(jointly termed the “contributing WLCPs”) may be combined using any of many possible approaches. For example, the contributing WLCPs may be averaged to combine them into combination WLCP424. The average may comprise the mean of the contributing WLCPs, the median of the contributing WLCPs, and so forth. Each individual WLCP of the contributing WLCPs may also be individually weighted.

Combination WLCP424may be used as (current) top_level_control_parameter (TLCP)430. Current TLCP430is used as the bit rate control parameter (e.g. to set a quantization level) for the compression/coding standard or approach that is being used. In an MPEG implementation, for example, current TLCP430corresponds to the quant_scale, the quant_matrix, or both. Using combination WLCP424as current TLCP430smoothes quantization levels from one time window to the next. However, the quantization level can still change too dramatically and/or be subject to spurious deviations in the information-flow-to-be forwarded such that changes in the presentation quality after decompression are perceivable to the human eye or ear. To avoid this, (previous) TLCPs422may be used to calculate current TLCP430; this can minimize or reduce the likelihood that quantization levels change too quickly by incorporating a history of TLCPs.

In other words, the TLCP to be used in quantizing the information flow into data stream202may be modified by using previously calculated TLCPs. Current TLCP430may be calculated from combination WLCP424, previous TLCPs422, weighting coefficients426, and weighting coefficient428. This calculation may be accomplished, for example, via an autoregressive model such as:
TLCP(n)=Σk=n−1, n−2, . . . ,n−man(k)TLCP(k)+an(n)C(n),
where “C(n)” is the result of combining the contributing WLCPs to produce combination WLCP424for the current time instant. The parameter “m” is set based on the desired memory length for the current TLCP430calculation. The historical memory length aspect of the current TLCP430calculation is increased as the value of “m” is increased. The parameter “an(k)” is represented in flow diagram400by weighting coefficients426, and the parameter “an(n)” is represented by weighting coefficient428. In an exemplary implementation, an(k) is set equal to 0.9 for k=n−1, and zero for smaller values of k, and an(n) is set equal to 0.1. In general, the greater the value of an(k) relative to that of an(n), the slower the quantization rate changes because there is greater emphasis placed on the historical (i.e., previous) TLCP values422. An exemplary simplification of the term an(k) is to have a dependence only on the difference between n and k, i.e. an(k)=a(n−k).

The algorithm of flow diagram400(ofFIG. 4) thus provides a mechanism for dynamically providing rate control for an information flow that is being compressed/coded into a data stream. The mechanism limits or governs the total bit accumulation of the resulting data stream while minimizing or reducing perceptible beating effects. Dynamic rate control units304(ofFIG. 3) may implement, optionally in conjunction with other components of headend302and client device108, the algorithm of flow diagram400.

Exemplary Dynamic Rate Control Units

FIG. 7Aillustrates an exemplary dynamic rate control unit304from a component perspective. Dynamic rate control unit304includes one or more processors702and one or more memories704. Processor702is capable of processing various instructions to control the operation of dynamic rate control unit304and to communicate with other components and/or other electronic/computing devices. Memory704can be implemented with one or more memory components, examples of which include a random access memory (RAM), a disk drive or other mass storage component, a non-volatile memory (e.g., ROM, Flash, EPROM, EEPROM, etc.), and so forth. While any single type of memory or combination of memory types is possible, memory704most likely includes at least (i) a RAM for processing and (ii) a mass storage or non-volatile memory for longer-term storage. Memory704is adapted to store various instructions and/or information such as operating system and/or configuration information, stream-able data, and so forth.

Specifically, memory704stores computer-executable instructions, relevant data structures, and/or any other information for implementing the algorithm of flow diagram400(ofFIG. 4) as denoted by dynamic rate control algorithm706. Dynamic rate control unit304may be realized in any of many possible manners. For example, processor702and memory704may be integrated together on one or more dedicated chips (e.g., one or more ASICs). Alternatively, processor702and memory704may be shared across one or more other tasks being performed by headend302or client device108. In fact, dynamic rate control algorithm706may be stored in general purpose memory and executed on general purpose processor(s) (not shown separately) of headend302or client device108using, for example, a multi-tasking and memory sharing scheme.

It should be noted that client devices108can include a range of processing and memory capabilities, and may include more or fewer types of memory components than those enumerated above. For example, full-resource clients108can be implemented with substantial memory and processing resources, including a disk drive or similar mass storage medium. Low-resource clients, however, may have limited processing and memory capabilities, such as a limited amount of RAM, no disk drive, limited processing capabilities, and so forth. Furthermore, client devices108may include a decoder to decode a broadcast video signal, such as an NTSC, PAL, SECAM or other TV system video signal.

FIG. 7Billustrates an exemplary dynamic rate control unit304from a functional perspective. Dynamic rate control unit304includes six (6) functional blocks. Each functional block may be implemented as an IC or part thereof, as a logical module operable by processor(s) in conjunction with memory or memories, as one or more computer-executable instructions, and so forth. The latter two examples may be stored in a computer-accessible memory (e.g., as part of dynamic rate control algorithm706(ofFIG. 7A)). The functional blocks752-762are described below with reference to specific aspects402-430of the algorithm of flow diagram400(ofFIG. 4). However, it should be understood that the functions performed by blocks752-762may overlap across multiple aspects of flow diagram400or may only perform a portion of one or more of such aspects.

A time and bitcount monitor block752performs aspects402and406of flow diagram400by monitoring and being capable of providing current_time402and current_bitcount406. Time and bitcount monitor block752may also perform aspects404and408by recording and being capable of providing time_slot404and target_bitcount408. A WLM generator block754performs aspects410,412, and416of flow diagram400after receiving parameters from time and bitcount monitor block752. WLM generator block754(along with the other functional blocks ofFIG. 7B) may also implement any of the alternatives described above with reference to the various aspects of flow diagram400. For example, WLM generator block754may generate WLM416based upon (i) the position in the time_window, (ii) the current_bitcount thereat, and (iii) the position in the GOP.

A WLCP determiner block756performs aspect420(new WLCP) in conjunction with aspect414(original WLCP), as is described above with reference toFIG. 4, using a WLM from WLM generator block754. A TLCP history storage block758stores previous TLCPs (for aspect422) in a memory of dynamic rate control304, such as memory704. The number of previous TLCPs stored in TLCP history storage block758corresponds to the parameter “m” as described above with respect to the autoregressive model implementation. A WLCPs combiner block760performs aspect424by, for example, receiving multiple WLCPs of multiple overlapping time_windows from WLCP determiner block756and averaging the multiple WLCPs. A TLCP calculator block762, when present, performs aspects426,428, and430to calculate a current TLCP from previous TLCPs and a combination WLCP as received from TLCP history storage block758and WLCPs combiner block760, respectively.

Methods for Dynamic Rate Control

Dynamic rate control may be described in the general context of computer-executable instructions. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. Dynamic rate control may also be practiced in distributed computing environments where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer-executable instructions may be located in both local and remote computer storage media.

The methods ofFIGS. 8 and 9are illustrated in flow diagrams divided into multiple method blocks. However, the order in which the methods are described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement one or more methods for dynamic rate control. Furthermore, although the methods are described below with reference to television entertainment environments100and300and the algorithm of flow diagram400where applicable, the methods can be implemented in any suitable hardware, software, firmware, or combination thereof and using suitable mathematical alternatives.

FIG. 8is a flow diagram800that illustrates an exemplary method for dynamically controlling a data stream. Flow diagram800includes three method blocks802,804, and806that may be performed by dynamic rate control units304. At block802, a data stream is monitored in multiple overlapping windows. For example, a bit accumulation from the data stream in each of the multiple overlapping windows may be monitored to determine how fast the data stream is consuming bits. At block804, the data stream is compared to a data limit in each window of the multiple overlapping windows. For example, at a given particular absolute point of the data stream that is located at varying relative positions in each window of the multiple overlapping windows, the bit accumulation at the particular point is compared to an expected bit accumulation at the corresponding relative position in each window of the multiple overlapping windows.

At block806, the data stream is modified responsive to the comparisons. For example, if the bit accumulations in each window exceed the expected bit accumulations at the corresponding relative positions, then the data stream can be modified by reducing bit rate consumption. The bit rate consumption may be reduced by increasing the quantization coarseness of the compression/coding being applied to the underlying information flow. If, on the other hand, the bit accumulations in each window are below the expected bit accumulations at the corresponding relative positions, then the data stream can be modified by increasing bit rate consumption. Various compromises, interpolations, and/or averages may be employed when some bit accumulations are above and some bit s accumulations are below the expected bit accumulations at the corresponding relative positions in the multiple overlapping windows. Some examples of which are provided above with reference to flow diagram400(ofFIG. 4). For instance, greater (or lesser) weight may be given to the modification recommendation originating from a window in which the given particular point is located at a relative position that is near the end of that window.

FIG. 9is a flow diagram900that illustrates an exemplary method for dynamically controlling a data rate. Flow diagram900includes eight method blocks that illustrate a dynamic rate control where coding/compressing starts at a first bit rate and is changed to a second bit rate. The method of flow diagram900may be performed at dynamic rate control units304. At block902, an information flow is coded (e.g., encoded, transcoded, compressed, etc.) using a first bit rate parameter. Using an MPEG coding process, for example, the bit rate parameter may correspond to a quant_scale, a quant_matrix, or both. With respect to flow diagram400, the bit rate parameter may correspond to a first (current) TLCP430. At block904, the bit accumulation of the bit stream that results from coding the information flow is monitored over time. In effect, the bit consumption of the bit stream is tracked at various times (as the flow diagram900is repeated during real-time use). These various times are notable as corresponding to the current bitcount accumulation.

The variance between the actual bit accumulation and an expected bit accumulation is determined at block906. The expected bit accumulation is predetermined for each time window based on bandwidth limits. A bit rate change recommendation may be determined from the variance. This bit rate change recommendation may correspond to a WLM of aspect416of flow diagram400. At block908, a bit rate recommendation for the current time window is determined from the variance (e.g., using a respective bit rate change recommendation). This determination may ultimately correspond to aspect420. At decision block910, it is determined whether there are still additional time windows for consideration. If so, then flow diagram900continues at block904to repeat blocks904-908for another time window. If not, then flow diagram900continues with block912. In other words, if all of the relevant overlapping time windows have been analyzed to secure a bit rate recommendation therefrom, then the method can proceed to combine them. It should be understood that all or part of the “repeating” of blocks904-908may be occurring substantially simultaneously.

At block912, the bit rate recommendations are combined. The bit rate recommendations for multiple time windows as determined in repeated performances of block908are thus combined. This combination may correspond to aspect424of flow diagram400. A second bit rate parameter is determined based on the combination at block914. The second bit rate parameter may correspond to a second (current) TLCP430. As such, the second bit rate parameter may be determined (i) directly from the combination of bit rate recommendations or (ii) using the first bit rate parameter (optionally along with other previous bit rate parameters) and the combination of bit rate recommendations in an autoregressive or other (e.g., mathematical) model. The latter option may correspond to aspects422,426, and428of algorithm400. After the second bit rate parameter is determined, coding is effectuated using the second bit rate parameter at block916. Flow diagram900may be repeated as the information flow/data stream is coded into the bit stream according to the current bit rate parameter. The bit stream may also be contemporaneously being forwarded from dynamic rate control unit304to output component308, local output component314, memory storage312, and so forth.

CONCLUSION

Although systems and methods have been described in language specific to structural features and/or methods, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary forms of implementing the claimed invention.