Fast Compressed-Domain N-Point Discrete Fourier Transform: The "Twiddless" FFT Algorithm

In this work, we present the twiddless fast Fourier transform (TFFT), a novel algorithm for computing the N-point discrete Fourier transform (DFT). The TFFT's divide strategy builds on recent results that decimate an N-point signal (by a factor of p) into an $N/p$-point compressed signal whose DFT readily yields $N/p$ coefficients of the original signal. However, existing compression-domain DFT analyses have been limited to computing only the even-indexed DFT coefficients. With TFFT, we overcome this limitation by efficiently computing both even- and odd-indexed DFT coefficients in the compressed domain with O(N log N) complexity. TFFT introduces a new recursive decomposition of the DFT problem, wherein N/2ⁱ coefficients of the original input are computed at recursion level i, with no need for twiddle factor multiplications or butterfly structures. Additionally, TFFT generalizes the input length to N = c · 2ᵏ (for k ≥ 0 and non-power-of-two $c > 0$), reducing the need for zero-padding and potentially improving efficiency and stability over classical FFTs. We believe TFFT represents a novel paradigm for DFT computation, opening new directions for research in optimized implementations, hardware design, parallel computation, and sparse transforms.