Efficient Systolic Implementation of DFT Using a Low-Complexity Convolution-Like Formulation

A reduced-complexity algorithm is presented for computation of the discrete Fourier transform, where$N$-point transform is computed from eight number of nearly$(N/8)$-point circular-convolution-like operations. A systolic architecture is also derived for very large-scale integration circuit implementation of the proposed algorithm. The proposed architecture is fully pipelined and contains regular and simple locally connected processing elements. It is devoid of complex control structure and is scalable for higher transform lengths. It is observed that the proposed systolic structure involves either less or nearly the same hardware-complexity compared with the corresponding existing systolic structures. In addition, it offers eight times more throughput and significantly low latency compared with the others.