An Orthogonal Time-Frequency Extraction Approach to 2D Systolic Architecture for 1D DFT Computation

An expandable two-dimensional systolic array consisting of N homogeneous processing elements in a rectangular sturcture to compute the one-dimensional DFT transform is proposed. DFT of size N = M^2 can be computed in 2M steps of pipelined operations, achieving the optimal Area–Time complexity of AT^2 e O(N^2). The architecture is based on a new approach that exploits the symbiosis between the one-dimensional systolic arrays of Kung [6] and Chang [7]. After a two-dimensional formulation with Common Factor Algorithm, recursive time and frequency extractions are applied to the column and row transforms respectively. Twiddle factor multiplication is integrated gracefully into the row recursion. The rearrangement of the input data enables the recursive operations to be pipelined orthogonally in the “dual-mode” processing elements. The proposed array structure is modular and expandable. A DFT of size 2^LN can be readily computed with 2^L N-size arrays abutted together without reconfiguration. VHDL modules have been written and simulated successfully for the proposed architecture.