Parallel Adder-Based DCT / IDCT Design Using Cyclic Convolution

Abstract

A device and method are described that apply 1-D and 2-D discrete cosine transforms (DCT) and inverse discrete cosine transforms (IDCT) to sets of input data, typically 8×8 or 16×16 matricies of coefficients. One device includes input lines, logic to pre-add input values and generate operands and one or more adder networks that effectively carry out the multiplication operations required to apply a DCT/IDCT transform. The device may apply a 1-D transform twice to accomplish a 2-D transform. Alternatively, the device may either include successive stages of logic for the second 1-D transform or it may send data transformed once back through the same logic to pre-add and adder networks for the second 1-D transform. Calculations may be carried out after Booth encoding of operands. The processing may be split between producing v p , a vector of sums of output values, and producing v n , a vector of differences of output values, which vectors may be recombined to produce an output vector v.

1 . A permutation device accepting an input a set u 0 , u 2 , u 4  and u 6  and producing successive outputs sets (u 0 , u 2 , u 4 , u 6 ), (u 0 , u 6 , −u 4 , −u 2 ,), (u 0 , −u 2 , u 4 , −u 6 ), and (u 0 , −u 6 , −u 4 , u 2 ,), comprising: 
 muxes  0  . . .  3  coupled, respectively, to inputs u 0 , u 2 , u 4  and u 6 ;    registers  0  . . .  3  coupled to the output of muxes  0  . . .  3 , wherein register  0  also is coupled to the input of mux  0 , register  1  is coupled to the input of mux  3 , register  2  is coupled to the input of mux  2  and register  3  is coupled the input of to mux  1 ; and    a control line coupled to the muxes, wherein muxes  0  . . .  3  select between inputs and register couplings in response to the control line.    
     
     
         2 . The device of  claim 1 , wherein register  1  is coupled to the input of mux  3  through additive inverse logic and register  2  is coupled to the input of mux  2  through additive inverse logic.  
     
     
         3 . A permutation device accepting an input a set u 1 , u 3 , u 5  and u 7  and producing successive outputs sets (u 1 , u 3 , u 5 , u 7 ), (−u 3 , u 7 , u 5 , u 1 ), (− 7 , u 5 , u 1 , −u 3 ), and (−u 5 , u 1 , −u 3 , −u 7 ), comprising: 
 muxes  0  . . .  3  coupled, respectively, to inputs u 1 , u 3 , u 5  and u 7 ;    registers  0  . . .  3  coupled to the output of muxes  0  . . .  3 , respectively, and register  0  is also coupled to the input of mux  3 , register  1  is coupled to the input of mux  0 , register  2  is coupled to the input of mux  1  and register  3  is coupled to the input of mux  2 ; and    a control line coupled to the muxes, wherein muxes  0  . . .  3  select between inputs and register couplings in response to the control line.    
     
     
         4 . The device of  claim 3 , wherein register  1  is coupled to the input of mux  0  through additive inverse logic.