2025/05/29 by Saulo Queiroz, Queiroz, Saulo
Computer Science · Engineering · #Advanced Electrical Measurement Techniques #Advanced Image Processing Techniques #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #Image and Signal Denoising Methods #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2505.23718
openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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/2i 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 ⋅ 2k (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.