Real Time Two-Dimensional Discrete Cosine Transform/Inverse Discrete Cosine Transform Circuit

1. Field of Invention

The present invention relates to an apparatus for digital signal processing, and more specifically, to a real time two-dimensional discrete cosine transform (DCT)/inverse discrete cosine transform (IDCT) circuit suitable for implementing in a very large scale integrated (VLSI) circuit.

2. Description of Related Art

Techniques for data compression have played an important role in an image-processing system due to increasingly large amounts of video data to be processed. Among all techniques for data compression, data coding or transformation is the most difficult part. The difficulties result from, in general, the complexity of implementing the coding or transform algorithm in a circuit as well as the inefficiency of the circuit. Since the DCT/IDCT process utilizes orthogonal transform techniques which have higher transformation efficiency, it has been widely used in video systems for data coding. Therefore, in order to satisfy requirements of some international video standards, such as Joint Picture Expert Group (JPEG), Motion Photography Expert Group (MPEG) and H.261, a fast real-time 2-D DCT/IDCT circuit is a great need.

In order to have input/output data maintained in continuity, a 2-D DCT/IDCT circuit can be formed by connecting two 1-D DCT/IDCT processors in series. Or in order to attain a higher transform efficiency, a 2-D transform algorithm may be directly implemented in a circuit. The latter is not practical since the hardware design is very complicated and the circuit dimension will be too large. Therefore, almost all conventional 2-D DCT/IDCT circuits, such as that disclosed in U.S. Pat. Nos. 4,791,598 and 5,249,146, utilize the structure having two 1-D processors connected in series.

FIG. 1 (Prior Art) depicts a 2-D DCT/IDCT circuit consisting of two 1-D processors. The DCT/IDCT circuit of FIG. 1 (Prior Art) performs two successive 1-D DCT/IDCT processes to achieve a 2-D transformation. The circuit includes a 1-D DCT/IDCT processor 15, a transpose buffer 16, another 1-D DCT/IDCT processor 17 and another transpose buffer 18. Two 1-D DCT/IDCT processes of a matrix X and its transpose matrix Z are carried out in 1-D DCT/IDCT processors 15 and 17 respectively. In order to keep the output data in correct order, two transpose buffers 16 and 18 are provided to interchange column elements and row elements of the matrices. There are two similar process stages in the circuit of FIG. 1 (Prior Art). That is, the function of a first stage consisting of 1-D DCT/IDCT processor 15 and transpose buffer 16 is similar to that of a second stage consisting of 1-D DCT/IDCT processor 17 and transpose buffer 18. Therefore, a minimal circuit dimension can be obtained by establishing a feedback loop from transpose buffer 16 to 1-D DCT/IDCT processor 15 and skipping elements of the second stage, i.e., 1-D DCT/IDCT processor 17 and transpose buffer 18.

Because the above-mentioned circuit has two operating stages, the executing time will be too long to carry out a real time operation. That is, even though the circuit dimension can be reduced, the circuit shown in FIG. 1 can not satisfy the high speed requirements of video systems.

Accordingly, the present invention provides a 2-D DCT/IDCT circuit consisting of elements operated at various rates for high speed data transformation thus achieving the real time requirement.

The present invention also provides a 2-D DCT/IDCT circuit having minimal elements to decrease the circuit dimension and facilitate implementation in a VLSI circuit.

A 2-D DCT/IDCT circuit according to the present invention comprises a rate buffer, a multiplexer, a one-dimensional DCT/IDCT processor, a transpose buffer and an inverse rate buffer. In the present invention, the data input rate of the rate buffer and output rate of the inverse rate buffer are at a first rate, while the transform process, which is carried out between the rate buffer and the inverse rate buffer by the 1-D DCT/IDCT processor, is at a second rate. Since the second rate is approximately two times the first rate, the 2-D DCT/IDCT circuit can satisfy the requirements of high speed operation. Moreover, since the 2-D DCT/IDCT circuit according to the present invention provides a specific arrangement of the order of input/output data, the hardware structure is simplified so that it is easy to integrate into a VLSI circuit.

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings, wherein like reference numerals represent like parts, in which:

FIG. 1 (Prior Art) is a block diagram of a prior art 2-D DCT/IDCT circuit;

FIG. 2 is a block diagram of a 2-D DCT/IDCT circuit according to the present invention;

FIG. 3 is a timing diagram of input/output data of the rate buffer in FIG. 2;

FIG. 4 is a timing diagram of input/output data of the multiplexer in FIG. 2;

FIG. 5 is a timing diagram of input/output data of all elements of the circuit in FIG. 2;

FIG. 6 is a timing diagram of input/output data of the inverse rate buffer in FIG. 2; and

FIG. 7 is a circuit diagram illustrating the rate buffer of FIG. 2.

The 2-D DCT/IDCT circuit of a preferred embodiment of the present invention is depicted in FIG. 2. The circuit comprises a rate buffer 10, a multiplexer 11, a one-dimensional (1-D) DCT/IDCT processor 12, a transpose buffer 13 and an inverse rate buffer 14.

The circuit of the present invention has an input data matrix X and an output data matrix Y. If matrix X has a dimension of N.times.N, for example, N=8, the input data matrix can be represented as ##EQU1##

Thus, the output matrix also has a dimension of N.times.N, i.e., matrix Y can be represented as ##EQU2##

Therefore, the input data of rate buffer 10 can be a one-dimensional sequence from input matrix X, for example, a row sequence of X.sub.00, X.sub.01, X.sub.02, X.sub.03, X.sub.04, X.sub.05, X.sub.06, X.sub.07, X.sub.10, X.sub.11, X.sub.12, X.sub.13, . . . , X.sub.20, X.sub.21, . . . , X.sub.70, X.sub.71, X.sub.72, X.sub.73, X.sub.74, X.sub.75, X.sub.76 and X.sub.77. The output data from inverse rate buffer 14 can also be a one-dimensional sequence of Y.sub.00, Y.sub.01, Y.sub.02, Y.sub.03, Y.sub.04, Y.sub.05, Y.sub.06, Y.sub.07, Y.sub.10, Y.sub.11, Y.sub.12, Y.sub.13, . . . , Y.sub.20, Y.sub.21, . . . , Y.sub.70, Y.sub.71, Y.sub.72, Y.sub.73, Y.sub.74, Y.sub.75, Y.sub.76 and Y.sub.77. All the elements of the 2-D DCT/IDCT circuit of the invention will be explained as follows.

Rate buffer 10 of the present invention provides a data input rate of a first rate and a data output rate of a second rate. That is, the aforementioned input data sequence is input to rate buffer 10 through port 10a at the first rate. Then a rearranged data sequence is output to multiplexer 11 from rate buffer 10 at the second rate. The second rate is preferably two times faster than the first rate. The various data input/output rates can be achieved by providing driving signals of different frequencies at the input end and output end of rate buffer 10. Therefore, a two-speed transform operation can be achieved inside the 2-D DCT/IDCT circuit of the present invention.

Multiplexer 14 provides two data paths for data transmission. A first data path 11b is provided for the rearranged input data sequence from rate buffer 10. This data path is active during a first time period. When a 1-D transformation of input data matrix X has been finished, a second time period begins and a second data path 11a is provided instead of the first data path by multiplexer 14 for transmitting another data sequence from transpose buffer 13.

1-D DCT/IDCT processor 12 is a 1.times.N two-speed processor whose latency is not greater than 2N-1. For example, if N is 8, a maximal processing time of 15 clock cycles is required. Furthermore, the throughput rate of 1-D DCT/IDCT processor 12 is approximate to the second rate. Data transmitted through the data paths of multiplexer 11 is transformed in 1-D DCT/IDCT processor 12. The structure of 1-D DCT/IDCT processor 12 has been disclosed in several articles and papers, and is known to those skilled in the art, the description is omitted here.

Transpose buffer 13 has a dimension of N.times.N. The data transformed by 1-D DCT/IDCT processor 12 is stored in transpose buffer 13 during the first time period. The stored data, which is denoted as matrix Z, is transposed into another data matrix Z.sup.t. Matrices Z and Z.sup.t are in 1-D format like that of the sequence from matrix X, as is stated above. Then during the second time period, matrix Z.sup.t is sent to 1-D DCT/IDCT processor 12 over second data path 11a of multiplexer 11.

As to inverse rate buffer 14, a data input rate of the second rate and a data output rate of the first rate must be consistent with rate buffer 10. During the second time period, data from 1-D DCT/IDCT processor 12 is stored in inverse rate buffer 14, and then output as data matrix Y at the first rate. The various data input/output rates can be achieved by providing driving signals of different frequencies at the input end and output end of inverse rate buffer 14.

Accompanying with the timing diagrams from FIG. 3 to FIG. 6, the operation of the 2-D DCT/IDCT circuit of the present invention will be described through an example which has the input and output data dimensions of 8.times.8.

Referring first to FIG. 3, timing relationships between the input data and output data of rate buffer 10 are illustrated with a reference timing coordinate whose unit time scale is 1/f. The second line in FIG. 3 depicts timing of the input data sequence from matrix X. In order to prevent data conflict, rate buffer 10 outputs data to multiplexer 11 through first data path 11b only after the first 56 elements of the input data sequence have been stored. That is, as is depicted in the second and third lines of FIG. 3, only when element X.sub.70 of the input data sequence is about to be stored in rate buffer 10, is the first element X.sub.00 of the sequence sent out from rate buffer 10. Obviously, data input rate f is half of the output rate in the drawing.

Next referring to FIG. 4, the timing relationships between first data path 11b and second data path 11a of multiplexer 11 are illustrated. During the first time period, data from rate buffer 10, i.e., the sequence consisting of X.sub.00 to X.sub.77, is transmitted through first data path 11b and output to 1-D DCT/IDCT processor 12, as is shown in the first and third lines of FIG. 4. When the sequence consisting of X.sub.00 through X.sub.77 has been output to 1-D DCT/IDCT processor 12, first data path 11b is closed while second data path 11a-is provided for the sequence of Z.sub.00 through Z.sub.77. The sequence consisting of Z.sub.00 through Z.sub.77 from transpose buffer 13 is transmitted through second path 11a to the 1-D DCT/IDCT processor 12 during the second time period, as shown in the second and third line of FIG. 4.

In the present invention, during the first time period, 1-D DCT/IDCT processor 12 has input data at input port 12a in the order of X.sub.0c, X.sub.1c, X.sub.2c, X.sub.3c, X.sub.4c, X.sub.5c, X.sub.6c and X.sub.70 with c from 0 to 7. The input data is transformed and output to transpose buffer 13. While during the second time period, data sequence of Z.sub.R0, Z.sub.R1, Z.sub.R2, Z.sub.R3, Z.sub.R4, Z.sub.R5, Z.sub.R6 and Z.sub.R7 with R from 0 to 7 is input into 1-D DCT/IDCT processor 12 from transpose buffer 13 through second data path 11a to generate output data sequence of Y.sub.R0, Y.sub.R1, Y.sub.R2, Y.sub.R3, Y.sub.R4, Y.sub.R5, Y.sub.R6 and Y.sub.R7 with R from 0 to 7.

FIG. 5 is a timing diagram illustrating the relationships among sequences X, Y and Z between the output of rate buffer 10 and input of inverse rate buffer 14. The first line of FIG. 5 shows the timing of data sequence of X.sub.00 through X.sub.77 from rate buffer 10. The data sequence is sent to 1-D DCT/IDCT processor 12 through multiplexer 12, as shown in the third line. After an executing time delay, the output data of first dimensional transformation from 1-D DCT/IDCT processor 12 is written into transpose buffer 13 as the sequence of Z.sub.00 through Z.sub.77. When the second time period begins, the sequence of Z.sub.00 through Z.sub.77 is read out by 1-D DCT/IDCT processor 12 for the second dimensional transformation, as is shown in the second line of FIG. 5. Then the final output sequence of Y.sub.00 through Y.sub.77 is acquired by inverse rate buffer 14 from 1-D DCT/IDCT processor 12, as shown in the last line of FIG. 5.

The final data sequence of the 2-D DCT/IDCT circuit, i.e., sequence Y.sub.00 through Y.sub.77, is output by inverse rate buffer 14 at the first rate. Referring to FIG. 6, in which the top line represents a reference time coordinate, the input data timing and the output data timing of inverse rate buffer 14 are also illustrated. The reference timing coordinate has a unit time scale of 1/f. Obviously, the sequence consisting of Y.sub.00 through Y.sub.77 is input into inverse rate buffer 14 at a rate of 2f, which is the second rate. While the data output from inverse rate buffer 14 is at a rate of f, which is the first rate. Since the output rate of inverse rate buffer 14 is the same as the input rate of rate buffer 10, as shown in FIG. 3, the input/output timing of the 2-D DCT/IDCT circuit can be consistent.

In order to obtain the various data input/output rates, rate buffer 10 and inverse rate buffer 14 of the present invention can be dual-port devices. For example, a dual-port static random access memory (SRAM), as is shown in FIG. 7, can be utilized as rate buffer 10. Referring to FIG. 7, two counters 101 and 103 are provided and connected to the input port and output port of dual-port SRAM 102 respectively. Counter 101, which is controlled by a write-enabling signal Bwrite through, is driven by a clock signal ckf which has a frequency of f. However, instead of signal ckf, counter 103, which is controlled by a read-enabling signal Bread, is driven by signal ck2f which has a frequency of 2f. Therefore, through the control of address signals WA and RA from counters 101 and 103, dual-port SRAM 102 can read in sequence X at the first rate and output sequence X' at the second rate. Moreover, since the wiring between the counters and the input/output ports of dual-port SRAM 102 can be arranged as desired, there can be several address modes. In other words, the order of the output sequence needs not to be the same as that of the input sequence. Inverse rate buffer 14 can also comprise a dual-port SRAM and two counters, while the signals which drive the input and output counters have an inverse frequency relationship as in the case of rate buffer 10.

Through the two-speed operation of the 2-D DCT/IDCT circuit, a real time transformation can be achieved. Furthermore, as compared with the conventional circuit of FIG. 1, rate buffer 10 and multiplexer 11 are provided in the present invention to replace the function of 1-D DCT/IDCT processor at the second stage. Since a 1-D DCT/IDCT processor has a circuit dimension approximately 10 times that of a rate buffer plus a multiplexer, the circuit dimension of the present invention can be largely reduced, and the hardware design is much easier. Therefore, the present invention is more suitable for VLSI implementation.