JPH04307662A - Discrete cosine converter and adverse discrete cosine converter - Google Patents

Abstract

PURPOSE:To reduce overall arithmetic value and to decrease the number of computing elements by performing the addition/subtraction of input data. CONSTITUTION:The data inputted through an input terminal 100 are supplied to an adder/subtractor 102 every two pieces set in a pair. Four product sum computing elements 110, 111, 112 and 113 are connected to the output of the adder/subtractor 102. Then, each product sum computing element performs a product sum operation between the input data and the data stored in a memory 120. Furthermore, the product sum computing element are connected in series with two accumulators 150 and 160 and carries out alternately two types of product sum operations. These operational results are successively outputted through a selector 190.

Description

[Detailed description of the invention]

0001

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a discrete cosine transform device and an inverse discrete cosine transform device.

0002

[Prior Art] In general, Nth-order discrete cosine transform (hereinafter referred to as DCT) and inverse discrete cosine transform (hereinafter referred to as IDC)
The DCT device and IDCT device that execute the
This is a device that multiplies a ×N DCT or IDCT transformation matrix by an N-order input data vector. For example, if N is 8 as shown in FIG. 4, an input data vector consisting of 8 data is input. At the input terminal 400, eight product-sum calculators 4 with the same configuration perform product-sum calculations of input data and eight DCT or IDCT transform coefficients in the row direction of the transformation matrix.
10, 411, 412, . The product-sum calculator 410 is
Input data input from the input terminal 418 of the product-sum calculator and DCT or ID read from the coefficient memory 420
The CT conversion coefficient is multiplied by a multiplier 430, the output data of the multiplier 430 is added to the output data of the register 450 by an adder 460, and the cumulative result is stored in the register 450. When the sum-of-products operation is completed, the sum-of-products operation data in the register 450 is stored in the register 470. When the product-sum operation is completed, register 45
The product-sum calculation data of 0 is stored in the register 470.

0003

[Problems to be Solved by the Invention] In the conventional method, N×N multiplication operations are performed to convert N pieces of input data, and (
Since it is necessary to perform addition operations N-1)×N times, there is a drawback that the amount of calculations is large and the scale of the calculation circuit becomes large.

An object of the present invention is to reduce the amount of computation and reduce the circuit scale while maintaining the functions of DCT and IDCT.
Our objective is to provide CT devices and IDCT devices.

[0005]

[Means for Solving the Problems] A discrete cosine transform device of the present invention is a discrete cosine transform device in which a plurality of product-sum calculation units are arranged to perform parallel calculations, and N (N is the number of powers of 2). A data combiner that generates a series of N/2 sets of combined data, each consisting of two pieces of input data, and simultaneously outputs the two pieces of data; An adder/subtracter that performs addition/subtraction, N/2 product-sum calculators (described below) that take the output data of the adders/subtractors as input data, and first and second product-sum calculators that output two each from the N/2 product-sum calculators. a selector that sequentially selects the product-sum calculation data of N/2 product-sum calculation units, and a multiplier for multiplying the input data by the output data of a coefficient memory in which the N/2 product-sum calculation units store predetermined multiplication coefficients; an adder that adds output data of the multiplier and output data of a first register described later; a second register that stores output data of the adder;
the first register storing output data of the first register;
and third and fourth registers for storing output data of the registers, and the output data of the third and fourth registers is configured to be the output data of the product-sum calculator.

Further, the inverse discrete cosine transform device of the present invention is an inverse discrete cosine transform device in which a plurality of product-accumulators are arranged to perform parallel operations. N/2 product-sum calculation units described below that take input data as input data; and a first selector that sequentially selects first product-sum calculation data output from the N/2 product-sum calculation units. ,
a second selector that sequentially selects second product-sum calculation data output from the N/2 product-sum calculation units; and addition/subtraction using the output data of the first and second selectors as input data. and a multiplier for multiplying the input data by the output data of a coefficient memory in which the product-sum calculation unit stores a predetermined multiplication coefficient, and the output data of the multiplier and the output data of the first register described below. a second register that stores output data of the adder; a first register that stores the second output data; and a second register that stores the output data of the first register. 3 and a fourth register, and the output data of the third and fourth registers is used as the output data of the product-sum calculator.

Furthermore, the discrete cosine transform and inverse discrete cosine transform apparatus of the present invention is a discrete cosine transform and inverse discrete cosine transform apparatus in which a plurality of product-accumulators are arranged to perform parallel operations. a data combiner that generates a series of N/2 sets of combination data in which two pieces of input data (the number of powers of ) are made into one set, and outputs the two pieces of data at the same time; a first adder/subtracter that adds and subtracts two data;
a first selector that selects either the output data of the adder/subtractor and the input data, and N/2 post-described product-sum calculators whose input data is the output data of the first selector;
a second selector that sequentially selects first and second output data of the N/2 product-sum calculators; and a first product-sum calculator output from the N/2 product-sum calculators. a third selector that sequentially selects data; a fourth selector that sequentially selects second product-sum calculation data output from the N/2 product-sum calculation units; a second adder/subtractor that receives the output data of the selector as input data; and a fifth selector that selects either the output data of the second selector or the output data of the second adder/subtractor. and the product-sum calculator includes a multiplier that multiplies input data by output data of a coefficient memory storing a predetermined multiplication coefficient, and adds the output data of the multiplier and the output data of the first register described below. a second register that stores output data of the adder;
the first register storing the second output data;
It has a third and fourth register that stores the output data of the first register, and has a configuration in which the output data of the third and fourth registers is used as the output data of the product-sum calculator.

[0008]

[Operation] N (N is a power of 2) The next DCT converts input data and output data, respectively.

[0009]

0010

[0011]

For each element of the DCT coefficient matrix C,

001
3]

There is a relationship as follows, and by using this relationship, the formula (
2) can be transformed into equation (8) when N is 8.

[0015]

Furthermore, equation (8) can be expanded into two determinants as shown in equations (9) and (10).

[0017]

From equations (9) and (10), the DCT operation is N
By adding and subtracting in advance two pieces of input data at symmetrical positions of an input data vector consisting of pieces of data, the number of times of multiplication with the DCT coefficient can be reduced to one-half compared to Equation (2).

From the above, the DCT device of the first invention can combine N pieces of input data into a data set when the order is N.

[0020]

A data combiner that converts into

[0022]

N/2 product-sum calculators which input the equation (9) and equation (10) alternately and output two calculation results; and a selector for sequentially selecting pieces of data and rearranging the output data of the product-sum calculator. As a result, the number of operations and the number of arithmetic circuits can be reduced by half compared to the conventional method.

[0024] N-order IDCT uses input data and output data respectively.

[0025]

When equation (11) is written in matrix form, it becomes equation (12).

[0027]

Here, y is an N×1 input data vector, x is an N×1 output data vector, and D is an N×N ID.
In the CT coefficient matrix,

[0029]

[0030] For each element of the IDCT coefficient matrix D,

[0031]

There is a relationship as follows, and by using this relationship, the formula (
12) can be transformed into equations (15) and (16) when N is 8.

[0033]

Furthermore, equation (15) is transformed into equations (17) and (18
) can be expanded into two determinants.

[0035]

From formulas (16), (17), and (18), I
DCT operation divides an input data series consisting of N data into even and odd numbers and performs a product-sum operation with DCT coefficients,
This can be realized by adding and subtracting product-sum calculation data, and the number of multiplications can be reduced to one-half compared to equation (12).

From the above, the IDCT device of the second invention has the following features:
For order N, N input data

[0038]

N/2 product-sum calculators that take as input, perform the calculations of equations (17) and (18) alternately, and output two calculation results, and the data output from the product-sum calculators.

004
0]

A data selector that is combined as shown below, and 1
It can be configured by an adder/subtracter that adds and subtracts two sets of data. As a result, the number of calculations and the calculation circuit can be reduced by half compared to the conventional method.

Further, the DCT and IDCT combined device of the third invention is the DCT device of the first invention and the IDC device of the second invention.
This is a combination of T devices, with a common product-sum calculator, and a selector added to the data input and output parts of the product-sum calculator to switch the data flow, realizing DCT and IDCT calculations. It has been made possible.

[0043]

Embodiments Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of the first invention. In FIG. 1, the DCT calculation device executes the DCT calculation by setting N to 8 and connecting four product-sum calculation units. Input data

[0045]

is input to the input terminal 100. The input data is combined into two sets by the data combiner 101,

[
0047

They are output in the following order. Output data from the data combiner 101 is input to an adder/subtracter 102. Adder/subtractor 102 performs addition and subtraction on one piece of input data. Addition/subtraction data output from adder/subtractor 102

[0049]

[0050] are product-sum calculators 110, 111, 112, 1
13. Product-sum calculators 110, 111, 112
, 113, the coefficient memories 120, . . .
CT coefficient

[0051]

[0052] is stored. Product-sum calculator 110,1
11, 112, and 113 are equation (9) and equation (10), respectively.
of

[0053]

In order to obtain the following, a sum-of-products operation is performed on the DCT coefficients and the input data. Product-sum calculators 110, 111, 11
2,113 has a configuration in which registers 150 and 160 used as accumulators are connected in series and can perform two product-sum operations alternately, and a register for storing the results of the two product-sum operations. Two registers 170 and 180 are connected in parallel to the output terminal of register 160. Each of the registers 170, 180, ... has DCT calculation data.

[0055]

[0056] is stored. registers 170, 180,
The DCT calculation data stored in... are sequentially selected by the selector 190,

[0057]

The signals are outputted from the output terminal 200 in the following order.

FIG. 2 is a block diagram showing an embodiment of the second invention. In FIG. 2, the IDCT calculation device executes the IDCT calculation by setting N to 8 and connecting four product-sum calculation units. Input data

[0060]

is input to the input terminal 100. Input data is input to four product-sum calculators 110 and 111 connected in parallel.
, 112, 113. Product-sum calculator 110,1
Coefficient memories 120, .

[0062]

[0063] is stored.

Product-sum calculators 110, 111, 112, 11
3 are the equations (17) and (18), respectively.

[0065]

In order to obtain the following, a sum-of-products operation is performed on the IDCT coefficients and the input data. Product-sum calculators 110, 111, 1
12 and 113 have a configuration in which registers 150 and 160 used as accumulators are connected in series so that two product-sum operations can be executed alternately, and registers 150 and 160 used as accumulators are used to store the results of the two product-sum operations. Two registers 170 and 180 are connected in parallel to the output terminal of register 160. Each of the registers 170, 180... has product-sum operation data.

[0067]

[0068] is stored. The product-sum operation data stored in the registers 270, . . . are selected by the selector 210.

006
9]

The product-sum operation data stored in the registers 180, . . . are selected by the selector 211 in the order of

[0071]

Selectors 210 and 211
The output data is input to the adder/subtractor 212, and the added/subtracted data

[0073]

##EQU1## is output from the output terminal 200.

FIG. 3 is a block diagram showing an embodiment of the third invention. In FIG. 3, when N is 8, the DCT/IDCT arithmetic device executes a DCT arithmetic operation or an IDCT arithmetic operation by combining FIG. 1 and FIG.

When executing the DCT operation, the selector 10
3 and 213 select the output data of the adder/subtractor 101 and the selector 190, respectively, and when performing IDCT operation,
Selectors 103 and 213 select output data from input terminal 100 and adder/subtractor 212, respectively.

[0077]

[Effects of the Invention] The discrete cosine transform device of the first invention has the following features:
By connecting a data combiner, adder/subtractor, and selector to a product-sum calculator connected in parallel, and connecting two accumulators of the product-sum calculator in series, the overall amount of calculation and calculation circuit can be reduced by about half. 1, and the calculation time can be shortened.

Further, the inverse discrete cosine transform device of the second invention includes a data combiner, a data combiner, and a product-sum calculator connected in parallel.
By connecting the adder/subtractor and selector and connecting two accumulators of the product-sum calculator in series, the overall amount of calculations and calculation circuits can be reduced to about half, and the calculation time can be shortened. .

Furthermore, in the discrete cosine transform device and inverse discrete cosine transform device of the third invention, a data combiner, an adder/subtractor, and a selector are connected to the product-sum calculator connected in parallel, and the accumulator of the product-sum calculator is connected in parallel. By connecting two devices in series, a DCT device and an IDCT device can be constructed that can reduce the total calculation amount and calculation circuit to about half, and the calculation time can be shortened.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of a (DCT calculation device) of a first invention.

FIG. 2 is a block diagram showing an embodiment of the (IDCT calculation device) of the second invention.

FIG. 3 is a block diagram showing an embodiment of the (DCT/IDCT calculation device) of the third invention.

FIG. 4 is a block diagram showing a conventional example.

[Explanation of symbols]

100,400 Input terminal 101 Data combiner 102,212 Adder/subtractor 110-113, 410-417 Product-sum calculator 120,420 Coefficient memory 130,430 Multiplier 140,460 Adder 150-180,450,470 Register 19
0,210,211,213,480 Selector 2
00,481 Output terminal

Claims (3)

[Claims] Claim 1: A discrete cosine transform device in which a plurality of product-sum calculation units are arranged to perform parallel calculations, in which N (N is a power of 2) input data are made into a set of two.
/A data combiner that generates two sets of combined data series and outputs the two data at the same time, an adder/subtractor that adds and subtracts the two data output from the data combiner, and inputs the output data of the adder/subtractor. N/ as data
It has two product-sum calculation units described below, and a selector that sequentially selects the first and second product-sum calculation data output two by two from the N/2 product-sum calculation units, and the A multiplier in which an N/2 product-sum calculator multiplies input data by the output data of a coefficient memory storing a predetermined multiplication coefficient, and an addition in which the output data of the multiplier is added to the output data of the first register described later. a second register storing output data of the adder;
the first register storing the second output data;
The method further includes third and fourth registers that store output data of the first register, and has a configuration in which the output data of the third and fourth registers is output data of the product-sum calculator. Characteristic discrete cosine transform device. 2. In an inverse discrete cosine transform device in which a plurality of product-sum calculation units are arranged to perform parallel calculations, N(N
is a power of 2) input data as input data, and N/2 product-sum calculation units described below, and first product-sum calculation data output from the N/2 product-sum calculation units. a first selector that sequentially selects the second product-sum calculation data outputted from the N/2 product-sum calculation units; a multiplier having an adder/subtracter that takes output data of the selector as input data, and in which the product-sum calculator multiplies the input data and output data of a coefficient memory storing a predetermined multiplication coefficient; Output data and postscript 1
an adder that adds output data of the registers, a second register that stores the output data of the adder, the first register that stores the second output data, and an output of the first register. The inverse discrete cosine transform has a configuration in which it has third and fourth registers for storing data, and output data of the third and fourth registers is output data of the product-sum calculator. Device. 3. In a discrete cosine transform or inverse discrete cosine transform device in which a plurality of product-accumulators are arranged to perform parallel operations, N (N is a power of 2) input data can be converted into two pieces of input data. a data combiner that generates a series of N/2 sets of combined data to be made into one set and outputs two pieces of data at the same time; a first adder/subtractor that adds and subtracts the two pieces of data output from the data combiner; , a first selector that selects either the output data of the first adder/subtractor or the input data, and N/2 post-described product sums whose input data is the output data of the first selector. a second selector that sequentially selects the first and second output data of the N/2 product-sum calculators; and a second selector that sequentially selects the first and second output data of the N/2 product-sum calculators; a third selector that sequentially selects product-sum calculation data; and a second selector that sequentially selects the product-sum calculation data of N/2 product-sum calculation units;
a fourth selector that sequentially selects product-sum operation data; a second adder/subtractor that receives output data of the third and fourth selectors as input data; and an output data of the second selector. a fifth selector that selects either one of the output data of the second adder/subtractor, and the product-sum calculator multiplies the input data and the output data of a coefficient memory storing a predetermined multiplication coefficient. a multiplier, the output data of the multiplier, and the first
an adder that adds output data of the registers, a second register that stores the output data of the adder, the first register that stores the second output data, and an output of the first register. A discrete cosine transform device comprising third and fourth registers for storing data, and configured to use output data of the third and fourth registers as output data of the product-sum calculator. and an inverse discrete cosine transform device.