Novel Recursive Solution for Area-Time Efficient Systolization of Discrete Fourier Transform

摘要

A new recursive solution based on Clenshaw''s recurrence relation is formulated for computation of the discrete Fourier transform (DFT). The proposed recursive formulation is used further to derive a simple, regular and locally connected linear array architecture for systolic implementation of the DFT. The proposed structure offers nearly twice the throughput and involves nearly the same area-complexity as that of the corresponding existing DFT structure based on Clenshaw''s recurrence relation.