FFT Radix

Started by vt20...@gmail.com February 2, 2008
I am trying to implement a 128 point FFT. I have 16 8-bit samples
aligned and ready for input into the FFT. I would like to know if the
terms "mixed radix fft" and "split radix fft" are considered
interchangeable. If not, what is different?

Is it possible to use 64 radix 2 butterflys in front of two 64 point
radix 4 based fft's? Does this make sense? If it is possible, do I
need to reorder the output of the radix 2's? Do i need to rescale the
twidles in the 64 pt ffts?

Thanks for your help!
I have not heard of mixed radix. but split radix is when you use
both radix2 and radix4 to compute N point FFT.

your output or input ordering/reordering will depend on if you
are implementing decimation in time or decimation in freq algo.
if you are doing decimation in time then you have to re-order
input. else re-order output.

let us assume that you are doing decimation in time.

1. implement 64 point radix 4 FFT.
2. implement 2 such structures.
3. the output of the 2 structures can be combined using radix2
   128 point single stage.

regards
bharat pathak

arithos designs
~dsp simplified.
www.arithos.com


>Is it possible to use 64 radix 2 butterflys in front of two 64 point >radix 4 based fft's? Does this make sense? If it is possible, do I >need to reorder the output of the radix 2's? Do i need to rescale the >twidles in the 64 pt ffts? > >Thanks for your help! >
On Feb 1, 11:48 pm, "vt2001...@gmail.com" <vt2001...@gmail.com> wrote:
> I am trying to implement a 128 point FFT. I have 16 8-bit samples > aligned and ready for input into the FFT. I would like to know if the > terms "mixed radix fft" and "split radix fft" are considered > interchangeable. If not, what is different? > > Is it possible to use 64 radix 2 butterflys in front of two 64 point > radix 4 based fft's? Does this make sense? If it is possible, do I > need to reorder the output of the radix 2's? Do i need to rescale the > twidles in the 64 pt ffts? > > Thanks for your help!
On Feb 1, 11:48 pm, "vt2001...@gmail.com" <vt2001...@gmail.com> wrote:
> I am trying to implement a 128 point FFT. I have 16 8-bit samples > aligned and ready for input into the FFT. I would like to know if the > terms "mixed radix fft" and "split radix fft" are considered > interchangeable. If not, what is different?
No, they have totally different meanings in the FFT literature (although some people online confuse the two). "Mixed-radix" is a generic term for when you use a variety of radices in succession. Most commonly the term refers to the case where you use different radices to handle composite sizes with a variety of prime factors, e.g. you might use mixed radices 2, 3, and 5 to handle size n = 3000. However, it can also be used when you use a mix of radices that are different powers of the same prime factor, e.g. n = 1024 could be done as radix 4 followed by radix 2 followed by radix 32 followed by radix 4. "Split-radix" is quite different. It refers to a "blending" of radices 2 and 4, but is *not* the same thing as mixed-radix where you do radix 2 then radix 4 then radix 2 etc. In particular, at each step of split radix you divide the transform into *three* subtransforms, one of size n/2 and two of size n/4. (This technique was originally used to reduce the count of arithmetic operations.) See: http://en.wikipedia.org/wiki/Split-radix_FFT_algorithm
> Is it possible to use 64 radix 2 butterflys in front of two 64 point > radix 4 based fft's? [ for a a 128 point FFT ]
More or less, but you are apparently miscounting. For example, you could do n=128 as one radix-2 step followed by three radix-4 steps, or three radix-2 steps followed by two radix-4 steps. But not two radix-2 steps combined with two radix-4 steps, which would give you n=64. Supposing you had one radix-2 step followed by three radix-4 steps, then the radix-2 step would have 64 radix-2 butterflies, while the radix-4 steps would have 32 radix-4 butterflies each.
> Does this make sense?
It is certainly mathematically possible (with my correction above). On the other hand, if you cared about efficiency then you wouldn't be asking this question, you would be using an optimized FFT code from somewhere. e.g. FFTW (www.fftw.org) does size 128 of real inputs using a hard-coded FFT of that size (2000 lines of straight-line code, generated by a special program), which will be far faster than doing explicit radix 4 or radix 2 loops.
> If it is possible, do I > need to reorder the output of the radix 2's? Do i need to rescale the > twiddles in the 64 pt ffts?
At some point there is always a re-ordering in an FFT with in-order output, but your question is a bit ill-defined. Exactly where it occurs, or even whether it has to occur at all as an explicit separate reordering step depends on how you organize the implementation. As for the twiddles, if you look at the derivation of the Cooley-Tukey FFT algorithm (see e.g. http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm), you'll see that the twiddle factors for each stage of the algorithm only depend on the radix at that stage and the size of the transform at that stage, not on the sequence of preceding radices. Regards, Steven G. Johnson
On Feb 3, 12:12&#2013266080;am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Feb 1, 11:48 pm, "vt2001...@gmail.com" <vt2001...@gmail.com> wrote: > > Is it possible to use 64 radix 2 butterflys in front of two 64 point > > radix 4 based fft's? [ for a a 128 point FFT ] > > More or less, but you are apparently miscounting. > > For example, you could do n=128 as one radix-2 step followed by three > radix-4 steps, or three radix-2 steps followed by two radix-4 steps. > But not two radix-2 steps combined with two radix-4 steps, ....
Oh, never mind, I misread your message. Yes, if you do a single radix-2 step, you obtain a pair of 64-point DFTs, and then you can do these 64-point DFTs by radix 4. For some reason I misread your message as saying you wanted to do only 2 radix-4 steps, sorry. In general, whenever you have an algorithm like Cooley-Tukey that breaks down a DFT into smaller DFTs recursively, you can do the smaller DFTs by any algorithm you want. Steven
"Steven G. Johnson" <stevenj@alum.mit.edu> wrote:
> On Feb 1, 11:48 pm, "vt2001...@gmail.com" <vt2001...@gmail.com> wrote: > > I am trying to implement a 128 point FFT. I have 16 8-bit samples > > aligned and ready for input into the FFT. I would like to know if the > > terms "mixed radix fft" and "split radix fft" are considered > > interchangeable. If not, what is different? > > No, they have totally different meanings in the FFT literature > (although some people online confuse the two). > > "Mixed-radix" is a generic term for when you use a variety of radices > in succession. Most commonly the term refers to the case where you use > different radices to handle composite sizes with a variety of prime > factors, e.g. you might use mixed radices 2, 3, and 5 to handle size n > = 3000. However, it can also be used when you use a mix of radices > that are different powers of the same prime factor, e.g. n = 1024 > could be done as radix 4 followed by radix 2 followed by radix 32 > followed by radix 4. > > "Split-radix" is quite different. It refers to a "blending" of > radices 2 and 4, but is *not* the same thing as mixed-radix where you > do radix 2 then radix 4 then radix 2 etc. In particular, at each step > of split radix you divide the transform into *three* subtransforms, > one of size n/2 and two of size n/4. (This technique was originally > used to reduce the count of arithmetic operations.) See: > http://en.wikipedia.org/wiki/Split-radix_FFT_algorithm
Your response reminded me of a question I've wondered about for the last year... I have also seen where the term split-radix is used to refer to the method of breaking-up an N-length FFT into two shorter length ones, lengths M & L. You calculate the length-N FFT using the following three steps. 1) Take L length-M FFTs on the lth samples: 0, L, 2L, ..., (M-1)L 1, L+1, 2L+1, ..., (M-1)L+1 ... L-1, 2L-1, 3L-1,..., ML-1 2) multiply by an additional phase rotation factor 3) Take M length-L FFTs on blocks of L samples 0 : L-1 L : 2L-1 ... (M-1)L : ML-1 It is pretty clear that this technique is not the same as that referred to in the wikipedia article. Do you know the name of the method referred to above? Regards, Ken P.
On Feb 4, 8:29 am, Ken Prager <pra...@ieee.org> wrote:
> Your response reminded me of a question I've wondered about for the last > year... > > I have also seen where the term split-radix is used to refer to the > method of breaking-up an N-length FFT into two shorter length ones, > lengths M & L. You calculate the length-N FFT using the following three > steps. > > 1) Take L length-M FFTs on the lth samples: > > 0, L, 2L, ..., (M-1)L > 1, L+1, 2L+1, ..., (M-1)L+1 > ... > L-1, 2L-1, 3L-1,..., ML-1 > > 2) multiply by an additional phase rotation factor > > 3) Take M length-L FFTs on blocks of L samples > > 0 : L-1 > L : 2L-1 > ... > (M-1)L : ML-1 > > It is pretty clear that this technique is not the same as that referred > to in the wikipedia article. Do you know the name of the method > referred to above?
Ken, that is just one step of the ordinary 1965 Cooley-Tukey algorithm. What you described can be thought of as one radix-L decimation-in-time step, or equivalently as one radix-M decimation-in- frequency step. (The output is not in-order, however; you are missing an LxM transpose step.) See also the Wikipedia article on the Cooley- Tukey algorithm. I think a lot of people get confused about the Cooley-Tukey algorithm because they only learn it as the composition of *all* the recursive steps (often not implemented recursively). For example, as the combination of all m radix-2 stages to get an N=2^m DFT. Really, though, the basic idea (clearly described back in 1965) is just the single step of decomposing of a size N = LM DFT into DFTs of size L and M, just like you outlined above (+ a transpose). Because the subproblems are also DFTs, one can apply the same algorithm recursively (although for 40 years the unnatural tradition has been to rearrange the computation from its naturally recursive depth-first order into a non-recursive breadth-first order, with a few exceptions like FFTW or Singleton in 1967). Alternatively, one can combine it with any other FFT algorithm (e.g. when you hit a large prime factor you can use Bluestein's or Rader's algorithm). From this perspective, it's obvious that one has no problem combining radix-2 and radix-4 steps like the original poster asked, because the algorithms for the different DFT subproblems can be completely independent. Anyone referring to the above algorithm as "split radix" is not using standard terminology. (Many variants of Cooley-Tukey have their own names, e.g. mixed radix, Stockham, four-step, etcetera, are just different choices of radices and/or how to do the transpositions. But split radix is a bit unique in that it refers to a mixture of radices 2/4 [along with some generalization thereof] in a *single* step as I described, so that the DFT is broken into interleaved DFT subproblems of unequal sizes.) Regards, Steven G. Johnson
In article 
<dd5bb85e-8f36-46ef-a696-1d2d092af834@p69g2000hsa.googlegroups.com>,
 stevenj.mit@gmail.com wrote:

> On Feb 4, 8:29 am, Ken Prager <pra...@ieee.org> wrote: > > Your response reminded me of a question I've wondered about for the last > > year... > > > > I have also seen where the term split-radix is used to refer to the > > method of breaking-up an N-length FFT into two shorter length ones, > > lengths M & L. You calculate the length-N FFT using the following three > > steps. > > > > 1) Take L length-M FFTs on the lth samples: > > > > 0, L, 2L, ..., (M-1)L > > 1, L+1, 2L+1, ..., (M-1)L+1 > > ... > > L-1, 2L-1, 3L-1,..., ML-1 > > > > 2) multiply by an additional phase rotation factor > > > > 3) Take M length-L FFTs on blocks of L samples > > > > 0 : L-1 > > L : 2L-1 > > ... > > (M-1)L : ML-1 > > > > It is pretty clear that this technique is not the same as that referred > > to in the wikipedia article. Do you know the name of the method > > referred to above? > > Ken, that is just one step of the ordinary 1965 Cooley-Tukey > algorithm. What you described can be thought of as one radix-L > decimation-in-time step, or equivalently as one radix-M decimation-in- > frequency step. (The output is not in-order, however; you are missing > an LxM transpose step.) See also the Wikipedia article on the Cooley- > Tukey algorithm. > > I think a lot of people get confused about the Cooley-Tukey algorithm > because they only learn it as the composition of *all* the recursive > steps (often not implemented recursively). For example, as the > combination of all m radix-2 stages to get an N=2^m DFT. Really, > though, the basic idea (clearly described back in 1965) is just the > single step of decomposing of a size N = LM DFT into DFTs of size L > and M, just like you outlined above (+ a transpose). Because the > subproblems are also DFTs, one can apply the same algorithm > recursively (although for 40 years the unnatural tradition has been to > rearrange the computation from its naturally recursive depth-first > order into a non-recursive breadth-first order, with a few exceptions > like FFTW or Singleton in 1967). Alternatively, one can combine it > with any other FFT algorithm (e.g. when you hit a large prime factor > you can use Bluestein's or Rader's algorithm). From this perspective, > it's obvious that one has no problem combining radix-2 and radix-4 > steps like the original poster asked, because the algorithms for the > different DFT subproblems can be completely independent. > > Anyone referring to the above algorithm as "split radix" is not using > standard terminology. (Many variants of Cooley-Tukey have their own > names, e.g. mixed radix, Stockham, four-step, etcetera, are just > different choices of radices and/or how to do the transpositions. But > split radix is a bit unique in that it refers to a mixture of radices > 2/4 [along with some generalization thereof] in a *single* step as I > described, so that the DFT is broken into interleaved DFT subproblems > of unequal sizes.) > > Regards, > Steven G. Johnson
Thanks, that clarifies things! Ken P.