Constraints on the SIMD vectorization of radix-2 and mixed-radix FFTS

Single instruction, multiple data (SIMD) signal processors for wireless communications require efficient vectorized algorithms for radix-2 and mixed-radix Fast Fourier Transforms (FFTs). Especially, mixed-radix FFTs are challenging for a processor that operates on power-of-two length vectors. We analyze the vectorization of pure radix-2 and mixed-radix FFTs and demonstrate that both FFTs have different constraints for an efficient vectorization. The radix-2 FFT can be efficiently vectorized if the FFT length is at least twice the vector length while the mixed-radix FFT requires the FFT length to be a multiple of the squared vector length.