Low-complexity recursive discrete fourier transform approximations for spectral estimation and autocorrelation computation

Abstract

The importance of the discrete Fourier transform (DFT) stems from its rich physical inter- pretation and its mathematical principles. In signal processing, the DFT plays a key role in spectral estimation, filtering, and fast signal convolutions. In order to reduce the computa- tional cost of the DFT, a series of algorithms called fast Fourier transforms (FFT) have been developed. Capable of reducing the multiplicative complexity, the FFT has allowed the widespread use of the DFT. However, even with the reduced arithmetic complexity derived from the FFT, the DFT computation can still be an obstacle in applications with restrictive conditions, such as energy consumption, chip occupancy area, and time. If small inaccuracies are allowed under such conditions, the DFT computation can be approximated. The present work approaches four different topics related to the DFT estimation. First, based on iterations of Cooley-Tukey’s radix-N algorithm, approximate transforms for sig- nals of lengths Nˆ2ˆn are proposed. Second, an approximate version of the Good-Thomas algorithm capable of performing the DFT calculation without multiplications is presented. Thirdly, using the canonical signed digit (CSD) representation, we present approximations for the transformation and twiddle factor matrices to also propose a multiplication-free Cooley-Tukey algorithm. Finally, a low-complexity estimator is proposed to calculate the autocorrelation of a given signal based on the properties of the DFT. All proposals include (i) construction of fast algorithms, (ii) evaluation of arithmetic complexity, and (iii) error analysis.