DIGITAL CODINGThis invention relates to digital coding and in the most important example to thecoding of video signals for transmission or otherwise.
The digital broadcast channels currently being specified for use within Europe andelsewhere each have sufficient digital capacity to accommodate a number ofindependent television services bound together in a "multiplex". It is a technically trivialmatter to divide the total digital capacity of a multiplex into fixed bit-rate fractions eachassigned to one service.
For a television service, it is usual for the video component to be compressedusing a video compression algorithm such as that known as MPEG-2 . Despite the use of video compression it will generally be the case that the encoded video data stream occupies the majority of the bit-rate allocated to that service.
The ability to subsequently change the video bit rate allocations of services sharing a multiplex is attractive to a broadcaster for the following reasons:1. By lowering the video bit rate of existing services within a multiplex,space may be relinquished to accommodate an additional service.
2. A service that is no longer required may be dropped from the multiplexand its digital capacity may be reassigned to those services remainingthereby increasing their video bit rates and thence their subjective picturequality.
3. Service video bit rates may be reassigned dynamically according toprogramme content. For example, bit-rate may be borrowed from aservice carrying visual material that is easy to encode (e.g. a news readertalking in front of an otherwise stationary set) and used to help boost thevideo bit rate (and hence picture quality) of a service carrying moredifficult programme material (e.g. a sports sequence - lots of fast actionand camera pans).
Ideally, it should be possible to make such adjustments whilst the multiplex is "onair" and without causing any interruption of the received services. Unfortunately, for reasons that will be described, it is technically very difficult (and often impossible) to make sustained changes to service video bit rates without upsetting the video decoder in the receiver. (It is always possible to drop a group of services from a multiplex and then re-introduce the group with a different assignment of bit-rates but this will clearly cause an Interruption of the affected services at the receiver).
The reason for the difficulty is as follows: A digital television broadcast receiver contains a video decoder whose function is to reverse the encoding process performed by the video coder in order to recover the original picture. An important part of a video decoder is the decoder buffers which is used to store coded video data prior to decoding. Study of the behaviour of the decoder buffer shows that a sustained change in the bit rate assigned to the video component of an on-air service will almost certainly lead to overflow or underfiow of the buffer. Either condition is highly undesirable and will result in corruption of the decoded picture and may require a complete reset of the decoder in order to recover from the situation.
It is an object of this invention to provide an improved approach to coding which addresses this problem.
Accordingly, the present invention consists in one aspect in a method of making a sustainable change to the output data rate of a coder without at any time causing overflow or underflow of the buffer of a decoder to which the coder is directly or indirectly connected by means of modifying the upper and lower limits of permitted coder buffer occupancy before, during and after a change in bit rate such that at all times the following equations are satisfied:
In another aspect, the present invention consists in a method of coding a signal at a controllable bit rate in a coder having a coder buffer, the coded signal being adapted for decoding in a decoder having a decoder buffer, comprising the steps of testing whether a desired bit rate change falls within acceptable limits; imposing buffer occupancy constraints upon the coder buffer in dependence upon the desired bit rate change; and implementing the bit rate change.
Preferably, the step of testing whether a desired bit rate change falls within acceptable limits, comprises comparing the ratio Arir of the desired bit rate change Ar to the current bit rate r, with fixed limits which are typically 1 and -1Advantageously, the size of the coder buffer Bc is greater than the size of the decoder buffer Bd, and said fixed limits are BJBd and -1Suitably, the step of implementing the bit rate change is delayed after the attainment of said buffer occupancy constraints by a time interval not less than the buffer delay T.
Alternatively, the step of testing whether a desired bit rate change falis within acceptable limits, comprises comparing the coder buffer occupancy ratio at an earlier time spaced by a time interval, with a time integral over said interval of the bit rate increased by the desired bit rate change.
The invention will now be described by way of example, with reference to the accompanying drawings, in which:Figure 1 is a block diagram of a prior art broadcast chain proposal incorporating coding and multiplexing;Figure 2 is a graph illustrating the relationship between the occupancy of coder and decoder buffers;Figure 3 is a graph similar to Figure 2, illustrating decoder buffer overflow resulting from a step increase in bit rate;Figure 4 is a graph similar to Figure 2, illustrating decoder buffer underflow resulting from a step decrease in bit rate::Figure 5 is a graph of showing permitted coder buffer occupancy in one arrangement according to the present invention;Figure 6 is a block diagram illustrating one embodiment of the present invention; Figures 7 & 8 are flow charts illustrating "loose" and "tight" coupling control procedures, respectively, for the apparatus of Figure 6;Figure 9 is a graph of permitted coder buffer occupancy in a modified arrangement according to the present invention;The invention can usefully be described with respect to the Mreference system" shown in Figure 1. Such systems are well known especially within the field of digital television broadcasting. Input video is compressed according to a video compression algorithm such as that known as MPEG-2 by a video coder (10).The video coder generates a variable number of bits per input video picture depending on the picture content. The variable bit rate output from the video coder is converted to a fixed bit rate in the coder buffer (12). The coder buffer is a first-in-first-out memory device enabling data to enter the buffer at a variable bit rate and be removed at a fixed bit rate determined by the multiplexer (14). A feedback system is employed to prevent the coder buffer becoming too full (a condition known as "overflow") or empty (a condition known as "underfiow"). The coded video data is delivered along with other programme components via the digital broadcast channel to a demultiplexer (16). The demultiplexer extracts the coded video and delivers it at a fixed bit rate to the decoder buffer (18).
The video decoder (20) decodes pictures at regular intervals determined by the television standard being used (e.g. 25 pictures per second). However, because each picture is represented by a variable amount of data this necessarily means that the video decoder must read a variable amount of data per picture period from the decoder buffer.
Thus the decoder buffer adapts the fixed bit rate video from the demultiplexer to the variable bit rate needs of the video decoder. Reconstructed video is output from the video decoder.
In systems of the type described by this reference system, there is a relationship between the occupancy (fuliness) of the coder and decoder buffers and this may be illustrated on a diagram as shown in Figure 2.
Figure 2 shows how the positions (addresses) of the write and read pointers within the coder and decoder buffers vary with time. It is usual for the coder buffer size, Be and the decoder buffer size, B,to be equal.
B0 =Bd = B [1]The buffers are "circular" meaning that when a write or read pointer reaches address (B - 1) it is automatically reset to address 0 upon the next address increment.
This is reflected in the labelling of the vertical axis in Figure 2.
Variable bit-rate data is input to the coder buffer. Thus the coder buffer write address does not increment linearly with time. Data is read from the coder buffer at a fixed bit rate and so the coder buffer read address does increment linearly with time.
Data read from the coder buffer is transferred via the multiplexer, broadcast channel and demultiplexer to the decoder buffer. This transfer process will take a fixed and finite time, however, in this analysis for the sake of clarity and without loss of generality the transfer time is ignored and the coder buffer read address and decoder buffer write address are assumed to be equal for all time, t. Thus, in Figure 2 it is shown that data read from coder buffer address n is instantaneously transferred and written into decoder buffer address n.
The video coder and the video decoder must process the same number of pictures per unit time, otherwise the decoded video will suffer temporal distortion ("playback" of the decoded video will be too slow or too fast). Therefore there must exist a fixed delay between a picture being coded in the video coder and subsequently decoded at the video decoder. Pursuing this line of reasoning to its conclusion it can be shown that there must exist a fixed delay between data being written into the coder buffer and the same data being read from the decoder buffer. This delay is shown as the "buffer delay,T" in Figure 2. The presence of this fixed delay enables the following important conclusions to be reached concerning the relationship between the coder buffer and the decoder buffer illustrated in Figure 2: 1.The shape of the coder write address and decoder read address curvesare identical except that they are separated in time by an amount equalto the buffer delay, T.
2. If 4 - t' = T (2] the coder buffer occupancy at time ti, Bo, and the decoder bufferoccupancy at time d Bo, when added together will equal the buffersize B.
Bo, + Bo, = B [3]Thus, there is a complementary relationship between the coder bufferoccupancy at time t, and the decoder buffer occupancy at time d: If thecoder buffer is rX6 full at time t" the decoder buffer will be (100-n)% fullat time t,.
The complementary relationship between coder and decoder buffer occupancies is extremely useful. A coder will generally contain a sophisticated internal control system to prevent the coder buffer becoming too full (overflow) or too empty (underflow). So long as the control system achieves this goal it is certain that the decoder buffer will also never overflow or underflow.
Unfortunately, this is no longer the case if the bit rate (i.e. the rate at which data istransferred from coder buffer to decoder buffer) is changed and this is illustrated inFigures 3 and 4.
Figure 3 illustrates the effect of a sustained increase in bit rate on the referencesystem. The point where the decoder read address curve crosses the minimum decoderread address limit represents the onset of decoder buffer overflow. For increases in bitrate of 100% or more, it will be found to be quite impossible to draw a coder writeaddress curve that does not result in decoder buffer overflow. For increases in bit rateless than 100% it will be found possible to devise a coder write curve that does notcause decoder buffer overflow but only by constraining the permitted range of coder buffer occupancy towards the higher end of the coder buffer. Such constraints areundesirable and may be Impossible to achieve in a practical system.
Figure 4 illustrates the effect of a sustained decrease in bit rate on the referencesystem. The point where the decoder read address curve crosses the decoder writeaddress line represents the onset of decoder buffer underflow. Although bufferunderflow will generally be the result of a decrease in bit rate, it is always possible to devise a coder write curve that does not cause decoder buffer overflow. However, to achieve this it is necessary to constrain the coder buffer occupancy towards the lower end of the coder buffer. Again, such constraints are undesirable and may be impossible to achieve in a practical system.
The reason a sustained change in bit rate may lead to decoder buffer overflow or underflow is as follows: It is essential that the buffer delay, T, remains constant regardless of any changes in bit rate, otherwise temporal distortion of the decoded video will occur. The buffer delay is made up of two components. They are the time taken for an item of data to propagate through the coder buffer, To and the time taken for the item of data to propagate through the decoder buffer, T,.
Referring to Figure 2: T= To + Td = Bo + BOd [4]o 1 where: Bo, is the coder buffer occupancy at time t,.
Bo, is the decoder buffer occupancy at time t,.
(Ar + r) is the bit ratere-arranging for Bio,: Bod;, = (r + Ai)T - Bo, [5]Thus if T is kept constant an increase in the bit rate (i.e. Ar > 0) will result in a higher decoder buffer occupancy at time t, than would be observed for the same value of coder buffer occupancy when operating at the original bit rate (i.e. Ar = 0) . The increase in decoder buffer occupancy makes decoder buffer overflow likely (or certain) particularly if the bit rate is Increased by a large amount or the coder buffer occupancy is low.Similarly, a decrease in the bit rate (i.e. Ar < 0) will result in a lower decoder buffer occupancy compared to that resulting from operation at the original bit rate and thus decoder buffer underflow is likely.
In one aspect, the present invention provides a novel method of controlling a video coder such that sustained changes in bit rate may be achieved over a limited range subject to certain constraints without causing interruption of the decoded video.
Further consideration of equation [4] will show that limited sustained changes in bit rate may be accommodated without causing overflow or underflow of the decoder buffer provided that the coder buffer occupancy is constrained to a reduced range. Applied to the reference system of Figure 1 where equations [1], [2] and [3] apply and assuming that the original bit rate, r is changed by an amount, Ar ,then the constrained range of permitted coder buffer occupancy, Bo, is given by:
There is shown in Figure 5 a graph of permitted coder buffer occupancy if underflow or overflow of the decoder buffer is to be prevented during a sustained change of bit-rate. It is apparent from this graph that the range over which the bit rate may be changed is limited to the range:
i.e. Between 0 and twice the original bit rate. Operation towards the extremes of this range requires severe limitation of the range of permitted coder buffer occupancy and this may be impossible to achieve in a practical video coder. However, for small changes in bit rate the limitation of coder buffer occupancy range may be acceptable.
The following are general equations which must always be satisfied if decoder buffer overflow and underflow are to be avoided. They are based on the work of Dr N.D.
Wells in GB-B-2 2420 97, to which reference is directed.
To avoid decoder buffer overflow at time t the following relationship must be satisfied:
Similarly, to avoid decoder buffer underflow at time, t, the following relationship must be satisfied:
It can be shown that in order to guarantee that these equations are satisfied during a change of bit rate, it is necessary for the coder to attain the constrained buffer occupancy range a time, T before the bit rate is changed (where T is the buffer delay).
Once the bit rate has assumed the new value, the coder must maintain its buffer occupancy within the constrained range until the bit rate is restored to the nominal value (,nor = 0 ).
Using an approach according to this invention, it is possible to control an otherwise conventional video coder such that sustained changes in its output bit rate may be made without causing underfiow or overflow of the decoder buffer. A possible implementation is shown in Figure 6.
In Figure 6, the output bit rate of the video coder (60) may be freely varied over the range defined by equation [8]. The "coder controller" block (62) is responsible for orchestrating the bit rate changes in such a way as to prevent overflow or underflow of the decoder buffer. The coder controller has a means to convey instructions to the video coder and a means of receiving messages returned from the coder. The "demand clock generator" block (64) effectively sets the actual output bit rate of the video coder under the direction of the coder controller.
Note that in a digital television broadcast system such as shown in Figure 1, the coder controller and the demand clock generator may form part of the multiplexer and the data passed from the coder to the coder controller may be incorporated into the coded video data stream.
It is possible to devise control procedures for the coder controller that facilitate a sustained change in the output bit rate of the video coder whilst ensuring that equations [9] & [10] are always satisfied and hence without causing overflow or underflow of the decoder buffer. Two examples of these are given in the flowcharts of Figures 7 and 8.
They are referred to as "loosely coupled" and "tightly coupled" respectively.
Control procedures as illustrated in Figure 7 permit a fairly "loose" coupling between coder and controller. The dialogue between coder and coder controller is quite relaxed, permitting the use of low data rate connections. Such a control procedure may be especially useful in situations where the coder is physically remote from the coder controller.
The loose coupling procedure operates as follows. It is assumed that the coder is initially operating at its nominal bit rate (Ar = 0). When a change in bit rate is desired, the coder controller (62) instructs the coder (60) to attain the appropriate constrained buffer occupancy range as determined by equations [6] and m. This may be achieved by modifying the maximum and minimum permitted buffer occupancy limit parameters in the coder's internal buffer control system. On achieving stable operation within the constrained range, the coder informs the coder controller. To ensure that equations [9] and [10] are satisfied under all conditions, the controller must now wait a time, T before instructing the demand clock generator to implement the new bit rate.To return subsequently to the original bit rate (Ar = 0), the coder controller (62) simply instructs the demand clock generator (64) to restore the original bit rate and informs the coder (60) that the constraints on buffer occupancy may be removed. (It is possible to extend this basic procedure to permit changes from one bit rate to another without returning to the nominal bit rate as an intermediate step).
In contrast, control procedures as illustrated in Figure 8 require a "tighter" coupling between coder and controller. The coder continually passes data to the controller and a fairly high bandwidth connection is required to support this. The advantage of this type of procedure is that the controller may instantaneously change the bit rate, that is to say there is no need to wait a time, T.
In the tightly coupled control procedure, data is continually conveyed from the coder to the controller such that at any moment, the amount by which the bit rate may be increased or decreased (without causing overflow or underflow of the decoder buffer) is known. For any time, t, this may be determined by observing the coder buffer occupancy over the previous time period, T. Application of equations [9] & [10] will enable the available range of bit rate variation to be determined. This calculation may be performed by the coder or by the controller. In the former case, it is the available range of bit rate variation that is continually conveyed to the controller and in the latter case it is the instantaneous buffer occupancy (or something closely related to it) that is continually conveyed to the controller.
Many variations and combinations of the two basic control procedures are possible.
In a second aspect of this invention, it has been recognised by the present inventor that the range of possible bit rates may be greatly increased and the constraints on buffer occupancy range may be reduced, if the video coder is fitted with a "coder buffer" of greater than conventional size.
Thus far, it has been assumed that the coder and decoder buffers are of equal size, B. Now consider a video coder possessing a buffer of size, Bc where B, > B.
Consideration of equation [4] will show that for such a coder sustained changes in bit rate without causing overflow or underflow of the decoder buffer may be accommodated over the following extended range:
provided that the coder buffer occupancy is constrained as follows
Figure 9 is a graph of permitted coder buffer occupancy plotted against (Ar/r) for a coder possessing a large buffer. It is apparent that the range of possible bit rates has beenincreased when compared to Figure 5 which shows the equivalent graph for a coder withbuffer of size, B. Also apparent and of special importance is the fact that for operationat bit rates in the range
the range of coder buffer occupancy is not reduced. i.e: Bo, Bo,""" = B [16]where: Bo is the maximum permitted buffer occupancy.
Bo~ is the minimum permitted buffer occupancy.
Thus a coder possessing a large buffer can support sustained changes in its output bit rate without causing overflow or underfiow of the decoder buffer and without requiring a reduction In the range of coder buffer occupancy.
Equations [9] and [10] are still valid for a coder possessing a large coder buffer and must be satisfied at all times if overflow and underflow of the decoder buffer is to be avoided. Thus a control procedure designed to facilitate the adjustment of the output bit rate of a coder possessing a large coder buffer must ensure that equations [9] and [10] are satisfied before, during and after the change of bit rate.
A variety of control procedures are possible including enhancements of the "loosely coupled" and "tightly coupled" procedures presented earlier. A further possibility is to avoid the use of a step change in bit rate but instead to change the bit rate slowly from one value to another whilst at the same time slowly changing the values of Bo r and Bo, in such a way as to ensure that equations [9] and [10] are satisfied at all times.
A glossary of the symbols used in this description and the accompanying drawings is for reference set out be low t, b 5 Moments in time. (Units: seconds).
T Buffer delay. (Units: seconds). GenerallyB, Size of coder buffer. (Units: bits) Size of decoder buffer. (Units: bits)B Nominal buffer size. (Units : bits). In this documentSo, Coder buffer occupancy. (Units: bits).
Bo, Decoder buffer occupancy. (Units: bits).
So,,, Coder buffer occupancy at time, t,. (Units: bits).
Bo, Decoder buffer occupancy at time, t,. (Units : bits).
Bo, n Coder buffer occupancy at time, (t-7). (Units: bits).
Bo, Maximum permitted coder buffer occupancy. (Units : bits).
Box Minimum permitted coder buffer occupancy. (Units : bits).
r Nominal bit rate. (Units : bits per second).
Ar Offset from nominal bit rate. (Units: bits per second). May be positive or negative.