FFT Algorithm: Split Radix vs Radix-4

Question

I wanted to know the difference between split radix and mixed radix algorithm.

I also wanted to know what is the difference between radix 2 ,radix 4 and radix 8 FFT

Answer 1

just did a Google image search and these diagrams have popped up.

these are radix-2 butterflies with expanded detail (showing where the "twiddle factor", Q, goes) for various DIF and DIT FFTs.

a radix-2 FFT (the simplest in concept) uses only radix-2 butterfly operations, each with 2 complex numbers going and and 2 complex numbers coming out.

these four radix-2 butterflies combined

make a radix-4 butterfly:

the image on the right just above would be a short-hand notation for a radix-4 butterfly. if there were 8 signals going into the dot and 8 coming out, it would be a radix-8 butterfly.

let $p \in \{1, 2, ...\}$ and $P \triangleq 2^p$. essentially a radix-$P$ FFT is an FFT that uses radix-$P$ butterflies and a radix-$P$ butterfly is, in and of itself, a complete $P$-point FFT with some phase adjustment on the internal twiddle factors.

a split-radix FFT has butterflies of different sizes. here is the best example i can think of:

a 256-point FFT can be done entirely using radix-4 butterflies because 256 is a power of 4: $256=4^4$. there would be 4 FFT passes and all of the passes would have radix-4 butterflies. a 256-point FFT can also be done with a radix-2 FFT and it would be 8 passes, all with radix-2 butterflies, instead of 4 passes.

now suppose you wanted a 512-point FFT. if you started with a radix-2 FFT, all you need to do is double the size of the buffer and add one more pass because $512=2^9$. so there is no split radix if you wanted to do that. turns out that the radix-4 FFT is a little more efficient than the radix-2 so you might want to replace 8 contiguous passes of the radix-2 FFT with 4 passes of a radix-4 FFT and one final (or one initial) pass using 2-point butterflies. that is a split-radix FFT.