Started by 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
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?

```
```I have not heard of mixed radix. but split radix is when you use

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?
>
>
```
```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
> 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?
>

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
> 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

"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
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:

> 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
But not two radix-2 steps combined with two radix-4 steps, which would
give you n=64.

> 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

>  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
> 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
>
> "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
> 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:

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,
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
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.
```