Re: FFT Radix

On Feb 1, 11:48 pm, "vt2001...@xxxxxxxxx" <vt2001...@xxxxxxxxx> 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...@xxxxxxxxx" <vt2001...@xxxxxxxxx> 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
.

Relevant Pages

  • Re: FFT Radix
    ... they have totally different meanings in the FFT literature ... "Mixed-radix" is a generic term for when you use a variety of radices ... could be done as radix 4 followed by radix 2 followed by radix 32 ... lengths M & L. You calculate the length-N FFT using the following three ...
    (comp.dsp)
  • Re: 64 x 64 FFT algorithm for 4096 pt. FFT
    ... Consider a conventional 4096, radix 2, sequential in, bit reverse out ... butterflies, with 4096/2 butterflies per stage. ... We'd ALSO have full multipliers between the 3rd and 4th stage, ... FFT)? ...
    (comp.dsp)
  • Re: float-radix?
    ... the radix is always 2. ... the highest digit is a nibble. ... with some possible loss of precision compared to radix-2. ... Not coincidentally, this is also the size of BCD digits, so the same hardware ...
    (comp.lang.lisp)
  • Re: 64 x 64 FFT algorithm for 4096 pt. FFT
    ... Is it the mixed radix FFT? ... order and twiddle sequence of each butterfly for the 8x8 graph in Fig. ... graph would look like if you had 2 stages of 64x64 butterflies). ...
    (comp.dsp)
  • Re: Radix-4 Radix-2 ordering
    ... N/2 size complex FFT and manipulate results with very little extra ... Depending on the number of DFTs ... You could do it as a 8x8x8x2 (radix 8 is quite efficient, ... mixed radix graphs, the reordering can be difficult if you want to do ...
    (comp.dsp)