Title :
Application-specific architecture for fast transforms based on the successive doubling method
Author :
Zapaga, E.L. ; Argüello, F.
Author_Institution :
Dept. Arquitectura de Computadores, Malaga, Spain
fDate :
3/1/1993 12:00:00 AM
Abstract :
The successive doubling method is an efficient procedure for the design of fast algorithms for orthogonal transforms of length N=rn, where the radix r is a power of 2. A partitioned systolic architecture is presented for the two standard radix successive doubling algorithms: decimation in time (DIT) and decimation in frequency (DIF). The index space of the data is projected onto the index space associated with a column of processors, interconnected using a perfect unshuffle (DIT) or shuffle (DIF) interconnection network, defined by permutations of the order log2 r. The result is a partitioned systolic array with Q processors (Q=ri, 0⩽i<n), which extracts the maximum spatial and temporal parallelism achieved by the successive doubling algorithm and can be integrated in VLSI and WSI technologies
Keywords :
parallel architectures; systolic arrays; transforms; DIF; DIT; VLSI; WSI; application specific architecture; decimation in frequency; decimation in time; fast transforms; index space; orthogonal transforms; partitioned systolic architecture; partitioned systolic array; permutations; successive doubling method; Discrete transforms; Geometry; Matrix decomposition; Parallel processing; Partitioning algorithms; Signal processing; Signal processing algorithms; Systolic arrays; Very large scale integration; Wafer scale integration;
Journal_Title :
Signal Processing, IEEE Transactions on