Radix-$N$ Algorithm for Computing $N^{2^{n}}$-Point DFT Approximations
Luan Portella, Diego F. G. Coelho, Fábio M. Bayer, Arjuna Madanayake, Renato J. Cintra · IEEE Signal Processing Letters · 2022
The ever increasing technological demand for the DFT computation poses several challenges both to theory and hardware realization. The design of usual fast Fourier transform (FFT) algorithms seems to have reached a stage of diminishing returns in terms of performance. Alternatively, approximate transform methods have been demonstrated to provide substantial gains in terms of energy-efficiency and performance by tolerating small inaccuracies in the results. In this paper, we present a transform scaling method variant of the Cooley-Tukey algorithm to obtain DFT approximations of large blocksize. The proposed method scales up a givenN-point transformation to anN2-point transformation. Such scaling can be successively applied leading to$\mathop {{N}^2} olimits^n $-point transformations. We have fully presented the 324-point DFT approximation which stems from a multiplierless 32-point DFT approximation. The proposed approximation is equipped with a fast algorithm; we also supply the arithmetic complexity assessment and an error analysis.