An orthogonal time-frequency extraction approach to 2D systolic architecture for 1D DFT computation

An expandable two-dimensional systolic array consisting of N homogeneous pr ocessing 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) = 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, rec ursive time and frequency extractions are applied to the column and row tra nsforms respectively. Twiddle factor multiplication is integrated gracefull y into the row recursion. The rearrangement of the input data enables the r ecursive operations to be pipelined orthogonally in the "dual-mode" process ing elements. The proposed array structure is modular and expandable. A DFT of size 2(L)N can be readily computed with 2(L)N-size arrays abutted toget her without reconfiguration. VHDL modules have been written and simulated s uccessfully for the proposed architecture.