JP2003345778A - Two-dimensional inverse discrete cosine transform circuit and image decoding device - Google Patents

Abstract

(57) Abstract: Provided is a two-dimensional inverse discrete cosine transform circuit having a reduced circuit scale by reducing registers, and an image decoding device using the same. In a one-dimensional inverse discrete cosine transform circuit (42), in each of steps (44) to (46) of operation, a register for storing an intermediate result is not provided, but only a register for storing an operation result of a final operation step (47) is provided. by this,
The number of registers can be reduced, and the circuit scale can be reduced.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a two-dimensional inverse discrete cosine transform circuit, and more particularly to an MPEG (Moving Picture E-mail).
xpert Group) relates to a two-dimensional inverse discrete cosine transform circuit of an image decoding device.

[0002]

2. Description of the Related Art MP is a compression / decompression technique for image data.
The EG method is known. In MPEG, the core of the technology used to compress and decompress image data is motion-compensated prediction (MC).
n), Discrete Cosine Transform (DCT)
nsform) and variable length coding (VLC: variable length)
h coding). The DCT is basically a transform for decomposing a time signal into frequency components like a Fourier transform.
That is, it can be considered that the Fourier transform has a complex number operation and is decomposed into a real part and an imaginary part, whereas the DCT extracts only the real part. Equation 1 represents a DCT conversion equation.

When a video screen is compressed / expanded by MPEG, the screen is first moved in the horizontal and vertical directions by N, respectively.
It is divided into small blocks consisting of pixels, and then two-dimensional DCT is performed on the small blocks consisting of N × N pixels. The larger N is, the better the coding efficiency is, but the amount of calculation increases. Usually, about N = 8 is often used.

When encoding (compressing) with MPEG, DC
Using T, the screen (image signal) is decomposed into frequency components and processed. At the time of decoding (expansion), an inverse discrete cosine transform IDCT (Inverse DCT) which is an inverse transform of DCT is used.
Using T), the frequency component is returned to the screen (image signal) again. Equation 2 represents the IDCT conversion equation.

[0005]

(Equation 1)

[0006]

(Equation 2)

In the two-dimensional DCT or IDCT operation, if the conversion formula is simply executed as it is, the number of operations becomes enormous. For example, to perform a two-dimensional IDCT operation of 8 × 8 pixels requires 4096 multiplications and 4096 additions. Therefore, as shown in Equations 3 and 4, the two-dimensional ID
CT is simplified to one-dimensional IDCT, and one-dimensional IDC
By calculating T, the number of calculations of the two-dimensional IDCT can be reduced.

[0008]

(Equation 3)

[0009]

(Equation 4)

That is, for 8 × 8 elements, first, one-dimensional IDCT is performed on eight rows in the horizontal direction.
Next, one-dimensional IDCT is performed on eight rows in the vertical direction. When the one-dimensional IDCT is performed twice in this manner, 1024 multiplications and 1026 additions are required. DC
The same applies to T. To further speed up the operation of two-dimensional DCT or IDCT, one-dimensional DCT or IDCT
It is necessary to reduce the number of CT operations themselves.
Therefore, various high-speed operation algorithms have been proposed. In particular, a high-speed algorithm called “butterfly operation” has been used in conventional MPEG encoders and decoders.
When the butterfly operation is used, 256 multiplications and 41 additions are performed.
Only six calculations are required.

The above operations of DCT and IDCT are usually executed by a large-scale integrated circuit (LSI). Therefore, since the number of operations is reduced, the scale of the operation circuit is reduced. However, even when the number of operations is reduced using a high-speed algorithm, large-scale hardware is required if two-dimensional DCT or IDCT operation is simply performed. Therefore, usually, two-dimensional DCT
Alternatively, the size of an arithmetic circuit can be reduced by having a unit function block for IDCT operation and repeatedly using the function block. In order to further reduce the size of the arithmetic circuit, further contrivance is required. Compared with DCT, the data after inverse quantization is input to the two-dimensional IDCT.
The bit width of the IDCT coefficients is large, so that ICT
In the case of DCT, the circuit scale becomes more problematic. In addition, a television receiver or a compressed image reproducing device is an IDC
Since a configuration with the function of T is sufficient, the present invention
An object is to reduce the circuit scale of DCT.

[0012]

FIG. 1 is a diagram showing a general configuration of a two-dimensional inverse discrete cosine transform circuit. FIG.
The two-dimensional inverse discrete cosine transform circuit 10 shown in
An input selection circuit 11 for selectively outputting either a data matrix input from the outside or a data matrix transposed inside the two-dimensional inverse discrete cosine transform circuit;
, And a one-dimensional inverse discrete cosine transform circuit 12 that performs one-dimensional inverse discrete cosine transform, and stores the output of each row of the one-dimensional inverse discrete cosine transform circuit 12. After storing one block, the transpose transform is performed. And a transposition memory 13 for performing the operation.

Here, the one-dimensional inverse discrete cosine transform is
This is the conversion represented by the above equation (3) or (4). Equations (3) and (4) are further simplified to give equation (5)
Write as follows.

(Equation 5) As a result, eight pieces of converted data are calculated from the eight pieces of input data.

In the two-dimensional inverse discrete cosine transform circuit 10 shown in FIG. 1, first, for example, one row (eight pieces) of data in the X direction is inversely quantized by an inverse quantization circuit in an MPEG decoder. It is input to the discrete cosine transform circuit 12. The one-dimensional inverse discrete cosine transform circuit 12 performs one-dimensional inverse discrete cosine transform on the one row of data. Output data of the one-dimensional inverse discrete cosine transform circuit 12 is stored in the transposition memory 13. The transposition memory 13 sequentially stores data row by row at, for example, 8 rows × 8 columns = 64 addresses. After all the data of 8 rows (64 pieces) of one block are converted and stored in the transposition memory 13, the transposition memory 13 transposes the matrix of 8 rows × 8 columns, and transposes the rows and columns. I do.

The matrix of 8 rows × 8 columns after the transpose is input to a one-dimensional inverse discrete cosine transform circuit 12 through an input selection circuit 11.
, And the matrix of 8 rows × 8 columns transposed in the transposition memory 13 is recursively input to the one-dimensional inverse discrete cosine transform circuit 13. Data is read out sequentially for each column of addresses in the transposition memory 13, and the one-dimensional inverse discrete cosine transform circuit 12 performs one-dimensional inverse discrete cosine transform as in the first time. The output data that has been subjected to the two-dimensional inverse discrete cosine transform twice is output as the output data of the two-dimensional inverse discrete cosine transform circuit 10. As described above, the two-dimensional inverse discrete cosine transform is performed by repeating the one-dimensional inverse discrete cosine transform twice.

In the one-dimensional inverse discrete cosine transform circuit 13, Chen's algorithm is widely used as an algorithm for performing one-dimensional inverse discrete cosine transform at high speed. In the fast algorithm, the DCT coefficient F
(U) is converted into a pixel value f (x), for example, an 8 × 8 matrix is transformed into a small matrix having many zeros. In this way, the number of multiplications is reduced, and the operation of the IDCT transform is speeded up and simplified. Chen's algorithm relates to a method of decomposing the transformation matrix into small matrices. FIG. 2 is a butterfly diagram of the Chen algorithm. In the butterfly diagram of FIG. 2, C1 to C7 are co
s (1/16) π to cos (7/16) π, S1 to S7 are si
n (1/16) π to sin (7/16) π respectively. As shown in FIG. 2, the DCT coefficients F (0) to F (7) are input, multiplied by constants C1 to C7 or S1 to S7, and added in the combination indicated by each arrow, The pixel values f (0) to f (7) are calculated.

The operation shown in the butterfly diagram of FIG.
Is divided into two steps. The arithmetic circuits in steps 1 to 4 each include an adder circuit and a multiplying circuit composed of an adder circuit, and have DCT coefficients F (0) to
F (7) is multiplied by constants C1 to C7 or S1 to S7, and the multiplied DCT coefficients are added in the combination shown in FIG. 2, and in each step, an intermediate result (column X in FIG. 2) is obtained. , Y, Z circles) and the pixel value result f
(0) to f (7) are obtained.

FIG. 3 is a diagram clearly showing the arrangement of registers in the configuration of the two-dimensional inverse discrete cosine transform circuit of FIG. In FIG. 3, reference numerals 16, 17, 18, 19
Indicates an arithmetic circuit in steps 1 to 4,
Reference numerals 20, 21, 22, and 23 denote arithmetic circuits 1 respectively.
A plurality of registers for holding the operation results of 6, 17, 18, and 19 at one time. As shown in FIG. 3, the conventional one-dimensional inverse discrete cosine transform circuit includes registers 20, 21, 22,
23 is provided to temporarily hold the intermediate result and the final result obtained by the arithmetic circuits 16 to 19 in each step. By providing a register for each step, the calculation of each step is synchronized, and the processing of the operation is assured. However, since a plurality of registers are provided in each step, there is a problem that the number of registers increases and the circuit scale increases.

Consider the total number of registers and the total amount of data in a conventional one-dimensional inverse discrete cosine transform circuit. C in FIG.
From the butterfly diagram of Hen's algorithm, if simply considered, there are eight nodes at each step, so one register is provided at each node, and therefore there are 32 nodes at four steps, and all 4 × 8 = 32 registers Is required. As the bit width, since the data after inverse quantization is input to the two-dimensional inverse discrete cosine transform, the DCT coefficients F (0) to F (0)
(7) is 12 bits. Actually, as shown in FIG. 3, since the transposed data after the one-dimensional inverse discrete cosine transform and the data after the inverse quantization are selected and inputted, the bit width to be stored in the transposed memory is used. In each step, the operation is performed, so even if it is considered that the average is 20 bits, 20 × 32 = 64
The zero bit must be temporarily stored.

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and has as its object to provide a two-dimensional inverse discrete cosine transform circuit having a reduced circuit scale by reducing registers and an image decoding apparatus using the same. Is to do.

[0021]

In order to solve the above-mentioned problems, a two-dimensional inverse discrete cosine transform circuit according to the present invention includes an arithmetic circuit unit for performing one-dimensional inverse discrete cosine transform on input data; A one-dimensional inverse discrete cosine transform circuit including storage means for storing an operation result of the one-dimensional inverse discrete cosine transform output from the arithmetic circuit unit; and a transpose transform for output data of the one-dimensional inverse discrete cosine transform circuit Transposing means for outputting the transposed data to the one-dimensional inverse discrete cosine transform circuit; and selecting one of the data output from the transposing means and data input from the outside, and selecting the one-dimensional inverse discrete Input selection means for outputting to the cosine transform circuit, wherein the one-dimensional inverse discrete cosine transform circuit decomposes the one-dimensional inverse discrete cosine transform operation into a plurality of steps and sequentially performs the operation. , The storage unit, among the plurality of steps, without storing the operation results of each step except the last step, to store only the calculation result of the last step.

An image decoding apparatus according to the present invention uses the two-dimensional inverse discrete cosine transform circuit.

According to the above-described two-dimensional inverse discrete cosine transform circuit and image decoding apparatus, since the registers are provided only after the final step without providing the registers at each step, the circuit scale can be reduced.

[0024]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of a two-dimensional inverse discrete cosine transform circuit and an image decoding apparatus according to the present invention will be described with reference to the drawings. First Embodiment FIG. 4 is a configuration diagram of a two-dimensional inverse discrete cosine transform circuit 40 according to the present embodiment. A two-dimensional inverse discrete cosine transform circuit 40 shown in FIG. 4 is an input selection circuit that selectively outputs one of a data matrix input from the outside and a data matrix transposed inside the two-dimensional inverse discrete cosine transform circuit. 41, a one-dimensional inverse discrete cosine transform circuit 42 that receives the output of the input selection circuit 41 and performs one-dimensional inverse discrete cosine transform, and stores the output of each row of the one-dimensional inverse discrete cosine transform circuit 42, and stores one block. After transposing, a transposition memory 43 that performs a so-called transpose transformation for transposing rows and columns of a matrix is provided.

In the two-dimensional inverse discrete cosine transform circuit 40, first, for example, the data of one row (for example, eight) in the X direction is converted from the inverse quantizer circuit in the MPEG decoding device to the one-dimensional inverse discrete cosine transform circuit 42. Is input to The one-dimensional inverse discrete cosine transform circuit 42 performs one-dimensional inverse discrete cosine transform on the input data of one row. Output data of the one-dimensional inverse discrete cosine transform circuit 42 is stored in the transposition memory 43. The transposition memory 43 sequentially stores data, for example, in rows of 8 rows × 8 columns = 64 addresses. After all the data of 8 rows (64 pieces) of one block are converted and stored in the transposition memory 43, the transposition memory 43 performs transposition on the matrix of 8 rows × 8 columns, and transposes the rows and columns. I do.

The matrix of 8 rows × 8 columns after the transposition is input to a one-dimensional inverse discrete cosine transform circuit 42 via an input selection circuit 41.
Then, the matrix of 8 rows × 8 columns transposed in the transposition memory 43 is recursively input to the one-dimensional inverse discrete cosine transform circuit 42. Data is read out sequentially for each column of addresses in the transposition memory 43, and the one-dimensional inverse discrete cosine transform circuit 42 performs one-dimensional inverse discrete cosine transform in the same manner as the first time. The output data that has been subjected to the two-dimensional inverse discrete cosine transform twice is output as output data of the two-dimensional inverse discrete cosine transform circuit.
As described above, the two-dimensional inverse discrete cosine transform is performed by repeating the one-dimensional inverse discrete cosine transform twice.

In the one-dimensional inverse discrete cosine transform circuit 42, one-dimensional inverse discrete cosine transform is performed at high speed using the Chen algorithm shown in the butterfly diagram of FIG. As described above, the calculation by the Chen algorithm is divided into four steps. The arithmetic circuits 44, 45, 46 in the one-dimensional inverse discrete cosine transform circuit 42,
Numeral 47 denotes an arithmetic circuit of Steps 1 to 4, each having an adder circuit and a multiplying circuit composed of an adder circuit. As shown in the butterfly diagram of FIG.
The CT coefficients F (0) to F (7) are multiplied by constants C1 to C7 or S1 to S7, and the multiplied DCT coefficients are added in the combination shown.

In the conventional one-dimensional inverse discrete cosine transform circuit 12, the registers 20 to 23 for storing the operation results of the operation circuits 16 to 19 are provided for each step.
The circuit scale was large. In this embodiment, as shown in FIG. 4, a register for holding the operation results of the intermediate operation circuits 44 to 46 is not provided, and the operation circuit 47 in the final step is provided.
The register group 48 will be provided only later. That is, the calculation results in the middle of steps 1 to 3 are not held, but are sequentially transferred on the circuit, and the calculations are performed collectively.

FIGS. 5A to 5C show time charts of operations in the one-dimensional inverse discrete cosine transform circuit 42 of the present embodiment. FIG. 5A shows a clock signal, and FIG.
(B) shows the timing of four steps for processing one line. As shown in FIG. 5B, Steps 1 to 4 are continuously performed, for example, over four clocks. Steps 1 to 4 are repeated eight times, and the input 8 × 8
After processing all eight rows in the X direction of the matrix, for example, the result of the first one-dimensional inverse discrete cosine transform of the stored previous block (8 × 8 matrix) is read out, and FIG. Within the four clock periods shown, the second one-dimensional inverse discrete cosine transform operation of the previous block (8 × 8 matrix) is performed. As a result, one-dimensional and two-dimensional operations can be performed alternately.

FIGS. 6A to 6F show timing charts of operations in the conventional one-dimensional inverse discrete cosine transform circuit 10 for comparison with the time chart of the present embodiment. FIG. 6A shows a clock signal, and FIG.
(B) to (E) show the timing of four steps for processing one line. As shown in FIGS. 6B to 6E, when Step 1 is completed, the calculation result is held in the register 20 (FIG. 3), and synchronized with each circuit in Step 1 by the next clock. The result is passed to the operation circuit of step 2. Steps 2, 3, and 4 are performed in the same manner, that is, one-step operation is performed with one clock. An operation similar to that of FIG. 5C is performed within the four clock periods shown in FIG.

In contrast to the conventional method in which one step is processed by one clock, in the present embodiment, four steps are processed at once by four clocks, and data is held in a register between steps so that synchronization is not adjusted. , Operate asynchronously. As a result, the number of registers can be reduced to eight as compared with the conventional configuration shown in FIG. 3, and the circuit scale can be reduced.

Second Embodiment FIG. 7 shows the configuration of an image decoding device 70 according to the second embodiment. The image decoding device 70 includes a variable length decoding circuit 71, an inverse quantization circuit 72, an IDCT circuit 73, and a motion vector restoration circuit 74. Variable length decoding circuit 71
Performs variable-length decoding on input compressed image data based on a Huffman code stored in a Huffman table provided therein. Inverse quantization circuit 72
Performs inverse quantization on the decoding result of the variable length decoding circuit 71 based on a quantization threshold stored in a quantization table provided therein to obtain a DCT coefficient. The two-dimensional IDCT circuit 73 performs two-dimensional IDCT on the DCT coefficients obtained by the inverse quantization circuit 72. The motion vector restoration circuit 74 restores a motion vector with respect to the processing result of the two-dimensional IDCT circuit 73, and generates a video output as decompressed data.

The two-dimensional IDCT circuit 73 has the configuration shown in FIG. That is, the one-dimensional I of the two-dimensional IDCT circuit 73
In the DCT circuit, the circuit scale is reduced by providing a register only in the last step, instead of providing a register in each step of the butterfly operation.

Although the present invention has been described based on the preferred embodiments, the present invention is not limited to the above-described embodiments, and various modifications can be made without departing from the gist of the present invention. It is. In an embodiment of the present invention,
Although the Chen algorithm has been described as an example, the present invention is not limited to this, and another Wang algorithm, for example, may be used. Further, in the embodiment of the present invention, the processing from step 1 to step 4 is performed with four clocks. However, the present invention is not limited to this, and it may be understood that the calculation period is actually necessary.

[0035]

According to the present invention, in the one-dimensional inverse discrete cosine transform circuit, a register is provided only in the final step, instead of providing a register in each step of the operation, so that the circuit scale can be reduced. .

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a general configuration of a two-dimensional inverse discrete cosine transform circuit.

FIG. 2 is a butterfly diagram illustrating an algorithm of one-dimensional inverse discrete cosine transform.

FIG. 3 is a configuration diagram of a conventional two-dimensional inverse discrete cosine transform circuit.

FIG. 4 is a configuration diagram of a two-dimensional inverse discrete cosine transform circuit according to the first embodiment of the present invention.

FIGS. 5A to 5C are time charts of the one-dimensional inverse discrete cosine transform circuit according to the first embodiment of the present invention.

6 (A) to 6 (F) show the conventional 1
4 is a time chart of the inverse dimensional discrete cosine transform circuit.

FIG. 7 is a configuration diagram of an image decoding device according to a second embodiment of the present invention.

[Explanation of symbols]

10: two-dimensional inverse discrete cosine transform circuit, 11: input selection circuit, 12: one-dimensional inverse discrete cosine transform circuit, 13: transposed memory, 16 to 19: arithmetic circuit, 20 to 23: register, 40: two-dimensional inverse discrete Cosine transform circuit, 41: input selection circuit, 42: one-dimensional inverse discrete cosine transform circuit, 43
... Transposition memories, 44 to 47 ... Operation circuits, 48 ... Registers, 70 ... Image decoding devices, 71 ... Variable length decoding circuits,
72: inverse quantization circuit; 73: two-dimensional IDCT circuit; 74
... Motion vector restoration circuit.

Claims (2)

[Claims] 1. An arithmetic circuit unit for performing one-dimensional inverse discrete cosine transform on input data, and storage means for storing an operation result of the one-dimensional inverse discrete cosine transform output from the arithmetic circuit unit. A one-dimensional inverse discrete cosine transform circuit, transposing means for performing transpose on output data of the one-dimensional inverse discrete cosine transform circuit, and outputting the transposed data to the one-dimensional inverse discrete cosine transform circuit; Input selection means for selecting one of data output from the means and data input from the outside and outputting the selected data to the one-dimensional inverse discrete cosine transform circuit; The operation of the dimensional inverse discrete cosine transform is decomposed into a plurality of steps and sequentially performed. A two-dimensional inverse discrete cosine transform circuit that stores only the operation result of the last step without storing the result. 2. A variable length decoding circuit for performing variable length decoding on input compressed image data, and an inverse quantization circuit for performing inverse quantization on output data of the variable length decoding circuit. A two-dimensional inverse discrete cosine transform circuit that performs two-dimensional inverse discrete cosine transform on output data from the inverse quantization circuit, wherein the two-dimensional inverse discrete cosine transform circuit performs a one-dimensional inverse discrete cosine transform. A one-dimensional inverse discrete cosine transform circuit including an arithmetic circuit unit to be applied, and storage means for storing an operation result of the one-dimensional inverse discrete cosine transform output from the arithmetic circuit unit; and an output of the one-dimensional inverse discrete cosine transform circuit Transposing means for performing transposition transformation on data and outputting the transposed data to said one-dimensional inverse discrete cosine transform circuit; and data outputted from said transposition means and external Input selecting means for selecting one of the input data and outputting the selected data to the one-dimensional inverse discrete cosine transform circuit, wherein the one-dimensional inverse discrete cosine transform circuit performs a plurality of one-dimensional inverse discrete cosine transform operations. The image decoding device stores the operation result of each step other than the last step among the plurality of steps and stores only the operation result of the last step.