A new systolic array algorithm for discrete Fourier transform

A new systolic algorithm for computing the discrete Fourier transform (DFT) is presented. The algorithm exhibits the minimum required time O(Nt_a) and the computational complexity O(2N²), which are much better than the time O(Nt_a+Nt_m) and the complexity O(4N²) in existing systolic algorithms, where t_a and t_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