Global Indexing Scheme for Reduced Number of Applied Twiddle Factors in Split-Radix FFT Algorithms
Paweł Tarasiuk, Adam Wojciechowski, Mykhaylo Yatsymirskyy · 2021 IEEE 16th International Conference on Computer Sciences and Information Technologies (CSIT) · 2021
In this paper, we propose a novel modification to the split-radix FFT algorithm [1]. The novel idea is based on the optimized indexing of butterfly operations, which guarantees global grouping by twiddle factors wkn= exp(2πik/n) through the whole processing. This is more extensive than some known implementations that group the twiddle factors by block or by stage [2], and it is the first publication where fully global grouping scheme is applied to any algorithm based on the split-radix FFT. The proposed algorithm was implemented in C programming language and benchmarked for signal sizes$n 64 \ldots 65 536$, which includes both typical sequences used in sound and digital image processing and notably longer sequences, related to big data. Our testing environment was configured specifically for testing the properties of algorithms, with special consideration for the compiler configuration and software implementation techniques. The experiments confirmed the ~20% advantage of split-radix FFT over radix-2 FFT [3], and shown further 15-25% improvement achieved with our novel method.