Variable-length code decoder

A method that decodes serially received MPEG variable length codes by executing instructions in parallel. The method includes an execution unit which includes multiple pipelined functional units. The functional units execute at least two of the instructions in parallel. The instructions utilize and share general purpose registers. The general purpose registers store information used by at least two of the instructions.

CROSS REFERENCE TO APPENDIX INCLUDING COMPUTER PROGRAM LISTINGS

Appendices A-E, which are integral parts of the present disclosure, include a listing of a computer program and its related data in one embodiment of this invention. This computer program listing contains copyrighted material. The copyright owner, ATI Technologies, which is also the Assignee of the present patent application, has no objection to the facsimile reproduction by anyone of the patent document or the present disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyrights whatsoever.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to video decoding. More particularly, the present invention relates to decoding video data encoded under one of the MPEG standards.

2. Discussion of Related Art

The Motion Picture Experts Group (MPEG) has promulgated two encoding standards for full-motion digital video and audio, popularly referred to as “MPEG-1” and “MPEG-2”, which provide efficient data transmission. MPEG encoding techniques can be used in digital video such as high definition television (HDTV). A publication describing MPEG-1 and MPEG-2 encoding and decoding techniques, Mitchell, J., Pennebaker, W., Fogg, C., and LeGall, D.,MPEG Video Compression Standard, Chapman and Hall, New York, N.Y. (1996), is incorporated herein by reference. The detailed description below is applicable to both MPEG-1 and MPEG-2 standards, unless otherwise provided. To simplify the description, where the description is applicable to both MPEG-1 and MPEG-2 standards, the term “MPEG” refers to both standards.

Under either MPEG standard, a video sequence is organized as a series of “pictures”. Each picture can be one of three types: predicted pictures (P-pictures), intra-coded pictures (I-pictures), and bidirectionally coded pictures (B-pictures). I-pictures are encoded without respect to other pictures. Each P-picture or B-picture is encoded as a set of differences with respect to one or more reference pictures, which can be I-pictures or P-pictures.

Each picture is further divided into data sections known as “slices”, each consisting of a number of “macroblocks,” which are each organized as eight or twelve 8-pixel by 8-pixel (8×8) blocks. Under one level of color precision, a macroblock includes four 8×8 blocks of brightness (luminance) samples, two 8×8 blocks of “red” samples (“red-chrominance”), and two 8×8 blocks of “blue”. (“blue-chrominance”) samples. Under this level of color precision, red-chrominance and blue-chrominance samples are sampled only half as often as the luminance samples. Under another level of color precision, a macroblock includes four 8×8 luminance blocks, four 8×8 red-chrominance blocks, and four 8×8 blue-chrominance blocks. Information regarding each macroblock is provided by a macroblock header which identifies (a) the position of the macroblock relative to the position of the most recently coded macroblock, (b) which of the 8×8 blocks within the macroblock are encoded as intra-blocks (i.e., without reference to blocks from other pictures), and (c) whether a new set of quantization constants is to be used.

The first step in encoding the 8×8 blocks is to transform each block into the frequency domain using a 2-dimensional discrete cosine transform (DCT). The applicable 2-dimensional DCT consists of a “horizontal” and a “vertical” spatial DCT, as is known in the art. DCT represents the luminance or chrominance values of a block as a set of coefficients in a sum of cosine functions. Next, each coefficient of the block in frequency space is “quantized.” For I-pictures, quantization is intended to reduce the coefficients of the higher frequencies to zero. For P-pictures and B-pictures, which represent temporal changes in the luminance or chrominance values over time, quantization also reduces many of the coefficients to zero. The quantized coefficients can be achieved by dividing each coefficient of a block by a corresponding integer quantization constant, and then rounding the result to the nearest integer.

The 2-dimensional blocks are then read as a linear list of values by scanning the values of the 8×8 block under a “zigzag scanning order.” MPEG-2 specifies two zigzag scanning orders, which are depicted inFIG. 1. Under either of these zigzag scanning orders, zero coefficients tend to congregate or “run” next to each other, allowing a compact representation (a “run-level” pair, as described below). An end-of-block symbol is used to indicate that all remaining coefficients in the zigzag scanned list are zero.

All non-zero coefficients, other than the DC-coefficient, defined below, are then represented using a “run-level” coding. “Level” is the amplitude of a non-zero coefficient. “Run” is the number of zero-amplitude coefficients between the most recent non-zero coefficient and the present non-zero coefficient. For I-pictures, the DC-coefficient, which is the zero-frequency coefficient, is represented as a difference from the DC-coefficient of the most recent reference block of the same block type (i.e., luminance, red-chrominance, or blue-chrominance). Next, the “run-level” encoded lists are transformed into variable-length codes using a Huffman coding technique. Huffman coding assigns shorter codes to more frequently occurring values. (The macroblock header is also encoded).

A conventional decoding process200of an MPEG block is depicted schematically inFIG. 2. An MPEG decoder receives an input encoded video data stream (“bitstream”) from a video data source, such as a satellite transmitter, a disk, or a DVD ROM. The bitstream consists of variable-length codes obtained using an encoding process described above. As shown inFIG. 2, a bitstream fetch operation202captures the bitstream. A decode operation204then recovers the run, level, and length of each variable-length code, according to the encoding standard used and the picture type. Typically, the variable-length codes are decoded using a table look-up technique. To recover the current DC-coefficient, the DC-coefficient of the most recent I-picture encoded block of the same block type is added to the present DC-coefficient.

The next step of decoding process200is depicted inFIG. 2as inverse scan206. Inverse scan206assigns the coefficients from the variable length decode operation204into 8×8 blocks. Next, an inverse quantization step208multiplies each coefficient in an 8×8 block obtained from inverse scan206by the same corresponding quantization constant used in the quantization procedure during encoding, and rounds the result to the nearest integer. In addition, to compensate for precision losses during encoding and decoding, an “oddification” step (MPEG-1) or a “mismatch control” step (MPEG-2) is applied during inverse quantization procedure208.

Next, an inverse discrete cosine transform (IDCT)210, such as described by Mitchell, J., Pennebaker, W., Fogg, C., and LeGall, D.,MPEG Video Compression Standard, Chapman and Hall, New York, N.Y. (1996), is applied to the 8×8 blocks to return the blocks to a time domain representation, which is also known as a spatial domain representation.

In the prior art, the decoding process200described thus far, i.e., from the bitstream fetch operation202to the IDCT210, is already too computationally demanding for decoding using a typical conventional microprocessor. For example, a DVD player using only an Intel x86 CPU to decode MPEG data cannot perform the above decoding process fast enough. Even at 200 MHz, an x86 CPU must dedicate all of its resources to process video. Even then, some frames would be lost.

A DVD player with a separate MPEG decoder and an x86 CPU achieves better results. With a separate MPEG decoder, the demand on the x86 CPU is significantly diminished. However, there are several drawbacks to a separate MPEG decoder. First, partitioning the decoding tasks between the processors is complex, especially when the processors execute different instruction sets. Second, a separate MPEG decoder results in higher costs for MPEG decoding. Third, even then, MPEG decoding for replay on a HO-type HDTV is still not quick enough to avoid frame loss.

Therefore, what is needed is an MPEG decoder which decodes variable-length codes for replay on a HO-type HDTV quickly enough to avoid frame loss but without the expense and complexity of a dedicated MPEG decoder.

SUMMARY

An embodiment of the invention includes a computer system for executing instructions to decode variable length codes, the variable length codes being sequentially-received. The computer system includes an execution unit that includes multiple functional units executing at least two of the instructions in parallel; general purpose registers, where each of the instructions share the general purpose registers; and special purpose registers, where each of the instructions share the special purpose registers.

The present invention will be more fully understood in light of the following detailed description taken together with the accompanying drawings.

Note that use of the same reference numbers in different figures indicates the same or like elements.

DETAILED DESCRIPTION

Overview

An embodiment of the present invention is depicted inFIG. 3.FIG. 3depicts an exemplary code segment300for decoding two (or more) sequential MPEG variable-length codes from an input bitstream. In this embodiment, decoding includes operations202-210described with respect toFIG. 2. As shown inFIG. 3, code segment300includes calls to instructions LDBITSR, VIDRSVLD, VIDVLD, VIDUV, VIDMUX, VIDIQMO, VIDIQSC, VIDIDCT, and JUV. Instruction LDBITSR loads two sequential variable-length codes. For a first variable-length code, call302calls instruction VIDRSVLD. Next calls304-309are calls to a group of instructions labeled “A”, which includes instructions VIDUV, VIDMUX, VIDIQMO, VIDIQSC, VIDIDCT, and JUV. Following completion of instruction JUV, a first variable-length code is decoded. For the next sequential variable-length code, the first call is call303which hails instruction VIDVLD. Next calls304-309are calls to the group of instructions labeled “A”. Following completion of instruction JUV, the next sequential variable-length code is decoded.

After all instructions VIDUV, VIDMUX, VIDIQMO, VIDIQSC, and VIDIDCT are applied to all coefficients of a full block, instruction PBFY (not depicted) is executed to complete a horizontal inverse discrete transform for all coefficients of the block.

While the code has been described as operating serially, that is, completing the decoding of a first variable-length code prior to beginning decoding of a subsequent sequential variable-length code, in practice, multiple instructions may execute simultaneously (so called “interleaved operation”) thereby decoding simultaneously multiple variable-length codes. Interleaved operation maximizes hardware execution of the instructions and thereby minimizes the time to decode variable-length codes. Interleaved operation will be discussed in more detail below.

Suitable Hardware Platform

A suitable apparatus to execute operations specified by the instructions of code segment300ofFIG. 3is depicted inFIG. 4A.FIG. 4Aincludes a central processing unit (CPU)402, which in this embodiment, executes an x86 compatible instruction set architecture. CPU402includes first ALU410.1, second ALU410.2, third ALU410.3, general purpose registers404, conventional memory management unit (MMU)492, conventional data cache490, special purpose registers496, instruction cache493, and instruction controller494.

First ALU410.1, second ALU410.2and third ALU410.3are respectably depicted inFIGS. 4B,4E and4H and each is described in more detail below. In this embodiment, general purpose registers404stores 64, 64 bit registers. In this embodiment, special purpose registers496stores registers video_mbstate and video_uv, discussed in more detail below. The conventional instruction cache493stores instructions. The conventional instruction controller494executes instructions and coordinates pipelined operation, discussed in more detail below.

Each of first ALU410.1, second ALU410.2, third ALU410.3, and special purpose registers496communicate through bus498. Each of first ALU410.1, second ALU410.2, third ALU410.3, and general purpose registers404communicate through bus495. MMU492communicates with general purpose registers404, data cache490, instruction cache493, and a conventional main memory497. Instruction cache493and instruction controller494communicate.

In this embodiment, first ALU410.1includes hardware used by instructions LDBITSR and VIDMUX; second ALU410.2includes hardware used by instructions VIDRSVLD/VIDVLD and VIDUV; and third ALU410.3includes hardware used by instructions VIDIQMO, VIDIQSC, and VIDIDCT. In accordance with an embodiment of the present invention, providing dedicated ALUs to execute specific instructions allows for multiple instructions to execute simultaneously. Thereby, interleaved operation can be achieved.

First ALU410.1

FIG. 4Bschematically depicts first ALU410.1in more detail. A first stage includes a conventional adder411, capable of receiving four inputs, and a conventional two input arithmetic logic unit (ALU)412, both operating in parallel. A suitable arithmetic logic unit412is a conventional8way, 8 bit-Single Instruction Multiple Data (SIMD) two input arithmetic logic unit having adding, subtracting, AND, OR, and XOR capability with source merging at 8 bit boundaries for x86 compatibility. A suitable arithmetic logic unit411is described in “An Apparatus And A Method For Address Generation”, inventor Stephen C. Hale, Ser. No. 09/149,881, filed Sep. 8, 1998.

First ALU410.1further includes a zero extender circuit414, used during execution of instruction LDBITSR and that provides an input to adder411, and zero stuffer circuit416, used during execution of instruction VIDMUX. The output of zero extender circuit414is provided to both ALU412and zero stuffer circuit416.

FIG. 4Cschematically depicts zero extender414. Zero extender414includes an extender circuit415that receives the 3 least significant bits of input415.A. The extender circuit415converts the 3 bit input into a 32 bit value. The operation of extender circuit415is described in more detail with respect to LDBITSR. The output of the extender circuit415is an input to multiplexer418. Multiplexer418outputs the output value from extender circuit415when instruction LDBITSR executes. Otherwise, multiplexer418outputs the 32 bit input415.A.

The output of multiplexer418is coupled to an input terminal of adder411. Thus when instruction LDBITSR does not execute, input value415.A is coupled to adder411. Thereby an input of adder411is available for use when LDBITSR does not execute.

FIG. 4Dschematically depicts zero stuffer circuit416. Input416.A to the arithmetic logic unit412is coupled to zero stuffer circuit416. First stage416.1of zero stuffer device selects bits0. . .15,16-31,32-47, or48-63of input416.A, depending on the value of “select” signal. The output of first stage416.1is coupled to second stage416.2. Second stage416.2of zero stuffer circuit416stores the selected 16 bits into bits32to47of a 64 bit value, where bits0to31and bits48to63are zero. The zero stuffer circuit416outputs the 64 bit value as an input to multiplexer419. Multiplexer419selects an output of zero stuffer circuit416when instruction VIDMUX executes and otherwise selects an output of arithmetic logic unit412.

FIG. 4Eschematically depicts second ALU410.2. Second ALU410.2receives inputs of430,432,441, and442. Input432is provided to a flip flop433, which provides the input432to a multiplexer434. Inputs430and432are provided to VIDVLD/VIDRSVLD circuit436. VIDVLD/VIDRSVLD circuit436is described in more detail with respect to instructions VIDVLD and VIDRSVLD. The VIDVLD/VIDRSVLD circuit436provides outputs436.I and436.G to respective multiplexers434and435. Multiplexer434selects output436.I when instruction VIDRSVLD executes.

Multiplexer435is coupled to receive inputs430and436.G. Multiplexer435selects output436.G when either instruction VIDRSVLD or VIDVLD execute. Multiplexer435provides its output to shift amount decoder431. Shift amount decoder431and multiplexer434provide respective outputs431.A and434.A to shifter/rotater439. Shifter/rotater439shifts the input434.A by an amount specified by output431.A.

ALU440, which is similar to ALU412, receives inputs441and442. Input442is further coupled to VIDUV circuit443, described in more detail below. The outputs of the ALU440and VIDUV circuit443are coupled to a multiplexer445, which selects the output from VIDUV circuit443when instruction VIDUV executes.

Multiplexer446receives input436.J from VIDVLD/VIDRSVLD circuit436and an input from ALU440and selects the input from VIDVLD/VIDRSVLD circuit436when either instruction VIDRSVLD or VIDVLD execute.

FIG. 4Fschematically depicts VIDVLD/VIDRSVLD circuit436used during execution of instructions VIDRSVLD and VIDVLD. The operation of VIDVLD/VIDRSVLD circuit436is described with respect to instructions VIDVLD and VIDRSVLD.

Input divider443.1receives a 64 bit-input, also coupled to an input of ALU440of the second ALU410.2, and outputs5quantities. In this embodiment, the relationship between the 5 quantities and bits in the 64 bit input value is shown in the following table:

Second input443.6and fifth input443.7are coupled to scan table circuit443.2. Scan table circuit443.2converts each of443.6and fifth input443.7in a manner described in more detail below with respect to instruction VIDUV.

Format converter443.3receives the first input443.5and outputs a 16 bit value having the following properties: 1) the least significant bit is 0; 2) the two most significant bits are each set to the most significant bit of 13-bit output; 3) bits13to1are set to the 13-bit output.

Each of the outputs from scan table circuit443.2, format converter443.3as well as the third and fourth inputs are coupled to output format converter443.4. Output format converter443.4generates a 64 bit value, having the following properties:

FIG. 4Hschematically depicts third ALU410.3. Third ALU410.3includes a conventional multiplier450, that performs multiplication operations, and an ALU452, similar to ALU412of first ALU410.1. Logic is provided that is used during separate executions of instructions VIDIDCT, VIDIQMO, and VIDIQSC.

Logic for VIDIDCT

A least significant bit of input450.A is provided to an AND gate459. When instruction VIDIDCT executes, the least significant bit of input450.A is set to 0.

Logic for VIDIQMO

The output of multiplier450,450.C, is provided to round circuit454, which implements the steps of1102and1103, described below, using hardwired logic. Multiplexer456selects output454.A from the round circuit454where the instruction VIDIQMO executes.

The output454.A of multiplexer456is an input to ALU452. Where output454.A is to be incremented, in accordance with step1104, described below, a second input to the ALU452is a 1.

Output452.A from ALU452is provided to oddification circuit460, which performs the operations of steps1106and1107, described below, using hardwired logic. Multiplexer462selects the output of oddification circuit460when instruction VIDIQMO executes.

Logic for VIDIQSC

Instructions

FIG. 5provides a flow diagram of an operation of instructions of code segment300.FIG. 5particularly illustrates information, e.g., eob and UV, passed between instructions. The feedback and feedforward sharing of information allows for interleaved instruction operation, introduced earlier. In this embodiment, each instruction references parameters within 64 general purpose registers (FIG. 4A, item404). The instructions thus share use of the general purpose registers, which are used by any instructions requiring explicit operands.

An alternative implementation could be to assign a distinct memory region for each instruction. However such implementation would require more memory space and more memory access hardware to each memory region than the shared general purpose registers of this embodiment. In this embodiment, only a single set of memory access circuitry are needed for the general purpose registers because all instructions share the general purpose registers. Sharing of general purpose registers further allows for sharing of all hardware or instructions required in instruction processing, e.g., state for context switching.

Further, all instructions share use of bypass and interlock control circuitry because the instructions share use of general purpose registers404. Bypass is well known in the art as the practice of providing speculative results from one instruction to another instruction. Interlock control is well known in the art as the practice of delaying execution of an instruction that requires an unavailable result until the result is available.

Referring toFIG. 3, call301executes instruction LDBITSR, which fetches 64 bits of input variable-length code from an input data stream (“bitstream”) from memory490. A flow diagram600showing the tasks performed by instruction LDBITSR is depicted inFIG. 6A.FIG. 6Bschematically depicts the operation of instruction LDBITSR. InFIG. 6B, step numbers fromFIG. 6Aare used to denote association between steps ofFIG. 6Aand schematically depicted operations ofFIG. 6B. Pseudo-code for instruction LDBITSR is provided in Appendix A.

In this embodiment, instruction LDBITSR is encoded as a 32-bit instruction having the following format:

As shown inFIG. 6A, at step601, the value of a variable “BitStreamPtr”, which includes a 32-bit memory byte-address corresponding to the most recently retrieved 64 bits of a bitstream, is loaded from the general purpose register specified in field “Src1”. The bitstream includes variable-length codes encoded under one of the MPEG standards.

In step602, the value of a variable “BytePtr”, which represents displacement to the memory byte-address specified in BitStreamPtr, is loaded from the general purpose register specified by field “Src2” of the LDBITSR instruction. In this embodiment, LDBITSR provides the 3 bit “BytePtr” to the selector device415described with respect to first ALU410.1. The zero extender device415of selector device414effectively converts “BytePtr” into a 32 bit value by tacking 0's into the 29 most significant bits, i.e., bits31to3.

In step603, variable “BitStreamPtr” the memory byte-address of the next 64 bits of variable-length codes to be processed from the bitstream, is updated by incrementing “BitStreamPtr” by “Byteptr”.

In step604, using the memory byte-address obtained in step603, 64 bits are retrieved from the bitstream in memory490and stored (step605) into the general purpose register specified by field “Dest” of the LDBITSR instruction. As shown inFIG. 5, the 64 bits (shown as “Bytes”) are available to the next instruction, either VIDRSVLD or VIDVLD.

In this embodiment, reads and writes to memory490include conventional segmentation and paging operations common to x86 compatible memory access operations. Segmentation and paging is generally: for an input address, ADDR, using multiple lookup tables to determine an address, ADDR2, in memory associated with input address, ADDR, and storing the ADDR/ADDR2combination in a memory cache for subsequent use and to avoid future accesses to the lookup tables.

Referring toFIG. 6, in step606, variable “Bitstreamptr” is stored into the least significant 32 bits of the general purpose register specified by the field “Src1.”

As shown inFIG. 5, the byte-address (shown as “AddPtr”) is available to a subsequent execution of instruction LDBITSR.

In this embodiment, instruction LDBITSR is not executed prior to calls310-315because the length of the longest variable-length code is 28 bits, so that every 64 bits loaded includes at least an additional variable-length code to be decoded.

Instructions VIDRSVLD and VIDVLD

Next, as shown inFIG. 3, for a first variable-length code of the bitstream, call302executes instruction VIDRSVLD. For the next sequential variable-length code, call303executes instruction VIDVLD. Instruction VIDRSVLD of call302and instruction VIDVLD of call303are both used to align the next variable-length code in the current 64 bits of variable codes, and are thus described together here.

A flow diagram700, illustrative of both instructions VIDRSVLD and VIDVLD, is shown inFIG. 7A.FIGS. 7B and 7Cschematically depict the operations of respective instructions VIDRSVLD and VIDVLD. InFIGS. 7B and 7C, step numbers fromFIG. 7Aare used to denote association between steps ofFIG. 7Aand schematically depicted operations ofFIGS. 7B and 7C. Steps701-713are performed by instruction VIDRSVLD and steps703-713are performed by instruction VIDVLD.FIG. 4Fdepicts the circuit used to execute the instructions VIDRSVLD and VIDVLD.

Table 2 depicts the encoding of instruction VIDRSVLD:

As shown in Table 2, the bit pattern bits [32:26, 25:24, 11:6] identify the instruction VIDRSVLD. Fields “Dest”, “Src1”, and “Src2” specify respectively the general purpose registers for result destination and operand registers of the instruction. The encoding for instruction VIDVLD is the same as instruction VIDRSVLD, except that the bit pattern ‘011100’ is provided at bits [11:6].

In this embodiment, instructions VIDVLD and VIDRSVLD use VIDVLD/VIDRSVLD circuit436ofFIG. 4P. Thus reference will be made to the circuit when used.

At step701, bit reverser436.1of circuit436is used to perform a bit order reversal on each 8-bit byte of the 64 bits, read from the general purpose register specified by “Src1”. In this embodiment, step701rearranges the bit at position n of each 8-bit byte to position (7-n), where n is 0 to 7.

Then, at step702, using bit shifter436.2, the 64 bits output from the bit reverser436.1is right-shifted (towards the least significant bit) by a number of bits specified in a 3-bit field “BitPtr”, from the 3 most significant bits of the general purpose register specified by field “Src2” (input436.C ofFIG. 4F), in order to shift out a previously decoded symbol and to align an undecoded symbol in the least significant bits of the 64 bit output. Thus use of “BitPtr” allows a variable-length code within the 64 bits from the bit reverser436.1to be decoded regardless of where located in the 64 bits. Zero bits are inserted into the most significant bits, where a number of zero bits is the same as specified in “BitPtr”. Bit shifter436.2outputs a 64 bit quantity.

In this embodiment, a multiplexer436.3of circuit436receives inputs of 1) the output from bit shifter436.2and2) the 64 bits input to the bit reverser436.1. When the instruction VIDRSVLD executes, the multiplexer436.3outputs input1) and otherwise, input2). The output of multiplexer436.3(436.I) is an input to MUX434(FIG. 4E).

In step703, which is common to both instructions VIDRSVLD and VIDVLD, the 28 least-significant bits of the 64 bits from multiplexer436.3(hereafter variable “bits”) are provided to VLD circuit436.4, discussed in more detail below. Further the 45 bits from positions3to32and46to60from the general purpose register “Src2” are provided to VLD circuit436.4. Four bits from special purpose register “VIDEO_MBstate” (FIG. 5) are provided to VLD circuit436.4.

At step704, a variable-length code decoding step in accordance with the MPEG standards is performed on “bits”. In this embodiment, VLD circuit436.4includes a hardwired implementation of step704.FIGS. 8A and 8Bdescribe step704in further detail. Suitable pseudo-codes of step704as executed in instructions VIDRSVLD and VIDVLD are provided respectively in Appendices B-1 and B-2.

The following table represents variables and sources of such variables used by VLD circuit in step704.

As shown inFIG. 8A, at step801, the values for variables “PredictorLumaOut”, “PredictorCbOut”, and “PredictorCrOut”, which are DC-coefficients of I-picture for respective luminance, blue-chrominance, and red-chrominance block types, are set to default values. If the end of the current macroblock was reached (step802), i.e., the general purpose register specified in field “Src2” contains an asserted “eomb” flag, the values of variables “level” and “length” are both set to zero and a variable “eobOut” is set 1, to indicate the end of the current macroblock (step803). From step803, the program returns to step705ofFIG. 7A.

However, if the end of the current macroblock is not reached, step804ofFIG. 8Aretrieves values of variables “mb_intra”, “mpeg2”, “intra_vlc_format”, and “cbp” from special purpose register “Video_MBstate”. The value of variable “mb_intra” indicates whether a block is from an I-picture. The value of variable “mpeg2” indicates whether a block is coded using MPEG-1 or MPEG-2 format. The value of variable “intra_vlc_format” selects a table for decoding the current variable-length code. The value of variable “cbp” indicates which blocks of the current macroblock are encoded. In this embodiment, variable “cbp” is represented by 12 bits, each bit indicating the encoding status of one of the 12 8×8 blocks. Thus, if a bit in “cbp” is set, the corresponding 8×8 block in the current macroblock is encoded. The following table depicts the block type each bit of “cbp” represents: “Y”, “U” and “V”. “Y”, “U”, and “V” stand for, respectively, luminance, blue-chrominance, and red-chrominance.

In step804, the value of variable “intra_dc” is also set. When set, the current variable-length code encodes a DC-coefficient of an intra-coded block (i.e., a block in an I-picture). The value of variable “intra_dc” is determined from the values of variables “eobIn” and “mb_intra”, which indicate whether the last variable-length code of the previous block is an end-of-block and whether the present variable-length code is intra-coded, respectively.

In step805, the block type of the present block (i.e., luminance, red-chrominance, or blue-chrominance) is identified, and assigned as a value to a variable “cc”. The value (0-11) of variable “BlkNumIn” indicates which of the 12 8×8 blocks of a macroblock is currently being decoded.

In step806, a table is selected based on the block type then the value of variable “intra_vlc_format”. In this embodiment, tables 12, 13, 14, or 15 are provided. Look-up table 12 is used for DC-coefficients of an intra-coded luminance block. Look-up table 13 is used for DC-coefficients in intra-coded chrominance blocks. Look-up table 15 is used for non-DC coefficients that are coded in I-pictures under the MPEG-2 standard. Look-up table 14 is used for decoding all other types of non-DC coefficients.

In step807, based on the block type (i.e., value of variable “cc”), a predictor is selected. A predictor is the most recently output “level” value for the current block type. In step808, the linear position of the variable-length code is established. The linear position is the position, in the zigzag scanned list, of the non-zero coefficient encoded in the current variable-length code. Thus, variable “LinPosIn” can take values from 0 to 63. In step809, escape values are set. Escape values are variable-length codes that correspond to uncommon runs and levels. To limit the maximum length of the variable-length codes to 28 bits in length, the MPEG standards define certain bit patterns as escape codes to allow special exception processing, described in more detail later, when uncommon runs and levels not assigned a variable-length code occur (see step816). The value of variable “esc” is 1 when bits [0:5] have bit pattern 0000 01 for a level which is not a DC-coefficient. A second escape pattern is signaled when variable “esc28b” has the bit pattern for bits [13:19] which is ‘000 00.

In step810, the variable-length decoder checks for conditions that require special handling, by examining certain variables for special bit patterns. For example, where the least significant bit of the value for variable “bits” is a 1 and the table 14 is selected (the current variable-length code corresponds to a DC-coefficient) and the value of variable “note3” is set to 1. Reference to the value of variable “note3” provides a shorthand for representing a common variable-length code with less bits. The technique is defined in the MPEG standard.

In step811, if the current variable-length code is an “end-of-block” code, then if the selected table is table 14, then variables “B14eob” is set to 1, else if the selected table is table 15, then “B15eob” is set to 1. The value of variable “eobOut” is set to 1 when either of variables “B14eob” or “B15eob” are 1. In step812, if the current variable-length code is an end-of-block symbol, the variable-length code decoder searches for the next coded block. In step813, if the next coded block is not found, the end of the current macroblock is reached. If the next coded block is found, in step814(FIG. 8B), the variable “BlkNumOut” is set to the index of the next coded block.

In step815, the variable-length code decoder checks if the special condition specified in the escape codes of step809are satisfied. If the current variable-length codes matches any of the escape bit patterns or special conditions (i.e., “esc”, “esc28b”, “b14eob”, “B15eob” and “note3”), in step816, the values of variables “length”, “run”, and levels are obtained by special processing, rather than table look-up in steps817-824described below. The following table depicts the values of “length”, “run”, and “level” for these special conditions, according to the MPEG standards. (Bit positions are shown as subscript).

Otherwise, in step817, a table look-up technique is used to obtain the decoded “length”, “run” and “level” values according to the selected one of tables 12, 13, 14, or 15, which are provided as in Appendices F-1 to F-4.

In step818, if the value of variable “table” is 12 or 13, i.e., the current variable-length code encodes either a respective luminance or chrominance DC-coefficient, steps819-820(a) set the value of variable “run” to 0 (step819), (b) determine from the selected table the length of the variable-length code (step820), and (c) calculate the corresponding DC-level difference encoded in the variable-length code (step821). (This DC-level difference is added subsequently to the previous DC-coefficient of the same type to obtain the DC-coefficient, in accordance with MPEG standard).

In step821, if look-up table 14 or 15 is used, i.e., the current variable-length code encodes an run-level pair, step822looks up the selected table to determine the length of the variable length code, to determine the encoded “run” and “level” values, in accordance with the MPEG standards. Tables 14 and 15 are shown in Appendices F-2 to F-4.

In this embodiment, the table look-up functions of steps819,820and822are implemented in hardware. In the software MPEG decoding technique of the prior art, approximately 30 instructions were used to carry out the decode. Thus, considerable time-savings result by hardwiring the table look up function.

Referring next to step705ofFIG. 7A. The value of variable “escLevel” is set equal to the value of variable “level”. In this embodiment, VLD circuit436.4ofFIG. 4Fincludes a hardwired implementation of step705. If the value of variable “escLevel” is an illegal value, an exception “Exception_VECT_VLD,” described below, is triggered to invoke error-handling mechanisms.

Next, in step706, the final value for variable “level” is set for each variable-length code. For a DC-coefficient of an I-picture, the level difference is summed to the value of the predictor variable “pred”. For non-DC coefficients, if the variable-length code is not an I-picture, the final level value is twice “QFS” (the “level” value retrieved from the table) plus one or minus one, depending on whether “QFS” is negative or not. In this embodiment, VLD circuit436.4ofFIG. 4Fincludes a hardwired implementation of step706.

In step707, the linear position of the next coefficient in the zigzag scanned list is set. Where the variable-length code is the first in a block and not an end-of-block code, the next linear position is simply the “run” value. Otherwise, where the variable-length code is not an end-of-block code, the present linear position is the present linear position (i.e., the value of variable “LinPosIn”) plus “run” and 1. If the present variable-length code is end-of-block code, the present linear position is set to 0 where the previous linear position was 63, or 63 otherwise. In this embodiment, VLD circuit436.4ofFIG. 4Fincludes a hardwired implementation of step707.

In step708, the variables “BytePtr” and “BitPtr” are concatenated (input436.F), with “BytePtr” as the most significant bits, and added to a 6 bit version of “length”. Variable “BitPtr” (input436.D) is expanded to 6 bits (436.H) using circuit436.5. The 6 bit version of the variable “BitPtr” and the concatenated “BytePtr” and “BitPtr” (436.F) are provided to multiplexer436.7, which selects the 6 bit version of the variable “BitPtr” (436.H) when instruction VIDRSVLD executes. The output of MUX436.7is an input to adder436.8.

Variable “length” from VLD circuit436.4(input436.8) is converted into a 6 bit version using zero extender436.6. The 6 bit version of “length” (input436.G) is an input to adder436.8and to MUX435(FIG. 4E).

With respect to the output sum from adder436.8, the most-significant 3 bits and the least significant 3 bits are assigned, respectively, as values for variables “BytePtr” and “BitPtr”. This step (708) updates variables “BytePtr” and “BitPtr” to point to the beginning byte and the beginning bit of the next variable-length code for use in instructions LDBITSR, VIDVLD and VIDRSVLD.

The output436.K from the VLD circuit436.4and the output436.L from adder436.8are combined into a 64 bit value (“VLD output”) (436.J ofFIG. 4F), where “BytePtr” and “BitPtr” occupy the respective3most significant and 3 least significant bits of the 64 bit value. The VLD output is fed into multiplexer446(FIG. 4E).

As shown inFIG. 5, variable “BytePtr” is available for use in a subsequent execution of instruction LDBITSR. Variables “BytePtr” (shown as “Ptr”), “eob”, and prediction variables (“PredictorLumaOut”, “PredictorCbOut”, “PredictorCrOut”) are available for use in a subsequent execution of instructions VIDRSVLD or VIDVLD. Variables “BytePtr” and “level” are available to instruction VIDUV.

Referring toFIG. 7A, in step710, the 64 bits retrieved from the bit stream in the general purpose register specified by field “Src1” of the LDBITSR instruction is further right-shifted using shifter device414, with a zero replacing each shifted bit, where the number of bit positions shifted is equal to “length”. The resulting shifted bits are stored in the general register specified by field “Dest”. The shifted bits are available for use in the next execution of instruction VIDRSVLD or VIDVLD (shown as “Bits” inFIG. 5).

In step711, the variable-length code decoder checks for any error or exception conditions that may have arisen during encoding. Table 5 depicts possible error conditions:

In this embodiment, execution of “Exception_VECT_VLD” includes three stages: 1) preface, 2) exception execution, and 3) return from exception (RFE). Preface includes 1) storing the current execution information, e.g., program counter and status word, into a hardware stack, 2) completing side-effects.

Next, exception execution of the Exception_VECT_VLD includes: 1) assigning a run and level to the variable length code, 2) discarding from the bitstream an illegal code, or 3) indicating that an error is found in the bit stream. Action 1) may be performed for example in conditions 4-8. Conditions 4-8 in Table 5 generally correspond to uncommon run and level pairs for which encoding requires more than 28 bits. Action 3) is performed for example when an exceptional condition has recurred more than a predetermined number of times. Thus the Exception_VECT_VLD chooses to complete the triggering instruction (ignore the triggering event) or fix the triggering event a restart the triggering instruction using the fixed event.

Next, RFE instruction restores the program counter and status word and resume execution of the instruction, in accordance with the Exception_VECT_VLD choice.

Referring back toFIG. 3, at call304instruction VIDUV is executed.FIG. 9Adepicts a flow diagram900of instruction VIDUV (call304).FIG. 9Bschematically depicts a bit level flow diagram of instruction VIDUV. InFIG. 9B, step numbers fromFIG. 9Aare used to denote association between steps ofFIG. 9Aand schematically depicted operations ofFIG. 9B. Pseudocode for instruction VIDUV is provided in Appendix C.

Table 6 depicts the encoding of instruction VIDUV:

In step901, function ScanTable converts a linear position of a variable-length code as represented by variables “LinPosH”, “LinPosL”, into block coordinates (“UPos”, “VPos”) within an 8×8 block.FIG. 1depicts the two possible scan orders for converting linear position, “LinPosH”, “LinPosL”, into coordinates (“UPos”, “VPos”).

In this embodiment, in step901, the VIDUV instruction provides “LinPosH” and “LinPosL”, each 3 bits, to the scan table circuit443.2, introduced with respect to VIDUV circuit443(FIG. 4G). The scan table circuit443.2converts the linear position, “LinPosH” and “LinPosL”, into coordinates “Upos” and “Vpos” according to the conversion table of Appendix G. For a zigzag pattern102(FIG. 1), the middle column is used, and for a zigzag pattern104(FIG. 1), the right most column is used. The scan table circuit443.2outputs “Upos” and “Vpos”, each being 3 bits, to output format converter443.4.

In step902, the 13-bit variable “LevelIn,” having 12 value bits and 1 sign bit is converted into a 16-bit value variable “Level”, by 2-bits of sign extension and appending a “0” bit at the least significant end.

In this embodiment, in step902, the VIDUV instruction provides the 13-bit variable “LevelIn” to the format converter443.3of VIDUV circuit443(FIG. 4G), which outputs the 16 bit value, “Level”, having the following properties: 1) the least significant bit is 0; 2) the two most significant bits are each set to the most significant bit of “LevelIn”; 3) “Level13 . . . 1” is set to “LevelIn”.

In step903, the coordinates (“UPos”, “VPos”), 16 bit “Level”, and variables “eob” and “merge” from general purpose register “Src1” are stored in register “Dest”. In an embodiment, steps902and903can be performed in parallel.

In this embodiment, in step903, instruction VIDUV uses output format converter of443.4of second ALU410.2(FIG. 4G). Output format converter generates a 64 bit value, having the following properties:

In step904, one byte of information (“coordinate information”) including coordinates (“UPos”, “VPos”) and variable “eob”, which indicates whether a coordinate corresponds to an end-of-block code, are stored in a field of special purpose register “Video_UV”. The “Video_UV” consists of 8 bytes, that is 1 byte of information for each of 8 coordinates. The “UVReg” field identifies which of the 8 bytes are modified by instruction VIDUV.

As shown inFIG. 5, the one byte of information in special purpose register “Video_UV” is available to other instructions including VIDMUX and VIDIDCT. As shown, variables “level”, “UPos”, “VPos”, and “eob” are provided for use by instruction VIDIQMO. Variables “UPos”, “VPos” (shown respectively as [ACC], [Cosine], and [Wt*QS] inFIG. 5) are provided for use in instructions VIDMUX and VIDIDCT.

Referring toFIG. 3, at call305, instruction VIDMUX is executed.FIG. 10shows a flow diagram1000of instruction VIDMUX. Pseudocode for instruction VIDMUX is provided in Appendix D. Table 7 depicts the encoding of instruction VIDMUX.

TABLE 731 . . .25 . . .23 . . .17 . . .14 . . .26241816151211 . . . 65 . . . 011011111DestSrc1ID0UVReg100100000000
Bits [31:26, 25:24, 11:6, and 5:0] specify the VIDMUX instruction. Fields “Dest” and “UVReg” specify, respectively, the general purpose register used in the instruction as result destination and a byte in the special purpose register “Video_UV”. Field “Src1ID” includes a “base address” into a general purpose register file, from which a general purpose register number can be calculated.

In step1001, block coordinates (u,v) for the coefficient decoded in VIDRSVLD or VIDVLD (call302or303) are loaded. Bits [2:0] of field “UVReg” specifies which 8-bit identification segment in 64 bit-register Video_UV includes coordinate information.

In step1002, directive {MuxData :=GPR[Src1ID∥u0∥v2 . . . 0]} loads the contents of the general purpose register, specified by the concatenation of “SrcID”, u0, and v2 . . . 0, that includes the dequantization constant associated with the coefficient having block coordinates (u, v). Variable “Scr1ID” selects a range of 16 registers and the concatenation of u0and v2 . . . 0identifies a specific register among the 16 registers. Table 8 depicts values of Src1ID and the corresponding general purpose register selected by Src1ID.

TABLE 8general purpose registerSrc1IDbase address0R01R162R323R48
Thereby variable “MuxData” represents a 64 bit quantity that includes the desired dequantization constant, variable “Wt*QS”. A variable “MuxControl”, being the 2 most significant bits of coordinate “u” specifies which 16-bit region, i.e., either bits0-15,16-31,32-47, or48-63, of variable “MuxData” is the desired dequantization constant, variable “Wt*QS”.

Instruction VIDMUX next utilizes zero stuffer device416ofFIG. 4D. A 64 bit input signal416.A to zero stuffer device416is “MuxData” and signal “select” is variable “MuxControl”. Zero stuffer device416selects the 16 bits specified by “MuxControl” in “MuxData”; stores the 16 bits in a 16-bit region, i.e., either bits0-15,16-31,32-47, or48-63, specified by “MuxControl”, where all bits but the 16-bit region are zero; and outputs a 64 bit value.

In step1003, the 64 bit value output from zero stuffer416is stored into the general purpose register specified by field “Dest”.

Referring toFIG. 5, the 16-bit dequantizing constant (shown as Wt*QS), is provided for use in instruction VIDIQMO.

Referring toFIG. 3, call306(i.e., instruction VIDIQMO) is then executed. A flow diagram1100for instruction VIDIQMO is depicted inFIG. 11A.FIG. 11Bschematically depicts the operation of instruction VIDIQMO. Table 9 depicts the encoding of instruction VIDIQMO.

Bits [31:26, 25:24, and 11:6] specify the instruction VIDIQMO. Fields “Dest”, “Src1”, and “Src2” each specify one of 64 general purpose registers used in the instruction for result destination and source operands.

In step1101, the dequantizing value, “Wt*QS”, and the coefficient, “Level”, are multiplied to yield a 32-bit value result (“result”).

In step1102, if the product (i.e., the value of variable “result”) is negative, the 6 least significant bits are set to zero (step1103) and the result is incremented by 2−11(step1104).

In this embodiment, round circuit454(FIG. 4H) implements the steps of1102and1103using hardwired logic.

In step1105, a sign extension is performed to convert the 26-bit result to a 32-bit value (“In”). Steps1102-1105implement MPEG standard rounding.

Step1106determines if oddification is to be applied to “In”. If (1) MPEG-1 type encoding has been employed; (2) the 8×8 block coordinates of a coefficient are not (0,0) or (7,7); and (3) the block is not part of an intra-picture, then an MPEG-1 oddification techniques will be applied to “In”. In this embodiment, for coordinates (7, 7), a further inquiry is whether a non-zero coefficient is present. If there is a non-zero coefficient at (7, 7) and an end of block signal is not associated with the coordinate, then oddification is to be performed on the coefficient at coordinates (7, 7). Values of variables used to decide whether to perform oddification include “UPos”, “VPos”, “eob” from the general purpose register specified in field “Src1”, variables “macroblock_intra” and “mpeg2” from special purpose register “Video_MBstate”. Variables “macroblock_intra” and “Video_MBstate” represent whether the current block is part of an I-picture, and whether MPEG-2 format encoding has been applied, respectively.

In step1107, oddification is performed. A discussion of MPEG-1 oddification techniques is provided in Mitchell, J., Pennebaker, W., Fogg, C., and LeGall, D.,MPEG Video Compression Standard, Chapman and Hall, New York, N.Y. (1996). First, if “In” is positive and the least significant bit of “In” is zero, then “In” is decremented by 2−11. Next, if “In” is negative and the least significant bit of “In” is zero, then “In” is incremented by 2−11.

In this embodiment, oddification circuit460(FIG. 4H) performs the operations of steps1106to1107.

In step1108, “In” is stored as “Wt*QS*Level” in the general purpose register specified by the “Dest” of the VIDIQMO instruction.

As shown inFIG. 5, instruction VIDIQMO makes available “eob” for use by instructions JUV and VIDIQSC and variable “Wt*QS*Level” (shown as “mo”) for use by instruction VIDIQSC.

Referring toFIG. 3, call to instruction VIDIQSC (i.e., call307) is performed. A flow diagram1200of instruction VIDIQSC is provided inFIG. 12A.FIG. 12Bschematically depicts the operation of instruction VIDIQSC. In this embodiment, the execution of instruction VIDIQSC is performed using a hardwired logic implementation, depicted schematically as VIDIQSC circuit464ofFIG. 4H.

Table 10 depicts the encoding of instruction VIDIQSC.

Bits [31:26, 25:24, and 11:6] specify instruction VIDIQSC. The fields “Dest”, “Src1”, and “Src2” specify respectively general purpose registers used in the instruction.

In step1201, variable “Wt*QS*Level” is saturated in accordance with MPEG standard.

In step1202, if the dequantized product is encoded using MPEG-2, i.e., variable “mpeg2” is 1, then a mismatch control or accumulation procedure may be applied. Mismatch accumulation (1203) is performed by an exclusive-OR of the least-significant bits of successive “Wt*QS*level”, and the values of variables “lsbIn” and “mmcIn”. The result is assigned as a value to variable “mmcOut”. This procedure is a shortcut to determining if the sum of all “Wt*QS*level” is odd or even. The variable “lsbIn” is then copied into variable “lsbOut”.

Step1204determines whether to apply a mismatch modification. If (“UPos”, “VPos”) is (7,7) then a mismatch modification is applied in step1205. In step1205, mismatch modification is performed by toggling the least significant bit of saturated “Wt*QS*level”, which is the value of variable “mmcIn”, even if the coefficient at (7, 7) is zero. The value of variable “lsbOut” stores the toggled value of variable “mmcIn”.

Step1206determines whether to clear the mismatch state. If variable “eob” indicates an end-of-block associated with the coefficient at coordinates (7, 7), then accumulated mismatch control variable “mmcOut” is set to zero in step1207. In step1208, if the current video data is not encoded under the MPEG-2 standard, then the value of variable “lsbOut” is set to the value of variable “lsbIn” and the value of accumulated mismatch control variable “mmcOut” is set to zero.

In step1209the value of variable “lsbIn” is stored as the value of variable “lsbOut”, replacing the least significant bit of the saturated value of variable “Wt*QS*Level”.

In step1210, the “Wt*QS*Level” value is extended from 12 bits to 16 bits by inserting zeroes.

In step1211, the 16-bit “Wt*QS*Level” is replicated four times and stored in the general purpose register specified by the field “Dest” of the VIDIQSC instruction. For the least significant 16 bits in that general purpose register, in step1212, the least significant bit is replaced with the value of variable “mmcOut”.

As shown inFIG. 5, the contents of field “Dest”, including variable “mmcOut” are available to subsequent executions of instruction VIDIQSC. The four copies of “Wt*QS*Level” (shown as “sc”) are available for use in instruction VIDIDCT.

Referring toFIG. 3, instruction VIDIDCT (i.e., call308) is executed to perform a horizontal inverse discrete cosine transform for an 8×8 block (instruction PBFY completes the horizontal inverse discrete cosine for all coefficients in a block). A flow diagram1300of instruction VIDIDCT (call308) is depicted inFIG. 13A.FIG. 13Bschematically depicts the operation of instruction VIDIDCT. Pseudocode for instruction VIDIDCT is provided in Appendix E.

Table 12 depicts the encoding of instruction VIDIDCT.

In step1301, the values of variables “u” and “v”, which represent respectively the coordinates of a coefficient in an 8×8 block are extracted from special purpose register “Video_UV”, based on “VideoID”, the byte position of the coefficient's information.

In step1302, an appropriate accumulator, represented by variable “r”, is chosen. There are 16 accumulators, numbered 0 to 15. An accumulator is allocated for each “u” or “v” coordinate in a block. Consistent with the MPEG standard, in a horizontal IDCT, a single coefficient is effectively multiplied by a row of 8 cosine values. Each product is then added or accumulated in each of the coordinates along a row. Hence for each row, eight cosine products are accumulated for each coordinate. An analogous procedure accumulates eight cosine products for each coordinate along a column in a vertical IDCT.

Table 13 indicates the accumulator number used for each coordinate in a block. The accumulator number corresponds to the concatenation of u0with v2 . . . 0.

General purpose registers are used as accumulators. The value of variable “DestID” specifies a base address of a group of general purpose registers. Table 14 depicts the general purpose register group corresponding to each DestID value.

TABLE 14General purpose register BaseDestIDAddress0R01R162R323R48
The appropriate accumulator, specified by the value of variable “r”, is chosen by the concatenation of u0with v2 . . . 0with the base address of the general purpose register specified by field “DestID”.

In step1303, four cosine values are chosen. The value of variable “s” includes 4 cosine values. The value of variable “Src1ID2”, encoded in the instruction, also represents a base address for a group of general purpose registers. Table 15 depicts the relationship between Scr1ID2 and the group of general purpose registers.

TABLE 15generalpurposeSrc1ID2register base0R01R82R163R244R325R406R487R56
The value of variable u2 . . . 0is concatenated with the bit pattern in field “Src1ID2” to provide the general purpose register number. The general purpose register corresponding to the general purpose register number thus obtained stores the four cosine values (i.e., value of variable “s”).

Table 16 depicts an example of 8 rows of 4 cosine values specified in the MPEG standards to be used in the IDCT. The table 16 is merely illustrative and is not a precise representation of the values. See the MPEG standards for the desired precision of the cosine values. Variable u2 . . . 0discussed earlier specifies which row of four cosine values to use.

The full cosine IDCT matrix is 8 by 8. However, because of the symmetry of the full matrix, only a half of the matrix needs to be stored and used. For rows 0, 2, 4, and 6, values in columns 4 . . . 7 of the cosine matrix (not depicted) are the same as in columns 3 . . . 0. For rows 1, 3, 5, and 7, values in columns 4 . . . 7 of the cosine matrix (not depicted) are negative the values in columns 3 . . . 0.

In step1304, four copies of a coefficient, denoted as variable “t” in the pseudo code, are loaded from the general purpose register labeled “Src2”. Using AND circuit459ofFIG. 4H, the least significant bit of the copy of the least significant bits is set to zero. In this embodiment, the least significant bit is discarded here because it is used to record the MPEG-2 mismatch control state and thus should not be subject to an horizontal IDCT.

In step1305, bits i to 15+i of coefficient (“t15+i . . . i”) are multiplied to a corresponding cosine value (i.e., the value of variable s15+i . . . i). The product is assigned to as the value of 32-bit variable “p”.

In step1306, the variables “r” and “p” are added and stored in register “n”. A suitable process of step1306follows. The 32-bit variable “p” is added to a 32-bit value of variable “n”, which is stored in the accumulator specified by the value of variable “r15+i . . . i”. The value of variable “r” is expanded into a 32-bit value by placing the most significant bit of “r15+i . . . i” into bit position31and by filling the 15 least significant bits with zeros. The 16-bit value of variable “r” is placed in bits30to15. The 32-bit product “p” is then added to the 32-bit expanded value of variable “r”.

In step1307, function Round rounds 32-bit accumulator variable “n” to the nearest integer. In this embodiment, the least-significant bits of variable “n” represent a fraction. The range of values of variable “n” ranges from −1 to just under +1. The rounded value is assigned to variable “o”.

In step1308, function SaturateSS converts the value of variable “o”. For values between −2 to just under −1, the value of variable “o” is assigned −1. Similarly, for a value from +1 to +2, the value of variable “o” is assigned +1. Essentially, saturation occurs when a 16-bit value has overflowed to 17-bit value. The result of function SaturateSS is stored in 16 bits of variable “result15+i . . . i”.

Steps1305-1308are repeated three more times, assigning the iteration index “i” the values 16, 32, and 48, respectively. The i values select the 16-bit quantities at bits16-31, bits32-47, and bits48-63, respectively from each of values of variables “s” (i.e., the cosine matrix), and the coefficients in variable “t”. In this embodiment, four iterations of steps1305to1308are performed in parallel.

Instruction JUV

Referring toFIG. 3, instruction JUV (call309) is executed next. Table 17 depicts the encoding of instruction JUV.

Bits [31:26, 25:24, and 23] specify instruction JUV. The value of variable “Disp” represents a displacement, i.e., the number of 32-bit words, between the instruction sequentially following the JUV instruction, and a next instruction.FIG. 14depicts a flow diagram1400of instruction JUV (call309). In step1401, a bit in the special purpose register Video_UV is examined to determine whether there is an end-of-block signal associated with a coefficient. If an end-of-block code is not detected, JUV ends. Execution continues at the instruction sequentially following instruction JUV.

If an end-of-block code is detected, then in step1402, a displacement, provided as the value of variable “target_displ”, is added to the value of variable “ip_seq”, which represents the address of the next instruction.

Instruction PBFY is executed after all instructions VIDUV, VIDMUX, VIDIQMO, VIDIQSC, and VIDIDCT are applied to all coefficients of a full block. Instruction PBFY causes the horizontal IDCT of a coefficient described with respect toFIG. 13Ato be applied across an 8 coordinate row of a block.FIG. 15depicts an operation1500of instruction PBFY.

Table 18 depicts the encoding of instruction PBFY.

Under the MPEG standard for horizontal IDCT each coordinate in a row receives a contribution from the cosine products of all coordinates in its row. In the instruction VIDIDCT, only a contribution of cosine products from alternating coordinates was made. As depicted in Table 13, horizontal IDCT of consecutive coefficients across a row are stored in staggered accumulators. For example, in the top row, row 0, accumulator 0 stores accumulations for positions (0, 0), (0, 2), (0, 4), and (0, 6) while accumulator 8 stores accumulations for positions (0, 1), (0, 3), (0, 5), and (0, 7). In instruction PBFY, contributions from (0, 5) and (0, 7) are made to respective positions (0, 0), (0, 2) and contributions from (0, 1) and (0, 3) are made to respective positions (0, 4) and (0, 6). Contributions in PBFY are analogous to interlocking teeth where positions (x,7) to (x,4) are folded into respective positions (x,0) to (x,3). For rows 0, 2, 4, and 6 contributions from (x, 7) to (x, 4) are additive. However, for odd rows numbered 1, 3, 5, and 7, negative contributions are made from (x, 7) to (x, 4). This is scheme is due to the symmetries of the cosine matrix discussed above. For even rows, columns 0-3 of the cosine matrix are the same as columns 7-4 respectively. For odd rows, columns 0-3 of the cosine matrix are the negative of columns 7-4 respectively.

As stated earlier, instruction VIDIDCT does not perform a full horizontal inverse discrete cosine transform on a coefficient. Following decoding of all variable length codes in a single block, instruction PBFY is executed to complete a horizontal inverse discrete cosine transform on the coefficients of a block.

In step1501, by directive “switch(msize)”, the contents of registers “Src1” and “Src2” are reversed by operand. Registers Src1 and Src2 include respective alternating accumulators used in a row. For example for row 0, the top row, Src1 would include accumulator 0 and Src2 would include accumulator 8. Where the operand size is 16 bits, the most significant operand, i.e., in bits63. . .48, switches place with the least significant operand, in bits15. . .0. Variable “Msize” specifies whether an operand is 8, 16, or 32 bits. The process continues until the order of operands is reversed.

In step1502, each operand of registers “Src1” and “Src2” are added and subtracted in parallel. Variable “sum” represents the sum of the contents of registers “Src1” and “Src2”. Variable “diff” represents the contents of register “Src1” minus the contents of register “Src2”. Overflow values of “sum” or “diff” are saturated. Table 11, discussed above, depicts saturation formats.

In step1503, variables “sum” and “diff” are stored in respective general purpose registers “Dest” and “Dest+1”. The contents of the registers are made available for a subsequent vertical IDCT.

To complete variable length decode of a block, following the instruction PBFY, a conventional vertical IDCT is performed. A block is thereby converted to the time domain. In this embodiment, an exemplary vertical IDCT uses a process available from IBM entitled AAN Algorithm.

This embodiment of the present invention provides a system of flexibly mapping groups of 64 general purpose registers to various uses by the different instructions.

Example of Interleaved Operation

Table 19 illustrates, for a single clock cycle having sequential stages C, D, R, A, M, E, and W, a relationship between sequential stages C, D, R, A, M, E, and W, and operative components of first ALU410.1, second ALU410.2, and third ALU410.3.

Appendix H illustrates an example operation of multiple instructions during stages of multiple clock cycles. See Appendix I for the sequential order of the instructions of Appendix H. For example in cycle1627, in stage R, first ALU410.1begins executing instruction LDBITSR. Instruction LDBITSR is not completed until cycle1632. However, in cycle1628, stage R, the second ALU410.2begins executing instruction VIDRSVLD with an operand as one of the variable length codes loaded by instruction LDBITSR. Instruction VIDRSVLD is not completed until cycle1633. In cycle1630, stage R, second ALU410.2begins executing instruction VIDUV. Instruction VIDUV is not completed until cycle1634. In cycle1636, stage R, the first ALU410.1begins executing instruction VIDMUX. Instruction VIDMUX is not completed until cycle1641. In cycle1639, stage R, the third ALU410.3begins executing instruction VIDIQMO. Instruction VIDIQMO is not completed until cycle1643. In cycle1642, stage R, the third ALU410.3begins executing instruction VIDIQSC. Instruction VIDIQSC is not completed until cycle1646. In cycle1644, stage R, the third ALU410.3begins executing instruction VIDIDCT. Instruction VIDIDCT is not completed until cycle1648(not depicted). Thus instructions that operate on a single coefficient begin prior to completing instructions begun prior. Note that in Appendix H, “r” represents a number of a general purpose register and “0.2” following an instruction represents that an instruction is operating for a second coefficient.

As shown in Appendix H, simultaneously with decoding of the second coefficient, at least a first, fifth, sixth, and seventh coefficient are at some stage of decoding.

In practice, the user can specify an order of instructions which maximizes the speed of variable length code decoding.

In the example of Appendices H and I, at most 8 coefficients can be decoded at any time (8 corresponding to the number of registers in VIDEO_UV Register). Of course, if both the size of VIDEO_UV Register and the number of general purpose registers are increased, the number of coefficients decoded at any time increases.

MODIFICATIONS

The above-described embodiments of the present invention are illustrative and not limiting. It will thus be obvious to those skilled in the art that various changes and modifications may be made without departing from this invention in its broader aspects. For example, the instruction set architecture-could be MIPS or RISC based. The embodiments of the present invention could apply, e.g., to MPEG-4, JPEG, and H.261 type codes. Therefore, the appended claims encompass all such changes and modifications as fall within the true spirit and scope of this invention.