PARALLEL ARCHITECTURE FOR FAST TRANSFORMS WITH TRIGONOMETRIC KERNEL

We present an unified parallel architecture for four of the most impor tant fast orthogonal transforms with trigonometric kernel: Complex Val ued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cos ine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be tra nsformed on a constant geometry how using perfect unshuffle or shuffle permutations. The other three require some type of hardware modificat ion to guarantee the constant geometry of the successive doubling meth od. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section perm its the evaluation of the CFFT and FCT transforms in a data recirculat ions and the RFFT and FHT transforms in n - 1 data recirculations, wit h a being the number of stages of a transform of length N = r(n). Also , the efficiency of the partitioned parallel architecture is optimum b ecause there Is no cycle loss in the systolic computation of all the b utterflies for each of the four transforms.