Digital Signal Processing

N-Point Discrete Fourier Transform in O(n Log_2n) Time Complexity for Any N Larger Than 0

Authors: Saulo Queiroz
Comments: 3 Pages.

We present a novel recursive algorithm for computing the $N$-point Discrete Fourier Transform (DFT) with $O(N log_2 N)$ time complexity, applicable for any integer $N > 0$. Unlike conventional Fast Fourier Transform (FFT) algorithms that often require zero-padding to the nearest power of two, our method operates directly on arbitrary-length input sequences, eliminating the need for zero-padding. At each recusive stage, the algorithm relies on a novel decomposition structure that performs $2(N-1)$ complex additions and $N$ complex ultiplications for typical cases, yielding a total complexity of $T(N)=2T(N/2)+10N-4=10Nlog_2N-4N+K$ real floating point operations (where $K$ is a constant). Although the resulting constants are higher than in classic FFT algorithms -- like radix-2 FFT, that performs $5Nlog_2N$ real floating point operations -- our algorithm does not need zero-padding, which end up by increasing the true complexity of existing FFTs due to the enlarged signal length.
Category: Digital Signal Processing