Realization of discrete Fourier transforms using a nesting algorithm
Wan-Chi Siu, Kar-Lik Wong · International Journal of Electronics · 1991
A nesting discrete Fourier transform technique is proposed for computing discrete Fourier transforms. This technique relies on only two primitive modules and other modules are generated by a standard nesting procedure. In software realization, the speed of computation of this approach is comparable to the speed of computation of Winograd Fourier transform algorithms, whereas the program size of the present approach is smaller than that of WFTAs. This approach is most suitable for cases where there are restrictions on the memory size. For a hardware realization, two simple systolic cells are suggested for the realization of long DFTs using a pipeline systolic structure. This new architecture is most suitable for realization using VLSI techniques and requires significantly fewer devices compared to methods reported before.