US 5,276,784 AGrant
2-D Discrete Cosine Transform Circuit With Reduced Number of Multipliers
Issue Date:1994-01-04
•8 Claims
•8 Drawing Sheets
Abstract
An image data processing apparatus includes a <v> calculating block 7 for calculating a vector <v> from a vector <x> which has 64 elements in a real space and which has been generated as a sequence of image data in 8 rows and 8 columns in the real space, a <w> calculating block 8 for calculating a vector <w> from the vector <x> in the real space, and a <c> calculating block 9 for adding and subtracting elements of the vector <v> and elements of the vector <w>, thereby producing a vector <c> which has 64 elements in a space of spatial frequencies. The elements of the vector <c> in the space of spatial frequencies are arranged into data in 8 rows and 8 columns in the space of spatial frequencies.
Metadata
Assignee
- Sony Corporation
Inventor
- Mitsuharu Ohki
Application Information
Application Number:US 8086583
Filing Date:1991-12-17
Priority Date:1990-12-28
Art Unit:231
Classifications
IPC:
G06F 1562
Field of Search:
395382364140-143;121;129-132;133;162-164;12741-44;56703;709.09;725
Patent Drawings (8 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to an image data processing apparatus for processing image data for a two-dimensional discrete cosine transform (DCT) or inverse discrete cosine transform (IDCT).
2. Description of the Prior Art:
Compressing image data for transmission often employs the discrete cosine transform (hereinafter referred to as "DCT") of two-dimensional image data arrayed in 8 rows and 8 columns, and decoding compressed image data into original image data often employs the inverse discrete cosine transform (hereinafter referred to as "IDCT") of two-dimensional image data arrayed in 8 rows and 8 columns. If it is assumed that a matrix of 8.times.8 image data in a real space with elements xi, j is indicated by X, a matrix of 8.times.8 data in a space of spatial frequencies with elements ci, j is indicated by C, and a transform matrix of 8 rows and 8 columns for a DCT is indicated by N, then the following equations (1) are satisfied for DCT, IDCT:
The matrices N, X, C are defined as follows: ##STR1##
In the above equations (2), a=cos(.pi./16), .alpha.=cos(2.pi./16), b=cos(3.pi./16), c=cos(5.pi./16), .beta.=cos(6.pi./16), d=cos(7.pi./16), and the matrix N.sup.t is a matrix transposed from the matrix N. The DCT is a linear transform from the matrix X to the matrix C, and the IDCT is a linear transform from the matrix C to the matrix X.
One conventional two-dimensional DCT processing circuit with a serial input and a serial output, and one conventional two-dimensional IDCT processing circuit with a serial input and a serial output will be described below with reference to FIGS. 1 and 2, respectively, of the accompanying drawings. The multiplication by 1/4 of coefficients contained in the definition of DCT and IDCT will not be described below as it can easily be carried out by shifting 2 bits.
FIG. 1 shows a conventional two-dimensional DCT processing circuit. The two-dimensional DCT processing circuit includes a first 8.times.8 matrix processing circuit 1 to which there are serially supplied the elements xi, j of a matrix X in a real space. The first 8.times.8 matrix processing circuit 1 then multiplies the matrix X by a matrix N, producing a matrix NX, and serially supplies the 64 elements of the matrix NX to a rearranging circuit 2. The rearranging circuit 2 rearranges the inputted 64 elements of the matrix NX in a predetermined order, and supplies the rearranged 64 elements to a second 8.times.8 matrix processing circuit 3. The second 8.times.8 matrix processing circuit 3 multiplies the supplied matrix NX by a matrix N.sup.t, producing a matrix (NX)N.sup.t, and serially outputs the 64 elements ci, j of the matrix (NX)N.sup.t to a following processing circuit (not shown).
FIG. 2 shows a conventional two-dimensional IDCT processing circuit. The two-dimensional IDCT processing circuit includes a third 8.times.8 matrix processing circuit 4 to which there are serially supplied the elements ci, j of a matrix C in a space of spatial frequencies. The third 8.times.8 matrix processing circuit 4 then multiplies the matrix C by a matrix N.sup.t, producing a matrix N.sup.t C, and serially supplies the 64 elements of the matrix N.sup.t C through a rearranging circuit 5 to a fourth 8.times.8 matrix processing circuit 6. The fourth 8.times.8 matrix processing circuit 6 multiplies the supplied matrix N.sup.t C by the matrix N, producing a matrix (N.sup.t C)N, and serially outputs the 64 elements xi, j of the matrix (N.sup.t C)N.
Generally, a matrix processing circuit for processing serially inputted 8.times.8 matrices and serially outputting the produced matrix requires 8 multipliers. Therefore, each of the conventional two-dimensional DCT and IDCT processing circuits requires 16 (=2.times.8) multipliers. According to a generalization of this requirement, a two-dimensional N.times.N matrix (N is an integer of 2 or more) DCT or IDCT processing circuit requires 2N multipliers. Since the circuit scale of a multiplier is considerably larger than the circuit scale of an adder or a subtractor and also since the overall circuit scale of a processing circuit composed of multipliers is determined substantially depending on the number of the multipliers used, the conventional DCT and IDCT processing circuits have been relatively large in overall circuit scale.
Calculations carried out by multipliers are subject to a round-off error or a truncation error because numbers that are handled are of a limited number of digits. The conventional DCT processing circuit tends to produce a large error due to accumulated round-off errors because a total of two multiplications are effected by the first and second processing circuits 1, 2. The same problem occurs with the conventional IDCT processing circuit.
Japanese Laid-Open Patent Publication No. 62-61159 discloses a technique for reducing the number of multipliers by way of matrix resolution in DCT and IDCT processing apparatus for processing matrices with 8 one-dimensional elements. However, no proposal has been made for reducing the number of multipliers in two-dimensional processing apparatus.
Objects and Summary of the Invention
In view of the drawbacks of the conventional image data processing apparatus, it is an object of the present invention to provide an image data processing apparatus which allows two-dimensional DCT and IDCT calculations to be effected with a reduced number of multipliers.
According to the present invention, there is provided, as shown in FIG. 3 of the accompanying drawings, a first image data processing apparatus for performing a discrete cosine transform to determine data in N rows and N columns (N is an integer of 2 or greater) in a space of spatial frequencies from image data in N rows and N columns in a real space, the image data processing apparatus comprising a first vector calculating circuit for calculating a first vector from a vector which has N.sup.2 elements in a real space and which has been generated as a sequence of the image data in N rows and N columns in the real space, a second vector calculating circuit for calculating a second vector from the vector in the real space, an adder-subtractor for adding and subtracting elements of the first vector and elements of the second vector, thereby producing a vector which has N.sup.2 elements in a space of spatial frequencies, and means for arranging elements of the vector in the space of spatial frequencies into data in N rows and N columns in the space of spatial frequencies.
According to the present invention, there is also provided, as shown in FIG. 8 of the accompanying drawings, a second image data processing apparatus for performing an inverse discrete cosine transform to determine image data in N rows and N columns (N is an integer of 2 or greater) in a real space from data in N rows and N columns in a space of spatial frequencies, the image data processing apparatus comprising a first vector calculating circuit for adding and subtracting elements of a vector which has N.sup.2 elements in a space of spatial frequencies and which has been generated as a sequence of the data in N rows and N columns in the space of spatial frequencies, thereby producing elements of a first vector and elements of a second vector, a second vector calculating circuit for calculating a third vector from the first vector, a third vector calculating circuit for calculating a fourth vector from the second vector, an adder for adding elements of the third vector and elements of the fourth vector, thereby producing a vector which has N.sup.2 elements in a real space, and means for arranging elements of the vector in the real space into image data in N rows and N columns in the real space.
In the first image data processing apparatus, the multiplication of matrices in N rows and N columns for a discrete cosine transform (DCT) is replaced with the multiplication of a constant matrix in N.sup.2 rows and N.sup.2 columns and a vector having N.sup.2 elements. Based on the characteristics of DCTs, the constant matrix can be represented by the sum (see the equation (7), for example, below) of a first product of a matrix having all elements that are either 0 or .+-.1 and a matrix in which the number of elements other than 0 and .+-.1 in each row is smaller than N, and a second product of a matrix having all elements that are either 0 or .+-.1 and a matrix in which the number of elements other than 0 and .+-.1 in each row is smaller than N. The multiplication of the matrix in which the number of elements other than 0 and .+-.1 in each row is smaller than N and a vector can be carried out by multipliers the number of which is smaller than N. Consequently, the first vector calculating circuit (7) and the second vector calculating circuit (8) may be composed of less than 2N multipliers in total. Furthermore, since the multiplication of a matrix having all elements are 0 or .+-.1 and a vector can be carried out by an adder-subtractor, the final result of DCT calculations can be determined as a vector representation by the adder-subtractor (9).
In the second image data processing apparatus, the multiplication of matrices in N rows and N columns for an inverse discrete cosine transform (IDCT) is replaced with the multiplication of a constant matrix in N.sup.2 rows and N.sup.2 columns and a vector having N.sup.2 elements. Based on the characteristics of IDCTs, the constant matrix can be represented by the sum (see the equation (8), for example, below) of a first product of a matrix in which the number of elements other than 0 and .+-.1 in each row is smaller than N and a matrix having all elements that are either 0 or .+-.1, and a second product of a matrix in which the number of elements other than 0 and .+-.1 in each row is smaller than N and a matrix having all elements that are either 0 or .+-.1. Calculations for an IDCT are effected in a process that is an inverse of the process of calculations for a DCT. First, the elements of the vector <c> in the space of spatial frequencies are added and subtracted by the first vector calculating circuit (39), thereby producing the elements of the first vector <y> and the elements of the second vector <z>. Then, the third vector <y'> and the fourth vector <z'> are determined respectively by the second vector calculating circuit (40) and the third vector calculating circuit (41) which are composed of less than 2N multipliers altogether. Finally, the vector <x> in the real space is determined by the adder (42).
The above and other objects, features, and advantages of the present invention will become apparent from the following description of illustrative embodiments thereof to be read in conjunction with the accompanying drawings, in which like reference numerals represent the same or similar objects.
Brief Description of the Drawings
FIG. 1 is a block diagram of a conventional two-dimensional 8.times.8 DCT processing circuit;
FIG. 2 is a block diagram of a conventional two-dimensional 8.times.8 IDCT processing circuit;
FIG. 3 is a block diagram of a two-dimensional 8.times.8 DCT processing circuit according to the present invention;
FIG. 4 is a block diagram of a <v> calculating block in the DCT processing circuit shown in FIG. 3;
FIG. 5 is a block diagram of a <w> calculating block in the DCT processing circuit shown in FIG. 3;
FIG. 6 is a block diagram of a <c> calculating block in the DCT processing circuit shown in FIG. 3;
FIG. 7 is a block diagram of an n-input adder-subtractor;
FIG. 8 is a block diagram of a two-dimensional 8.times.8 IDCT processing circuit according to the present invention;
FIG. 9 is a block diagram of a <y>, <z>calculating block in the IDCT processing circuit shown in FIG. 8;
FIG. 10 is a block diagram of a <y'> calculating block in the IDCT processing circuit shown in FIG. 8;
FIG. 11 is a block diagram of a <z'> calculating block in the IDCT processing circuit shown in FIG. 8;
FIG. 12 is a block diagram of a <y>, <z>calculating block in a two-dimensional 8.times.8 IDCT processing circuit according to another embodiment of the present invention; and
FIG. 13 is a block diagram of a modification of the <y>, <z> calculating block shown in FIG. 12.
Detailed Description of the Preferred Embodiments
FIGS. 3 through 11 show a DCT processing circuit for processing two-dimensional matrixes arrayed in 8 rows and 8 columns and an IDCT processing circuit for processing two-dimensional matrices arrayed in 8 rows and 8 columns, according to the present invention. Heretofore, the DCT and IDCT are defined according to the equations (1) given above. According to the present invention, a matrix X of 8 rows and 8 columns of 64 elements xi, j in a real space, as defined according to the equations (2), is transformed into a vector <x> having 64 elements xk (k=0, 1, . . . , 63). The elements xk of the vector <x> and the elements xi, j of the matrix X correspond to each other according to an equation (3) given below. Specifically, x0=x0,0, x1=x7,7, x2=x3,3, . . . , x63=x3,2. ##STR2##
Likewise, a matrix C of 8 rows and 8 columns of 64 elements ci, j in a space of spatial frequencies, as defined according to the equations (2), is transformed into a vector <c> having 64 elements ck (k=0, 1, . . . , 63). The elements ck of the vector <c> and the elements ci, j of the matrix C correspond to each other according to an equation (4) given below. Specifically, c0=c0,0, c1=c4,4, c2=c0,4, . . . , c63=c6,1. ##STR3##
Thus, the vectors <x>, <y> can be defined as follows: ##EQU1##
The above definition indicates that the two-dimensional 8.times.8 DCT is regarded as a linear transform from the vector <x> with the 64 elements in the real space into the vector <c> with the 64 elements in the space of spatial frequencies, and the two-dimensional 8.times.8 IDCT as a linear transform from the latter vector <c> into the former vector <x>. If a transformation matrix of 64 rows and 64 columns for the linear transform of the DCT is indicated by M and a transformation matrix of 64 rows and 64 columns for the linear transform of the IDCT is indicated by M', then the DCT and the IDCT are defined as follows:
When the transformation matrix M is represented by the sum of products of the matrix, the DCT is expressed as follows:
where P, Q, R, and S are respectively constant matrices of 64 rows and 64 columns. Similarly, when the transformation matrix M' is represented by the sum of products of the matrix, the IDCT is expressed as follows:
where P.sup.t, Q.sup.t, R.sup.t, and S.sup.t are respectively transposed matrices of P, Q, R, and S.
The matrix P has 32 rows and 64 columns in the upper half whose elements are 0, 1, or -1, and 32 rows and 64 columns in the lower half whose elements are all 0, as indicated by the following equation (9): ##STR4##
In the equation (9), the symbol + represents 1, the symbol - represents -1, and the blank space represents 0. The same definition applies to similar equations given below. The multiplication of the matrix P and a vector having 64 elements can therefore be carried out only by an adder-subtractor circuit.
The matrix Q can be expressed by the following equation (10) using the same constants r, .alpha., .beta. as used in the equations (2): ##EQU2##
The matrix Q is made up of 64 rows and 64 columns, containing 16 smaller matrices Q1 each of 4 rows and 4 columns along a diagonal line inclined downwardly to the right, with only those smaller matrices Q1 having nonzero elements and the other elements being all 0. Since each of the smaller matrices Q1 contains only one element other than 0 or .+-.1 in each row (however, .alpha. and -.alpha., for example, are counted together as one element), the original matrix Q and the vector of 64 elements, which are serially inputted and outputted, can be multiplied by only one multiplier.
The matrix R has 32 rows and 64 columns in the upper half whose elements are all, and 32 rows and 64 columns in the lower half whose elements are 0, 1, or -1, as indicated by an equation (11) given below. The multiplication of the matrix R and a vector having 64 elements can therefore be carried out only by an adder-subtractor circuit. ##STR5##
The matrix S can be expressed by the following equation (12) using the same constants a, b, c, and d as used in the equations (2): ##EQU3##
The matrix S is made up of 64 rows and 64 columns, containing 16 smaller matrices Q1 each of 4 rows and 4 columns along a diagonal line inclined downwardly to the right, with only those smaller matrices S1 having nonzero elements and the other elements being all 0. Since each of the smaller matrices S1 contains only two elements other than 0 or .+-.1 in each row (however, a and -a, for example, are counted together as one element), the original matrix S and the vector of 64 elements, which are serially inputted and outputted, can be multiplied by only two multipliers.
Consequently, if a DCT is expressed according to the equation (7), then the DCT can be effected on serially inputted and outputted matrices by only three multipliers. Accordingly, the number of multipliers used is much smaller than the number of 16 multipliers used by the conventional DCT circuit. The equation (7) allows the DCT to be carried out in a single multiplication, no round-off errors or truncation errors are accumulated. Inasmuch as the matrices Q.sup.t, P.sup.t, S.sup.t, R.sup.t used in the IDCT according to the equation (8) have the same characteristics as those of the matrices Q, P, S, R, respectively, the IDCT according to the equation (8) can also be carried out by only three multipliers, as can be understood from circuit arrangements described later on.
For the purpose of illustrating circuit arrangements that carry out the calculations according to the equations (7) and (8), the equation (7) is modified as follows: ##EQU4##
The vectors <v> and <w> can be expressed as follows: ##EQU5##
Similarly, the equation (8) is modified into the following equation (15): ##EQU6## The vectors <y> and <z> in the equation (15) are expressed by the following equations (16), and the vectors <y'> and <z'> in the equation (15) are expressed by the following equations (17): ##EQU7##
With the above definition, the two-dimensional 8.times.8 DCT according to the equation (13) can be calculated in three steps described below. The multiplication of (1/8) can be performed by a shift of three bits, and hence will not be described below.
(Step D1) The elements of the vector <x> are serially inputted to determine the vector <v> according to the equations (14).
(Step D2) The vector <w> is determined from the elements of the vector <x> according to the equations (14).
(Step D3) The calculation of P <v>+R <w> is effected based on the vectors <v> and <w>, thus determining the vector <c>.
Similarly, the two-dimensional 8.times.8 IDCT according to the equation (15) can be calculated in the following three steps:
(Step I1) The elements of the vector <c> are serially inputted to determine the vectors <y> and <z> according to the equations (16).
(Step I2) The vectors <y'> and <z'> are determined from the elements of the vectors <y> and <z> according to the equations (17).
(Step I3) The calculation of <y'>+<z'> is effected based on the vectors <y'> and <z'>, thus determining the vector <x>.
FIG. 3 shows a two-dimensional 8.times.8 DCT processing circuit according to the present invention. As shown in FIG. 3, the two-dimensional 8.times.8 DCT processing circuit comprises a <v> calculating block 7 for calculating a vector <v>, a <w> calculating block 8 for calculating a vector <w>, and a <c> calculating block 9 for calculating a vector <c>. The <v> and <w> calculating blocks 7, 8 are supplied with the 64 elements xi (i=0, 1, . . . , 63) of a vector <x>. If the 64 elements are shifted by one element in a period equal to one clock pulse, then when the elements xi are supplied to the <v> and <w> calculating blocks 7, 8, the <v> calculating block 7 supplies the 64 elements vi of the vector <v> serially to the <c> calculating block 9 with a delay of four clock pulses, and the <w> calculating block 8 supplies the 64 elements wi of the vector <w> serially to the <c> calculating block 9 with a delay of four clock pulse. The <c> calculating block 9 then supplies the 64 elements ci of the vector <c>, which is produced according to the step D3 above, serially to a subsequent circuit in synchronism with 64 clock pulses.
FIG. 4 shows the <v> calculating block 7 in specific detail. In FIG. 4, the elements xi of the vector <x> are supplied through an accumulative adder 10 and a register 11 with a hold function to one input terminal of a data selector 12. The elements xi of the vector <x> are also supplied directly to an input terminal of a data selector 14 and through a two's complement unit 13 to the other input terminal of the data selector 14. The data selector 14 supplies output data through an accumulative adder 15 and a register 16 with a hold function to the other input terminal of the data selector 12. The two's complement unit 13 is used to multiply input data supplied hereto by -1. The data selector 12 supplies selected data to a multiplier 17. A coefficient setting circuit 18 periodically supplies a multiplier 17 with multiplying coefficients in the order of 1, r, .alpha., .beta., 1, r, . . . . The multiplier 17 multiplies the inputted data from the data selector 12 by the coefficients supplied from the coefficient setting circuit 18, producing the vector (v), and serially outputs the 64 elements vi-4 (" -4" means that the outputted data are four clock pulses delayed with respect to the inputted data) of the vector (v).
Operation of the <v> calculating block 7 shown in FIG. 4 will be described below.
The elements vi of the vector <v> and the elements xi of the vector <x> are related to each other as follows: ##EQU8##
The equation (18) shows that the elements v4j.about.v4j+3 (j=0, 1, . . . , 15) of the vector <v> can be expressed by the elements x4j.about.x4j+3 of the vector <x> as follows: ##EQU9##
Therefore, the vector <v> can be determined by multiplying the inputted vector <x> successively by the 2.times.4 matrix Q4, the 4.times.2 matrix Q3, and the 4.times.4 matrix Q2 contained in the equation (19). As the four elements of the outputted vector can be determined from the data, corresponding to four clock pulses, of the inputted vector, the elements of the outputted vector are delayed four clock pulses with respect to the elements of the inputted vector. The equation (19) can be expressed according to ordinary equations as follows:
Specifically, in FIG. 4, the added values in the accumulative adders 10, 15 are reset to 0 by a reset pulse RP that is turned on initially in the period of four clock pulses. Thereafter, a switching signal G1 causes the data selector 14 to select the elements xi in the period of first two clock pulses, and to select the data outputted from the two's complement unit 13 in the period of next two clock pulses. In response to a hold pulse HP that is turned on finally in the period of four clock pulses, the registers 11, 16 hold the respective data inputted from the accumulative adders 10, 15. The reset pulse RP is also turned on in synchronism with the hold pulse HP, resetting the counts in the accumulative adders 10, 15. During the period of these four clock pulses, the calculations relative to the matrices Q4, Q3 according to the equation (19) are carried out in those circuits which precede the registers 11, 16, and the registers 11, 16 hold the data (x4j+x4j+1+x4j+2+x4 j+3) and the data (x4j+x4j+1-x4j+2-x4j+3), respectively.
Subsequently, the data selector 12 selects the data outputted from the register 11 in the first two of next four clock pulses, and selects the data outputted from the register 16 in the last two of the four clock pulses. The registers 11, 16 output the data held thereby at all times. The multiplier 17 and the coefficient setting circuit 18 now perform the calculation relative to the matrix Q2 according to the equation (19). Concurrent with the calculation relative to the matrix Q2, the circuits preceding the registers 11, 16 effect the calculations relative to the matrices Q4, Q3 according to the equation (19) on the next four elements xi. In this manner, the <v> calculating block 7 serially outputs the 64 elements of the vector <v> with a delay of four clock pulses with respect to the inputted data.
FIG. 5 shows the <w> calculating block 8 in specific detail. In FIG. 5, the elements xi of the vector <x> are supplied directly to one input terminal of a two-input data selector 19 and also through a two's complement unit 20 to the other input terminal of the data selector 21. The data selector 19 supplies output data to one input terminal of a two-input, two-output data selector 21, whose other input terminal is supplied with data having a value of 0. The data selector 21 outputs input data parallel to each other or in crossing relation, depending on the level of a control signal G3 applied thereto. One output data from the data selector 21 is supplied through an accumulative adder 22 and a register 23 with a hold function to a multiplier 24. A coefficient setting circuit 25 periodically supplies the multiplier 24 with coefficients a, d, b, c. The multiplier 24 multiplies the inputted data from the register 23 by the coefficients supplied from the coefficient setting circuit 25, and supplies resultant data to one input terminal of an adder 26.
The other output data from the data selector 21 is supplied through an accumulative adder 27 and a register 28 with a hold function to a multiplier 29. A coefficient setting circuit 30 periodically supplies the multiplier 29 with coefficients d, -a, -c, b. The multiplier 29 multiplies the inputted data from the register 28 by the coefficients supplied from the coefficient setting circuit 30, and supplies resultant data to the other input terminal of the adder 26. The adder 26 serially outputs the 64 elements wi-4 of the vector (w). As with the vector <v>, the elements of the vector <w> are delayed four clock pulses with respect to those of the vector <x>.
Operation of the <w> calculating block 8 shown in FIG. 5 will be described below.
The elements wi of the vector <w> and the elements xi of the vector <x> are related to each other as follows: ##EQU10##
The equation (20) shows that the elements w4j.about.w4j+3 (j=0, 1, . . . , 15) of the vector <w> can be expressed by the elements x4j.about.x4j+3 of the vector <x> as follows: ##EQU11##
Therefore, the vector <w> can be determined by multiplying the inputted vector <x> successively by the 2.times.4 matrix S3 and the 4.times.2 matrix S2 contained in the equation (21). As the four elements of the outputted vector can be determined from the data, corresponding to four clock pulses, of the inputted vector, the elements of the outputted vector are delayed four clock pulses with respect to the elements of the inputted vector. The equation (21) can be expressed according to ordinary equations as follows:
Specifically, in FIG. 5, the added values in the accumulative adders 22, 27 are reset to 0 by a reset pulse RP that is turned on initially in the period of four clock pulses. Thereafter, a switching signal G2 causes the data selector 19 to select elements xi and two's complemented elements xi alternately, and a switching signal G3 causes data selector 21 to output its inputted data in parallel during the first two clock pulses, and in crossing relation during latter two clock pulses. In response to a hold pulse HP that is turned on finally in the period of four clock pulses, the registers 23, 28 hold the respective data inputted from the accumulative adders 22, 27. The reset pulse RP is also turned on in synchronism with the hold pulse HP, resetting the counts in the accumulative adders 22, 27. During the period of these four clock pulses, the calculation relative to the matrix S3 according to the equation (21) is carried out in those circuits which precede the registers 23, 28, and the registers 23, 28 hold the data (x4j-x4j+1) and the data (x4j+2-x4j+3), respectively.
Subsequently, the matrix S2 according to the equation (21) is calculated by the multipliers 24, 29 and the adder 26 in the period of next four clock pulses. Concurrent with the calculation relative to the matrix S2, the circuits preceding the registers 23, 28 effect the calculation relative to the matrix S3 according to the equation (21) on the next four elements xi. In this manner, the <w> calculating block 8 serially outputs the 64 elements of the vector <w> with a delay of four clock pulses with respect to the inputted data.
FIG. 6 shows the <c> calculating block 9 in specific detail. The <c> calculating block 9 includes one-input, 64-output serial-to-parallel (S/P) converters 31, 32 whose input terminals are supplied respectively with the 64 elements vi of the vector <v> and the 64 elements wi of the vector <wi>. The S/P converter 31 converts the 64 elements vi that are inputted in the period of 64 clock pulses into parallel data v0.about.v63, and holds the parallel data in its output unit for next 64 clock pulses. Similarly, the S/P converter 32 holds parallel data w0.about.w63 in its output unit for the period of 64 clock pulses. 64 two-input, one-output data selectors 33 have input terminals supplied with the respective parallel data v0, v1, . . . , v63 from the S/P converter 31, and other input terminals supplied with the respective parallel data w0, w1, . . . , w63 from the S/P converter 32. A 64-input, one-output adder-subtractor 34 from the 64 data selectors 33, respectively. The output terminal of the adder-subtractor 34 serially outputs the 64 elements ci of a vector <c> in a space of spatial frequencies.
FIG. 7 shows an n-input, one-output adder-subtractor in detail. In the case where n=64, the illustrated n-input, one-output adder-subtractor corresponds to the adder-subtractor 34 shown in FIG. 6. The n-input, one output adder-subtractor has n identical processing units 35 connected respectively to its n input terminals, and input data I0, I1, . . . , In-1 are supplied respectively to the processing units 35. For example, the leftmost processing unit 35 has a three-input, one-output data selector 36. The input data I0 is supplied directly to a first input terminal of the data selector 36 and also through a two's complement unit 37 to a second input terminal of the data selector 36. The data selector 36 has a third input terminal supplied with data whose value is 0. In response to an externally supplied control signal H0, the data selector 36 selects one of the supplied inputted data at a time. The leftmost processing unit 35 thus outputs I0, -I0, or 0. Likewise, the other processing units 35 output Ii, -Ii, or 0 depending on a control signal Hi (i=1, 2, . . . , n-1).
The data outputted from the n processing units 35 are then accumulatively added by (n-1) adders 38, and the resultant sum data is final output data from the n-input adder-subtractor. Therefore, the n-input adder-subtractor, which is supplied with the inputted data I0.about.In-1, outputs:
with qi being of a value of either 0, 1, or -1.
The <c> calculating block 9 shown in FIG. 6 operates as follows: The <c> calculating block 9 shown in FIG. 6 determines the vector <c> according to the following equation:
From the equations (9) and (11), the equation (22 may be expressed as follows: ##EQU12##
In the equation (23), the matrix P1 is composed of 32 rows and 64 columns whose elements are 0 or .+-.0 only, and the matrix R1 is also composed of 32 rows and 64 columns whose elements are 0 or .+-.0 only. Thus, the equation (23) can be divided into the following two equations: ##EQU13##
In the equations (24), qi,j (i=0, 1, . . . , 63, j=0, 1, . . . , 63) has a value of 0, 1, or -1, and q0,j.about.q31,j are determined based on the matrix P1, and q32,j.about.q63,j are determined based on the matrix R1. It can be seen from the equations (24) that the former 32 elements, c0.about.c31, of the 64 elements of the vector <c> can all be determined simply by adding and subtracting the 64 elements of the vector <c>, and the latter 32 elements, c32.about.c63 can all be determined simply by adding and subtracting the 64 elements of the vector <w>.
The 64 data selectors 33 shown in FIG. 6 select the elements vi with the first 32 clock pulses of 64 clock pulses, and accordingly the 64-input adder-subtractor 34 successively calculates the first 32 elements of the vector <c> according to the first one of the equations (24). The 64 data selectors 33 then select the elements wi with the latter 32 clock pulses of 64 clock pulses, and accordingly the 64-input adder-subtractor 34 successively calculates the last 32 elements of the vector <c> according to the second one of the equations (24).
The circuits shown in FIGS. 4 through 6 make it easy to process the serially inputted vector <x> in the real space for DCT and to serially output the vector <c> in the space of spatial frequencies. The total number of multipliers employed in the circuits shown in FIGS. 4 through 6 is 3, resulting in a substantial reduction in the number of multipliers used as compared with the 16 multipliers that have heretofore been used.
A two-dimensional 8.times.8 IDCT processing circuit according to the present invention will be described below. The IDCT processing circuit is supplied with the serially inputted 64 elements of a vector <c> in a space of spatial frequencies, and serially outputs the 64 elements of a vector <x> in a real space. From the equations (16) and (17) above, the vector <x> can be expressed as follows: ##EQU14##
In the IDCT processing circuit, therefore, two vectors <y> and <z> are first determined from the vector <c>, then vectors <y'> and <z'> are determined respectively from the vectors <y> and <z>, and finally the elements of the determined vectors are added, producing the vector <x>. The multiplication of the vector <x> by 1/8 will not be described here.
FIG. 8 shows such a two-dimensional 8.times.8 IDCT processing circuit. In FIG. 8, the two-dimensional 8.times.8 IDCT processing circuit comprises a <y>, <z> calculating block 39 for calculating vectors <y>, <z>. The <y>, <z>calculating block 39 is serially supplied with the elements c0.about.c63 of the vector <c>. The <y>, <z> calculating block 39 calculates the elements of two vectors <y> and <z> from the elements of the vector <c>, and serially supplies the 64 elements y0.about.y63 of the vector <y> to a <y'>calculating block 40 and also serially supplies the 64 elements z0.about.z63 of the vector <z> to a <z'> calculating block 41. Then, the <y'> calculating block 40 serially supplies the 64 elements y0'.about.y63' of a vector <y'> to one input terminal of an adder 42, and the <z'> calculating block 41 serially supplies the 64 elements z0'.about.z63' of a vector <z'> to the other input terminal of the adder 42. The adder 42 serially outputs the 64 elements x0.about.x63 of the vector <x>.
FIG. 9 shows the <y>, <z> calculating block 39 in specific detail. The <y>, <z> calculating block 39 includes a one-input, 64-output serial-to-parallel (S/P) converter 43. The S/P converter 43 is serially supplied with the 64 elements ci in synchronism with 64 clock pulses, and then outputs data c0.about.c63, which are a parallel arrangement of the elements ci, to its 64 data output units in the period of next 64 clock pulses. The <y>, <z> calculating block 39 also includes 32-input adder-subtractors 44, 45 (each equivalent to the circuit shown in FIG. 7 with n=35). The adder-subtractor 44 is supplied with the first 32 parallel data c0.about.c31 of the 64 data from the S/P converter 43, and the adder-subtractor 45 is supplied with the last 32 parallel data c32.about.c63 of the 64 data from the S/P converter 43. Based on the relationship between the equations (9) and (25 ), the elements of the vector <y> are determined from the elements of the vector <c> according to the following equation: ##EQU15##
In the equation (26), P1.sup.t indicates a matrix which is transposed from the upper matrix of 32 rows and 64 columns in the equation (9). Since the elements qi,j' (j=0, 1, . . . , 31) of the matrix P1.sup.t are 0, 1, or -1, the elements of the vector <y> can be determined by adding and subtracting the first 32 elements c0.about.c31 of the vector <c>. Therefore, the adder-subtractor 44 shown in FIG. 9 serially calculates and outputs the 64 elements y0.about.y63 of the vector <y> by performing additions and subtractions corresponding to the matrix P1.sup.t.
Likewise, based on the relationship between the equations (11) and (25), the elements of the vector <z> are determined from the elements of the vector <c> according to the following equation: ##EQU16##
In the equation (27), R1.sup.t indicates a matrix which is transposed from the lower matrix of 32 rows and 64 columns in the equation (11). Since the elements qi,j' (j=32, 33, . . . , 63) of the matrix R1.sup.t are 0, 1, or -1, the elements of the vector <y> can be determined by adding and subtracting the last 32 elements c32.about.c63 of the vector <c>. Therefore, the adder-subtractor 45 shown in FIG. 9 serially calculates and outputs the 64 elements z0.about.z63 of the vector <z> by performing additions and subtractions corresponding to the matrix RI.sup.t.
FIG. 10 shows the <y'> calculating block 40 in specific detail. In FIG. 10, the elements yi of the vector <y> that are serially supplied are supplied to a multiplier 46, which multiplies the supplied elements yi by coefficients 1, r, .alpha., .beta. that are periodically supplied from a coefficient setting unit 47. The multiplier 46 then supplies output product data through an accumulative adder 48 and a register 49 with a hold function to one input terminal of a data selector 50. The output product data is also supplied directly and through a two's complement unit 52 to respective input terminals of a data selector 51. The data selector 51 supplies selected output data through an accumulative adder 53 and a register 54 with a hold function to the other input terminal of the data selector 50. The data selector 50 then outputs the elements yi-4' of the vector <y'> with a delay of four clock pulses with respect to the elements of the inputted vector <y>.
Operation of the <y'> calculating block 40 shown in FIG. 10 will be described below. The vector <y'> and the vector <y> are related to each other as follows: ##EQU17##
The matrix according to the equation (28) contains elements which are all 0 other than 16 smaller matrices Q1.sup.t each of 4 rows and 4 columns along a diagonal line inclined downwardly to the right. Consequently, the equation (28) can be expressed in its entirety by the following equation (29): ##EQU18##
In the equation (29), j=0, 1, 2, . . . , 15, and the four elements y4j'.about.y4j+3' of the vector <y'> can be determined by multiplication the vector composed of the four elements y4j.about.y4j+3 of the vector <y> successively by the matrices Q7, Q6, and Q5. In the circuit shown in FIG. 10, as with the circuit shown in FIG. 4, the added values in the accumulative adders 48, 53 are reset to 0 by a reset pulse RP that is turned on initially in the period of four clock pulses, and are held in the respective registers 49, 54 by a hold pulse HP that is turned on finally in the period of four clock pulses. The registers 49, 54 always output the held data during the period of following four clock pulses. The data selector 51 selects the data outputted from the multiplier 46 in the period of first two of the four clock pulses, and selects the data outputted from the two's complement unit 52 in the period of next two clock pulses. The data selector 50 selects the data outputted from the register 49 in the period of first two of the four clock pulses, and selects the data outputted from the register 54 in the period of next two clock pulses.
In the circuit shown in FIG. 10, therefore, the matrix Q7 according to the equation (29) is calculated by the multiplier 46, the matrix Q6 by the accumulative adders 48, 53, the data selector 51, and the two's complement unit 52, and the matrix Q5 by the data selector 50.
FIG. 11 shows the <z'> calculating block 41 in specific detail. In FIG. 11, the elements zi of the vector <z> that are serially supplied are supplied to a multiplier 55, which multiplies the supplied elements zi by coefficients a, d, b, c that are periodically supplied from a coefficient setting unit 56. The multiplier 55 then supplies output product data through an accumulative adder 57 and a register 58 with a hold function to one input terminal of a data selector 59. The elements zi of the vector <z> are also supplied to a multiplier 60, which multiplies the supplied elements zi by coefficients d, -a, -c, b that are periodically supplied from a coefficient setting unit 61. The multiplier 60 then supplies output product data through an accumulative adder 62 and a register 63 with a hold function to the other input terminal of the data selector 59. The data selector 59 supplies selected output data directly and through a two's complement 65 to respective input terminals of a data selector 64. The data selector 64 then serially outputs the elements zi-4' of the vector <z'> with a delay of four clock pulses with respect to the elements of the inputted vector <z>.
Operation of the <y'> calculating block 40 shown in FIG. 11 will be described below. According to the equations (12) and (25), the vector <z'> can be determined by multiplying the vector <z> and a matrix as follows: ##EQU19##
The matrix of 64 rows and 64 columns according to the equation (30) contains elements which are all 0 other than 16 smaller matrices S1.sup.t each of 4 rows and 4 columns along a diagonal line inclined downwardly to the right. Consequently, the equation (30) can be represented by the following equation (31): ##EQU20##
In the equation (31), j=0, 1, 2, . . . , 15, and the four elements z4j'.about.z4j+3' of the vector <z'> can be determined by multiplying the vector composed of the four elements z4j.about.z4j+3 of the vector <z> successively by the matrices S5 and S4.
In the circuit shown in FIG. 11, as with the circuit shown in FIG. 10, the added values in the accumulative adders 57, 62 are reset to 0 by a reset pulse RP that is turned on initially in the period of four clock pulses, and are held in the respective registers 58, 63 by a hold pulse HP that is turned on finally in the period of four clock pulses. The registers 58, 63 always output the held data during the period of following four clock pulses. The data selector 59 selects the data outputted from the register 58 in the period of first two of the four clock pulses, and selects the data outputted from the register 63 in the period of next two clock pulses. The data selector 64 alternately selects the data outputted from the data selector 59 and the data outputted from the two's complement unit 65.
In the circuit shown in FIG. 11, therefore, the matrix S5 according to the equation (31) is calculated by the multipliers 55, 60, and the matrix S4 by the data selectors 59, 64 and the two's complement unit 65.
Another embodiment of the present invention will be described below with reference to FIGS. 12 and 13. According to this embodiment, the <y>, <z> calculating block 39 in the circuit shown in FIG. 8 for IDCT calculations is implemented by a smaller-scale circuit arrangement. The vectors <y> and <z> defined according to the equation (25) are expressed as follows:
where P', R', and T are respectively constant matrices of 64 rows and 64 columns as defined as follows: ##EQU21##
The matrix T contains elements which are all 0 other than 16 smaller matrices T1 each of 4 rows and 4 columns along a diagonal line inclined downwardly to the right. The elements of the smaller matrices T1 are 1 and -1. ##STR6##
The matrix P' according to the above equation (34) includes 64 rows and 32 columns in the lefthand half whose elements are 0, 1, or -1, and 32 rows and 64 columns in the righthand half whose elements are all 0. ##STR7##
The matrix R' according to the above equation (35) includes 64 rows and 32 columns in the righthand half whose elements are 0, 1, or -1, and 32 rows and 64 columns in the lefthand half whose elements are all 0.
If it is assumed that a vector T <c> is expressed as a vector <c'> and the vector <c'> has 64 elements c0'.about.c63', then the following relationship can be derived from the equation (33): ##EQU22##
Because of the characteristics of the smaller matrices T1, the equation (36) can be represented by the following equation (37): ##EQU23##
In the equation (37), j=0, 1, . . . , 31, and the two elements of the vector <c'> can be determined by adding and subtracting the two elements of the vector <c>. Using the vector <c'>, the vectors <y> and <z> according to the equations (32) can be calculated as follows: ##EQU24##
In the equations (38), the matrix P1' is the same as the matrix in the lefthand half of the equation (34), and the matrix R1' is the same as the matrix in the righthand half of the equation (35). According to the equations (38), the vector <y> can be determined simply by adding and subtracting the first 32 elements c0'.about.c31' of the vector <c'>, and the vector <c> can be determined simply by adding and subtracting the succeeding 32 elements c32'.about.c63' of the vector <c'>. Another <y>, <z> calculating block for calculating the equations (36) and (38) is shown in FIG. 12.
As shown in FIG. 12, the <y>, <z> calculating block includes a one-input, two-output S/P converter 66, a two-input, one-output adder-subtractor 67 (equivalent to the circuit shown in FIG. 7 with n=2) for calculating the equation (37), and a one-input, 64-output S/P converter 68. The 64 serial elements c0.about.c63 of the vector <c> are converted into the 64 serial elements c0'.about.c63' of the vector <c'> by the S/P converter 66 and the adder-subtractor 67. These elements c0'.about.c63' are serially supplied to an input terminal of the S/P converter 68. The S/P converter 68 has 64 output terminals which output the elements c0'.about.c63' parallel to each other. The first 32 elements c0'.about.c31' of the outputted parallel data are supplied to a lefthand 32-input, one-output adder-subtractor 69, and the succeeding 32 elements c32'.about.c63' are supplied to a righthand 32-input, one-output adder-subtractor 70. The lefthand adder-subtractor 69 calculates the matrix P1' according to the equations (38), and serially outputs the elements yi of the vector <y>, and the righthand adder-subtractor 70 calculates the matrix R1' according to the equations (38), and serially outputs the elements zi of the vector <z>.
The <y>, <z> calculating block shown in FIG. 12 may be modified as shown in FIG. 13. In FIG. 13, the <y>, <z> calculating block includes 16 two-input, one-output data selectors 71 having input terminals supplied with the first 32 elements c0'.about.c31' outputted parallel from the S/P converter 68. The data selectors 71 supply output data to the input terminals of a lefthand 16-input, one-output adder-subtractor 72 (equivalent to the circuit shown in FIG. 5 with n=16). The <y>, <z> calculating block also includes 16 two-input, one-output data selectors 73 having input terminals supplied with the succeeding 32 elements c32'.about.c63' outputted parallel from the S/P converter 68. The data selectors 73 supply output data to the input terminals of a righthand 16-input, one-output adder-subtractor 74.
The adder-subtractor 72 is supplied with only the data representing half of the 32 elements c0'.about.c31' from the data selectors 71. As can be seen from the equation (34), at least one of two adjacent elements in each row of the matrix P1' according to the equation (38) is 0 at all times. Therefore, inasmuch as the elements ci' that are virtually employed in the calculations relative to the matrix P1' according to the equations (38) are less than half the supplied elements, the calculations relative to the matrix P1' can be carried out by the 16-input adder-subtractor 72. Likewise, at least one of two adjacent elements in each row of the matrix R1' according to the equation (38) is 0 at all times as can be seen from the equation (35). Consequently, the righthand 16-input adder-subtractor 74 can effect the calculations relative to the matrix R1'.
With the present invention, a matrix of N rows and N columns in a real space and a matrix of N rows and N columns in a space of spatial frequencies are converted respectively into vectors each having N.sup.2 elements, and the vectors are processed for DCT or IDCT. Accordingly, desired data can be processed for two-dimensional DCT or IDCT with a reduced number of multipliers.
Having described preferred embodiments of the invention with reference to the accompanying drawings, it is to be understood that the invention is not limited to that precise embodiments and that various changes and modifications could be effected by one skilled in the art without departing from the spirit or scope of the invention as defined in the appended claims.
Claims
What is claimed is:
1. An image data processing apparatus for performing a discrete cosine transform by which input image data arranged in a matrix of N.sup.2 input data elements consisting of N rows and N columns (N being an integer of 2 or greater) are transformed into N.sup.2 transformed image data elements, said image data processing apparatus comprising: a first calculating circuit including a memory element, and which serially receives a sequence of said N.sup.2 input data elements for calculating therefrom a sequence of N.sup.2 first vector data elements and serially outputting said sequence of first vector data elements; a second vector calculating circuit serially receiving said sequence of said N.sup.2 input data elements for calculating therefrom a sequence of N.sup.2 second vector data elements and serially outputting said sequence of second vector data elements; and means, having a first input terminal that serially receives said sequence of first vector data elements and a second input terminal that serially receives said sequence of second vector data elements, for adding and subtracting data elements of said sequences of vector data elements to serially produce therefrom said N.sup.2 transformed image data elements, and for serially outputting said N.sup.2 transformed image data elements.
2. An apparatus according to claim 1, in which: said first calculating circuit comprises a first multiplier for sequentially multiplying selected accumulations of said input data elements by selected coefficients to produce said first vector data elements; said second calculating circuit comprises a second multiplier for sequentially multiplying differences obtained from first pairs of said input data elements by selected coefficients to produce a sequence of first products, a third multiplier for sequentially multiplying differences obtained from second pairs of said input data elements by selected coefficients to produce a sequence of second products, and an adder for summing respective products of said sequences of first and second products; and said first, second and third multipliers are the only multipliers in said apparatus.
3. An image data processing apparatus for performing an inverse discrete cosine transform by which a sequence of N.sup.2 input image data elements (N being an integer of 2 or greater) are transformed into N.sup.2 inverse transformed data elements, said image processing apparatus comprising: a first calculating circuit serially receiving said sequence of input image data elements for adding and subtracting elements of said sequence to produce therefrom a sequence of N.sup.2 first vector data elements and a sequence of N.sup.2 second vector data elements, and for serially outputting said first and second vector data elements; a second calculating circuit including a memory element, and which serially receives said sequence of first vector data elements for calculating therefrom a sequence of N.sup.2 third vector data elements and serially outputting said sequence of third vector data elements; a third calculating circuit serially receiving said sequence of second vector data elements for calculating therefrom a sequence of N.sup.2 fourth vector data elements and serially outputting said sequence of fourth vector data elements; and an adder for receiving and adding corresponding respective elements of said sequences of third and fourth vector data elements to produce said N.sup.2 inverse transformed data elements.
4. An apparatus according to claim 2, in which: said second calculating circuit comprises a first multiplier for sequentially multiplying said first vector data elements by selected coefficients; said third calculating circuit comprises second and third multipliers for sequentially multiplying said second vector data elements by respective selected coefficients; and said first, second and third multipliers are the only multipliers in said apparatus.
5. A discrete cosine transform apparatus for serially receiving a sequence of 64 input data elements corresponding to an 8.times.8 matrix of image data and serially outputting a sequence of 64 transformed data elements corresponding to an 8.times.8 matrix of transformed image data, the apparatus comprising: a first accumulation-multiplication (AM) circuit that includes a first accumulative adder for summing four of said sequence of input data elements to form a first accumulation, a second accumulative adder for summing a first pair of said four data elements to form a sum and subtracting therefrom each of a second pair of said four data elements to form a second accumulation, respective memory elements that hold said first and second accumulations, and a first multiplier for multiplying a selected one of said first and second accumulations by a selected coefficient to form a first vector data element; a second accumulation-multiplication (AM) circuit that includes a third accumulative adder for forming a first difference of said first pair of said four data elements, a second multiplier for multiplying said first difference by a selected coefficient to form a first product, a fourth accumulative adder for forming a second difference of said second pair of said four data elements, a third multiplier for multiplying said second difference by a selected coefficient to form a second product, and an adder for summing said first and second products to form a second vector data element; and means connected to said first and second AM circuits for sequentially receiving and storing 64 first vector data elements formed by said first AM circuit from said 64 input data elements and 64 second vector data elements formed by said second AM circuit from said 64 input data elements, and for adding and subtracting selected ones of said stored vector data elements to form said 64 transformed data elements.
6. An apparatus according to claim 5 in which said first, second and third multipliers are the only multipliers in said apparatus.
7. An inverse discrete cosine transform apparatus for serially receiving a sequence of 64 input data elements corresponding to an 8.times.8 matrix of transformed image data and serially outputting a sequence of 64 output data elements corresponding to an 8.times.8 matrix of inverse transformed image data, the apparatus comprising: means for sequentially receiving and storing said 64 input data elements, for adding and subtracting selected ones of said stored input data elements to form 64 first vector data elements, and for adding and subtracting other selected ones of said stored input data elements to form 64 second vector data elements; a first multiplication-accumulation circuit that includes a first multiplier for multiplying ones of said first vector data elements by selected coefficients to form first products, a first accumulative adder for summing four of said first products to form a third vector data element, a first memory element that stores said third vector data element, a second accumulative adder for summing a first pair of said four products and subtracting therefrom each of a second pair of said four products to form another third vector data element, and a second memory element that stores said other third vector data element; a second multiplication-accumulation circuit that includes a second multiplier for multiplying ones of said second vector data elements by selected coefficients to form second products, a third accumulative adder for summing four of said second products to form a fourth vector data element, a third multiplier for multiplying said ones of said second vector data elements by other selected coefficients to form third products, and a fourth accumulative adder for summing four of said third products to form another fourth vector data element; and an adder connected to said first and second multiplication-accumulation circuits for sequentially adding corresponding ones of said third and fourth vector data elements to form said 64 output data elements.
8. An apparatus according to claim 7, in which said first, second and third multipliers are the only multipliers in said apparatus.