On the efficient implementation of the split-radix FFT

The recently developed split-radix algorithm for size 2^MDFTs appears to offer the lowest combined count of multiplies and additions among known algorithms, as well as fewer multiplies than Cooley-Tukey algorithms of radix 8 or below. Thus it seems well-suited to applications where DFT computation time is limited by multiply and/or addition time. We show that the algorithm is less attractive when evaluated in terms of butterflies. Specifically, it requires 20 to 50% more butterflies than an otherwise similar radix-4 Cooley-Tukey FFT, and its relatively irregular structure complicates pipelined implementation. These considerations are important when contemplating DFT machines based on VLSI butterfly primitives.