Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2000-06-29
2003-03-04
Britton, Howard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S423100, C375S340000, C712S300000
Reexamination Certificate
active
06529554
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of encoding data using a computer and more specifically to reducing branch mispredicts on MPEG run length encoding.
2. Description of the Related Art
MPEG, which stands for “Moving Picture Experts Group,” is a generic technique of compactly representing digital, video and audio signals for consumer distribution. In general terms, MPEG transforms a stream of discreet samples into an encoded bit stream which is then transferred through a medium. The transferred medium can be a communications link, such as a modem, a network (such as the Internet), a storage device (such as a compact disc), etc. The MPEG syntax provides an efficient method to represent image sequences in the form of more compact coded data. This compactness allows images to be transferred in digital format in less actual bytes of data than that required for the actual viewing of the video picture. MPEG1, MPEG 2 and the more recent MPEG 4 video standards are known in the art.
Once the MPEG data is transferred, the recipient can then decode the encoded data to replicate the original stream of discreet video samples. For example, a digital video disc (DVD) is an optical disk storage technology which is used to store motion video (such as movies) on a DVD compact disc. Using an MPEG specification, such as the MPEG 2 (Moving Picture Experts Group, Standard 2), the decoded video frames can be displayed on a computer monitor or on a television screen (such as high definition television, HDTV). Another example of the use of MPEG video is the transfer of video information over the Internet in which motion video can be downloaded and displayed on a computer monitor. In these multimedia applications, the audio generally accompanies the video data.
MPEG video encoding, as well as other techniques of video encoding, has processing stages which are referred to as quantization and run-length encoding. For example, a block of pixel data is typically transformed using an algorithm, such as Discrete Cosine Transform (DCT), to generate a block of coefficients which is subsequently compactly encoded by the use of a quantization process. When a particular transform, such as the DCT, is used to generate the coefficients, many of the coefficients quantize to a value of zero or near zero. Such zero or near zero values are commonly encoded as a count or run-length of sequential coefficients quantized to zero so that the encoded data includes only the non-zero coefficients and the number of sequential zeros preceding or following the non-zero coefficient value.
Since DCT coefficients representing a block of data will more commonly have zeros in the lower right portion of the coefficient block, some form of “zigzag” scanning order is used to sequence the coefficients for run-length encoding. Non-zero coefficients are infrequent enough that generally a run number of zero values will separate the non-zero coefficients. The encoding compresses the run-length of quantized zeros (zero and near-zero coefficients) between the non-zero coefficients. For example, if two non-zero quantized coefficients are separated by twenty-three zeros, then a run-length of twenty-three will be inserted between the two non-zero quantized coefficient values. If two sequential non-zero quantized coefficients are found without an intervening zero between them, then a run length of zero coefficients will be inserted between them. Essentially, the number of sequential zero coefficients are translated into a run-length, instead of providing the actual zero quantized value. In this way, only the non-zero quantized coefficients are transferred along with the run-length of zero coefficients after the encoding.
The zigzag scanning known in the art utilizes a zigzag order look-up table that specifies the sequential order in which to read the coefficients in order to achieve the zigzag scan order. One disadvantage with this technique is that it does a conditional test and branch for each of the coefficients in a data block. This conditional branch is largely unpredictable as to whether it will be taken or not taken. On deeply pipelined processors, it is common practice to attempt to guess or predict which way a branch will go, rather than waiting for all previous instructions upon which the condition depends to complete. If the processor guesses incorrectly regarding the branch, the misprediction typically will use a pipeline flush to discard the incorrect data and the pipeline will need to be replayed from a point prior to the misprediction. In highly pipelined processor architecture, the misprediction results in a significant performance penalty. With the zigzag scanning technique, it is possible that the conditional branch will mispredict for nearly every non-zero coefficient and possibly also for some zero coefficients.
The present invention addresses these concerns.
REFERENCES:
patent: 5757432 (1998-05-01), Dulong et al.
patent: 6115812 (2000-09-01), Abdallah et al.
Mangione-Smith, William H., Subword extensions for video processing on mobile systems, IEEE Concurrency, Jul.-Sep. 1998, pp. 13-16.
Blakely , Sokoloff, Taylor & Zafman LLP
Britton Howard
Intel Corporation
LandOfFree
Low branch-mispredict technique for MPEG run length encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Low branch-mispredict technique for MPEG run length encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low branch-mispredict technique for MPEG run length encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3085710