WO1997017809A1

WO1997017809A1 - Digital coding

Info

Publication number: WO1997017809A1
Application number: PCT/GB1996/002771
Authority: WO
Inventors: Peter Ashley Sarginson
Original assignee: British Broadcasting Corporation
Priority date: 1995-11-10
Filing date: 1996-11-11
Publication date: 1997-05-15
Also published as: GB9523042D0; GB2307151A; EP0860085A1

Abstract

The bit rate of an MPEG-2 or other digital coder can be varied without causing buffer underflow or overflow in a downstream decoder by controlling coder buffer occupancy and by employing an oversized coder buffer.

Description

DIGITAL CODING

This invention relates to digital coding and in the most important example to the coding of video signals for transmission or otherwise.

The digital broadcast channels currently being specified for use within Europe and elsewhere each have sufficient digital capacity to accommodate a number of independent television services bound together in a "multiplex".

It is a technically trivial matter to divide the total digital capacity of a multiplex into fixed bit-rate fractions each assigned to one service.

For a television service, it is usual for the video component to be compressed using a video compression algorithm such as that known as PEG-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 various reason. By lowering the video bit rate of existing services within a multiplex, space may be relinquished to accommodate an additional service. A service that is no longer required may be dropped from the multiplex and its digital capacity may be reassigned to those services remaining thereby increasing their video bit rates and thence their subjective picture quality. Service video bit rates may be reassigned dynamically according to programme content or other criteria. For example, bit-rate may be borrowed from a service carrying visual material that is easy to encode (e.g. a news reader talking in front of an otherwise stationary set) and used to help boost the video bit rate (and hence picture quality) of a service carrying more difficult programme material (e.g. a sports sequence - with fast action and camera pans).

Ideally, it should be possible to make such adjustments whilst the multiplex is "on-air" 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 buffer" 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 underflow 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:

f

}(r _* Ar ).dt < B_d + Bo^^ t-τ

ln 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 Δr/r of the desired bit rate change Δr to the original bit rate r, with fixed limits which are typically

1 and -1 .

Advantageously, the size of the coder buffer B_c is greater than the size of the decoder buffer B_d , and said fixed limits are BJB_d and -1 .

Suitably, 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 falls within acceptable limits, comprises comparing the coder buffer occupancy ratio at aπ 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 showing permitted coder buffer occupancy versus change in bit rate 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 versus change in bit rate in a modified arrangement according to the present invention;

The invention can usefully be described with respect to the "reference system" shown in Figure 1. Such systems are well known especially within the field of digital television broadcasting.

Input video is compressed by a video coder (10) according to a video compression algorithm such as that known as MPEG-2. 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 "underflow"). 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 (fullness) 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, B_c and the decoder buffer size, j9,to be equal.

B_c = B_d = 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 lineariy 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, 7 " 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 curves are identical except that they are separated in time by an amount equal to the buffer delay, T.

If

t₂ - i = T [2]

the coder buffer occupancy at time t„ Bo_*, and the decoder buffer occupancy at time f, Bo_M when added together will equal the buffer size fl.

Bo^ + Bo_dt2 = B [3]

Thus, there is a complementary relationship between the coder buffer occupancy at time t, and the decoder buffer occupancy at time f.: If the coder buffer is π% full at time f_{T I} the decoder buffer will be (100-π)% full at time t,.

The complementary relationship between coder and decoder buffer occupancies may be exploited as follows. 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 is transferred from coder buffer to decoder buffer) is changed and this is illustrated in Figures 3 and 4.

Figure 3 illustrates the effect of a sustained increase in bit rate on the reference system. The point where the decoder read address curve crosses the minimum decoder read address limit represents the onset of decoder buffer overflow. For increases in bit rate of 100% or more, it will be found to be quite impossible to draw a coder write address curve that does not result in decoder buffer overflow. For increases in bit rate less than 100% it will be found possible to devise a coder write address curve that does not cause decoder buffer overflow but only by constraining the permitted range of coder buffer occupancy towards the higher end of the coder buffer. Such constraints are undesirable and may be impossible to achieve in a practical system.

Figure 4 illustrates the effect of a sustained decrease in bit rate on the reference system. The point where the decoder read address curve crosses the decoder write address line represents the onset of decoder buffer underflow. Although buffer underflow 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, 7^* , 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, T_c and the time taken for the item of data to propagate through the decoder buffer, 7^",. Referring to Figure 2:

τ = τ_{c +} τ_d = ^{Bo<» + Bo<«} [4]

where:

Bo_a, is the coder buffer occupancy at time t, . Bo„ is the decoder buffer occupancy at time t,. (Δr + r) is the bit rate

re-arranging for Bo„:

Bo_dt2 = (r * AήT - Bo^ [5]

Thus if T is kept constant, an increase in the bit rate (i.e. Δr > 0) will result in a higher decoder buffer occupancy at time f, than would be observed for the same value of coder buffer occupancy when operating at the original bit rate (i.e. Δr = 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. Δr < 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, Δr , then the constrained range of permitted coder buffer occupancy, Bo_c is given by:

B > Bo„ ≥ B Δr Δr ≥ 0 [6]

fl (1 + AL) > Bo_c ≥ 0 Δr ≤ 0 [7]

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:

-1 < ( — ) < 1 [8] r

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 f the following relationship must be satisfied:

t f(r + Ar ).dt < B_d + flo, -Kt-T) [9] t-τ

Similarly, to avoid decoder buffer underflow at time, f, the following relationship must be satisfied:

/(r ₊ Δr ).Λ > flo_c(/.7) [10] t-τ

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 original value (Δr = 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 underflow 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 meaning that 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 original bit rate (Δr = 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 [7]. 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 (Δr = 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 original bit rate as an intermediate step). In contrast, control procedures as illustrated in Figure 8 require a

"tighter" coupling between coder and controller meaning that 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, fl . Now consider a video coder possessing a buffer of size, fl_c where fl, > fl . 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:

.?• > > -ι [11] fl r

provided that the coder buffer occupancy is constrained as follows

B_c > Bo_{0 ≥} B £ B,

> — Δr ≥ B r f - 1 [12] l

fl 1 0 [13]

fl 1 + L \ > Bo_n ≥ 0 Δr < 0 [14]

Figure 9 is a graph of permitted coder buffer occupancy plotted against (Δr/r) for a coder possessing a large buffer. It is apparent that the range of possible bit rates has been increased when compared to Figure 5 which shows the equivalent graph for a coder with buffer of size, fl . Also apparent and of special importance is the fact that for operation at bit rates in the range:

the range of coder buffer occupancy is not reduced, i.e:

- B_0cmln = B [16]

where: flo„_™ is the maximum permitted buffer occupancy. flo^ 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 underflow of the decoder buffer and without requiring a reduction in the range of coder buffer occupancy. The coder buffer is with advantage at least twice the size of the decoder buffer and, with further advantage, at least four times the size of the decoder buffer, in MPEG-2, there is defined the VBV (Virtual Buffer Verifier) buffer. According to the present invention, a coder buffer size is preferably at least twice and more preferably four times the size of the VBV buffer.

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_^ 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 and claims is for reference set out below:-

t, t„ t, Moments in time. (Units : seconds).

7 Buffer delay. (Units : seconds). Generally 7 = _B_. r B_c Size of coder buffer. (Units : bits) fl. Size of decoder buffer. (Units : bits) fl Nominal buffer size. (Units : bits). In this document B_c ≥ B = B„. Bo_c Coder buffer occupancy. (Units : bits).

Bo„ Decoder buffer occupancy. (Units : bits). flo_rt, Coder buffer occupancy at time, f,. (Units : bits). flo_Λ Decoder buffer occupancy at time, ζ. (Units : bits).

BO^_T, Coder buffer occupancy at time, (t-T). (Units : bits). o_^, Maximum permitted coder buffer occupancy. (Units : bits). o^ Minimum permitted coder buffer occupancy. (Units : bits). r Nominal bit rate. (Units : bits per second).

Δr Offset from nominal bit rate. (Units : bits per second). May be positive or negative.

Claims

1. 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:

t

2. A coder incorporating a buffer of size greater than is required for operation at a single fixed output data rate in order to permit sustained changes to be made to its output data rate over a greater range of possible data rates when compared to a coder incorporating a buffer of the size required for operation at a single fixed output data rate, the coder comprising means for controlling 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: t

t

3. 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.

4. A method according to Claim 3, wherein the coder buffer size is at least twice the nominal decoder buffer size.

5. A method according to Claim 4, wherein the coder buffer size is at least four times the nominal buffer size.

6. A method according to any one of Claims 3 to 5, wherein the step of testing whether a desired bit rate change falls within acceptable limits, comprises comparing the ratio Δr/r of the desired bit rate change Δr to the current bit rate r, with fixed limits.

7. A method according to Claim 6, wherein said fixed limits are 1 and -1.

8. A method according to Claim 6, where the size of the coder buffer B is greater than the size of the decoder buffer B_d , and wherein said fixed limits are BJB_ύ and -1 .

9. A method according to any one of Claims 6 to 8, wherein 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.

10. A method according to any one of Claims 3 to 5, wherein the step of testing whether a desired bit rate change falls 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.

11. A method according to Claim 10, wherein the step of testing utilises the following inequality:

B_d +

> /(r + Aή.dt > flo, c(f-7) t-T

where Bo_e(t__η is the coder buffer occupancy at time t-T , B_d is the size of the decoder buffer and T is the buffer delay.

12. A method according to any one of Claims 3 to 5, wherein for a desired bit rate increase of Δr from a current bit rate of r , the coder buffer occupancy is constrained to be greater than or equal to the proportion Δr/r of the coder buffer size.

13. A method according to any one of Claims 3, 4, 5 or 12, wherein for a desired bit rate decrease of Δr from a current bit rate of r , the coder buffer occupancy is constrained to be less than the proportion (1+Δr/r) of the coder buffer size.

14. 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, wherein the size of the coder buffer exceeds that of the decoder buffer and wherein buffer occupancy constraints are imposed upon the coder buffer in dependence upon the desired bit rate change.