Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
1998-10-26
2002-10-22
Marcelo, Melvin (Department: 2665)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C375S365000
Reexamination Certificate
active
06470034
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is applicable to the field of digital video compression. It can be used to reduce the execution time, computational requirements as well as memory accesses required to search for the start code present in compressed bitstream. Start code search is common in the multiplexing and demultiplexing of multiple elementary video and audio stream. It is also used in the video and audio decoders to identify the start of various synchronization points in the elementary stream. In general this invention is useful when a search for a unique pattern within a bitstream is required. This invention is applicable when the start code exhibits the following characteristics of being byte aligned and begins with repeated bytes.
2. Description of the Related Art
In compressed digital audio and video data it is usually coded in segments representing a fixed frame of audio samples or parts of a picture. In each segment, the context of the current bit being decoded depends on the bits already decoded. Therefore the segment bitstream must be decoded sequentially from beginning to end. It is common to insert a unique sequence of bits or bytes to separate the data or indicate the start of a new segment of the data. This unique sequence of bits or bytes are commonly referred to as start codes. Start codes are useful for random access into the bitstream so that the decoder can start at the next possible entry point. It is also useful when the decoder looses the context of the bitstream due to data error and needs to resynchronize to the next segment of error free bitstream. In the case of the multiplexer that combines the audio and video elementary streams together, time stamps are tagged to start codes to identify the time to present the decoded data in order to achieve audio and video synchronization. Therefore it is desirable to be able to identify these start codes quickly.
An example of start codes used can be found in compression standards such as MPEG-1 and MPEG-2. In the rest of this document the start codes of the MPEG-2 video is used as an example. It contains 23 zeros followed by a 1. The byte following this will then indicate the type of start code. All the start codes are byte aligned. This means that they will always start at the beginning of the byte boundary. This simplifies the search as the comparison can be done at the byte level and not at the bit level.
For the rest of the document the sequence_header_code will be used as an example the bit pattern is “000000000000000000000000110110011” in binary or “00
h
00
h
01
h
B3
h
” in hexadecimal.
An example of the prior art is shown in
FIGS. 1 and 2
. It is common to scan through the bitstream comparing each bit or byte against the unique start code.
FIG. 1
shows a state diagram of a serial start code decoding process according to the prior art. In the serial start code decoding process, the bytes are sequentially compared to the start code pattern. The state machine changes state from state 1 to 4 depending on how many of the bytes have matched with the pattern. More specifically,
FIG. 1
shows the state diagram for the search of a start code representing the sequence_header_code. The state machine begins in state 0 where everything is reset. It stays in this state until the next byte is 00
h
when it goes into state 1. If the next byte is also 00
h
then it goes to state 2. Otherwise it reverts to state 0. From state 2 the state machine goes into state 3 if the next byte is 01
h
. If however the next byte is again 00
h
the machines remains in state 2. Otherwise it again reverts to state 0. Finally from state 3 if the next byte is B3
h
, then the state machine arrives at state 4 which is the final state where the start code has been found.
FIG. 2
shows the logical flow chart equivalent of the state machine. The logic begins in module
1
where the next byte is shifted for comparison in module
2
. If the byte is not equal to 00
h
the flow returns to module
1
where the subsequent byte is checked. If the byte is 00
h
then the logic flows to module
3
where the next byte is shifted In and compared in module
4
. If the byte is not equal to 00
h
, then the flow returns to module
1
where the subsequent byte is checked. If the byte is 00
h
the logic flows to module
5
where the next byte is shifted in and compared in module
6
. If the byte is again 00
h
the logic returns to module
5
. If the byte is 01
h
then the logic flows to module
7
. Otherwise the logic flows back to module
1
. In module
7
the next byte is shifted in and compared in module
8
. If the byte is B3
h
then the start code has been found. Otherwise the logic flows back to module
1
.
FIG. 1 and 2
illustrates the prior art where each byte in the bitstream is scanned sequentially against the pattern of the start code. The start code is found when 4 consecutive bytes in the bitstream matches the four consecutive bytes in the start code pattern.
The problem to be solve is to reduce the number of comparison required thus reducing the number of memory accesses as well as the computational requirements. As demonstrated in the example of the prior art in
FIGS. 1 and 2
, each byte of the bitstream has to be compared to a particular pattern.
SUMMARY OF THE INVENTION
In order to decrease the number of bytes compare during the start code search, this invention exploits the redundancy in the start code pattern. The following conditions are necessary for this invention to be useful. Firstly, the start code must be byte aligned thus implying that the start code can be aligned to any byte boundary. Therefore the search and comparison must be done byte by byte. Secondly, the start code pattern must contain two or more consecutive bytes that are the same.
The example start code from MPEG-2 satisfies the conditions above. The start code is byte aligned and the first two bytes in the start code pattern are both 00
h
. Therefore by comparing the second byte instead of the first byte we can make more than one conclusions when the byte is not 00
h
. The first conclusion is that the start code cannot begin at the first byte since the second byte of the bitstream and the second byte of the start code pattern do not match. The second conclusion is that the start code cannot begin at the second byte since the second byte of the bitstream and the first byte of the start code also do not match. Therefore by making one comparison we can make two conclusions if the comparison fails. This implies that only every second byte need to be checked. Thus halving the number of comparison and memory access.
According to a first aspect of the invention, a method of partitioning the coded representation of audio visual material into a plurality of access units whereby the beginning of each access unit is marked by a unique start code and that this start code is aligned to the byte boundaries, said method comprises:
making a first part by a series of two or more identical byte patterns; and
making a second part by one or more bytes that together with the first part forms a unique bit pattern that cannot be duplicated by the rest of the valid bitstream.
According to a second aspect of the invention, a method of start code detection in a bitstream comprising coded representation of audio visual material having the properties as in the first aspect, the method comprises the steps of:
aligning the bitstream to its byte boundary;
examining the bitstream for the start code pattern by comparing the byte at the location corresponding to the last byte of the series of identical byte patterns of the start code;
skipping all the bytes up to and including the said byte if the comparison shows that the byte is different from the byte pattern of the start code at that location; otherwise
proceeding with byte by byte comparison of the remaining bytes of the start code pattern to determine if there is a match.
According to a third aspect of the invention, an apparatus for start code detection in a bitstream comprising coded representation of aud
Greenblum & Bernstein P.L.C.
Marcelo Melvin
Matsushita Electric - Industrial Co., Ltd.
Mehra Inder Pal
LandOfFree
Method and apparatus for reduced complexity start code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reduced complexity start code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reduced complexity start code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944008