Fast Pipelined 2-D Discrete Cosine Transform Architecture

The present invention contains subject matter related to the subject matter of the following patent and patent applications:

1. U.S. patent application Ser. No. 07/948,237, entitled "Algorithm and Circuits for Matrix Multiplication" filed Sep. 21, 1992, for Jinn-Nan Kao; and

2. U.S. Pat. No. 5,204,830, entitled "Fast Pipelined Matrix Multiplier" filed Feb. 13, 1992 for Jinn-Shyan Wang and Jinn-Nan Kao.

The above-listed patent and patent application are assigned to the assignee hereof and are incorporated herein by reference.

The present invention is directed to an electronic circuit for performing a Discrete Cosine Transform of an inputted matrix. In particular, the invention provides an improved Discrete Cosine Transform circuit which utilizes less area on an integrated circuit chip without reducing the processing speed of the circuit.

The Discrete Cosine Transform (DCT) is a frequently used operation in several applications. For example, it is advantageous in the area of video image data compression to apply a two dimensional (2-D) DCT to inputted video data.

The discrete cosine transform is defined as: ##EQU3## where x.sub.ij are input elements in an N.times.N matrix, with i,j=0,1,2, . . . , N-1 and where z.sub.mn are output elements in an N.times.N matrix with m,n=0,1,2, . . . , N-1 and where: ##EQU4## The Inverse Discrete Cosine Transform (IDCT) is defined as: ##EQU5## The matrix expression for equation (1) is

where X is the input data matrix, C is the cosine transform matrix and C.sup.t is the transpose of the matrix C. If the input matrix X is an N.times.N matrix, then equation (3) may be expressed as: ##EQU6## The computation of the IDCT is similar to that of the DCT except that the matrix C.sup.t is substituted for the matrix C and vice versa. Therefore, the discussion may continue with only the DCT without loss of generality. Equation (3) may be divided into two multiplications as follows:

where Y is an intermediate product matrix and C.sup.t is the transpose of C.

There are several conventional techniques and circuits for performing a DCT of an inputted data matrix. N. Ahmed, T. Natarajan & K. Rao, "Discrete Cosine Transform," IEEE Trans. on Computers, vol. C-23, January, 1974, 90-93 teaches a general DCT technique. N. Cho & S. Lee, "Fast Algorithm and Implementation of 2-D Discrete Cosine Transform," IEEE Trans. on Cir. & Sys., vol. 38, no. 3, March 1991, p. 297-305 discloses a circuit that computes an 2-D N.times.N DCT using N 1-D DCT circuits or with multiplexers and N/2 1-D DCT circuits. M. Sun, T. Chen & A. Gottlieb, "VLSI Implementation of a 16.times.16 Discrete Cosine Transform," IEEE Trans. on Cir. & Sys., vol.36, no. 4, April, 1989, p.610-17 teaches a 2-D DCT circuit with DCT stages having a memory for storing partial results in the matrix calculations of 1-D DCT's. H. Hou, "A Fast Recursive Algorithm For Computing the Discrete Cosine Transform," IEEE Trans. on Acoustics, Speech and Signal Processing, vol. ASSP-35, no. 10, October, 1987, p.1455-61 teaches decimation techniques for reducing an N.times.N DCT to an N/2.times.N/2 DCT.

FIG. 1 shows an efficient circuit 10 for computing the product of three matrices disclosed in U.S. Pat. No. 5,204,830 which may also be used to compute the DCT of equation (4). The circuit computes a 2.times.2 DCT using a first 1-D DCT stage 12 for computing Y=XC.sup.t and a second 1-D DCT stage 14 for computing the matrix Z=CY. The first stage 12 has a central column register circuit 20 for receiving one element of the matrix X per clock cycle and one column multiplication circuit 16 or 18 for each column of the matrix C.sup.t which column multiplication circuit 16 or 18 receives one element of the corresponding column per clock cycle. Each column multiplication circuit 16, 18 computes the elements of a corresponding column of the matrix Y using rowcolumn multiplication, i.e., by multiplying the elements of the inputted column by corresponding elements of an appropriate row of the matrix C.sup.t and adding together the products. To compute all of the elements of the column of the matrix Y, each column multiplication circuit 16 or 18 receives the elements of the corresponding column of the matrix C.sup.t N times, while the central column register circuit receives each element of the matrix X in the order from the first row to the last row. The computed elements of the matrix Y are then inputted to the second stage 14 which operates in a similar fashion as the stage 12 to compute the elements of the matrix Z.

The column multiplication circuits 16,18 have a plurality of processing elements PE1, PE2, and PE3 which compute part of a product according to Booth's algorithm. According to Booth's algorithm, a multiplicand is multiplied by an M-bit multiplier by examining each m.sup.th bit of the multiplier (0.ltoreq.m.ltoreq.M-1) one at a time. If the m.sup.th bit of the multiplier is a logic `1`, the multiplicand shifted m bits to the left is accumulated in a running total which, after examining the M-1.sup.th bit produces the product. Thus, the multiplicand 6 (`110` in binary) is multiplied with the multiplier 11 (`1011` in binary) by adding together `110` (for the 0.sup.th bit of `1011`), 1100 (for the 1.sup.st bit of `1011`) and `110000` (for the 3.sup.rd bit of `1011`) to produce `1000010`. Each processing element PE1 16-1, PE2, 16-2, . . . , PE3 16-4 computes a partial result for a particular m.sup. th bit, with the processing element PE3 16-4 also adding together several multiplicand-multiplier products to compute an element of the matrix Y. For example, the processing element 16-2 corresponds to the m=1.sup.th bit and utilizes the m=1.sup.th bit of the matrix element stored in the register 21-1 as a selector control bit to a multiplexer 36-2. If the bit is a logic `1`, the multiplexer selects the multiplicand (inputted from the register 30-1) shifted left m=1 bits. If the bit is a logic `0` then the value `0` is selected. The selected value outputted from the multiplexer 36-2 is added to an accumulating result inputted from the register 24-1 using an addition register 24-2. The circuits 16 and 18 are pipelined in that they sequentially receive one pair of arguments per cycle which trickle down from processing element PE1, PE2, . . . , to processing element PE2, . . . , PE3 in an analogous fashion to an assembly line.

The circuit 10 is modular and efficient. However, it is desirable to further reduce the chip area occupied by each 1-D DCT or IDCT stage.

It is therefore an object of the present invention to overcome the disadvantages of the prior art.

These and other objects are achieved by the present invention which utilizes a combined decimation technique and pipelining technique. In a decimation technique, the symmetrical property of the distribution of cosine coefficients in the DCT (IDCT) coefficient matrices is utilized to reduce the transform from an N.times.N transform to an N/2.times.N/2 transform. In such a case, equation (5) can be rewritten as follows: ##EQU7## where Y.sub.e is a matrix containing the even rows of the matrix Y, Y.sub.o is a matrix containing the odd rows of the matrix Y, X.sub.f is a matrix containing the front rows (in the upper half) of the matrix X, X.sub.r is a matrix containing the recent rows, in reverse order, (in the lower half) of the matrix X and C.sub.1 and C.sub.2 are N/2.times.N/2 DCT coefficient matrices. This equation may be rewritten as:

where:

Here A.sub.f and A.sub.r are N/2.times.N matrices. Likewise, the IDCT may be written as follows: ##EQU8## where C.sub.1.sup.t is the transpose of C.sub.1 and C.sub.2.sup.t is the transpose of C.sub.2. Equation (8) may be rewritten as:

where

Both R and T are N/2.times.N matrices.

According to one embodiment of the invention, a DCT circuit is provided for performing a 1-D DCT of a matrix Y=CX where, Y is an output DCT transform matrix, X is an inputted matrix and C is a cosine coefficient matrix. The circuit has a pre-processor stage which receives each element x.sub.ij i,j=1,2, . . . ,N, where N is an integer.gtoreq.4, of an input matrix X. The pre-processor stage simultaneously outputs Q.gtoreq.1 sequences of one or more columns of elements of a matrix A.sub.f having elements a.sub.ij =x.sub.ij +x.sub.(N-i+1)j i=1,2, . . . ,N/2, j=1,2, . . . ,N. In addition, the pre-processor stage also simultaneously outputs Q.gtoreq.1 sequences of one or more columns of elements of a matrix A.sub.r having elements a.sub.ij =x.sub.(i-N/2)j -x.sub.(3N/2-i+1)j i=N/2+1, N/2+2, . . . ,N j=1,2, . . . ,N. The DCT circuit also has a 1-D DCT processing stage which simultaneously receives each of the 2Q sequences of elements outputted by the pre-processor stage. In addition, the 1-D DCT processing stage receives P sequences of one or more rows of elements of an N/2.times.N/2 DCT cosine coefficient matrix C.sub.1 and P sequences of rows of elements of an N/2.times. N/2 DCT cosine coefficient matrix C.sub.2. The 1-D DCT processing stage has K.gtoreq.1 column multiplication circuits which each simultaneously outputs a sequence of one or more vectors of elements of a matrix Y.sub.o containing the elements y.sub.ij i=1,3, . . . ,N j=1,2, . . . ,N, where ##EQU9## The 1-D DCT processing stage also has another K.gtoreq.1 column multiplication circuits which each simultaneously outputs a sequence of one or more vectors of elements of a matrix Y.sub.e comprising elements Y.sub.ij i=2,4, . . . ,N j=1,2, . . . ,N where ##EQU10## The vectors contained in the sequences outputted from the 2K column multiplication circuits may be rows or columns depending on the particular ordering of the 2Q and 2P sequences inputted to the 1-D DCT processing stage.

Illustratively, a 2-D DCT circuit can be constructed as follows. A pre-processor stage and 1-D DCT stage as described above are provided which receive an inputted data matrix X and compute Y=CX. The outputted matrix Y is inputted to a transpose memory which outputs the transpose matrix Y.sup.t. A second pre-processor stage and a second 1-D DCT stage similar to the first are also provided which compute Z=CY.sup.t.

According to another embodiment of the invention, an IDCT circuit is provided for performing a 1-D IDCT of a matrix Y=C.sup.t Z, where Z is an inputted transformed matrix, Y is an output matrix and C.sup.t is a transposed cosine coefficient matrix. The IDCT circuit has a 1-D IDCT processing stage which simultaneously receives Q.gtoreq.1 sequences of one or more columns of elements z.sub.ij i=1,3, . . . ,N, j=1,2, . . . ,N, where N is an integer.gtoreq.4 of a matrix Z.sub.o. The 1-D IDCT stage also simultaneously receives Q sequences of one or more columns of elements z.sub.ij i=2,4, . . . ,N, j=1,2, . . . ,N of a matrix Z.sub.e. Furthermore, the IDCT processing stage simultaneously receives P.gtoreq.1 sequences of one or more rows of elements of an N/2.times.N/2 IDCT cosine coefficient matrix C.sub.1.sup.t and P sequences of rows of elements of an N/2.times.N/2 IDCT cosine coefficient matrix C.sub.2.sup.t. The 1-D IDCT processing stage has K.gtoreq.1 column multiplication circuits which each simultaneously outputs a sequence of one or more vectors of elements of a matrix R containing the elements r.sub.ij i=1,2, . . . ,N/2 j=1,2, . . . ,N, where ##EQU11## The 1-D IDCT processing stage also has K.gtoreq.1 column multiplication circuits which each simultaneously outputs a sequence of one or more vectors of elements of a matrix T comprising elements t.sub.ij i=1,2, . . . ,N/2 j=1,2, . . . ,N where ##EQU12## The vectors of the matrices R and T outputted from the 2K column multiplication circuits may be rows or columns depending on the particular ordering of the 2Q and 2P sequences inputted to the 1-D IDCT processing stage. The IDCT circuit also has a postprocessing stage for receiving the 2K sequences of vectors of the matrices R and T. The post-processing stage outputs elements of a matrix Y.sub.f having elements y.sub.ij i=1,2, . . . ,N/2, j=1,2, . . . ,N where y.sub.ij =r.sub.ij +t.sub.ij and elements of a matrix Y.sub.r having elements y.sub.ij i=N/2+1, N/2+2, . . . ,N, j=1,2, . . . ,N where y.sub.ij =r.sub.(i-N/2)j -t.sub.(i-N/2)j.

Illustratively, a 2-D IDCT circuit can be constructed in an analogous fashion as a 2-D DCT circuit using two IDCT stages, two post processing stages and a transpose memory.

In short, a DCT transform circuit which utilizes a combined parallel pipelining and decimation technique is disclosed. The DCT transform circuit according to this combined technique provides an efficient parallel processing solution which requires less circuitry and therefore occupies less area on an IC chip.

FIG. 1 depicts a conventional parallel pipeline DCT circuit.

FIG. 2 depicts a 2-D DCT circuit block diagram according to a first embodiment of the invention.

FIG. 3 depicts a 1-D DCT/IDCT processing stage according to a first embodiment of the invention.

FIG. 4 depicts a column register circuit and a column multiplication circuit of FIG. 3 in greater detail.

FIG. 5 depicts a processing element of the column multiplication circuit of FIG. 4 in greater detail.

FIG. 6 depicts a pre-processing stage for performing a 4.times.4 DCT.

FIG. 7 depicts a 1-D DCT/IDCT processing stage according to a second embodiment of the invention.

FIG. 8 depicts a 1-D DCT/IDCT processing stage according to a third embodiment of the invention.

FIG. 9 depicts a pre-processing stage for performing an 8.times.8 DCT.

FIG. 10 depicts a 2-D IDCT circuit block diagram according to a second embodiment of the present invention.

FIG. 11 depicts an illustrative post-processing stage shown in FIG. 10.

FIG. 12 depicts a second illustrative post-processing stage shown in FIG. 10.

In the present invention, a combined parallel pipelining and decimation technique are used to provide an efficient DCT or IDCT circuit which utilizes little IC chip area for a desired processing speed.

FIG. 2 depicts a block diagram of a 2-D DCT circuit 100 according to a first embodiment of the present invention. The circuit 100 has a pre-processing circuit 110 which receives an input N.times.N data matrix X and outputs two N/2 data matrices A.sub.f and A.sub.r. The matrix A.sub.f is multiplied with a first N/2.times.N/2 DCT cosine coefficient matrix C.sub.1 in a 1-D DCT circuit 120 to produce the matrix Y.sub.o containing the odd rows of an intermediate product matrix Y. Simultaneously, the matrix A.sub.r is multiplied with a second N/2.times.N/2 DCT cosine coefficient matrix C.sub.2 in the 1-D DCT circuit 120 to produce the matrix Y.sub.e containing the even rows of the intermediate product matrix Y. The matrices Y.sub.o and Y.sub.e are received in the transpose memory 130 which outputs the transpose matrix Y.sup.t. The pre-processor circuit 140 receives the transpose matrix Y.sup.t and outputs the matrices A'.sub.f and A'.sub.r . The matrix A'.sub.f is multiplied with the matrix C.sub.1 in the 1-D DCT circuit 150 to produce the matrix Z.sub.o. Simultaneously, the matrix A'.sub.r is multiplied with the matrix C.sub.2 in the 1-D DCT circuit 150 to produce the matrix Z.sub.e.

In the circuit of FIG. 2, the pre-processor circuits 110 and 140 may be identical and the 1-D DCT circuits 120 and 150 may be identical. Alternatively, the circuits 140 and 150 may be adapted to process data having more bits than the circuits 110 and 120. This is because the data words processed in the circuits 140 and 150 are likely to have more bits by virtue of the multiplication in the circuit 120.

FIG. 3 shows a 1-D DCT processing stage 200 which may be used to perform a 4.times.4 1-D DCT Y=CX where both X and C are 4.times.4 matrices. However, using a decimation technique, the 4.times.4 1-D DCT Y=CX is reduced two 2.times.2 1-D DCT's Y.sub.e =C.sub.1 .multidot.A.sub.f and Y.sub.o =C.sub.2 .multidot.A.sub.r where: ##EQU13## Here, each a.sub.ij of the matrix A.sub.f is given by:

and each a.sub.ij of the matrix A.sub.r is given by:

The circuit of FIG. 3 is provided with Q=2 column circuits 220-1, 220-2 for receiving Q=2 sequences of columns of elements of the matrices A.sub.f and Q=2 column circuits 220-3, 220-4 for receiving Q=2 sequences of columns of elements of the matrices A.sub.r, where Q is an integer.gtoreq.1. Each circuit 220-1, . . . ,220-4 receives one element of the corresponding sequence per cycle. The 1-D DCT circuit also has P=2 column circuits 230-1 and 230-2 for receiving P=2 sequences of rows of the DCT cosine coefficient matrix C.sub.1 and P=2 column circuits 230-3 and 230-4 for receiving P=2 sequences of rows of the DCT cosine coefficient matrix C.sub.2. Each column circuit 230-1, . . . ,230-4 receives one element of its respective sequence per cycle.

Two types of column circuits are used in the 1-D DCT processing stage 200, register column circuits and multiplication column circuits. Such circuits are disclosed in U.S. Pat. No. 5,204,830. Furthermore, U.S. patent application Ser. No. 07/948,237 discloses modified column circuits. As such, the operation of these circuits is only explained briefly herein.

FIG. 4 shows a column register circuit 910 having a number of registers 920-1, 920-2, . . . , 920-1 interconnected to form a serial shift register. In addition, a column multiplication circuit 930 is shown having a number of processing elements 930-1, 930-2, . . . , 930-1 interconnected in a similar sequential fashion. The column multiplication circuit 930 has an adder circuit 931 connected to the last processing element 930-1 and an accumulator 932 connected to the adder 931. Illustratively, the column register circuit 910 and column multiplication circuit 930 calculate an element of a product matrix. To that end, a sequence of elements of a column of a first matrix are inputted to one of the column circuits and a sequence of elements of a row are inputted to the other column circuit. For example, as shown, the column elements u.sub.11, u.sub.21, . . . , u.sub.i1 are inputted to the first register 920-1, one element per cycle. These elements are shifted down from register to register, (e.g., an element u.sub.11 stored in the register 920-1 is shifted to the register 920-2 as the element u.sub.21 is stored in the register 920-1) one register per cycle. Likewise, the row elements v.sub.11, v.sub.12, . . . , v.sub.1j are inputted, one element per cycle to the first processing element 930-1 which elements v.sub.11, v.sub.12, . . . , v.sub.1j trickle down the column multiplication circuit 930 processing element to processing element.

Each pair of connected registers and processing elements defines a multiplication level, i.e., the register 920-1 and processing element 930-1 define a first multiplication level, the register 920-2 and the processing element 930-2 define a second level, etc. Each register, e.g., 920-2, outputs three bits of the element stored therein to a corresponding processing element, e.g., 930-2 via lines 944. The processing elements use these bits to perform a multiplication according to a modified Booth algorithm. FIG. 5 shows the circuitry used inside a processing element, e.g., the processing element 930-2, for performing a multiplication. A matrix element from a previous processing element, e.g., the processing element 930-1, in the multiplication column 930 is inputted via a line 941 to a register 942. (The first matrix element 930-1 simply receives a matrix element inputted to the column multiplication circuit 930.) The element is also fed as a data input d to a multiplexer 943 which is capable of outputting the values 0, d, 2d, -d, or -2d depending on a select control signal inputted to the multiplexer 943. The multiplexer 943 receives a three bit input via the lines 944. The particular three bits of the M bit value stored in the register are the L+1.sup.th, L.sup.th and L-1.sup.th where L is the level of the register and processing element and 1.ltoreq.L.ltoreq.M (a dummy value of 0 is used for L-1.sup.th bit where L is the first level). The value outputted by the multiplexer 943 based on these values is summarized in Table 1:

The value outputted by the multiplexer 943 is outputted to an adder 945 such as a carry save adder. The adder 945 also receives the results of the previous processing element (i.e., outputted from a similar adder circuit therein) and adds the previous results to the output of the multiplexer 943 shifted left 2(L-1) bits. (The first processing element 930-1 simply stores the value outputted from the multiplexer 943, as there is no previous result to be added.) This sum is then outputted to the adder 945 of the next processing element on the next clock. Thus, on each clock, the same pair of elements and their partial product propagate to a register or processing element and adder circuit, respectively, of a subsequent multiplication level until the last processing element is reached. At this point, if carry save adders are used, then any left over sum and carry bits are added to the result in the adder 931.

Each multiplication level may simultaneously process a different pair of elements. For example, on the clock after the first multiplication level 920-1, 930-1 processes the first two elements (e.g., u.sub.11, v.sub.11), the first multiplication level 920-1, 930-1 receives and processes the next two elements (e.g., u.sub.21, v.sub.12). Meanwhile, the second multiplication level 920-2, 930-2 processes the first two elements (i.e., u.sub.11, v.sub.11). This feature, which is analogous to the operation of an assembly line, is referred to as "pipelining". On the clock after the adder circuit 931 adds any left over carry and sum bits to the product of the first two elements, the partial product, sum and carry bits of the next two elements are inputted to the adder circuit 931.

An inspection of the sequences inputted to the register column circuit 910 and the multiplication column circuit 930 reveals that the following sequence of products are sequentially outputted from the adder circuit 931: v.sub.11 u.sub.11, v.sub.12 u.sub.21, v.sub.13 u.sub.31, . . . , v.sub.1j u.sub.i1. The accumulator 932 therefore adds up each of these elements to produce the element w.sub.11 of the matrix product W of U and V. By appropriate selection of sequences inputted to the register and multiplication column circuits 910 and 930, it is possible to sequentially output the elements of one or more columns or rows of the product matrix W.

Returning to FIG. 3, Table 2 shows exemplary sequences inputted to each circuit 220-1, 220-2,220-3 and 220-4.

If the circuits 220-1, . . . ,220-4 receive the inputs shown in Table 2, then the circuits 230-1, . . . , 230-4 may illustratively receive the sequences shown in Table 3.

Illustratively, the circuits 230-1, . . . ,230-4 are column multiplication circuits and the circuits 220-1, . . . ,220-4 are column register circuits. Alternatively, the circuits 220-1, . . . ,220-4 multiplication column circuits and the circuits 230-1, . . . ,230-4 are register column circuits. Thus, the 1-D DCT stage has 2K=4 column multiplication circuits. In the former case, the circuits 230-1, . . . ,230-4 output values shown in Table 4.

Thus, K=2 column multiplication circuits 230-1 and 230-2 output the rows of the matrix Y.sub.o and K=2 column circuits 230-3 and 230-4 output the rows of the matrix Y.sub.e. In the case that the column circuits 220-1, . . . ,220-4 are column register circuits, then one of the column circuits 220-1, 220-2 and one of the column circuits 220-3, 220-4 may be omitted. If the column circuits 220-2 and 220-4 are omitted, the column circuit 220-1 is connected to the column circuit 230-2 in a similar fashion as it is connected to the column circuit 230-1. Likewise, the column circuit 220-3 is connected to the column circuit 230-4 in a similar fashion as it is connected to the column circuit 230-3. In an analogous fashion, in the case that the circuits 230-1, . . . ,230-4 are the column register circuits, one of the column circuits 230-1, 230-2 and one of the column circuits 230-3, 230-4 may be omitted.

The performance of a 1-D DCT circuit depends on how many clocks are required for receiving the input matrix elements. As shown, each column circuit receives a total of eight matrix elements, one per cycle, and thus requires eight clocks to compute the 1-D DCT of an input matrix. A comparable conventional 1-D DCT circuit such as shown in FIG. 1 with four multiplication column circuits requires sixteen clocks to receive the inputted matrices. Thus, using a decimation technique, a 1-D DCT processing stage may be provided which operates at approximately twice the speed of the conventional 1-D DCT processing stage. Alternatively, a 1-D DCT processing stage utilizing a decimation technique may be provided in which the individual processing elements of each column multiplication circuit need only operate at half the speed of the processing elements in a conventional 1-D DCT processing stage.

FIG. 6 shows an embodiment of the pre-processor circuit 950 capable of producing the sequences inputted to the circuits 220-1, . . . , 220-4 (FIG. 3). As shown, the pre-processor circuit 950 has four registers 955-1, 955-2, 955-3, 955-4 serially connected to form a shift register 955. Each column of elements of the matrix X (used to form the matrices A.sub.f and A.sub.r) is successively shifted into in the shift register 955 in the order x.sub.11, x.sub.21, . . . , x.sub.41, x.sub.12, x.sub.22, . . . , x.sub.24, . . . , x.sub.44.

The pre-processor 950 also has two ring registers 961 and 962. The ring register 961 includes the registers 960-4 and 960-3 interconnected in a ring configuration. That is, the output of the register 960-4 is connected to the input of the register 960-3 and the output of the register 960-3 is connected to the input of the register 960-4. Similarly, the ring register 962 includes the registers 960-2 and 960-1 interconnected in a ring configuration. After an entire column is shifted into the column register 955, the column elements may be transferred to one of the two ring registers 961, 962. As shown, the element in the register 955-4 is transferred into the register 960-4, the element in the register 955-3 is transferred into the register 960-3, the element in the register 955-2 is transferred into the register 960-2 and the element in the register 955-1 is transferred into the register 960-1.

One register of each ring register 961 and 962, e.g., the registers 960-4 and 960-1, respectively, serves as the output of the ring register 961 or 962. Once in the ring register 961 or 962, the matrix elements may be rotated around the registers of the ring register so that each element is outputted from the ring register 961 or 962 (via the register 960-4 or 960-1) at least once.

The output of the ring registers 961 and 962 are connected to an adder circuit 963 and a subtraction circuit 964. The adder circuit 963 outputs the sum of the elements outputted by the ring registers 961, 962 to produce an element of the matrix A.sub.f. The subtraction circuit 964 outputs the difference of the elements outputted by the ring register 962 and the ring register 961 to produce an element of the matrix A.sub.r. Thus, it is possible to simultaneously generate the elements a.sub.11 and a.sub.31 by outputting the element x.sub.41 from the ring register 961 and the element x.sub.11 from the ring register 962. Likewise, the elements a.sub.21 and a.sub.41 can be simultaneously generated by outputting the element x.sub.31 from the ring register 961 and the element x.sub.21 from the ring register 962. Furthermore, the elements a.sub.11, a.sub.31 (and/or a.sub.21, a.sub.41) may be repeatedly generated a number of times by simply repeatedly outputting the same data in the ring registers 961, 962. Alternatively, or in addition, another column of the matrix X may be loaded into the ring registers to generate different elements of the matrices A.sub.f and A.sub.r. As shown, the ring registers output each element therein only once so as to produce a sequence of elements of the matrix A.sub.f and a sequence of elements of the matrix A.sub.r without any repetitions.

FIG. 7 shows an alternative embodiment of the 1-D DCT processing stage 300 having 2K=2 column multiplication circuits. As shown, Q=1 column circuit 320-1 is provided for receiving Q=1 sequence of column elements of the matrix A.sub.f and Q=1 column circuit 320-2 is provided for receiving Q=1 sequence of column elements of the matrix A.sub.r. Likewise, P=1 column circuit 330-1 is provided for receiving P=1 sequence of row elements of the matrix C.sub.1 and P=1 column circuit 330-2 is provided for receiving P=1 sequence of row elements of the matrix C.sub.2. The particular inputted sequences are shown in Table 5.

Illustratively, the 2P=2 column circuits 330-1 and 330-2 are the 2K=2 column multiplication circuits and the column circuits 320-1 and 320-2 are column register circuits. In such a case, the circuits 330-1 and 330-2 produce the output shown in Table 6.

Thus, the column circuit 330-1 outputs, in sequence, the elements of the first column of the matrix Y.sub.o followed by the second, third and fourth columns of the matrix Y.sub.o. In a similar fashion, the column circuit 330-2 outputs the elements of the first column of the matrix Y.sub.e followed by the second, third and fourth columns of the matrix Y.sub.e.

The performance of the 1-D DCT processing stage 300 is now analyzed. Each of the column circuits 320-1, 320-2, 330-1 and 330-2 receives a sequence of sixteen elements, one element per cycle. Thus, sixteen cycles are required for processing the matrices. If the processing must be performed in a particular time interval, the processing elements of the column circuits 330-1 and 330-2 must operate at twice the speed of the processing elements in the 1-D DCT processing stage 200 of FIG. 3. However, the 1-D DCT processing stage 300 requires only two column multiplication circuits. In comparison to a conventional circuit, the 1-D DCT processing stage 300 operates at the same speed as a conventional 1-D DCT processing stage with four column multiplication circuits despite having only two column multiplication circuits. Thus, the 1-D DCT processing stage 300 offers the same performance as a conventional 1-D DCT processing stage yet uses less space.

The pre-processing circuit 950 of FIG. 6 may be used to generate the sequences inputted to the column circuits 320-1 and 320-2. In this case, the ring registers 961 and 962 are used to output the elements therein twice. For example, the ring register 961 and 962 first output the elements x.sub.41 and x.sub.11, respectively to produce the elements a.sub.11 and a.sub.31. Then, the ring registers 961 and 962 output the elements x.sub.31 and x.sub.21 to produce the elements a.sub.21 and a.sub.41. Afterwards, the ring registers 961 and 962 once again output the elements x.sub.41 and x.sub.21, respectively to produce the elements a.sub.11 and a.sub.31. Likewise, the ring registers subsequently output the elements x.sub.31 and x.sub.21 to produce the elements a.sub.21 and a.sub.41. The next column of elements of the matrix X x.sub.12, x.sub.22, x.sub.32, x.sub.42 is then loaded into the ring registers 961 and 962 and the above process is repeated.

The 1-D DCT processing stages 300 (FIG. 7) and 200 (FIG. 3) could also be used for performing a 8.times.8 1-D DCT that has been reduced to a 4.times.4 DCT. Using a decimation technique, an 8.times.8 1-D DCT Y=CX is reduced to two 4.times.4 1-D DCT's Y.sub.e =C.sub.1 .multidot.A.sub.f and Y.sub.o =C.sub.2 .multidot.A.sub.r where: ##EQU14## As before, each a.sub.ij of the matrix A.sub.f is given by:

and each a.sub.ij of the matrix A.sub.r is given by:

In the case that the 1-D DCT processing stage 200 of FIG. 3 is used, the 1-D DCT stage 200 may receive the input sequences of Table 7 and output the sequences of Table 8.

Each column multiplication circuit 230-1, 230-2 alternately outputs the elements of two different rows of the matrix Y.sub.o and each column multiplication circuit 230-3, 230-4 alternately outputs the elements of two different rows of the matrix Y.sub.e. The 1-D DCT processing stage utilizes sixty-four clocks in processing the data yet only requires four column multiplication circuits 230-1, . . . , 230-4. This processing speed can only be obtained using a conventional 1-D processing DCT stage with at least eight column multiplication circuits.

In the case that the 1-D DCT processing stage 300 (FIG. 7) is used, the 1-D DCT processing stage 300 may receive the inputted sequences of Table 9 and output the sequences of Table 10.

The processing requires one hundred twenty-eight clocks.

FIG. 8 shows yet another embodiment of the 1-D DCT processing stage 400 having 2K=8 column multiplication circuits 430-1, 430-2, 430-3, 430-4, 430-5, 430-6, 430-7 and 430-8 which illustratively receive 2P (where P=4) sequences of DCT cosine coefficient matrix elements. (Alternatively, the 2K=8 column multiplication circuits may receive 2Q sequences of elements of the matrices A.sub.f and A.sub.r, where Q=4.) Two column register circuits 420-1 and 420-2 are also provided for receiving 2Q (where Q=1) sequences of elements of the matrices A.sub.f and A.sub.r. Tables 11 and 12 summarize illustrative input and output sequences, respectively, for the 1-D DCT processing stage 400.

Thus, each column multiplication circuit 430-1, . . . , 430-4 illustratively outputs one row of the matrix Y.sub.o and each column multiplication circuit 430-5, . . . , 430-8 illustratively outputs one row of the matrix Y.sub.e. The 1-D DCT processing stage utilizes thirty-two clock cycles to perform the 1-D DCT but requires eight column multiplication circuits 430-1 . . . , 430-8.

FIG. 9 shows a pre-processor circuit 850 for an 8.times.8 1-D DCT stage 200, 300 or 400. The pre-processor 850 is analogous to the pre-processor 950 and thus is only described briefly. Each column of elements of an inputted matrix, e.g., the matrix X, is successively shifted into the shift register 855. The individual elements of a column stored in the registers 855-1, 855-2, 855-3, 855-4, 855-5, 855-6, 855-7 and 855-8 of the shift register 855 are transferred to corresponding registers 860-1, 860-2, 860-3, and 860-4 and 860-5, 860-6, 860-7, and 860-8 of ring registers 862 and 861, respectively.

The ring register 861 sequentially outputs each element stored therein one element per cycle. Simultaneously, the ring register 862 outputs the elements stored therein one element per cycle. Each element outputted by the ring registers 861 is added to a corresponding element outputted by the ring register 862 in the adder circuit 863 to produce the elements of a column of the matrix A.sub.f. Likewise, each element outputted by the ring register 861 is subtracted, in a subtraction circuit 864, from a corresponding element simultaneously outputted by the ring register 862 to produce the elements of a column of the matrix A.sub.r.

The elements stored in the ring registers 861 and 862 propagate around the individual registers 860-5, . . . , 860-8 or 860-1, . . . , 860-4. Thus, after outputting each element, the elements in the ring register 861 or 862 have returned to their original registers 860-5, . . . ,860-8 or 860-1, . . . ,860-4. It is thus possible to repeatedly output the elements from each ring register 861 and 862 a desired number of times. Meanwhile, another column of elements of the matrix X may be shifted into the shift register 855 for transfer into the ring registers 861 and 862.

FIG. 10 shows an architecture 500 according to another embodiment of the present invention for performing a 2-D IDCT. An N.times.N transformed matrix Z is divided into two N/2.times.N matrices Z.sub.o and Z.sub.e where Z.sub.o contains the odd rows of Z and Z.sub.e contains the even rows of Z. Each matrix Z.sub.o and Z.sub.e is simultaneously fed into a 1-D IDCT processing stage 510 which also receives the N/2.times.N/2 IDCT cosine coefficient matrices C.sub.1.sup.t and C.sub.2.sup.t, where C.sub.1.sup.t and C.sub.2.sup.t are simply the transpose of C.sub.1 and C.sub.2, respectively. The 1-D IDCT processing stage outputs the matrices R and T where R=C.sub.1.sup.t Z.sub.o and T=C.sub.2.sup.t Z.sub.e. A post-processor stage 520 receives the matrices R and T and outputs the matrices Y.sub.f =R+T and Y.sub.r =R-T where Y.sub.f contains the front rows of the matrix Y=ZC.sup.t, and Y.sub.r contains the recent rows of the matrix Y. The matrices Y.sub.f and Y.sub.r are received in transpose memory 530 which outputs the matrices Y.sub.o.sup.t and Y.sub.e.sup.t where Y.sub.o.sup.t contains the even rows of a matrix Y.sup.t (the transpose matrix of Y) and Y.sub.e.sup.t contains the odd rows of Y.sup.t. In a similar fashion as before, Y.sub.o.sup.t, Y.sub.e.sup.t, C.sub.1.sup.t and C.sub.2.sup.t are received in a 1-D IDCT processing stage 540 (similar to 1-D IDCT processing stage 520) which outputs the matrices R' and T', where R'=C.sub.1.sup.t Y.sub.o.sup.t and T'=C.sub.2.sup.t Y.sub.e.sup.t. The matrices R' and T' are received in a post-processor stage 550 (which is similar to the post-processor stage 520) which outputs the matrices X.sub.f (front rows of the matrix X) and X.sub.r (recent rows of the matrix X) where X.sub.f =R'+T' and X.sub.r =R'-T'.

The 1-D IDCT processing stages 510 and 540 are identical to the 1-D DCT processing stages 120 and 150 of FIG. 2 except that transposed cosine coefficient matrices C.sub.1.sup.t and C.sub.2.sup.t are used instead of cosine coefficient matrices C.sub.1 and C.sub.2. Thus, the 1-D IDCT processing stages 510 and 540 may be implemented using the circuits 200 (FIG. 3) 300 (FIG. 7) or 400 (FIG. 8). For example, suppose an 8.times.8 1-D IDCT is to be performed on a transformed matrix Z. Then Z.sub.o, Z.sub.e, Y.sub.f, Y.sub.r, R, and T, may be written in matrix form as: ##EQU15##

Each element y.sub.ij, i=1,1, . . . ,N/2, j=1,2, . . . ,N, of the matrix y.sub.f is given by Y.sub.ij =r.sub.ij +t.sub.ij and each element y.sub.ij, i=N/2+1, N/2+2, . . . ,N, j=1,2, . . . ,N, of the matrix Y.sub.r is given by y.sub.ij =r.sub.(i-N/2)j -t.sub.(i-N/2)j. Table 13 contains illustrative input sequences which may be fed to the 1-D stage 200 shown in FIG. 3 to produce the output sequences shown in Table 14.

FIG. 11 shows an illustrative post-processing circuit 600 which may be used as the post-processing stage 520 or 550 in the circuit shown in FIG. 10. The post-processing circuit 600 illustratively includes an addition circuit 610-1 which adds together elements of the matrix R (e.g., outputted from the column multiplication circuit 230-1) with corresponding elements of the matrix T (e.g., outputted from the column multiplication circuit 230-3). The post-processing circuit 600 also includes a subtraction circuit 620-1 which subtracts elements of the matrix T from corresponding elements of the matrix R simultaneously inputted to the post-processing circuit 600. As shown, the addition circuit 610-1 outputs elements of the matrix Y.sub.f and the subtraction circuit outputs elements of the matrix Y.sub.r.

(Illustratively, the post-processing circuit 600 has K addition-subtraction circuit configurations as described above. Each of these addition-subtraction circuit configurations, such as addition 610-K and subtraction circuit 620-K, receives the output of a different pair of column multiplication circuits of the 1-D IDCT processing stage. For example, the input 630-1 receives the elements outputted from the column multiplication circuit 230-1, the input 630-2 receives the elements outputted from the column multiplication circuit 230-2, the input 630-3 receives the elements outputted from the column multiplication circuit 230-3 and the input 630-4 receives the elements outputted from the column multiplication circuit 230-4.)

FIG. 12 shows another illustrative post-processing circuit 700 which may be used as the post processing circuit 520 or 550 of FIG. 10. The post-processing circuit is designed to utilize fewer addition and subtraction circuits than the circuit 600 (FIG. 11). This is achieved by providing a first group of K registers for storing the elements of the matrix R and a second group of K registers for storing the elements of the matrix T outputted from each multiplication column circuit of the 1-D IDCT processing stage 510 or 540.

The embodiment of the post-processing circuit 700 shown in FIG. 12 is illustratively designed to be used with the 1-D processing stage 200 shown in FIG. 3. The post-processing circuit 700 includes four registers 710-1, 710-2, 710-3, and 710-4. That is, the circuit 700 has a first group of K=2 registers 710-1 and 710-2 for storing elements of the matrix R and a second group of K=2 registers 710-3 and 710-4 for storing elements of the matrix T outputted by the circuit 200 (FIG. 3). Each of the registers 710-1, 710-2, of the first group is connected to a corresponding column multiplication circuit 230-1 and 230-2 (FIG. 3) which outputs elements of the matrix R. Likewise, each of the registers 710-3, and 710-4 of the second group is connected to a corresponding column multiplication circuit 230-3, and 230-4 (FIG. 3) which outputs elements of the matrix T. The outputs of the registers 710-1 and 710-2 of the first group are connected to corresponding inputs of a multiplexer 720-1. Likewise, the outputs of the registers 710-3 and 710-4 of the second group are connected to corresponding inputs of a multiplexer 720-2. The output of the multiplexer 720-1 is connected to an input of an addition circuit 730 and a subtraction circuit 740. Similarly, the output of the multiplexer 720-2 is connected to an input of the addition circuit 730 and an input of the subtraction circuit 740.

Suppose the post-processor circuit 700 is used with a 1-D IDCT stage 200 to compute an 8.times.8 IDCT as discussed above. (The inputs to the registers 710-1 to 710-4 are summarized in Table 14). Every four cycles of the circuit 200, each of the registers 710-1 to 710-4 receives one element. The multiplexer 720-1 alternately selects the value stored in each register 720-1, 720-2 of the first group of K=2 registers. Simultaneously, the multiplexer 720-2 alternately selects the value stored in each of the second group of K=2 registers 720-3, 720-4. To that end, a select signal is applied to each multiplexer 720-1 and 720-2 to simultaneously select the values stored in the registers 710-1 and 710-3. A select signal is also subsequently applied to each each multiplexer 720-1 and 720-2 to simultaneously select the values stored in the registers 710-2 and 710-4. The values of the selected registers (i.e., 710-1 and 710-3 or 710-2 and 710-4) are simultaneously inputted to the addition circuit 730 to produce an element of the matrix Yf and to the subtraction circuit 740 to produce an element of the matrix Y.sub.r.

Because each column multiplication circuit 230-1, . . . , 230-4 (FIG. 3) requires four cycles to output each element of the matrix R or T, the multiplexers 720-1, 720-2, addition circuit 730 and subtraction circuit 740 need only operate at half the speed of the 1-D processing stage 200. For instance, a select signal may be applied to each multiplexer 720-1 and 720-2 every two cycles for selecting appropriate inputs to the addition circuit 730 and subtraction circuit 740. Furthermore, only one addition circuit 730 and one subtraction circuit 740 are required to compute the elements of the matrix Y.

In short, a DCT/IDCT circuit is disclosed which utilizes a combined decimation technique and pipelining technique. A DCT circuit according to the invention has a pre-processing stage receiving an N.times.N input matrix X and outputting two N/2.times.N matrices A.sub.f and A.sub.r. The DCT circuit also has a 1-D DCT processing stage which receives the matrices A.sub.f and A.sub.r and outputs the matrices Y.sub.o =C.sub.1 .multidot.A.sub.f and Y.sub.e =C.sub.2 .multidot.A.sub.r where C.sub.1 and C.sub.2 are N/2.times.N/2 DCT cosine coefficient matrices. The DCT circuit according to the present invention therefore has the same performance as a conventional DCT circuit yet requires fewer column multiplication circuits in the 1-D DCT processing stages, thereby occupying less area on an IC chip. Specifically, a 1-D processing stage with 2K column multiplication circuits may be provided which utilizes N.sup.3 /2K clocks for receiving each element of an inputted data sequence for processing.

The present invention has been disclosed with reference to specific illustrative embodiments. Numerous other embodiments may be devised by those having ordinary skill in the art without departing from the spirit and scope of the following claims.