A new systolic array algorithm for discrete Fourier transform
Chi‐Min Liu, Chein-Wei Jen · 1991
A new systolic algorithm for computing the discrete Fourier transform (DFT) is presented. The algorithm exhibits the minimum required time O(Nt/sub a/) and the computational complexity O(2N/sup 2/), which are much better than the time O(Nt/sub a/+Nt/sub m/) and the complexity O(4N/sup 2/) in existing systolic algorithms, where t/sub a/ and t/sub m/ are the computation time for a complex addition and a complex multiplication, respectively, and N is the DFT length. By exerting the benefits of the algorithm and adopting the scheme of tag control, a systolic array and a two-level pipelined systolic array are designed. The resulting arrays have outstanding performance on computing speeds, hardware cost, and the number of input/output (I/O) channels.>