Data rate control for variable rate compression systems

• US 6,023,233 A
• Filed: 03/20/1998
• Issued: 02/08/2000
• Est. Priority Date: 03/20/1998
• Status: Expired due to Fees

• Current Assignee: Craven, Peter G., Malcolm J. Law
• Original Assignee: Craven, Peter G., Malcolm J. Law
• Inventors: Law, Malcolm J., Craven, Peter G.
• Primary Examiner(s): YOUNG, BRIAN K
• Application Number:
  US09/044,986
• Time in Patent Office: 690 Days
• Field of Search: 341/51, 341/55, 341/50, 375/240, 370/395
• US Class Current: 341/51
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

An encoder for a data compression system comprises a core encoder and a FIFO buffer. The FIFO buffer is able to absorb short bursts of high data rate and deliver the data to a transmission medium at a rate that it can handle. A corresponding decoder includes a FIFO buffer which receives data at a rate not exceeding the maximum that the transmission medium can deliver, but delivers data to a core encoder at a rate which can, for short periods, greatly exceed the rate from a transmission medium. With consumer media such as CD and DVD, the decoder cost is paramount so it is important to minimize the size of buffer memory required. Another consideration is the delay caused by the buffering since it is important to the latency between the user selecting a track or index point and hearing the decoded audio.

Claims

1. A method of encoding a stream of input data samples to produce a stream suitable for use with a transmission medium having a limitation of peak data rate, comprising the steps of:

encoding the input data samples to produce a variable-rate stream of encoded data;

feeding the variable-rate stream to a FIFO buffer; and

, controlling the rate at which data are fed from the FIFO buffer to an output so that the rate at the output does not exceed a predetermined rate.

2. A method according to claim 1, further comprising the step of

transmitting to the output information relating to the amount of data in the FIFO buffer.

3. A method according to claim 1, further comprising the step of transmitting to the output information indicating the amount of data in the FIFO buffer to enable a decoder to determine when to start decoding.

4. A method according to claim 1, in which the said step of encoding performs lossless compression.

5. A method according to claim 1, in which the said step of encoding performs lossy compression.

6. A method according to claim 1, in which the said step of encoding further comprises the steps of:

quantising the said input data samples to produce a lower-resolution stream; and

, losslessly compressing the said lower-resolution stream.

7. A method according to claim 1, in which the input data is a video signal.

8. A method according to claim 1, in which the input data is an audio signal.

9. A method according to claim 1, in which the said step of controlling is accomplished by transferring to the output at each of a predetermined time-step, an amount of data which is the smaller of the amount of data remaining in the FIFO buffer and the maximum amount allowed by the said predetermined rate.

10. A method according to claim 1, further comprising the step of maintaining a model of a corresponding decoder, the decoder comprising a FIFO buffer followed by a core decoder, wherein the encoder assumes an initial delay between the decoder receiving the encoded stream and passing it to the core decoder, the decoder'"'"'s FIFO buffer filling partially during the delay, and in which the said step of controlling is performed so that the decoder'"'"'s FIFO buffer should not under-run.

11. A method according to claim 10, in which the said FIFO buffer in the model decoder is assumed to have a finite capacity, and in which the said step of controlling is performed with regard also to the criterion that the model decoder'"'"'s FIFO buffer should not over-run.

12. A method according to claim 10, further comprising the step of processing data relating to the data rate of the said variable-rate stream in order to determine a value for the said initial delay such that the said decoder'"'"'s FIFO buffer will not under-run.

13. A method according to claim 10, further comprising the steps of:

deriving from the said model a varying delay between the decoder'"'"'s reception of a part of the transmitted stream and its decoding by the core decoder; and

, periodically transmitting information relating to the said varying delay, thereby enabling a decoder which is presented with a part of the encoded data-stream not including its beginning to determine an appropriate delay after which to start decoding.

14. A method according to claim 10, further comprising the step of adjusting the amount of data transmitted in each of a predetermined time-step to minimise the amount of data in the FIFO buffer of the said model decoder, and thereby minimise the decode latency of the encoded stream.

15. A method according to claim 14, in which the said step of adjusting is performed by processing in reverse order data relating to the data rate of the said variable-rate stream.

16. A method according to claim 14, in which the said step of adjusting uses a finite look-ahead over data relating to the data rate of the said variable-rate stream.

17. A method according to claim 1, further comprising the step of performing a pre-scan of the entire stream of data to be transmitted to determine a value for the said predetermined rate.

18. A method according to claim 1, in which the said encoded stream of data is transmitted together with another stream of data, further comprising the step of processing data relating to the data rate of other stream of data at a number of instants to determine an appropriate value for the said predetermined rate at each instant.

19. A method according to claim 1, in which the said step of encoding is parameterisable in a manner that affects the data rate of the said variable-rate stream, further including the step of adjusting the parameters in response to the amount of data in a buffer which receives the said variable-rate stream.

20. A method according to claim 19, in which the buffer is the FIFO buffer.

21. A method according to claim 19, in which the buffer is a simulated buffer which empties at a rate responsive to the amount of data it contains.

22. A method according to claim 19, in which the step of encoding is lossy and discards an amount of data which increases as the said buffer fills.

23. A method according to claim 22, in which the said step of encoding further comprises the steps of:

quantising the said input data samples to produce a lower-resolution stream; and

, losslessly compressing the said lower-resolution stream, wherein a step size used in the quantising increases as the said buffer fills.

24. A method according to claim 19, in which the said step of adjusting the parameters includes adjusting the computational effort applied in the said step of encoding.

25. A recording medium (including, without limitation, CD or DVD) containing an encoded data stream produced using the method of claim 1.

26. A recording medium according to claim 25, in which the encoded data stream includes information to allow an appropriate decoder, comprising an input which feeds a FIFO buffer, and a core decoder which reads data from the FIFO buffer at a variable rate which sometimes exceeds the maximum rate of the input stream, and delivers decoded data to an output, arranged so that after the serial stream is applied to the input there is a delay before the core decoder entracts the data from the FIFO buffer and decodes it, to determine said delay.

54. An encoder according to claim 32, adapted to operate in accordance with the method of claim 1.

27. A data-compression system for producing a variable-rate compressed stream with a limited peak rate, comprising an encoder having a core encoder followed by a FIFO buffer, and a decoder having a FIFO buffer followed by a core decoder, such that during passages of peak data rate, the decoder'"'"'s FIFO buffer delivers data to the core decoder at a faster rate than the said limited peak rate.

28. A data-compression system according to claim 27, wherein the encoder is configured to transmit information which allows the decoder to establish an appropriate delay through the decoder'"'"'s FIFO buffer.

29. A decoder for a serial stream of compressed data, comprising an input which feeds a FIFO buffer, and a core decoder which is configured to read data from the FIFO buffer at a variable rate which sometimes exceeds the maximum rate of the input stream, and delivers decoded data to an output, arranged so that after the serial stream is applied to the input, there is a delay before the core encoder entracts the data from the FIFO buffer and decodes it.

30. A decoder according to claim 29, in which the said delay is determined by the decoder.

31. A decoder according to claim 29, in which the decoder is configured to read information from the input stream in order to determine the said delay.

32. An encoder for a serial stream of data, comprising a core encoder which delivers a variable-rate stream of compressed data, a FIFO buffer which receives data from the core encoder, and an output, the encoder being configured so that the rate at which data is transferred from the buffer to the output does not exceed a predetermined rate.

33. An encoder according to claim 32, which is configured to transmit information relating to the amount of data in the FIFO buffer.

34. An encoder according to claim 32, which is configured to transmit information indicating the amount of data in the FIFO buffer to enable a decoder to determine when to start decoding.

35. An encoder according to claim 32, in which the core encoder is adapted to perform lossless compression.

36. An encoder according to claim 32, in which the core encoder is adapted to perform lossy compression.

37. An encoder according to claim 36, in which the core encoder is configured for audio signals and comprises a prequantiser followed by a lossless encoder.

38. An encoder according to claim 32, in which the core encoder is adapted to perform compression of video signals.

39. An encoder according to claim 32, which is adapted to transfer at each of a predetermined time step to the output an amount of data which is the smaller of that remaining in the FIFO buffer and the maximum amount allowed by the said predetermined rate.

40. An encoder according to claim 32, comprising means for maintaining a model of a corresponding decoder, the decoder comprising a FIFO buffer followed by a core decoder, wherein the encoder assumes an initial delay between the decoder receiving the encoded stream and passing it to the core decoder, the decoder'"'"'s FIFO buffer filling partially during the delay, and on this assumption the encoder is operative to control the amount of data transmitted on each time step so that the decoder'"'"'s FIFO buffer does not under-run.

41. An encoder according to claim 40, in which the model assumes a finite capacity for the decoder'"'"'s FIFO buffer, and the encoder is operative to ensure that the decoder'"'"'s buffer does not over-run.

42. An encoder according to claim 40, in which the core encoder is configured to perform a pre-scan of the entire stream of data to be transmitted to determine a value for the said initial delay such that the said decoder'"'"'s FIFO buffer will not under-run.

43. An encoder according to claim 40, which is configured to derive from the said model a varying delay between the decoder'"'"'s reception of a part of the transmitted stream and its decoding by the core decoder, and transmit information related to the said varying delay, thereby enabling a decoder which is presented with a part of the encoded data-stream not including its beginning to start decoding the said part after an appropriate delay.

44. An encoder according to claim 32, which is configured to collect data relating to the data rate produced by the core encoder for the entire stream of data to be transmitted, and determine an appropriate value for the said predetermined data rate.

45. An encoder according to claim 40, which is configured to further adjust the amount of data transmitted in each time-step with the object of minimising the amount of data in the FIFO buffer of the said model decoder, and thereby minimise the decode latency of the encoded stream.

46. An encoder according to claim 45, which is adapted to perform said further adjustment using a backward pass over the data stream.

47. An encoder according to claim 45, which is adapted to perform said further adjustment using a look-ahead over a finite time-window on the transmitted stream.

48. An encoder according to claim 32, in which the said core encoder is parameterisable in a manner that affects the encoded data rate, and the parameters are adjustable in response to the amount of data in a buffer connected to the output of the core encoder.

49. An encoder according to claim 48, in which said buffer is the FIFO buffer.

50. An encoder according to claim 48, in which said buffer is a simulated buffer which is filled from the core encoder and emptied at a rate responsive to the amount of data it contains.

51. An encoder according to claim 49, in which the core encoder is lossy, and the amount of data discarded increases as the said buffer fills.

52. An encoder according to claim 51, in which the core encoder is a lossy encoder adapated for audio signals, comprising a prequantiser followed by a lossless encoder, wherein the said discarding of data is accomplished by increasing the step size of the prequantiser.

53. An encoder according to claim 48, in which the at least one of the said parameters controls the computational effort applied in the core encoder.