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
$\begingroup$
$\endgroup$
1
-
$\begingroup$ So, what literature did you consult so far? I mean, no offense, we're all honored that you assume it's easy for us to explain algorithm better than standard literature, but you probably have something that explains atleast the radix 2 ones.. $\endgroup$ – Marcus Müller Jan 24 '17 at 16:22
Add a comment
|
$\begingroup$
$\endgroup$
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.
answered Jan 24 '17 at 18:42
$\begingroup$
$\endgroup$
From Computational Frameworks for the Fast Fourier Transform:
Standard radix-2 procedures are based upon the fast synthesis of two half-length DFTs. The split-radix algorithm is based upon a clever synthesis of one half-length DFT together with two quarter-length DFTs
On the otherhand, Radix p uses divide and conquer to recursively split the dft into p size n/p dtfs
