JP2000172674A - Inverse DCT operation device and inverse DCT operation method - Google Patents

Abstract

(57) Abstract: An inverse DCT operation apparatus and method for performing an inverse DCT operation on input data encoded by a DCT operation or the like, with an operation accuracy by IEEE and a small circuit, An object is to perform an inverse DCT operation at high speed. When a one-dimensional matrix operation is sequentially performed by decomposing an inverse DCT operation on input data, a plurality of coefficient values of the input data are rearranged, and a serial-type coefficient value is converted into a parallel-type coefficient value. And a product-sum operation unit 1 having a plurality of addition / subtraction units for performing addition / subtraction of information already stored using the output of the serial / parallel conversion unit as an address. A plurality of addition / subtraction units in the unit are used again, and a plurality of values which are the result of the product-sum operation by the product-sum operation unit are added or subtracted from each other, and then the parallel / serial conversion is performed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for performing a discrete cosine transform (DCT) operation, which is a type of orthogonal transform, to decode the encoded data. On the other hand, the inverse DCT (in
Inverse DCT arithmetic unit and inverse D for performing inverse discrete cosine transform) operation
The present invention relates to a CT calculation method.

Here, the DCT operation is a kind of orthogonal transform using a fast Fourier transform for removing redundancy of a spatial frequency component of analog moving image data or the like.
A technique for encoding the moving image data into digital moving image data and compressing the moving image data according to a high-efficiency encoding method such as PEG (moving picture experts group). The present invention provides an IEEE (Institute of Electrica) for decoding digital moving image data and the like compressed in this way and reproducing the original analog moving image data with high accuracy.
l and Electronics Engineers, Inc .: A technique for performing an inverse DCT operation in a small-scale circuit while satisfying the operation accuracy specified by an electronics-related American society.

[0003]

2. Description of the Related Art FIG. 20 is a block diagram showing an example of a configuration of a conventional inverse DCT operation device. However, here, for example, a one-dimensional method using a DA (distributedarithmetic) method as disclosed in Japanese Patent Application Laid-Open No. 4-313157 (applicant: Mitsubishi Electric Corporation, filed on November 5, 1992). Is representatively shown.

In a one-dimensional inverse DCT operation device shown in FIG. 20, an inverse DCT operation on input data divided into a plurality of blocks and encoded is performed twice in one-dimensional 8 × 8.
Into 8 × 8 in the first and second dimensions
Are sequentially executed to obtain decoded output data. More specifically, in FIG. 20, a data rearranging circuit 200 that rearranges the order in which the coefficient values of the input data are output is provided. Further, the output side of the data rearrangement circuit 200 is connected to the input side of the product-sum operation unit 300. The product-sum operation unit 300 includes a plurality of product-sum operation circuits (for example, first
-To-eighth product-sum operation circuits 350-1 to 350-35
The output side of these eight product-sum operation circuits is connected to the input side of the post-processing unit 400. The post-processing unit 400 outputs the decoded output data.

[0005] The flow of the inverse DCT operation on coded input data in the inverse DCT operation device having such a configuration will be described. First, the data rearrangement circuit 200 rearranges the order in which the coefficient values of the encoded input data are output. In principle, for serial input data that is input one word at a time, parallel input data is output by aligning all words from the least significant bit to the most significant bit and outputting parallel input data. Is performed to rearrange the coefficient values in the parallel format.

Next, the parallel coefficient values thus obtained are stored in a memory or the like in the product-sum operation unit 300 in advance. The values obtained from the memory or the like in the product-sum operation unit 300 are stored in the first to eighth product-sum operation circuits 3 using the parallel-format values stored in this manner as addresses.
By performing addition or subtraction by 50-1 to 350-8, and performing cumulative addition without using a multiplier, the product-sum operation of the parallel format coefficient values is performed.

However, a point to be noted here is that the result of the product-sum operation of the coefficient values in the parallel format by the first to eighth product-sum operation circuits is subjected to parallel / serial conversion and finally decoded. In order to obtain the output data, it is necessary to perform post-processing such as adding or subtracting a plurality of values obtained as a result of the product-sum operation. In the inverse DCT operation device of FIG.
At 00, post-processing of the product-sum operation is performed by adding or subtracting a plurality of values obtained as a result of the product-sum operation of the coefficient values in the parallel format.

[0008]

As described above, in the conventional inverse DCT operation device using the DA method, a post-processing section is provided on the output side of a plurality of product-sum operation circuits. Are added or subtracted between a plurality of values obtained as a result of the product-sum operation of the coefficient values by the product-sum operation circuit. However, the circuit such as the post-processing unit is redundant, and providing such an extra circuit causes a problem that the circuit scale of the inverse DCT operation device is increased unnecessarily.

In particular, when decoding a large amount of moving image data compressed in accordance with the MPEG standard, the inverse DCT operation of a two-dimensional 8 × 8 matrix is performed on each of a plurality of blocks with the operation accuracy specified by IEEE. Need to do. However, in a configuration in which eight accumulators are executed in parallel and a product-sum operation is performed as in a conventional inverse DCT operation device, many clock cycles are wasted to satisfy the above operation accuracy. Inverse DC for moving image data
It takes a lot of time to complete the T operation.

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and has an inverse DCT operation device for executing an inverse DCT operation at high speed with a small-scale circuit while satisfying the operation accuracy specified by IEEE. It is an object of the present invention to provide an inverse DCT operation method.

[0011]

FIG. 1 is a block diagram showing the principle configuration of the present invention. However, here, the configuration of the inverse DCT operation device of the present invention is simplified. In order to solve the above problem, the inverse DCT operation device of the present invention decomposes an inverse DCT operation on arbitrary encoded input data into at least two one-dimensional matrix operations as shown in FIG. When decoding the input data by sequentially executing the predetermined number of one-dimensional matrix operations, a plurality of coefficient values of the input data are rearranged and then transmitted in a serial format. A serial / parallel conversion unit 4 for converting a numerical value into a coefficient value in a parallel format, and a plurality of addition / subtraction units for performing addition / subtraction of information already stored using a value output from the serial / parallel conversion unit 4 as an address. And a product-sum operation unit 1. Here, the plurality of addition / subtraction units are a plurality of cumulative addition units (in FIG. 1, the first to n-th cumulative addition units 3-1) in the product-sum operation unit 1.
３−3-n).

In the inverse DCT operation device of the present invention shown in FIG. 1, a plurality of addition / subtraction units in the product-sum operation unit 1 are used again, and a plurality of product-sum operations obtained by the product-sum operation unit 1 are obtained. The input data is decoded by adding or subtracting the values, and then performing parallel / serial conversion by the parallel / serial converter 5.

Further, the inverse DCT operation device according to the first preferred embodiment of the present invention decomposes the inverse DCT operation on arbitrary encoded input data into two one-dimensional matrix operations to perform one-dimensional operation. A coefficient value rearranging unit for rearranging a plurality of coefficient values of the input data when decoding the input data by sequentially executing a predetermined number of matrix operations in the first and second dimensions; A serial / parallel conversion unit for converting a coefficient value sent in a serial format from the numerical value rearranging unit into a parallel format coefficient value;
A product-sum operation unit having a plurality of addition / subtraction units for performing addition / subtraction of information already stored, using a value output from the parallel conversion unit as an address, and a result of a first-dimension product-sum operation performed by the product-sum operation unit A transposition unit that transposes a plurality of values obtained from the transposition unit, inputs a plurality of values in a parallel format sent from the transposition unit to the product-sum operation unit, and performs a second-dimensional product of the plurality of values. A sum operation is performed, the plurality of addition / subtraction units in the product-sum operation unit are used again, and a plurality of values obtained as a result of the second-dimensional product-sum operation are added or subtracted, and then parallel / serial conversion is performed. Is performed to decode the input data.

Further, the inverse DCT operation device according to the second preferred embodiment of the present invention decomposes the inverse DCT operation on any encoded input data into two one-dimensional matrix operations, When decoding the input data by sequentially executing a predetermined number of matrix operations in the first and second dimensions, rearrangement of a plurality of coefficient values of the input data is performed.
Coefficient value rearranging units, and coefficient values sent in serial form from each of these two coefficient value rearranging units,
A product-sum operation unit having a serial / parallel conversion unit for converting to a coefficient value in a parallel format, and a plurality of addition / subtraction units for performing addition / subtraction of information already stored using a value output from the serial / parallel conversion unit as an address. And two transposition units that transpose a plurality of values obtained as a result of the first-dimension product-sum operation by the product-sum operation unit, and are transmitted from each of these two transposition units. The plurality of values in the parallel format are input to the product-sum operation unit, and a second-dimensional product-sum operation of the plurality of values is performed, and the plurality of addition / subtraction units in the product-sum operation unit are used again. The input data is decoded by adding or subtracting a plurality of values sent from each of the two transposition units and then performing parallel / serial conversion.

Further, the inverse DCT operation device according to the third preferred embodiment of the present invention decomposes the inverse DCT operation on any encoded input data into two one-dimensional matrix operations, When decoding the input data by sequentially executing a predetermined number of matrix operations in the first and second dimensions, rearrangement of a plurality of coefficient values of the input data is performed.
Coefficient value rearranging units, and coefficient values sent in serial form from each of these two coefficient value rearranging units,
A serial / parallel conversion unit for converting into a coefficient value in a parallel format, and a plurality of first addition / subtraction units for performing addition / subtraction of information already stored using a value output from the serial / parallel conversion unit as an address A two-dimensional sum-of-products operation unit, and transposes a plurality of values obtained as a result of the first-dimensional sum-of-products operation by the one-dimensional sum-of-products operation unit 2
And two transposition units.

The inverse DCT operation device according to a third preferred embodiment of the present invention further comprises, as an address, a plurality of values in a parallel format sent from each of the two transposed units, for the information already stored. A two-dimensional product sum calculation unit having a plurality of second addition / subtraction units for performing addition / subtraction. The second plurality of second addition / subtraction units in the two-dimensional product sum calculation unit are used again, and The input data is decoded by adding or subtracting a plurality of values obtained as a result of the second-dimensional product-sum operation by the product-sum operation unit and then performing parallel / serial conversion.

Preferably, in the inverse DCT operation device according to the first to third preferred embodiments of the present invention, when the product-sum operation unit is initialized to perform cumulative addition relating to the first-dimensional matrix operation. Then, the least significant bit in the decimal part of the parallel format coefficient value is rounded. More preferably, in the first and second preferred embodiments of the present invention, the one-dimensional product summation unit calculates the coefficient value of the parallel format output from the serial / parallel conversion unit in the lowest order. A bit holding unit that temporarily holds the bits while shifting them one bit at a time from the bit to the most significant bit, and a cumulative adding unit that performs cumulative addition using the plurality of addition / subtraction units. Performing the cumulative addition using the information already stored in the value storage unit in the cumulative addition unit and the addition / subtraction unit, using one bit of the parallel format coefficient value stored in the bit storage unit as an address. I am trying to do it.

Further, preferably, in the third preferred embodiment of the present invention, the one-dimensional product sum-of-products calculating unit calculates the coefficient value in the parallel format output from the serial / parallel converting unit in the least significant bit. And a first bit holding unit that temporarily holds the data while shifting one bit at a time from the first bit to the most significant bit, and performs cumulative addition related to a first-dimensional matrix operation using the plurality of first addition / subtraction units. And a first accumulative adder, wherein the first accumulative adder includes the first accumulator.
The information already stored in the first value storage unit in the first cumulative addition unit and the first addition / subtraction unit are set using, as an address, one bit of the coefficient value in the parallel format held in the bit holding unit. And the cumulative addition according to the first-dimensional matrix operation is performed, and the two-dimensional product-sum operation unit calculates the plurality of values in the parallel format sent from each of the two transposed units, The second method of temporarily storing data while shifting one bit at a time from the least significant bit to the most significant bit
And a second accumulative addition unit that performs accumulative addition relating to a two-dimensional matrix operation using the plurality of second addition / subtraction units. The second accumulative addition unit includes the second accumulative addition unit. The information already stored in the second value storage unit in the second accumulative addition unit is used as the address of one bit of the plurality of values in the parallel format held in the second bit holding unit. The addition and subtraction unit is used to execute the cumulative addition related to the above-described second-dimensional matrix operation.

Further, preferably, in the second and third preferred embodiments of the present invention, the two coefficient value rearranging sections are configured to alternately rearrange a plurality of coefficient values of the input data. The first coefficient value sorting RAM of
And the second coefficient value rearranging RAM, and before the first coefficient value rearranging RAM reads out the result of rearranging the coefficient values of one block, executes the second coefficient value rearranging. In the numerical rearrangement RAM, the writing operation of the coefficient value of another block transmitted next is executed, and the same reading operation and writing operation are performed on the coefficient value of the block transmitted thereafter. Has become.

Further, preferably, in the second and third preferred embodiments of the present invention, the two transposed units include a plurality of values obtained as a result of a first-order product-sum operation of the coefficient values. On the other hand, the first transposition RAM is configured by a first transposition RAM and a second transposition RAM for performing transposition alternately, and before the read operation of the result obtained by transposing the value of one block in the first transposition RAM is performed. In the second
The write operation of the value of the block transmitted next is executed in the transposition RAM, and the same read operation and write operation are performed on the value of the block transmitted thereafter.

On the other hand, the inverse DCT operation method of the present invention decomposes the inverse DCT operation on any encoded input data into at least two one-dimensional matrix operations, In order to sequentially execute the matrix operation of the above and perform decoding of the input data, the coefficient values transmitted in the serial format after rearranging the plurality of coefficient values of the input data are converted into the coefficient values in the parallel format. Using a plurality of addition and subtraction units that perform addition and subtraction of information stored in advance, using the value converted and converted into the parallel format as an address,
A product-sum operation is performed by performing cumulative addition using the information stored in advance and the plurality of addition / subtraction units, and the plurality of addition / subtraction units are used again. The input data is decoded by performing parallel / serial conversion after adding or subtracting values.

Next, when performing the product-sum operation, which is the premise of the inverse DCT operation device and the inverse DCT operation method of the present invention, the multiplication operation is performed without using a multiplier, and is already stored in a value storage unit such as a memory. The theoretical background of the inverse DCT operation of the DA method that obtains the result of the product-sum operation by performing the cumulative addition using the added information and the addition / subtraction unit including the adder and the subtractor will be described below.

For example, an inverse DCT operation on input data of a two-dimensional 8 × 8 matrix is performed by an operation of (8 × 8 matrix) * (1 × 8 matrix) (ie,
1st dimension matrix operation) ↓ Transpose of 1st dimension matrix operation result ↓ (8 × 8 matrix) * (1 × 8 matrix) operation (ie, 2
Dimensional matrix operation) ↓ Two operations of (8 × 8 matrix) * (1 × 8 matrix) like transposition of 2D matrix operation result (that is, two one-dimensional matrix operations) In general, the method is performed by disassembling this.

The above (8 × 8 matrix) * (1 × 8 matrix) k
The product-sum operation in the line is represented as in the following equation (1).

[0025]

(Equation 1) In this equation (1), x (component x _{m, n} ) is input data, C (component C _km ) is a one-dimensional 8 × 8 inverse DCT transformation matrix, and y is output data.

Here, a method of executing the above product-sum operation without using a multiplier will be described below. In this case, if x is expressed in N-bit binary notation, it becomes as shown in the following equation (2).

[0027]

(Equation 2) By substituting equation (2) into equation (1), equation (3) described in the following [Equation 3] is obtained.

[0028]

(Equation 3) That is, it is represented as the following equation (4) in [Equation 4].

[0029]

(Equation 4) Here, R (component R _k ) is n of each component of input data x.
It can be constituted by a memory in which the value of the second bit (8 bits in total) is used as an address.

When the matrix operation used in the above equation (1) is represented by components, it is as shown in the following equation (5).

[0031]

(Equation 5) If the matrix operation of the equation (5) is to be executed as it is, 2 ⁸ = 256 are required as the number of words of R _k . Also, since k takes a range of 0 to 7, a total of 2048
Word is needed.

Here, when the symmetry of the transformation matrix C is used, the product-sum operation is decomposed as shown in the following equations (6) and (7), respectively. can do. First, the following equations (6) and (7)
Are performed.

[0033]

(Equation 6)

[0034]

(Equation 7) Next, as shown in Expression (8) described in the following [Equation 8], s (components s _{0 to} s ₃ ) and t (components t ₀ to
Output data y (component y ₀ ~y ₇₎ is obtained by performing addition and subtraction of two components of t _3).

[0035]

(Equation 8) When the above-described operation is performed, the number of words of R _k needs to be 2 ⁴ = 16. On the other hand, since k ranges from 0 to 7, a total of 64 words are required. That is, by decomposing the matrix operation as described above, the number of words required for the matrix operation can be reduced to 1/16 of the number of words when the matrix operation of the above-described equation (5) is directly executed. .

In the configuration of the conventional inverse DCT arithmetic unit, a plurality of accumulative adders execute the operations of Expressions (6) and (7) and then execute the operation of Expression (8). Adders and subtractors were provided. On the other hand, in the inverse DCT operation device (and the inverse DCT operation method) of the present invention,
As described with reference to the principle diagram of FIG. 1, by executing the operation of Expression (8) again using the addition / subtraction units in the plurality of accumulative addition units, a plurality of conventionally-added adders and subtractors can be realized. It becomes unnecessary.

Thus, according to the inverse DCT operation apparatus and the inverse DCT operation method of the present invention, unnecessary circuits such as a plurality of adders and subtractors for post-processing of the product-sum operation are not required. At least two-dimensional inverse DCT operation can be performed with a large-scale circuit and with a small number of clock cycles. Furthermore, according to the inverse DCT operation device according to the first preferred embodiment of the present invention, post-processing of the product-sum operation is performed by using the addition / subtraction units in the plurality of accumulating units again, and the first and second dimensions are added. One coefficient value rearrangement RA is performed for the product-sum operation unit that performs the product-sum operation of the 8 × 8 matrix or the like.
Since M and one transposed RAM are provided,
While satisfying the two-dimensional inverse DCT operation accuracy specified by IEEE, it is possible to perform efficient pipeline processing with a smaller circuit and a smaller number of clock cycles than before.

Further, according to the inverse DCT operation device according to the second preferred embodiment of the present invention, post-processing of the product-sum operation is performed by using the addition / subtraction units in the plurality of accumulation addition units again, and the first dimension Since two coefficient value rearranging RAMs and two transposed RAMs are provided for a product-sum operation unit that performs a product-sum operation of an 8 × 8 matrix or the like in the second dimension, two-dimensional data defined by IEEE While achieving the inverse DCT calculation accuracy of the first embodiment, it is possible to perform very efficient pipeline processing with a smaller circuit than before and with a smaller number of clock cycles than in the first embodiment.

Further, according to the inverse DCT operation device according to the third preferred embodiment of the present invention, post-processing of the product-sum operation is performed again by using the addition / subtraction units in the plurality of accumulation addition units again, and the first dimension And two transposition RAMs and two coefficient value rearranging RAMs are provided for two product-sum operation units for separately performing the product-sum operation of an 8 × 8 matrix or the like of the second dimension. While satisfying the two-dimensional inverse DCT operation accuracy defined by
Very efficient pipeline processing can be performed with a smaller number of clock cycles than in the case of the second embodiment.

[0040]

BRIEF DESCRIPTION OF THE DRAWINGS FIG.
The configuration of the preferred embodiment of the present invention will be described with reference to FIG. FIG. 2 is a block diagram showing a specific configuration of the product-sum operation unit applied to the inverse DCT operation device of the present invention. Hereinafter, the same components as those described above will be denoted by the same reference numerals.

In FIG. 2, a product-sum operation unit 1 (see FIG. 1) applied to the inverse DCT operation device of the present invention temporarily stores a parallel-type coefficient value output from a serial / parallel conversion unit 4. Bit holding unit for holding (see FIG. 1)
Shift registers (in FIG. 2, the first shift register to the sixteenth shift register 20-1)
20 to 16-16) and 16 cumulative adders (in FIG. 2, the first cumulative adder to the sixteenth cumulative adder 30-
1 to 30-16). further,
These accumulative adders use, as an address, one bit of the value held in the 16 shift registers, information already stored in a value storage unit (see FIG. 18 described later) in the accumulative adder, Cumulative addition is performed using a plurality of adder / subtractors (see FIG. 18 described later) including adders and subtracters in the accumulator.

The product-sum operation unit, the serial / parallel conversion unit 4 and the parallel / serial conversion unit 5 configured as described above.
Thus, the product-sum operation circuit 10 is configured. More specifically, the first to sixteenth shift registers 20 will be described.
After receiving the coefficient value sent from the serial / parallel conversion unit 4, -1 to 20-16 shift the bit from the least significant bit to the most significant bit one bit at a time. 16 accumulative adders 30-1 to 30-
16 is supplied with the coefficient value.

In these first to sixteenth cumulative addition sections,
The first to component s ₀ ~s ₃ or component t ₀ ~t ₃ of the above formula in the value output from the sixteenth shift register (8)
Is used as an address, and a value already stored in the value storage unit in the accumulative addition unit is referred to. Further, the accumulative addition section accumulates and adds the reference values referred from the value storage section every time the values of the first to sixteenth shift registers are shifted by one bit. When performing such cumulative addition, the accumulated value (ie, 1
The value obtained by shifting the result before the cycle (the result of the addition before the cycle) to the right by one bit (that is, a value obtained by multiplying by）) and the reference value are added.
The above-described cumulative addition corresponds to the calculation of the above-described equation (6) or (7).

When all the values output from the first to sixteenth shift registers 1-16 have been shifted, the first to sixteenth
, The accumulated values can be added or subtracted again by using the adder and the subtracter in the accumulating adder of, and the results of 16 types of product-sum operations can be obtained at the same time. Such addition or subtraction corresponds to the calculation of the above-described equation (8). Finally, the parallel / serial converter 5 converts the 16 values corresponding to the results of the 16 types of product-sum operations sent from the first to sixteenth accumulators into serial values. Then, the data is sequentially output as decoded output data.

With the above configuration, by performing parallel processing such as pipeline processing of input data in the 16 accumulators, the number of clock cycles can be reduced as compared with the conventional one while satisfying the operation accuracy specified by IEEE. Can perform one-dimensional and two-dimensional 8 × 8 matrix inverse DCT operations, and the circuit size can be reduced by using the adder and the subtracter in the accumulator again.

FIG. 3 is a block diagram showing the configuration of the first embodiment of the present invention. Inverse DC according to the first embodiment of FIG.
In the T arithmetic unit, the 8 × in the first and second dimensions
A product-sum operation circuit 10 having a configuration as shown in FIG. 2 is provided to sequentially execute matrix operations of eight matrices and obtain results of 16 types of product-sum operations. This product-sum operation circuit 10
As described above, 16 shift registers for temporarily holding coefficient values in parallel format related to input data;
There are 16 accumulative adders that execute accumulative addition using values output from these shift registers and values already stored.

Further, in the first embodiment, a coefficient value rearranging RAM (random access memory) constituting a coefficient value rearranging section for rearranging a plurality of coefficient values of input data is provided.
y: an abbreviation for random access memory) 6 and a transposition RAM 8 that constitutes a transposition unit that transposes a plurality of values obtained as a result of the product-sum operation of the coefficient values (that is, an operation of exchanging rows and columns). Have been.

In the coefficient value rearranging RAM 6, in order to enable the product-sum operation circuit 10 to execute the first-dimensional product-sum operation, the serial-valued coefficient value of the input data is written, and then the coefficient value is output. The order is rearranged, and a plurality of values obtained as a result of the rearrangement are read. On the other hand, in the transposition RAM 8, 8
In order to make it possible to execute the second-dimensional multiply-accumulate operation of the × 8 matrix, a plurality of values obtained as a result of the first-dimensional multiply-add operation by the multiply-accumulate operation circuit 10 are written. The transposition is performed, and a plurality of values obtained as a result of the transposition are read.

Further, in the first embodiment shown in FIG. 3, a multiplexer (MPX) 7 is provided between the coefficient value rearranging RAM 6 and the product-sum operation circuit 10. The multiplexer 7 is used to execute one of the first-dimensional product-sum operation and the second-dimensional product-sum operation in the product-sum operation circuit 10, and the serial-format data transmitted from the coefficient value rearranging RAM 6 is used. A product-sum operation circuit 10 selects one of a plurality of values converted into a plurality of values in a parallel format or a plurality of values sent in a parallel format from the transposition RAM 8.
It has a function to input to

In the inverse DCT operation device having such a configuration, after performing the second dimension product-sum operation in the product-sum operation circuit 10, a plurality of addition / subtraction units in the 16 accumulative addition units are used again. By performing parallel / serial conversion after adding or subtracting a plurality of values obtained as a result of the product-sum operation in the second dimension, decoded output data is obtained.

More specifically, when performing the inverse DCT operation of the 8 × 8 matrix of the input data in the first embodiment, first, the coefficient value rearranging RAM of FIG.
The processing of converting the coefficient values sent in the serial format from No. 6 into the coefficient values in the parallel format is performed. Such serial / parallel conversion processing is performed by the serial / parallel conversion unit 4 in FIG. 1 (“coefficient loading” described later).

Second, the coefficient values in the parallel format output from the serial / parallel converter 4 are loaded into the 16 shift registers 20-1 to 20-16 in FIG. These shift registers 20-1 to 20-16 shift the 16-bit accumulators 30-1 to 30-3 in FIG. 2 while shifting one bit at a time from the least significant bit to the most significant bit.
The above coefficient value is supplied to 0-16.

In these 16 accumulators, four of the values output from the 16 shift registers (4
With reference to the value already stored in the value storage unit in the accumulative addition unit, using the bit) as an address, a reference value is obtained. Further, the 16 accumulative adders accumulate and add the reference values that are referred to each time the values of the 16 shift registers are shifted one bit at a time. When performing such cumulative addition, a value obtained by shifting the accumulated value to the right by one bit and a reference value are added. When all the values output from the 16 shift registers have been shifted, the adder / subtracter such as an adder or a subtractor in the 16 accumulators is used again to add or subtract the accumulated values. , And 16 types of results of the first-dimension product-sum operation can be obtained simultaneously (“cumulative addition” described later).

Third, a plurality of values obtained as a result of the product-sum operation in the first dimension are input to the transposition RAM 8, and a transposition operation for exchanging rows and columns is performed. The data is again input to the 16 shift registers in the sum operation circuit 10. The product-sum operation circuit 10 performs a two-dimensional product-sum operation using the values already stored in the value storage units in the 16 accumulators and the values output from the 16 shift registers. . Further, the adder and the subtractor in the 16 accumulators are used again to add or subtract a plurality of values obtained as a result of the product-sum operation in the second dimension, and then perform parallel / serial conversion. Thus, decrypted serial-format output data is obtained (“result output” described later).

In the first embodiment, by performing parallel processing on a plurality of coefficient values, a relatively small number of clock cycles can be achieved while satisfying the inverse DCT operation accuracy of a two-dimensional 8 × 8 matrix defined by IEEE. This makes it possible to execute efficient and efficient pipeline processing. Further, in the first embodiment, the adder and the subtractor in the accumulator are used when performing the post-processing of the product-sum operation in the second dimension. This eliminates the need for a unit and reduces the circuit scale.

Further, in the first embodiment, when the accumulative addition unit in the product-sum operation circuit is initialized to perform the accumulative addition related to the matrix operation of the first dimension, the coefficient value of the parallel format is initialized. The least significant bit in the decimal part is rounded (rounded). In this way, 2
Since the number of bits of the coefficient value can be reduced at the time of cumulative addition of the dimension, the inverse DCT defined by IEEE
The pipeline processing can be executed with a minimum number of clock cycles while satisfying the operation accuracy.

FIG. 4 is a block diagram showing the configuration of the second embodiment of the present invention. Inverse DC according to the second embodiment of FIG.
Also in the T-operation device, as in the case of the above-described first embodiment, matrix operations of the first and second 8 × 8 matrices are sequentially performed to obtain 16 types of product-sum results. For this purpose, a product-sum operation circuit 10 having the configuration shown in FIG. 2 is provided.

Further, in the second embodiment, two coefficient value rearranging RAMs (in FIG. 4, the first coefficient RAM) for alternately rearranging a plurality of blocks constituting a plurality of coefficient values are described. Numerical data rearranging RAM 61 and second coefficient value rearranging RAM 62) and two transposing RAMs (in FIG. 4, in FIG. 4) for alternately transposing blocks of a plurality of values obtained as a result of the product-sum operation. First transpose R
AM 81 and a second transposed RAM 82).

Further, in the second embodiment shown in FIG. 4, a multiplexer 71 is provided between the two coefficient value rearranging RAMs and the product-sum operation circuit 10. This multiplexer 7
Reference numeral 1 denotes a serial format sent from the two coefficient value rearranging RAMs in order to execute either the first-dimensional product-sum operation or the second-dimensional product-sum operation in the product-sum operation circuit 10. A function of selecting either one of a plurality of values converted into a plurality of values in a parallel format or a plurality of values transmitted in a parallel format from two transposition RAMs and inputting the selected value to the product-sum operation circuit 10. Have.

In the inverse DCT operation device having such a configuration, after performing the second dimension product-sum operation in the product-sum operation circuit 10, a plurality of addition / subtraction units in the 16 accumulative addition units are used again. By performing parallel / serial conversion after adding or subtracting a plurality of values obtained as a result of the product-sum operation in the second dimension, decoded output data is obtained.

The first and second coefficient value rearrangement R
In the AMs 61 and 62, the first coefficient value rearranging RAM 61
In the second coefficient value rearranging RAM 62, before the read operation of the result of rearranging the coefficient values of one block is performed, the writing operation of the coefficient value of another block transmitted next is performed in the second coefficient value rearranging RAM 62. Be executed. Further, the same read operation and write operation are sequentially performed on the coefficient values of the blocks transmitted thereafter. In this case, the write operation of the other coefficient value rearranging RAM can be performed while the read operation of one coefficient value rearranging RAM is being performed.
The rearrangement of the coefficient values can be executed at a higher speed than in the case of the embodiment.

On the other hand, in the first and second transposition RAMs 81 and 82, before the read operation of the result of transposing the value of one block in the first transposition RAM 81 is executed, In the second transposition RAM 82, the operation of writing the value of the block transmitted next is executed. Further, the same read operation and write operation are sequentially performed on the values of the blocks transmitted thereafter. In this case, the write operation of the other transposed RAM can be performed while the read operation of one transposed RAM is being performed, so that the one-dimensional one-dimensional operation can be performed at a higher speed than in the case of the first embodiment. Transposition after the product-sum operation of the eyes can be performed.

In the second embodiment, the coefficient value rearranging RAM and the transposition RAM are each increased by one in comparison with the configuration of the first embodiment, but are smaller than those in the first embodiment. Very efficient pipeline processing can be executed with the number of clock cycles. FIG. 5 is a block diagram showing the configuration of the third embodiment of the present invention. here,
Serial / parallel converter for serial / parallel conversion of a plurality of coefficient values of input data (for example, see FIG. 2)
Are provided in the one-dimensional product sum arithmetic circuit 11 and
A parallel / serial converter (for example, see FIG. 2) that performs parallel / serial conversion of a plurality of values obtained as a result of the product-sum operation in the dimension is provided in the two-dimensional product-sum operation circuit 12.

In the inverse DCT operation device according to the third embodiment shown in FIG. 5, a first-dimension product-sum operation circuit 11 for executing a first-dimension 8 × 8 matrix product-sum operation and a second-dimension 8 A two-dimensional product-sum operation circuit 12 for executing a product-sum operation of a × 8 matrix is provided separately. However, the configuration of each of the one-dimensional product-sum operation unit 11 and the two-dimensional product-sum calculation circuit 12 is substantially the same as the configuration of the product-sum calculation circuit 10 of FIG.

More specifically, the one-dimensional product sum-of-arithmetic circuit 11 is a circuit for temporarily storing a coefficient value in a parallel format output from the serial / parallel converter.
Shift registers and 16 first accumulative adders. Further, each of these accumulators uses the value output from the serial / parallel converter as an address, the information already stored in the value memory in the accumulator, the adder in the accumulator, The first-order cumulative addition is performed using a plurality of addition / subtraction units including a subtraction unit.

On the other hand, the two-dimensional product sum operation circuit 12
Includes 16 shift registers for temporarily holding a plurality of values in the parallel format sent from each of the two transposition units 83 and 84, and 16 second accumulative addition units. I have. Further, each of these accumulative adders uses, as an address, a plurality of values in a parallel format transmitted from each of the two transposed units as information stored in a second value storage unit in the accumulative adder. And a plurality of second adding / subtracting units including an adding unit and a subtracting unit in the above-mentioned accumulating unit.

Further, in the third embodiment, two coefficient value rearranging RAMs (in FIG. 5, a first coefficient RAM) for alternately rearranging a plurality of blocks constituting a plurality of coefficient values. And two transpositions for alternately transposing a plurality of value blocks obtained as a result of the one-dimensional product-sum operation of the coefficient values. RAM (in FIG. 5, a first transposed RAM 83 and a second transposed RAM 84
) Are provided.

Further, in the third embodiment shown in FIG. 5, a first multiplexer 72 is provided between the two coefficient value rearranging RAMs and the one-dimensional product sum arithmetic circuit 11. The first multiplexer 72 includes two coefficient value rearrangements RA
It has a function of selecting a plurality of values in the parallel format sent from any one of the coefficient value rearranging RAMs of M and inputting them to the one-dimensional product sum arithmetic circuit 10.

On the other hand, in the third embodiment shown in FIG.
First transposed RAM 83 and second transposed RAM 84
, A second multiplexer 92 is provided. The second multiplexer 92 has a function of selecting a plurality of values in a parallel format sent from one of the two transposed RAMs and inputting the selected values to the two-dimensional product sum arithmetic circuit 12.

In the inverse DCT operation device having such a configuration, after performing the second-dimensional product-sum operation in the two-dimensional product-sum operation circuit 12, a plurality of addition / subtraction units in the 16 accumulative addition units are again operated. To add or subtract a plurality of values obtained as a result of the product-sum operation in the second dimension,
By performing serial conversion, decoded output data is obtained.

The first and second coefficient value rearrangement R
In the AM 63, 64, the first coefficient value rearranging RAM 63
Before the read operation of the result of the rearrangement of the coefficient values of one block is performed in the above, the operation of writing the coefficient values of another block transmitted next in the second coefficient value rearrangement RAM 64 is performed. Be executed. Further, the same read operation and write operation are sequentially performed on the coefficient values of the blocks transmitted thereafter. In this case, the first and second coefficient value rearranging RAM 6
Since a plurality of coefficient values of the input data can be continuously transmitted from the third and the 64th to the one-dimensional product-sum operation circuit 11, the coefficient values can be transmitted at a higher speed than in the second embodiment. Can be performed.

On the other hand, in the first and second transposition RAMs 83 and 84, before the read operation of the result of transposing the value of one block in the first transposition RAM 83 is executed, In the second transposition RAM 84, the operation of writing the value of the block transmitted next is executed. Further, the same read operation and write operation are sequentially performed on the values of the blocks transmitted thereafter. In this case, the first and second transposed RAMs 8
Since a plurality of values in the parallel format can be continuously transmitted from the third and the fourth to the two-dimensional product-sum operation circuit 12, the coefficient values can be calculated at a higher speed than in the case of the second embodiment. Sorting can be performed.

In the third embodiment, the coefficient value rearranging RAM, the transposition RAM, and the product-sum operation circuit are each increased by one as compared with the configuration of the first embodiment. Very efficient pipeline processing can be executed with a smaller number of clock cycles than in the example. With such a configuration, it is possible to realize the operation of calculating one coefficient value in one cycle.

FIGS. 6 and 7 are timing charts 1 and 2 for explaining the overall operation of the first embodiment of the present invention. However, here, a timing chart of pipeline processing for six blocks of input data composed of moving image data and the like when the inverse DCT operation device having the configuration shown in FIG. 3 is operated is illustrated. . In this case, one scale on the time axis indicates the length of time corresponding to 16 cycles.

These six blocks are composed of four luminance data Y0, Y1, Y2 and Y3 based on the MPEG standard.
And two pieces of color difference data Cb and Cr, and are usually called macroblocks. One block in this macro block has 8 × 8 = 64 values. 6 and 7
As shown in, the product-sum operation of multiple coefficient values of the input data is performed by "coefficient loading", "cumulative addition", and "result output".
And each of these stages is realized by parallel processing (ie, pipeline processing). Hereinafter, such parallel processing will be described.

“Coefficient loading” is a write operation of input data for six blocks (for example, Y0 write to Cr in FIG. 6).
Write and read operations (for example, Y0 read to Cr read in FIG. 6) are performed.
This is a process of rearranging the coefficient values of six blocks sent in serial form from the reference form (see FIG. 2) into coefficient values in parallel form. In this coefficient value rearranging process, the first and second dimension luminance data Y0 (1st) and Y0 (2n)
d), Y1 (1st), Y1 (2nd), Y2 (1s)
t), Y2 (2nd), Y3 (1st) and Y3 (2
nd), the first- and second-dimensional color difference data Cb
(1st), Cb (2nd), Cr (1st) and C
Processing for r (2nd) is sequentially executed. The coefficient value rearrangement processing as described above is executed in the serial / parallel conversion unit in FIG.

In the "cumulative addition", a parallel format coefficient value output from the serial / parallel conversion unit in FIG. 2 is loaded into 16 shift registers, and the least significant bit is shifted from the least significant bit to the most significant bit in these shift registers. This is a process of supplying a coefficient value to a plurality of cumulative addition units while shifting one bit at a time toward a bit. This accumulative addition process is executed by a plurality (for example, 16) of accumulative adders in FIG.
In these accumulators, four values (4 bits) in the 16 shift registers are used as addresses to refer to values already stored in the circuit and to obtain reference values. The accumulative addition unit accumulates and adds the values referred to each time the values of the 16 shift registers are shifted. In this cumulative addition, the value obtained by shifting the accumulated value (ie, the result of the addition one cycle before) to the right by one bit (ie, 1
/ 2 times) and the reference value. When all the values of the 16 shift registers have been shifted, a plurality of accumulative adders can be used again to add or subtract the accumulatively added values to simultaneously obtain the results of the 16 product-sum operations. .

The “result output” is obtained as a result of the product-sum operation in the parallel / serial converter of FIG.
Is a process of outputting the values in a serial format (see FIG. 5,
Output data for six blocks is output as Y0 output, Y1 output, Y
2 output, Y3 output, Cb output and Cr output). In the transposition RAM of FIG. 3, after performing transposition for exchanging rows and columns of 16 values obtained as a result of the first-dimensional product-sum operation, the 16 values after the transposition are used to calculate the product-sum operation circuit. Are input again to the 16 shift registers. In this product-sum operation circuit, a second-dimension product-sum operation is performed using the values already stored in the value storage units in the 16 accumulators and the values output from the 16 shift registers. Further, the adder and the subtractor in the 16 accumulators are used again to add or subtract a plurality of values obtained as a result of the product-sum operation in the second dimension, and then perform parallel / serial conversion. , The decoded serial output data is obtained.

By performing the parallel processing as described above,
Two-dimensional 8 with the arithmetic precision specified by IEEE
The inverse DCT operation of the × 8 matrix can be executed with a relatively small number of clock cycles (for example, the number of clock cycles for the inverse DCT operation of six blocks of data is 960), and the circuit scale is small. I'm done.

FIGS. 8 and 9 are timing charts 1 and 2 for explaining the overall operation of the second embodiment of the present invention. However, here, a timing chart of pipeline processing for six blocks of input data composed of moving image data and the like when the inverse DCT operation device having the configuration shown in FIG. 4 is operated is illustrated. . In this case, one scale on the time axis indicates the length of time corresponding to 16 cycles.

These six blocks are composed of four luminance data Y0, Y1,..., As in the case of the first embodiment.
Y2 and Y3 and two color difference data Cb and Cr. Further, in the second embodiment of FIGS. 8 and 9, as described in the first embodiment, the product-sum operation of a plurality of coefficient values of input data is performed by “coefficient loading” and “cumulative addition”. "And" result output ", and each of these stages is realized by parallel processing. Since these three stages have already been described in the first embodiment, a detailed description thereof will be omitted here.

In the second embodiment, unlike the first embodiment, two coefficient value rearranging RAMs (for example, the first and second coefficient value rearranging RAM 6 shown in FIG. 4) are used.
1, 62), and the two transposed RAMs (for example, the first and second transposed RAMs 81, 82 in FIG. 4) are used to rearrange the coefficient values of the input data. Transpose multiple values.

As is clear from the timing charts shown in FIGS. 8 and 9, in the second embodiment, four luminance data Y0 and Y1 transmitted in serial form by two coefficient value rearranging RAMs. , Y2 and Y3 and 2
The coefficient values are alternately rearranged for the two color difference data Cb and Cr. More specifically, the first coefficient value rearranging RAM executes writing (writing), coefficient value rearranging and reading (reading) of the luminance data Y0, Y2 and the chrominance data Cb, and executes the second processing. The numerical value rearranging RAM executes writing (writing), coefficient value rearranging and reading (reading) of the luminance data Y1, Y3 and the color difference data Cr.

In the timing charts of FIGS. 8 and 9, by operating two coefficient value rearranging RAMs simultaneously, one block of coefficient value rearranged RAMs is read from one coefficient value rearranging RAM. During this operation, the coefficient values for the next block can be written to the other coefficient value rearranging RAM. Therefore, in the second embodiment, the coefficient value rearrangement process can be executed at a higher speed than in the case of the first embodiment.

Further, in the timing charts of FIGS. 8 and 9, by operating two transposition RAMs at the same time, the data after transposition processing of the product-sum operation result of one block is read from one transposition RAM. While
The next block of data can be written to the other transposed RAM. Therefore, in the second embodiment, the transposition process of the product-sum operation result can be executed at a higher speed than in the case of the first embodiment.

In the above-described first embodiment, as shown in the timing charts of FIGS. 6 and 7, after the first-dimension product-sum operation is performed in the sum-of-products operation circuit, the second-dimension product is calculated. There is a period during which the plurality of accumulators do not operate until the sum operation is performed. On the other hand, in the second embodiment shown in FIG. 8 and FIG.
Following the operation of converting the serial-type coefficient value sent from M to a parallel-type coefficient value and supplying it to a plurality of accumulators, the serial-type coefficient value sent from the other coefficient value rearranging RAM is Since the operation of converting to the coefficient value in the parallel format and supplying it to the multiple accumulators is performed,
It becomes possible to operate a plurality of accumulative adders continuously.

As described above, two coefficient value rearrangements RA
By performing parallel processing of 6 blocks of data using M and two transposition RAMs, the two-dimensional 8 × 8 matrix inverse DCT operation with the operation accuracy defined by IEEE A smaller number of clock cycles than the case of the embodiment (for example, inverse DCT of 6 blocks of data)
The number of clock cycles for the operation is 640 cycles, 6
(The number of clock cycles until the output of the result of the product-sum operation for the blocks is completed is 864).

FIGS. 10 and 11 are timing charts 1 and 2 for explaining the overall operation of the third embodiment of the present invention. However, here, a timing chart of a pipeline process for six blocks of input data composed of moving image data and the like when the inverse DCT operation device having the configuration shown in FIG. 5 is operated is illustrated. . In this case, one scale on the time axis indicates the length of time corresponding to 16 cycles.

These six blocks are composed of four luminance data Y as in the first and second embodiments.
0, Y1, Y2 and Y3 and two color difference data Cb,
And Cr. Further, in the third embodiment of FIGS. 10 and 11, as described in the first embodiment, the product-sum operation of a plurality of coefficient values of the input data is performed by “coefficient loading” and “cumulative addition”. "And" result output ", and each of these stages is realized by parallel processing. Since these three stages have already been described in the first embodiment, a detailed description thereof will be omitted here.

In the third embodiment, two coefficient value rearranging RAMs are used in the same manner as in the second embodiment.
(For example, the first and second coefficient value rearrangement RA in FIG. 5)
M63, 64), the coefficient values of the input data are rearranged, and two transposed RAMs (for example, the first RAM of FIG.
And the second transposition RAMs 83 and 84) are used to transpose a plurality of values after the product-sum operation. However, the third
In this embodiment, unlike the second embodiment described above, 1
A one-dimensional product-sum operation circuit for performing the product-sum operation for six blocks in the dimension and a two-dimensional product-sum operation circuit 12 for performing the product-sum operation for six blocks in the second dimension are separately provided. ing.

As is apparent from the timing charts shown in FIGS. 10 and 11, also in the third embodiment, four luminance data Y0, The coefficient values are rearranged alternately for Y1, Y2, and Y3 and the two color difference data Cb and Cr. More specifically, the first coefficient value rearranging RAM stores the luminance data Y
Write (write), coefficient value rearrangement, and readout (read) of 0, Y2, and color difference data Cb are performed, and the second coefficient value rearrangement RAM stores the luminance data Y1,
Write (write), coefficient value rearrangement, and read (read) of Y3 and color difference data Cr are executed.

In the timing charts of FIGS. 10 and 11, by operating two coefficient value rearranging RAMs simultaneously, the coefficient values of one block after the rearrangement processing for one block are read out from one coefficient value rearranging RAM. During this operation, the coefficient values for the next block can be written to the other coefficient value rearranging RAM. Further, the coefficient values read from the two coefficient value rearranging RAMs are loaded into 16 shift registers in the one-dimensional product-sum operation circuit that executes only the first-dimensional product-sum operation. I have.
Therefore, in the first-dimension product-sum operation circuit, the first dimension 6
Data for blocks Y0 (1st), Y1 (1st),
The coefficient values of Y2 (1st), Y3 (1st), Cb (1st), and Cr (1st) are loaded successively.
Therefore, in the third embodiment, the coefficient value rearrangement processing can be executed at a higher speed than in the case of the second embodiment.

On the other hand, in the timing charts of FIGS. 10 and 11, by operating two transposition RAMs at the same time, one block of transposition data is read from one transposition RAM while the data after transposition processing is being read. , The next block of data can be written to the other transposed RAM. Further, the transposed data read from the two transposition RAMs is loaded into 16 shift registers in a two-dimensional product-sum operation circuit that executes only the second-dimensional product-sum operation. I have. Therefore, in the one-dimensional product-sum operation circuit, the data Y for six blocks in the second dimension is calculated.
0 (2nd), Y1 (2nd), Y2 (2nd), Y3
The values of (2nd), Cb (2nd), and Cr (2nd) are loaded sequentially. Therefore, in the third embodiment, 1 is faster than in the case of the second embodiment.
Transposition processing of the product-sum operation result of the dimension can be executed.

As described above, two coefficient value rearrangements RA
M, by using two transposition RAMs and two multiply-accumulation circuits, to perform parallel processing of 6 blocks of data, thereby obtaining the inverse of a two-dimensional 8 × 8 matrix with the operation accuracy specified by IEEE. The DCT operation is performed by reducing the number of clock cycles (for example, the number of clock cycles for the inverse DCT operation of six blocks of data to 384 cycles, and the output of the product-sum operation of six blocks). (The number of clock cycles until the completion of the operation is 576 cycles).

In the third embodiment, FIG. 10 and FIG.
As is clear from reference to the "result output" of No. 1, serial data can be continuously converted by executing a very efficient pipeline processing with a smaller number of clock cycles than in the second embodiment. , The calculation of one coefficient value can be realized in one cycle.

Next, the product-sum operation according to the inverse DCT operation of the present invention will be described in detail by separating the product-sum operation in the first dimension and the product-sum operation in the second dimension. FIG. 12 and FIG.
3 is a first and a second part of a timing chart for explaining a first-dimension product-sum operation processing procedure in the first embodiment of the present invention, and FIG. 14 is a timing chart in the first embodiment of the present invention. 9 is a timing chart showing the movement of bits in the first-dimensional product-sum operation processing. Here, a timing chart showing operations of “coefficient loading”, “cumulative addition” and “result output” in the first-dimensional product-sum operation performed based on the clock, and data in the first-dimensional product-sum operation process A timing chart showing the movement of each bit of FIG.

In FIG. 12 and FIG. 13, "coefficient loading" means that the coefficient values of a plurality of coefficients (for example, coefficient 1 to coefficient 15 consisting of 16 coefficients) input to the serial / parallel conversion unit in serial form. , And rearrange them into coefficient values in a parallel format. As is clear from FIGS. 12 and 13,
16 clocks are required for this coefficient loading process.
When the coefficient loading process is completed, coefficient values for two columns or two rows of an 8 × 8 matrix (for one block) are loaded into 16 shift registers using one clock. At the same time, the 16 accumulators are initialized.

The values of the sixteen shift registers are used in the process of "cumulative addition". In the 16 accumulators,
Of the values output from the 16 shift registers, s ₀ to
s as ₃ or t ₀ ~t ₃ address 4 bits corresponding to the (aforementioned formula (8)), and refers to the value from the value storing section in the accumulative adder. 20 obtained from these value storage units
The value of the bit and the value of the register in the accumulator (21 bits) shifted to the right by one bit (here, the sign bit is sign-extended to represent the sign bit in two's complement representation). The result of the addition is fed back to the register and stored. As shown in FIG. 14, the above-described cumulative addition process is performed a number of times corresponding to the number of bits of the 16 shift registers (here, bits 0 to 0).
(12 bits of bit 11) are repeated. However, since the last bit (the 12th bit) is a sign bit, subtraction is performed. That is, the above-described processing of the cumulative addition corresponds to the calculation of the above-described equation (5) or (6). The value storage unit stores a previously calculated 20-bit value for 16 words (1 word = 16 bits).

As shown in the portion s + t or st in FIG. 14, when the above-described process of accumulating 12 bits is completed, the results of the accumulating portions output from the 16 accumulating portions are compared with each other. The addition or subtraction is performed again using the adder or the subtractor included in the accumulative addition unit, and the first-dimension product-sum operation is completed. Such addition or subtraction corresponds to the operation of Expression (7) described above. Furthermore, 14 bits (an integer part 11 bits and a decimal part 3 bits), which are valid bits of the result of the first dimension product-sum operation, are cut out and sent to the parallel / serial conversion unit. However, when rounding down the least significant bit, it is necessary to round down (operation of adding 1 to the fourth bit of the decimal part: that is, rounding off). In the first to third embodiments of the present invention, among the 16 accumulative adder, s ₀ ~s of formula (7)
When initializing the accumulative adder corresponding to the operation of ₃ , only the bit corresponding to the fourth bit of the decimal part is initialized to “1”, and the other bits are initialized to “0”. Rounding.

Further, in FIG. 12 and FIG.
The "result output" process is performed by sequentially outputting the 16-bit 14-bit cumulative operation results obtained in parallel in a serial format. Thus, 16 cycles are converted into one 1
As a unit, efficient pipeline processing is performed by executing parallel processing for the three stages of “coefficient loading”, “cumulative addition”, and “result output” as described above. It can be clearly understood that the above-described parallel processing is executed by the movement of each bit shown in FIG. The values of coefficient 1 to coefficient 16 thus obtained are stored in the transposed RAM.

FIGS. 15 and 16 are timing charts 1 and 2 for explaining the procedure of the second-dimension product-sum operation in the first embodiment of the present invention.
FIG. 17 is a timing chart showing the movement of the bits in the second-dimensional product-sum operation in the first embodiment of the present invention. Here, a timing chart showing operations of “coefficient loading”, “cumulative addition”, and “result output” in a second-dimensional product-sum operation performed based on a clock,
A timing chart showing the movement of each bit of the data in the second-dimensional product-sum operation is shown.

The second-dimension product-sum operation processing procedure will be described with reference to the timing charts of FIGS.
The transposition RAM performs an operation of transposing rows and columns of the result of the first-dimensional product-sum operation (ie, transpose), and inputs the value obtained by the transpose to the product-sum operation circuit again. In FIG. 15 and FIG. 16, “load coefficient” means that the coefficient values of a plurality of coefficients (for example, coefficient 1 to coefficient 16 composed of 16 coefficients) input to the product-sum operation circuit in a serial form are converted into parallel form. Sort by coefficient value. As is clear from FIGS. 15 and 16, the processing of this coefficient loading requires 16 clocks. When the coefficient loading process is completed, coefficient values for two columns or two rows of an 8 × 8 matrix (for one block) are loaded into 16 shift registers using one clock. The value stored in the transpose RAM is 14
Since the bits are bits, the 16 shift registers are loaded with 14-bit values.

The values of the sixteen shift registers are used for "accumulative addition" processing. In the 16 accumulators,
Of the values output from the 16 shift registers, s ₀ to
s as ₃ or t ₀ ~t ₃ address 4 bits corresponding to the (aforementioned formula (8)), and refers to the value from the value storing section in the accumulative adder. 20 obtained from these value storage units
The value of the bit and the value obtained by shifting the value of the register (21 bits) in the accumulator by one bit to the right (again, sign-extending the most significant bit to represent the sign bit in two's complement representation) The result of the addition is fed back to the register and stored. As shown in FIG. 17, the above-described cumulative addition process is performed by the number of times corresponding to the number of bits of the 16 shift registers (here, bits 0 to 0).
(14 bits of bit 13) are repeated. However, since the last bit (14th bit) is a sign bit, subtraction is performed. That is, the above-described processing of the cumulative addition corresponds to the calculation of the above-described equation (5) or (6). The value storage unit stores a previously calculated 20-bit value for 16 words.

As shown in the portion s + t or st in FIG. 17, when the above-described process of accumulating 14 bits is completed, the results of the accumulating portions output from the 16 accumulating portions are compared with each other. The adder or the subtractor included in the accumulator is used again to add or subtract, and the second-dimensional product-sum operation is completed. Such addition or subtraction corresponds to the operation of Expression (7) described above. Finally, using one clock, the result of the product-sum operation as shown in FIG. 15, FIG. 16 and FIG. 17 is rounded and overflow / underflow processing is performed to obtain the final result of the second-dimensional product-sum operation. Get a 9-bit value. The calculation result of the second dimension may be output due to the latter stage of the inverse DCT calculation device. However, it is necessary to output so as not to disturb the above pipeline processing.

As described above, in the configuration of the first embodiment of the present invention (FIG. 3), one macroblock (for six blocks)
Can be performed in 960 cycles while satisfying the operation accuracy defined by IEEE. Further, in the configuration of the second embodiment of the present invention (FIG. 4), the use of two coefficient value rearranging RAMs and two transposition RAMs allows the two-dimensional 8 × 8 matrix of one macroblock to be obtained. The inverse DCT operation can be performed in 640 cycles while satisfying the operation accuracy defined by IEEE.

Further, in the configuration of the third embodiment of the present invention (FIG. 5), two coefficient value rearranging RAMs, two transposed RAMs, and two product-sum operation units are used. Thus, the inverse DC of a two-dimensional 8 × 8 matrix of one macroblock
The T operation can be performed in 384 cycles while satisfying the operation accuracy defined by IEEE. This is 1
This means that one coefficient value can be processed by the clock.

FIG. 18 shows one example used in the embodiment of the present invention.
It is a block diagram which shows the specific structure of the accumulation | adding part of a dimension. As shown in FIG. 18, in a cumulative addition unit used for the first-dimension product-sum operation, the value of a parallel-format coefficient output from the serial / parallel conversion unit (for example, 4
Bit) is provided in advance. Further, on the output side of the value storage unit 31-1, an addition / subtraction unit 33-1 including a plurality of adders and subtractors, and a register 34-1 for holding the addition result or the subtraction result by the addition / subtraction unit 33-1 are provided. Right shift sign extension unit 3 for shifting the value of register 34-1 to the right to sign extend.
2-1 are provided.

In FIG. 18, the addition / subtraction unit 33-1 stores the 20-bit value obtained from the value storage unit 31-1 and the value of the register 34-1 (for example, a 21-bit value) by the right shift code extension unit 32-1. ) Shifted to the right by one bit (here, the sign bit is sign-extended in order to represent the sign bit in two's complement representation). further,
The addition result by the addition / subtraction unit 33-1 is stored in the register 34-1.
And is stored as output data for performing the second-dimensional product-sum operation.

FIG. 19 is a block diagram showing a second embodiment used in the embodiment of the present invention.
It is a block diagram which shows the specific structure of the accumulation | adding part of a dimension. As shown in FIG. 19, in the accumulative addition unit used for the first-dimension product-sum operation, a value storage unit 31-2 that previously stores a parallel-format value (for example, 4 bits) sent from the transposition RAM. Is provided. Further, on the output side of the value storage unit 31-2, an addition / subtraction unit 33-2 including a plurality of adders and subtractors, a register 34-2 for holding the addition result or the subtraction result by the addition / subtraction unit 33-2, ,
There is provided a right shift code extension section 32-2 for shifting the value of the register 34-2 to the right and performing sign extension.

In FIG. 19, the addition / subtraction unit 33-2 stores the 18-bit value obtained from the value storage unit 31-2 and the value of the register 34-2 (for example, the 19-bit value) by the right shift code extension unit 32-2. ) Shifted to the right by one bit (here, the sign bit is sign-extended in order to represent the sign bit in two's complement representation). further,
The addition result by the addition / subtraction unit 33-2 is stored in the register 34-2.
And is stored as output data after the inverse DCT operation processing.

[0111]

As described above, the inverse DCT of the present invention is used.
According to the arithmetic device, firstly, addition or subtraction for post-processing of the product-sum operation is performed by using the addition and subtraction units in the plurality of accumulation addition units again. Circuit can be saved, and the inverse DCT operation can be performed with a smaller number of clock cycles than before.

Further, according to the inverse DCT operation device of the present invention, secondly, post-processing of the product-sum operation is performed again by using the addition / subtraction units in the plurality of accumulative addition units, and the first and second dimensions are added.
Since one coefficient value rearranging RAM, one transposition RAM, and the like are provided for the product-sum operation unit that performs the product-sum operation of the dimension, a two-dimensional inverse DC defined by IEEE is provided.
It is possible to perform efficient pipeline processing with a smaller circuit and a smaller number of clock cycles than before, while satisfying the T operation accuracy.

Thirdly, according to the inverse DCT operation device of the present invention, post-processing of the product-sum operation is performed again by using the addition / subtraction units in the plurality of accumulative addition units again.
Since two coefficient value rearranging RAMs, two transposition RAMs, and the like are provided for the product-sum operation unit that performs the product-sum operation in the dimension, the two-dimensional inverse DCT operation accuracy specified by IEEE is satisfied. It is possible to perform highly efficient pipeline processing with a smaller circuit than before and with a smaller number of clock cycles than in the above case.

Fourth, according to the inverse DCT operation device of the present invention, fourthly, the coefficient values in the parallel format output from the serial / parallel conversion unit are shifted one bit at a time.
Since the parallel format coefficient values are temporarily held by a plurality of shift registers, parallel processing can be efficiently executed with a small number of clock cycles.

Fifth, according to the inverse DCT operation device of the present invention, when the accumulator and the like are initialized to perform the first-dimensional product-sum operation, the decimal part of the coefficient value in the parallel format is used. , The least-significant bit is rounded, so that in the second-dimension product-sum operation, parallel processing is efficiently executed with a small number of clock cycles while satisfying the operation accuracy defined by IEEE. It becomes possible.

Further, according to the inverse DCT arithmetic unit of the present invention, sixth, when two coefficient value rearranging RAMs are used to perform rearrangement on a plurality of coefficient values alternately, one coefficient value rearrangement is performed. Before reading the result of rearranging the coefficient values of one block in the RAM, the writing operation of the coefficient value of another block transmitted next is executed in the other coefficient value rearranging RAM. Thus, the coefficient value rearranging process can be executed at a relatively high speed.

Further, according to the inverse DCT operation apparatus of the present invention, seventhly, when two transposition RAMs are used to transpose a plurality of values obtained as a result of the product-sum operation of the first dimension alternately. Before the read operation of the result of performing the transposition of the value of one block in one transposed RAM is performed, the write operation of the value of the next transmitted block is performed in the other transposed RAM. Because
The transposition process can be performed at a relatively high speed.

Eighth, according to the inverse DCT operation apparatus of the present invention, post-processing of the product-sum operation is performed again by using the addition / subtraction units in the plurality of accumulators again,
Two coefficient value rearranging RAMs and two transposition RAs are provided for two product-sum operation units that separately perform the product-sum operation of the dimension.
Since the M and the like are provided, it is possible to satisfy the two-dimensional inverse DCT operation accuracy defined by IEEE, and to use a circuit smaller than the conventional one and with a smaller number of clock cycles than in the second embodiment. It is possible to perform efficient pipeline processing.

Ninth, according to the inverse DCT operation method of the present invention, ninth, addition or subtraction for post-processing of the product-sum operation is performed by using the addition / subtraction units in the plurality of accumulators again. The inverse DCT operation can be performed with a smaller circuit and a smaller number of clock cycles than in the conventional case.

[Brief description of the drawings]

FIG. 1 is a block diagram showing the principle configuration of the present invention.

FIG. 2 is a block diagram showing a specific configuration of a product-sum operation unit applied to the inverse DCT operation device of the present invention.

FIG. 3 is a block diagram showing a configuration of a first exemplary embodiment of the present invention.

FIG. 4 is a block diagram showing a configuration of a second exemplary embodiment of the present invention.

FIG. 5 is a block diagram showing a configuration of a third exemplary embodiment of the present invention.

FIG. 6 is a timing chart (part 1) for explaining the overall operation of the first embodiment of the present invention.

FIG. 7 is a timing chart (2) for explaining the overall operation of the first embodiment of the present invention.

FIG. 8 is a timing chart (part 1) for explaining the overall operation of the second embodiment of the present invention.

FIG. 9 is a timing chart (2) for explaining the overall operation of the second embodiment of the present invention.

FIG. 10 is a timing chart (part 1) for explaining the overall operation of the third embodiment of the present invention.

FIG. 11 is a timing chart (2) for explaining the overall operation of the third embodiment of the present invention.

FIG. 12 is a timing chart (part 1) for explaining a first-dimension product-sum operation processing procedure in the first embodiment of the present invention.

FIG. 13 is a timing chart (part 2) for explaining the first dimension product-sum operation processing procedure in the first embodiment of the present invention.

FIG. 14 is a timing chart showing the movement of bits in the first-dimensional product-sum operation in the first embodiment of the present invention.

FIG. 15 is a timing chart (part 1) for describing a second-dimensional product-sum operation processing procedure in the first embodiment of the present invention.

FIG. 16 is a timing chart (part 2) for describing a second-dimensional product-sum operation processing procedure in the first embodiment of the present invention.

FIG. 17 is a timing chart showing bit movements in a second-dimensional product-sum operation in the first embodiment of the present invention.

FIG. 18 is a block diagram showing a specific configuration of a first-dimensional accumulative addition unit used in the embodiment of the present invention.

FIG. 19 is a block diagram showing a specific configuration of a second-dimensional accumulator used in the embodiment of the present invention.

FIG. 20 is a block diagram illustrating a configuration example of a conventional inverse DCT operation device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Product-sum operation part 2-1-2-n ... 1st-nth data holding part 3-1-3-n ... 1st-nth accumulation | addition part 4 ... Serial / parallel conversion part 5 ... Parallel / Serial conversion unit 6 Coefficient value rearranging RAM 7 Multiplexer (MPX) 8 Transpose RAM 10 Product sum operation circuit 11 One-dimensional product sum operation circuit 12 Two-dimensional product sum operation circuit 20-1 to 20-20 -16 ... first to sixteenth shift registers 30-1 to 30-16 ... first to sixteenth accumulators 61 ... first coefficient value rearranging RAM 62 ... second coefficient value rearranging RAM 63 ... First coefficient value rearranging RAM 64 Second coefficient value rearranging RAM 71 Multiplexer 72 First multiplexer 81 First transposed RAM 82 Second transposed RAM 83 First transposed RAM 84 2nd transposition RAM 92 ... Multiplexer 200 ... data rearrangement circuit 300 ... product-sum operation unit 350-1～350-8 ... product-sum operation circuit 400 ... post-processing unit of the first to eighth

 ────────────────────────────────────────────────── ─── Continuation of front page (72) Inventor Tadami Kono 4-1-1, Kamidadanaka, Nakahara-ku, Kawasaki-shi, Kanagawa F-term within Fujitsu Limited (Reference) 5B056 AA05 AA06 BB11 BB31 CC01 DD06 FF02 FF03 FF05 FF08 FF16 HH03

Claims (10)

[Claims] 1. An inverse DCT operation on arbitrary encoded input data is decomposed into at least two one-dimensional matrix operations, and a predetermined number of one-dimensional matrix operations are sequentially executed to obtain the input data. An inverse DCT arithmetic unit for decoding a plurality of input data, wherein a plurality of coefficient values of the input data are rearranged, and a coefficient value transmitted in a serial format is converted into a coefficient value in a parallel format. And a product-sum operation unit having a plurality of addition / subtraction units for performing addition / subtraction of information already stored, using a value output from the serial / parallel conversion unit as an address. The addition / subtraction unit is used again, and a plurality of values obtained as a result of the product-sum operation by the product-sum operation unit are added or subtracted from each other, and then the parallel / serial conversion is performed. An inverse DCT operation device for decoding input data. 2. Decomposing an inverse DCT operation on arbitrary encoded input data into two one-dimensional matrix operations,
An inverse DCT operation apparatus for sequentially executing a predetermined number of matrix operations of a second dimension and a second dimension to decode the input data, wherein a coefficient value arrangement for rearranging a plurality of coefficient values of the input data Conversion unit; a serial / parallel conversion unit for converting a coefficient value sent from the coefficient value rearrangement unit in a serial format into a parallel format coefficient value; and addressing a value output from the serial / parallel conversion unit. A product-sum operation unit having a plurality of addition / subtraction units for performing addition / subtraction of information already stored; and a transpose for transposing a plurality of values obtained as a result of the first-dimensional product-sum operation by the product-sum operation unit A plurality of values in a parallel format sent from the transposition unit are input to the product-sum operation unit, and a second-dimensional product-sum operation of the plurality of values is performed. The plurality Use the addition and subtraction part again,
An inverse DCT operation device, wherein the input data is decoded by performing parallel / serial conversion after adding or subtracting a plurality of values obtained as a result of the second-dimensional product-sum operation. 3. Decomposing an inverse DCT operation on arbitrary encoded input data into two one-dimensional matrix operations,
In an inverse DCT operation device for sequentially executing a predetermined number of matrix operations of a second dimension and a second dimension to decode the input data, two inverses for rearranging a plurality of coefficient values of the input data are provided. A coefficient value rearranging section; a serial / parallel converting section for converting coefficient values sent in serial form from each of the two coefficient value rearranging sections to a parallel format coefficient value; A product-sum operation unit having a plurality of addition / subtraction units for performing addition / subtraction of information already stored, using a value output from the unit as an address, and a result of a first-dimension product-sum operation performed by the product-sum operation unit Two transposition units for transposing a plurality of values, wherein a plurality of values in a parallel format sent from each of the two transposition units are input to the multiply-accumulation unit and two of the plurality of values are input. The product-sum operation of the dimension And row, again using the plurality of addition and subtraction portions in the product-sum operation unit,
An inverse DCT operation device, wherein the input data is decoded by performing parallel / serial conversion after adding or subtracting a plurality of values obtained as a result of the second-dimensional product-sum operation. 4. Decomposing an inverse DCT operation on arbitrary encoded input data into two one-dimensional matrix operations,
In an inverse DCT operation device for sequentially executing a predetermined number of matrix operations of a second dimension and a second dimension to decode the input data, two inverses for rearranging a plurality of coefficient values of the input data are provided. A coefficient value rearranging section; a serial / parallel converting section for converting coefficient values sent in serial form from each of the two coefficient value rearranging sections to a parallel format coefficient value; A one-dimensional sum-of-products operation unit having a plurality of first addition / subtraction units for performing addition / subtraction of information already stored, using a value output from the unit as an address; And two transposition units for transposing a plurality of values obtained as a result of the product-sum operation of the two, and a plurality of values in a parallel format sent from each of the two transposition units are already stored as addresses. Of information A two-dimensional product sum operation unit having a plurality of second addition / subtraction units for performing subtraction, wherein the plurality of second addition / subtraction units in the two-dimensional product sum operation unit are used again, and the two-dimensional product sum is used. The input data is decoded by adding or subtracting a plurality of values obtained as a result of the second-dimensional product-sum operation by the sum operation unit, and then performing parallel / serial conversion, thereby decoding the input data.
CT calculation device. 5. The product-sum operation unit further shifts the coefficient value in the parallel format output from the serial / parallel conversion unit by one bit from a least significant bit to a most significant bit. A bit holding unit for temporarily holding, and a cumulative adding unit for performing cumulative addition using the plurality of adding / subtracting units, wherein the cumulative adding unit stores the coefficient values in the parallel format held in the bit holding unit. With 1 bit of the address as
4. The inverse DCT operation device according to claim 1, wherein the cumulative addition is performed using information already stored in a value storage unit in the cumulative addition unit and the addition / subtraction unit. 6. The one-dimensional multiply-accumulate unit further calculates a coefficient value of the parallel format output from the serial / parallel converter one bit at a time from a least significant bit to a most significant bit. A first bit holding unit that temporarily holds while shifting, and a first cumulative addition unit that performs cumulative addition related to a first-dimensional matrix operation using the plurality of first addition / subtraction units, The first accumulator has already stored in the first value memory in the first accumulator an address using one bit of the coefficient value in the parallel format held in the first bit memory as an address. Performing the cumulative addition relating to the first-dimensional matrix operation using the information and the first addition / subtraction unit, wherein the two-dimensional product-sum operation unit further comprises: Multiple values in the parallel format sent from A second bit holding unit that temporarily holds the bit by shifting one bit from the least significant bit toward the most significant bit, and a second-dimensional matrix operation using the plurality of second addition / subtraction units. A second accumulator that performs accumulative addition, wherein the second accumulator has, as an address, one bit of the plurality of values in the parallel format held in the second bit holding unit. The cumulative addition according to the second-dimensional matrix operation is performed using information already stored in a second value storage unit in the second cumulative addition unit and the second addition / subtraction unit. Inverse DCT operation device. 7. A rounding process of a least significant bit in a decimal part of a coefficient value in the parallel format when the product-sum operation unit is initialized to perform cumulative addition relating to a first-dimensional matrix operation. The inverse DCT operation device according to claim 1. 8. A first coefficient value rearranging RAM, and a second coefficient value rearranging unit, wherein the two coefficient value rearranging units perform rearrangement alternately for a plurality of coefficient values of the input data. Before the read operation of the result of rearranging the coefficient values of one block in the first coefficient value rearranging RAM is executed, the second coefficient value rearranging RAM performs the following. 5. The inverse operation according to claim 3, wherein a write operation of a coefficient value of another block sent to the block is executed, and a similar read operation and write operation are executed for a coefficient value of a block sent thereafter. DCT arithmetic unit. 9. A first transposition RAM, wherein said two transposition units alternately transpose a plurality of values obtained as a result of a product-sum operation of a first dimension of said coefficient values, and a second transposition RAM. Before the read operation of the result obtained by transposing the value of one block in the first transposed RAM is performed, the block of the next transmitted block in the second transposed RAM is constructed. 4. A value writing operation is performed, and a similar reading operation and writing operation are performed on a value of a block transmitted thereafter.
Or the inverse DCT arithmetic unit according to 4. 10. Decomposing an inverse DCT operation on arbitrary encoded input data into at least two one-dimensional matrix operations, and sequentially executing a predetermined number of one-dimensional matrix operations to obtain the input data. An inverse DCT operation method for decoding the input data, wherein a coefficient value transmitted in a serial format after rearranging a plurality of coefficient values of the input data is converted into a coefficient value in a parallel format. Using a plurality of addition / subtraction units that perform addition / subtraction of information stored in advance using the value converted into the parallel format as an address, and performing cumulative addition using the information stored in advance and the plurality of addition / subtraction units. By executing the product-sum operation by using the plurality of addition / subtraction units again, and adding or subtracting a plurality of values obtained as a result of the product-sum operation, and then performing parallel / serial conversion, An inverse DCT operation method, wherein the input data is decoded.