Patent Publication Number: US-6038580-A

Title: DCT/IDCT circuit

Description:
FIELD OF THE INVENTION 
     The present invention relates to a DCT/IDCT circuit, which is suitable for VLSI implementation and has the advantages of simple data routing, regular structure and modular design. 
     BACKGROUND OF THE INVENTION 
     In recent years, many proposed image compression standards have been DCT based algorithms, such as MPEG-1, MPEG-2, H.261, H.263, JPEG and so on. Consequently, the discrete cosine transform (DCT) has become a primitive function in image compression chips. Since DCT needs a large amount of multiplication, large hardware costs are incurred for real time applications. 
     The Discrete Cosine Transform (DCT) is an orthogonal transform consisting of a set the basis of which is sampled cosine functions. A generalized two dimension DCT is defined as below: ##EQU1## 
     These two equations are standard separable two-dimensional even cosine transforms and are implemented by row-column decomposition methods in traditional DCT/IDCT circuits, wherein the N×N 2-D DCT can be achieved by a N-point 1 -D DCT. The forward and inverse 1 -D DCT are given by: ##EQU2## 
     So, various fast algorithms have been introduced for reducing the amount of multiplication involved in this transform. These algorithms usually form a butterfly structure in a flow diagram. This butterfly structure has many drawbacks in IC implementation, such as irregular structure and complex data routing which may require large silicon area and longer design time. Moreover, since multiple stages of multipliers are accompanied by rounding or truncation in finite precision arithmetic, fixed internal precision can cause the resulting accuracy to be seriously reduced. 
     As a result of much effort, several designs on DCT have been developed in past decades. Peter. A. etc., in &#34;A High Performance Full-Motion Video Compression Chipset&#34;, published in &#34;IEEE Transaction Circuits and Systems For Video Technology&#34; Vol.2 NO.2 June 1992, pp. 111-122, presented the DCT circuit implemented by 4-point inner product and Wallace tree skill and disclosed that 20% of the hardware could be saved. Min-Ting Sun etc., in &#34;VLSI Implementation of 16×16 Discrete Cosine Transform&#34; published in &#34;IEEE Transaction Circuits and Systems&#34; Vol.36 NO.4 April 1989 pp.610-617, showed a concurrent architecture on DCT with 32 PEs and a RAM performing 16×16 transposition by exploiting distribute arithmetic. A SIMD-systolic architecture for DCT realized by butterfly algorithm is presented in &#34;A SIMD-Systolic Architecture and VLSI Chips for the two dimensional DCT and IDCT&#34; published in &#34;IEEE Transaction Consumer Electronics&#34; Vol.39 NO.4 Nov. 1993, pp.859-869 by Chen-Mie Wu and Auchy Chiou. Yi-Feng Tang etc. designed a DCT circuit by exploiting a fast DCT algorithm and multiplier-accumulator based on this distribute algorithm. Transpose memory inserted between each dimension of DCT is partitioned in order to reduce further hardware overheads. This design is pressed on &#34;A 0.8u 100 MHz 2-D DCT Core Processor&#34; published in &#34;IEEE Transaction on Consumer Electronics&#34; Vol.40 NO.3 August 1994. 
     In fact, there are still many issues which should be taken into consideration in IC implementation, such as those raised by the performing of both forward and inverse transforms, the complexity of the control circuit logic and the number of data storage and shuffling elements. 
     Therefore, an object of the present invention is to provide a DCT/IDCT circuit, which is suitable for VLSI implementation and has the advantages of low hardware costs, high efficiency and a regular structure. 
     SUMMARY OF THE INVENTION 
     To achieve the above-indicated objects and others, the present invention provides a DCT/IDCT circuit. This circuit consists of a pipe-lined SIMD processor array, a transpose memory and a control circuit. The processor array is capable of computing 1-D DCT. Furthermore, a N×N two dimensional data is computed by exploiting the row-column decomposition method. 
     In N-point DCT application, the processor array consists of N PEs (processor elements), where each is capable of computing an N/2 point inner product. Instead of the traditional multiplier-accumulator (MAC) design, the present processor computes the N/2-point inner product by the word-parallel bit- serial method. With N/2 ROM tables, a Wallace tree and a carry propagate adder, each PE can compute N/2-point inner product based on this method. This implementation achieves a cost-saving and better timing in comparison to conventional MAC design. Meanwhile, the DCT circuit also has the advantages of simple data routing, regular structure and modular design. These advantages mean that the circuit is suitable for VLSI implementation. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The following detailed description, given by way of example and not intended to limit the invention solely to the embodiments described herein, will best be understood in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a data flow diagram in discrete cosine transform (DCT) mode according to the present invention; 
     FIG. 2 is a data flow diagram in inverse discrete cosine transform (IDCT) mode according to the present invention; 
     FIG. 3 is a data sequence of the discrete cosine transform according to the present invention; 
     FIG. 4 is a circuit diagram of the pre/post processing circuit according to the present invention; 
     FIG. 5 is a controlled sequence of the pre/post processing circuit according to the present invention; 
     FIG. 6 is a circuit diagram of the pipe-lined SIMD DCT/IDCT circuit according to the present invention; and 
     FIG. 7 is a circuit diagram of the accumulators according to the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present DCT/IDCT circuit is designed for evaluating these two equations efficiently without losing the regular property. And a halved amount of multiplication in equations (3), (4) is obtained by: ##EQU3## 
     When the identities f even  (x)=f even  (N-1-x) and f odd  (x)=f odd  (N-1-x) are used. 
     FIG. 1 is a data flow diagram in forward discrete cosine transform (DCT) mode according to the present invention. For an N×N 2-D data, the present DCT circuit is made up four stages: a pre-processing circuit 10, a serial-to-parallel circuit 12, a computation circuit 14 and a parallel-to-serial circuit 16. 
     The pre-processing circuit 10 receives 2-D data (represented by f(x,y), where 0≦x,y≦N) from the input terminal column-wise by the order of ##EQU4## and serially produces the terms ##EQU5## where ##EQU6## Then, these terms are fed to the serial-to-parallel circuit 12. After all the data in the current column has been processed and fed into the serial-to-parallel circuit 12, the terms are put into the computation circuit 14. This circuit 14 generates the final result F(i,j) by evaluating the equation (5). When completing the computation, the results are fed into the parallel-to-serial circuit 16 simultaneously. Finally, the results are stored in a transpose-RAM 18 one after one. 
     The pipe-lined mechanism is described briefly below. When the j-th column data is computed by the computation circuit 14, the serial-to-parallel circuit 12 is idle. This implies it can receive the 2-D data, the (j+1 )th column, from the pre-processing circuit 10. However, the parallel-to-serial circuit 16 still stores the (j-1)th column result to the transpose-RAM 18 one after one. So, the data goes through the four stages one column after one column and never stops. FIG. 3 is the data sequence diagram in this case. The first pass of 2-D DCT is complete after the (N-1)th column data has been processed and written to the transpose-RAM 18. 
     Instead of receiving the data column-wise, the pre-processing circuit 10 receives the data from the transpose-RAM 18 row-wise via the second pass DCT procedures, which are the same as the first pass procedures. The 2-D DCT is complete when the second pass procedures are finished. The IDCT procedures are similar to the DCT procedures. They are only different in one stage, that involving the pre-processing circuit 10 and the post-processing circuit 20. The DCT should &#34;pre-process&#34; the 2-D data before it is fed into the serial-to-parallel circuit 12. In contrast, the IDCT &#34;post-processed&#34; the data generated by the computation circuit 24 before putting it into the next stage, the transpose RAM 28. FIG. 2 depicts the data flow diagram in inverse discrete cosine transform (IDCT) mode according to the present invention. 
     During the first pass procedures, the serial-to-parallel stage receives the data column-wise by the order of ##EQU7## and feeds it to the computation circuit 24 after all the data in the current column has been processed and fed into the serial-to-parallel circuit 22. The computation circuit 24 then produces the inner product terms f even  (x) and f odd  (x) by evaluating the equations (6) and (7). The inner product terms are outputted to the post-processing circuit 20 through the parallel-to-serial circuit 26. The post-processing circuit 20 then adds and subtracts the inner product terms f even  (x), f odd  (x) to obtain the result stored in the transpose-RAM 28. 
     Instead of receiving the 2-D data column-wise, the serial-to-parallel circuit 22 receives the data from the transpose-RAM 28 row-wise via the second pass IDCT procedures, which are the same as the first pass procedures. The 2-D IDCT is complete when the second pass procedures have been finished. 
     Moreover, the pre-processing circuit 10 and the post-processing circuit 20 share the same hardware resources. FIG. 4 is a circuit diagram of the pre/post processing circuit according to the present invention. The pre/post processing circuit consists of three D flip flops D1 ,D2,D3 connected in series and receives the data according to a control signal (not shown). The pre/post processing circuit 10/20 also includes an adder ASU to process the results from the D flip flops so that the pre-processed or post-processed data can be obtained. FIG. 5 is a controlled sequence in DCT mode, wherein DFF 1.q represents the output waveform of the D flip flop D1 and ASU.s represents the output waveform of the adder ASU. However, the same mechanism can be applied in IDCT mode. 
     For clarity, an 8×8 2-D DCT, with the word length of the fixed-point number being 20, is used in this case as an example. The DCT and IDCT according to the previous definition are: ##EQU8## 
     Based on SIMD architecture, these equations are evaluated by 8 PEs concurrently. Each PE performs the function of 4-point inner product. FIG. 6 shows the pipe-lined SIMD DCT/IDCT circuit of the present invention. In DCT mode, the serial-to-parallel circuit 12 and the parallel-to-serial circuit 16 are respectively made up 7 D flip flops (D0˜D6 and D0&#39;˜D6&#39;). And the computation circuit 14 is made up 8 registers (R0˜R7) and 8 ROM accumulators (A0˜A7). FIG. 7 shows the circuit diagram of the 4-point inner product. The 4-point inner product circuit is designed in accordance with the word-parallel bit-serial method. For example, PP0, PP1, PP2, PP3 are the partial product terms of ##EQU9## respectively. However, the whole circuit is pipe-lined. The serial-to-parallel circuit 12 and the parallel-to-serial circuit 16 eclipse 8 cycles per column for receiving the data. Evidently, the computation circuit 14 should complete the computation within 8 cycles for each column. A fast multiplier based on a 4-bit-overlap-1 recording scheme is applied to meet the requirement. Table. 1 depicts the recording scheme. The ICAND is substituted by the cosine coefficient. These tables are recorded in 32 ROMs. The partial sum are added by the carry saved adders CSA0,CSA1,CSA2 and accumulated by a carry propagate adder CPA finally. 
     In summation, the DCT/IDCT circuit of the present invention has the advantages of lower hardware costs, simpler data routing (due to the pre/post processing circuit 10/20) and higher efficiency (due to the ROM accumulators AC0-AC7). In addition, the modular design is also suitable for VLSI implementation. 
     
                       TABLE I                                                     
______________________________________                                    
Overlap bit X.sub.j+3                                                     
           Current triplet X.sub.j+2 X.sub.j+1 X.sub.j                    
                           Action in position j                           
______________________________________                                    
0          0 0 0           None                                           
0          0 0 1           +2 × ICAND                               
0          0 1 0           +2 × ICAND                               
0          0 1 1           +4 × ICAND                               
0          1 0 0           +4 × ICAND                               
0          1 0 1           +6 × ICAND                               
0          1 1 0           +6 × ICAND                               
0          1 1 1           +8 × ICAND                               
1          0 0 0           -8 × ICAND                               
1          0 0 1           -6 × ICAND                               
1          0 1 0           -6 × ICAND                               
1          0 1 1           -4 × ICAND                               
1          1 0 0           -4 × ICAND                               
1          1 0 1           -2 × ICAND                               
1          1 1 0           -2 × ICAND                               
1          1 1 1           None                                           
______________________________________                                    
 
    
     The foregoing description of a preferred embodiment of the present invention has been provided for the purposes of illustration and description only. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to practitioners skilled in this art. The embodiment was chosen and described to best explain the principles of the present invention and its practical application, thereby enabling those who are skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.