Rational input buffer arrangements for auxiliary information in video and audio signal processing systems

Claims

I claim:

1. A method of generating a bit stream by multiplexing non-compressed auxiliary information with an information stream, the information stream being obtained by compressing fixed-size units of an information signal with a varying compression ratio to provide varying-sized units of the information stream, the auxiliary information being for use in subsequently processing the information stream, the auxiliary information being composed of auxiliary information units, each of the auxiliary information units corresponding to one of the units of the information signal, the method comprising steps of:

dividing the information stream in time into information stream portions;

dividing the non-compressed auxiliary information in time into auxiliary information portions;

interleaving the information stream portions and the auxiliary information portions to provide the bit stream; and

controlling the information stream dividing, auxiliary information dividing, and interleaving steps by emulating decoding of the bit stream by a hypothetical system target decoder including demultiplexer means for demultiplexing the bit stream, a serial arrangement of an information stream buffer and an information stream decoder, and a serial arrangement of an auxiliary information buffer and an auxiliary information processor, each serial arrangement being connected to the demultiplexer means, the information stream dividing, auxiliary information dividing, and interleaving steps being controlled such that the information stream buffer and the auxiliary information buffer neither overflow nor underflow.

2. The method of claim 1, wherein, in the step of controlling the information stream dividing, auxiliary information dividing, and interleaving steps:

the demultiplexer means receives the bit stream and extracts therefrom the information stream and the auxiliary information for feeding to the information stream buffer and the auxiliary information buffer, respectively;

the information stream buffer has a first target size;

the auxiliary information buffer has a second target size;

the information stream decoder removes the varying-sized units of the information stream from the information stream buffer at a first target timing; and

the auxiliary information processor removes the corresponding auxiliary information units from the auxiliary information buffer at a second target timing.

3. The method of claim 2, wherein, in the interleaving step:

the bit stream comprises plural layers; and

the information stream portions and the auxiliary information portions are interleaved in the same one of the plural layers of the bit stream.

4. The method of claim 3, wherein the auxiliary information includes directory information for the information stream.

5. The method of claim 4, wherein:

the information stream includes plural access points, access points being ones of the varying-sized units of the information stream that are expandable without requiring expansion of others of the varying-sized units of the information stream; and

the directory information includes a unit of directory information relating to each of the access points.

6. The method of claim 5, wherein:

in the step of dividing the auxiliary information into auxiliary information portions, the directory information is divided into directory packets each including a number of the units of the directory information determined by the second target size;

in the step of dividing the information stream into information stream portions, each one of the information stream portions into which the information stream is divided includes the access points to which the directory information in a respective one of the directory packets relates; and

in the interleaving step, the respective one of the directory packets is interleaved adjacent the one of the information stream portions.

7. The method of claim 2, wherein, in the interleaving step:

the bit stream comprises plural layers; and

the information stream portions are interleaved in a first layer of the bit stream, and the auxiliary information portions are interleaved in a second layer of the bit stream, different from the first layer.

8. The method of claim 7, wherein the auxiliary information is a set of time stamps for decoding ones of the variable-sized units units of the information stream.

9. The method of claim 8, wherein:

in the controlling step, the auxiliary information buffer has an occupancy determined by the second target size, the auxiliary information fed from the demultiplexer means, and the auxiliary information removed by the auxiliary information processor;

the step of dividing the information stream into information stream portions divides the information stream into plural information packets;

the step of dividing the auxiliary information into auxiliary information portions results in auxiliary information portions each composed of one of the time stamps;

the step of interleaving the information stream additionally includes a step of generating an information packet header for each of the information packets; and

in the step of interleaving the information stream portions and the auxiliary information portions, one of the auxiliary information portions is inserted into the information packet header of ones of the information packets selected according to the occupancy of the auxiliary information buffer.

10. The method of claim 8, wherein:

in the controlling step, the auxiliary information buffer has an occupancy determined by the second target size, the auxiliary information fed from the demultiplexer means, and the auxiliary information removed by the auxiliary information processor;

the step of dividing the information stream into information stream portions divides the information stream into plural information packets;

the step of dividing the auxiliary information into auxiliary information portions results in auxiliary information portions each composed of one of the time stamps;

the step of interleaving the information stream portions additionally includes a step of generating an information packet header for each of the information packets;

in the step of interleaving the information stream portions and the auxiliary information portions, the auxiliary information portions are periodically inserted into the information packet header of the information packets at a time stamp coding frequency; and

in the controlling step, at least one of the time stamp coding frequency and the second target size is controlled in such a manner that maximizes the occupancy of the information stream buffer without causing the information stream buffer to overflow.

11. The method of claim 7, wherein:

the information stream decoder is one of plural information stream decoders, the information stream decoders being phase locked; and

the auxiliary information buffer has a size set to accommodate one and no more than one auxiliary information unit.

12. An encoder for generating a bit stream, the encoder comprising:

means for compressing fixed-size units of an information signal with a varying compression ratio to provide varying-sized units of an information stream;

information stream dividing means for dividing the information stream in time into information stream portions;

auxiliary information dividing means for dividing non-compressed auxiliary information in time into auxiliary information portions, the auxiliary information being for use in subsequently processing the information stream, the auxiliary information being composed of auxiliary information units, each of the auxiliary information units corresponding to one of the units of the information signal;

multiplexing means for sequentially arranging the information stream portions and the auxiliary information portions to provide the bit stream, the multiplexing means including a control means for controlling the information stream dividing means and the auxiliary information dividing means by emulating decoding of the bit stream by a system target decoder including demultiplexer means for demultiplexing the bit stream, a serial arrangement of an information stream buffer and an information stream decoder, and a serial arrangement of an auxiliary information buffer and an auxiliary information processor, each of the serial arrangements being connected to the demultiplexer means, the control means controlling the information stream dividing means and the auxiliary information dividing means such that the information stream buffer and the auxiliary information buffer neither underflow nor overflow.

13. The encoder of claim 12, wherein:

the demultiplexer means receives the bit stream and extracts therefrom the information stream and the auxiliary information for feeding to the information stream buffer and the auxiliary information buffer, respectively;

the information stream buffer has a first target size;

the auxiliary information buffer has a second target size;

the information stream decoder removes the varying-sized units of the information stream from the information stream buffer at a first timing; and

the auxiliary information processor removes the corresponding auxiliary information units from the auxiliary information buffer at a second target timing.

14. The encoder of claim 12, wherein:

the bit stream provided by the multiplexing means comprises plural layers; and

the multiplexing means arranges the information stream portions and the auxiliary information portions in the same one of the plural layers of the bit stream.

15. The system of claim 12, wherein:

the bit stream provided by the multiplexing means comprises plural layers; and

the multiplexing means arranges the information stream portions in a first layer of the bit stream and arranges the auxiliary information portions in a second layer of the bit stream, different from the first layer.

16. A system wherein an information signal is compressed for transfer, together with non-compressed auxiliary information, to a medium as a bit stream, and wherein the bit stream is transferred from the medium and is processed to recover the information signal by expansion, and to recover the auxiliary information, the auxiliary information being for use in subsequently processing the information signal, the system comprising:

an encoder comprising:

means for compressing the information signal to provide an information stream, fixed-sized units of the information signal being compressed using a varying compression ratio to provide varying-sized units of the information stream, and

multiplexing means for sequentially arranging time-divided portions of the information stream and time-divided portions of the non-compressed auxiliary information to provide the bit stream for transfer to the medium, the multiplexing means including control means for determining a division of the information stream and of the auxiliary information into the respective time-divided portions by emulating decoding of the bit stream by a system target decoder including demultiplexer means for demultiplexing the bit stream, a serial arrangement of an information stream buffer and an information stream decoder, and a serial arrangement of an auxiliary information buffer and an auxiliary information processor, each of the serial arrangements being connected to the demultiplexer means, the information stream buffer and the auxiliary information buffer each having a size; and a decoder, comprising:

demultiplexing means for extracting the information stream and the auxiliary information from the bit stream transferred from the medium,

first input buffer means for receiving the auxiliary information from the demultiplexing means, the first input buffer means having a size of at least the size of the auxiliary information buffer,

means for removing each of the auxiliary information units from the first input buffer means,

second input buffer means for receiving the information stream from the demultiplexing means, the second input buffer means having a size of at least the size of the information stream buffer, and

decoder means for removing each one of the varying-sized units of the information stream from the second input buffer means, and for expanding the one of the varying-sized units of the information stream removed from the second input buffer means to recover a respective one of the fixed-sized units of the information signal.

17. The system of claim 16, wherein the control means determines the division of the information stream and of the auxiliary information into the respective time-divided portions such that the bit stream, when subject to the emulated decoding by the system target decoder causes the information stream buffer and the auxiliary information buffer neither to underflow nor overflow.

18. The system of claim 16, wherein: the bit stream provided by the multiplexing means has plural layers; and the multiplexing means arranges the time-divided portions of the information stream and of the non-compressed auxiliary information in the same one of the plural layers of the bit stream.

19. The system of claim 18, wherein the auxiliary information is directory information relating to the information stream.

20. The system of claim 19, wherein:

the information stream includes plural access points, access points being ones of the varying-sized units of the information stream that are expandable without requiring expansion of others of the varying-sized units of the information stream; and

the directory information includes a unit of directory information relating to each one of the access points.

21. The system of claim 19, wherein:

the control means determines a division of the directory information into directory packets each including a number of units of the directory information, and determines a division of the information stream into the information stream portions such that each one of the information stream portions into which the information stream is divided includes the access points to which the directory information in a respective one of the directory; packets relates; and

the multiplexing means multiplexes the respective one of the directory packets adjacent the one of the information stream portions.

22. The system of claim 16, wherein:

the bit stream provided by the multiplexing means has plural layers; and

the multiplexing means arranges the information stream portions in a first layer of the bit stream and arranges the auxiliary information portions in a second layer of the bit stream, different from the first layer.

23. The system of claim 22, wherein the auxiliary information is a set of time stamps for decoding ones of the varying-sized units of the information stream.

24. The system of claim 23, wherein:

the auxiliary information buffer has an occupancy determined by the size of the auxiliary information buffer, the auxiliary information fed from the demultiplexer means, and the auxiliary information removed by the auxiliary information processor;

the control means is for:

determining a division of the information stream into plural information packets and generating an information packet header for each of the information packets,

determining a division of the set of time stamps into auxiliary information portions each composed of one of the time stamps;

periodically inserting ones of the auxiliary information portions into the information packet header of selected ones of the information packets at a time stamp coding frequency; and

controlling at least one of the time stamp coding frequency and the size of the auxiliary information buffer in such a manner that maximizes the occupancy of the information stream buffer without causing the information stream buffer to overflow.

25. A method of deriving a bit stream from an information signal, the method comprising steps of:

compressing units of the information signal to provide units of an information stream, the units of the information stream including access points, access points being ones of the units of the information stream that are expandable without requiring expansion of others of the units of the information stream;

deriving pointers from the information stream, each of the pointers pointing to one of the access points in the information stream; and

multiplexing the information stream with the pointers to provide the bit stream, the information stream being multiplexed with the pointers by:

generating information packets each including a portion of the information stream,

generating pointer packets each including different ones of the pointers, and

locating a set of the information packets containing plural consecutive ones of the access points adjacent a one of the pointer packets containing ones of the pointers pointing only to the plural consecutive ones of the access points.

26. The method of claim 25, wherein the multiplexing step includes steps of:

generating dummy pointers, and generating pointer packets each including the dummy pointers;

multiplexing the information packets with the pointer packets including the dummy pointers prior to the deriving step; and

overwriting the dummy pointers in each of the pointer packets in the bit stream with ones of the pointers derived in the deriving step, the ones of the pointers overwritten into each one of the pointer packets being the ones of the pointers pointing to the plural consecutive ones of the access points immediately preceding the one of the pointer packets in the bit stream.

27. A method of deriving a bit stream from an information signal, the method comprising steps of:

providing an encoder including:

means for compressing units of the information signal to provide units of an information stream,

first buffer means, having a size, for buffering the units of the information stream,

means for generating a time stamp when the first buffer means receives each of the units of the information stream,

second buffer means, having a size, for buffering the time stamps, and

multiplexing means for multiplexing the information stream from the first buffer means and the time stamps from the second buffer means to provide the bit stream;

defining a hypothetical system target decoder, the hypothetical system target decoder including demultiplexer means for demultiplexing the bit stream, a serial arrangement of an information stream buffer and an information stream decoder, and a serial arrangement of a time stamp buffer and a time stamp processor, each serial arrangement being connected to the demultiplexer means;

determining a first size for the first buffer means and a second size for the second buffer means by emulating decoding of the bit stream using the hypothetical system target decoder; and

encoding the information signal using the encoder with the size of the first buffer means and the size of the second buffer means respectively set to the first size and the second size determined by the determining step.

28. The method of claim 27, wherein:

in the step of defining the system target decoder:

the information stream buffer and the time stamp buffer each have a size, and

the information stream decoder decodes the information stream in response to ones of the time stamps removed from the time stamp buffer by the time stamp processor; and

in the determining step, the first size for the first buffer means and the second size for of the second buffer means are determined from the size of the information stream buffer and the size of the time stamp buffer.

29. The method of claim 28, wherein:

in the encoder, the multiplexing means periodically inserts the time stamps into the bit stream at a time stamp coding frequency;

the information stream has a bit rate; and

the determining step includes steps of:

determining a buffering delay from the time stamp coding frequency and the bit rate, and

determining the first size for the first buffer means and the second size for the second buffer means from the buffering delay.

30. A decoder for a bit stream obtained by multiplexing non-compressed auxiliary information with an information stream, the information stream being obtained by compressing fixed-size units of an information signal with a varying compression ratio to provide varying-sized units of the information stream, the auxiliary information being for use in subsequently processing the information stream, the auxiliary information including auxiliary information units, each of the auxiliary information units corresponding to one of the units of the information signal, the decoder comprising:

demultiplexing means for extracting the information stream and the auxiliary information from the bit stream;

first input buffer means for receiving the auxiliary information from the demultiplexing means;

removing means for removing each of the auxiliary information units from the first input buffer means;

second input buffer means for receiving the information stream from the demultiplexing means; and

decoder means for removing one of the varying-sized units of the information stream from the second input buffer means in response to each of the auxiliary information units removed from the first input buffer means by the removing means, and for expanding the one of the varying-sized units removed from the second input buffer means to recover a respective one of the fixed-size units of the information signal.

31. The decoder of claim 30, wherein the decoder means removes the one of the varying-sized units of the information stream from the second input buffer means at a time indicated by each of the auxiliary information units removed from the first input buffer means by the removing means.

FIELD OF THE INVENTION

This invention relates to apparatus for compressing and expanding digital information signals, and, in particular, to the buffering of auxiliary information included with information signals compressed with a dynamically varying compression ratio.

BACKGROUND OF THE INVENTION

For storage on or distribution via such media as CD-ROMs, laser disks (LDs), video tapes, magneto-optical (MO) storage media, digital compact cassette (DCC), terrestrial or satellite broadcasting, cable systems, fibre-optic distribution systems, telephone systems, ISDN systems etc., video and audio signals are compressed and coded, and the resulting video stream and audio stream are then multiplexed to provide a bit stream for feeding to the medium. The bit stream is later reproduced from the medium, is demultiplexed, and the resulting video stream and audio stream are decoded and expanded to recover the original audio and video signals.

Two of the main international standards related to compressing audio and video signals for storage on or distribution via a medium are those known as MPEG-1 and MPEG-2. These standards have been established by the Motion Picture Experts Group (MPEG) operating under the auspices of the International Standards Organization (ISO) and the International Electrotechnical Committee (IEC).

The MPEG standards are established under the assumption that they will be used in a wide range of applications. As a result, the standards allow for such possibilities a phase-locked system, in which the sampling rate clock of the audio signal is phase locked to the same clock reference (SCR) as the frame rate clock of the video signal, and a non phase-locked system in which the sampling rate clock of the audio system and the frame rate clock of the video system operate independently. Irrespective of whether the system is phase locked, the MPEG standards require the addition of a time stamp to the multiplexed bit stream at least once every 0.7 s, and that the encoder provide separate time stamps for use by the audio decoder and by the video decoder.

One of the aims of the MPEG standards is to provide maximum flexibility for encoder and decoder design while ensuring that the bit stream provided by any encoder can be successfully decoded by any decoder. One of the ways in which this compatibility is established is by the concept of the System Target Decoder.

A typical audio and video signal processing system 110 according to the MPEG-1 and MPEG-2 standards is shown in FIG. 1. In this, the encoder 100 receives the video signal S2 from the video signal storage medium 2, and receives the audio signal S3 from the audio signal storage medium 3. The audio signal S3 could alternatively be (and is more usually) also received from the video signal storage medium 2 instead of from a separate audio storage medium.

The encoder 100 compresses and codes the video and audio signals, and multiplexes the resulting audio stream and video stream to provide the multiplexed bit stream S100, which is fed for storage or distribution by the medium 5. The medium can be any medium suitable for storing or distributing a digital bit stream, for example, a CD-ROM, a laser disk (LD), a video tape, a magneto-optical (MO) storage medium, a digital compact cassette (DCC), a terrestrial or satellite broadcasting system, a cable system, a fibre-optic distribution system, a telephone system, an ISDN system, etc.

The encoder 100 compresses and codes the video signal picture-by-picture. Each picture of the video signal is compressed in one of three compression modes. A picture compressed in the intra-picture compression mode is called an I-picture. In the intra-picture compression mode, the picture is compressed by itself without reference to other pictures of the video signal. Pictures compressed in the inter-picture compression mode are called P-pictures or B-pictures. A P-picture is compressed using forward prediction coding using as a reference picture a previous I-picture or P-picture, i.e., a picture occurring earlier in the video signal. Each block of a B-picture may use as a reference block any one of the following: a block of a previous I-picture or P-picture, a block of a following P-picture or I-picture (i.e., a picture occurring later in the video signal), or a block obtained by performing linear processing on a block of a previous I-picture or P-picture and block of a following I-picture or P-picture. In addition, blocks of a B-picture may be compressed in the intra-picture compression mode. Typically, about 150 kbits (kb; 1 kb=1024 bits) of the video stream are required for an I-picture, 75 kb of the video stream are required for a P-picture, and 5 kb of the video stream are required for a B-picture.

The digital video and audio processing system 110 also includes the decoder 600, which receives as its input signal the bit stream S5 from the medium 5. The decoder performs demultiplexing inverse to the multiplexing performed in the encoder 100. The decoder also applies decoding and expansion to the resulting audio stream and video stream using processing complementary to that performed by the encoder 100 to provide the recovered video signal 6A and the recovered audio signal 6B. The recovered video signal 6A and the recovered audio signal 6B respectively closely match the video signal S2 and the audio signal S3 fed into the encoder 100.

FIG. 1 also shows the system target decoder (STD) 400 which is used to define the processing performed by the encoder 100 and the decoder 600. In practical video and audio signal processing systems, the encoder seldom includes an actual system target decoder, but instead performs the encoding processing and multiplexing taking account of the system target decoder parameters. Also, in practical systems, the decoder is designed to have performance equalling or exceeding that of the system target decoder. These relationships between the system target decoder and the encoder and the decoder are indicated in FIG. 1 by the broken line labelled S4A interconnecting the system target decoder and the encoder, and the broken line labelled S4B interconnecting the system target decoder and the decoder.

The system target decoder 400 is also known as a hypothetical system target decoder, system reference decoder, or reference decoding processing system. From now on it will be referred to as a system target decoder.

System target decoders are defined in international standard specifications such as CCITT H.261 and the MPEG-1 standard to provide guidelines for the designers of video and audio encoders and decoders for these standards.

In the MPEG-1 system standard, the system target decoder includes a reference video decoder and a reference audio decoder. In addition, the system target decoder includes an input buffer for the reference video decoder and an input buffer for the reference audio decoder. The size of each input buffer is defined in the standard. The standard also defines the operation of the two reference decoders, especially with regard to the way in which they remove the audio stream and the video stream from their respective buffers.

The concept of the system target decoder provides compatibility between encoders and decoders of different designs as follows. All encoders are designed to provide a bit stream that can be successfully decoded by the system target decoder, and that does not cause the respective input buffers in the system target decoder to overflow or underflow. In addition, all decoders are designed to have performance parameters that are equal to or better than those defined for the system target decoder. As a result, all such decoders will be capable of successfully decoding the bit stream produced by any of the encoders designed to produce a bit stream capable of being decoded by the system target decoder. The bit stream produced for decoding by the system target decoder is called a "constraint system parameter stream."

The structure of the hypothetical system target decoder 400 shown in FIG. 1 is as follows. The demultiplexer 401 notionally receives the bit stream S100 from the encoder 100. The demultiplexer 401 demultiplexes the bit stream into a video stream and an audio stream. The video stream is fed to the video input buffer 402, the output of which is connected to the video decoder 405. The audio stream from the demultiplexer 401 is fed into the audio input buffer 403, the output of which is connected to the audio decoder 406. In the example shown in FIG. 1, the video input buffer 402 has a storage capacity of 46 k bytes and the audio input buffer 403 has a storage capacity of 4 k bytes, as specified by the MPEG-1 standard. The video decoder 405 removes the video stream from the video input buffer 402 one video access unit at a time, i.e., one picture at time, at a timing corresponding to the picture rate of the video signal, e.g., once every 1/29.94 seconds in an NTSC system. The amount of the video stream removed from the video input buffer for each picture varies because of the different amount of compression applied to each picture. The audio decoder 406 removes the audio stream from the audio input buffer 403 one audio access unit at a predetermined timing.

It is desirable from the standpoint of the construction of the system, and to maximize flexibility, that, in the real decoder 600, the element corresponding to the demultiplexer 401 in the STD include a switching circuit, and that the elements corresponding to the video decoder 405 and the audio decoder 406 in the STD be provided using a high-speed processor (DSP) having a configuration suitable for performing high-speed signal processing operations. Such processors normally cannot include a large amount of storage for cost reasons. Therefore, the MPEG standards take these practical considerations into account and set the storage capacities of the video input buffer 402 and the audio input buffer 403 to the relatively small values set forth above.

FIG. 2 shows the structure of the constraint parameter (multiplex) system bit stream CPSP that is notionally fed into the system target decoder 400. The bit stream shown in FIG. 2 has a multi-layer structure, and includes various headers in a multiplex layer and the audio stream and the video stream in a signal layer. In this structure, plural packs serially arranged in time. Each pack begins with a pack header, and includes at least one video packet and at least one audio packet. Each video packet begins with a packet header and includes the video stream of at least pan of at least one picture. One video packet will accommodate the video stream of more than one B-picture, but several video packets are required to accommodate the video stream of one I-picture. There is no requirement that a picture begin immediately after the packet header: the picture may start at any point in the video packet.

Each video packet header may include at least one video time stamp showing the presentation time of the first picture that begins in the packet. If the first picture is an I-picture or a P-picture, and its decoding time differs from its presentation time, a decoding time stamp may also be included. The purpose and use of the video time stamps will be described below.

Each audio packet includes at least one audio access unit of the audio stream, and begins with an audio packet header. The audio packet header may include a presentation time stamp showing the output timing of the audio signal obtained by decoding the first audio access unit beginning in the audio packet. Each audio access unit is about 384 bytes in MPEG-1.

FIG. 2 shows a video packet that includes the video stream of the end of the picture i, and the video stream of at least the beginning of the picture i+1. The video time stamp vts included in the video packet header shown is the video time stamp of the picture i+1, because the picture i+1 is the first picture that begins in the video packet. FIG. 2 also shows the audio packet that includes the audio signal of the end of the access unit j, and the audio signal of the access units j+1 and j+2. The audio time stamp ats included in the audio packet header is the time stamp of the audio access unit j+1, because the access unit j+1 is the first access unit that begins in the audio packet.

The encoder 100 compresses and codes the video signal S2 and at least codes the audio signal S3 to provide a video stream and an audio stream, respectively, and multiplexes the audio stream, the video stream, and the various headers to provide the multiplexed bit stream S100 having the format shown in FIG. 2. The encoder feeds the multiplexed bit stream to the medium 5 for transmission or storage. The multiplexed bit stream is such that, if the encoder had fed the multiplexed bit stream to the system target decoder 400 for decoding, the system target decoder would have decoded the multiplexed bit stream successfully, and no overflow or underflow would have occurred in either of the input buffers in the system target decoder.

Because of the requirement that the multiplexed bit stream S100 be capable of being successfully decoded by the system target decoder 400, the encoder 100 applies a dynamically-varying compression and coding processing to at least the video signal S2. The compression ratio of the compression applied by the encoder 100 varies with time. Moreover, since the amount of the video stream that can be used to represent a picture of the video signal S2 depends on the occupancy of the video input buffer of the system target decoder at the instant that the picture is compressed, the amount of compression applied to a given picture varies dynamically. The amount of the video stream derived from a given video sequence will differ if the given video sequence is processed on different occasions. Accordingly, the compression ratio of at least the video stream produced by the encoder 100 varies constantly.

As shown above, the audio stream and the video stream are time multiplexed to provide the multiplexed bit stream S100. The audio stream of the audio signal belonging to a given picture of the video signal is located in the multiplexed bit stream some time earlier or later than the video stream of the picture. As a result of this, the decoder 600 must provide timing synchronization between the recovered video signal produced by expanding the video stream, and the recovered audio signal produced by expanding the audio stream. To provide this synchronization, the MPEG standard stipulates that the encoder add the above-mentioned time stamps to at least some of the video packet headers and the audio packet headers. The video time stamps and the audio time stamps show timings prescribing the clocks to be used to perform synchronized decoding of the video stream and the audio stream. The video time stamps and the audio time stamps also show the times at which units (i.e., pictures) of the recovered video signal and units of the recovered audio signal obtained by expanding respective access units of the video stream and the audio stream are to be presented at the decoder output. Such timing information is necessary to prevent audio/video synchronization errors from occurring if the decoder is unable to decode lost or corrupted audio or video access units. This will be described in more detail below.

FIG. 3 shows the structure of the decoder 600. In the decoder 600, the demultiplexer 601 receives the multiplexed bit stream from the medium 5. The demultiplexer demultiplexes the multiplexed bit stream into the video stream, the video time stamps, the audio stream, and the audio time stamps. The video time stamps and the audio time stamps are respectively fed to the pict