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.

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

"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 3, 12:12&#4294967295;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

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

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