Re: how do you calculate index of output for mixed radix DIF FFT?

On Mar 29, 5:46 am, kevinjmc...@xxxxxxxxxxxx wrote:
On Mar 27, 2:22 pm, chrisde...@xxxxxxxxx wrote:

Hi,
   does anybody know how to calculate output for mixed radix FFT using
the decimation in frequency method?
use a 30 point FFT for instance implemented using radix 5 ---> radix 2
---> radix 3.

what will the output index be? for single radix case, you flip the
base-radix digits used to represent the index. what about for the case
of the above mixed radix example? how will the output index be? any
idea?

thanks!
Chris

The decimation type doesn't really matter when it comes to output
sequence.  Big FFTs are made up of smaller FFTs with twiddle factors
between the stages.  For instance, with a 5x8x7 transform, you could
implement the smaller FFTs (i.e.: butterflies) with either decimation
type.  But your output sequence will depend entirely on the size of
the butterflies, the order in which they are performed, and the
sequence of their inputs and outputs (usually presumed to be
sequential in, sequential out, although algorithms exist for which
this is not the case).

Your specific question was about a 5x3x2 = 30 graph.  There's a 5x2x3
graph depicted on p.378 below:

L. R. Rabiner, B. Gold, Theory and Application of Digital Signal
Processing.  Englewood Cliffs, NJ, Prentice-Hall, 1975.

the output sequence is (read from left to right by row):

0 10 20 5 15 25
1 11 21 6 16 26
2 12 22 7 17 27
3 13 23 8 18 28
4 14 24 9 19 29

Now if you changed the order of butterflies to do a 5x3x2, both your
interstage twiddles and output sequence would be different.  For a
5x3x2, I think you’d get the following, based on the comments in the
above reference:

0 5 10 15 20 25
1 6 11 16 21 26
2 7 12 17 22 27
3 8 13 18 23 28
4 9 14 19 24 29

The input/output sequence of an FFT can be seen as matrix
permutations, and they can sometimes be complicated, especially if
you‘re doing a lot of stages with different sized butterflies.  There
are a lot of papers about it.  The above reference is a good place to
start.

As for me, I tend to avoid the prime factor, multiple stage algorithms
in favor of two stage power of two algorithms.  For instance, an N =
32 graph is simply an 8x4 mixed radix.  And N = 512 is just a 32x16
mixed radix.  And with only two stages, both the interstage twiddles
and output permutations are easier to figure out.  And their
architectures are more amenable to hardware implementation.

But the prime factor stuff can be fun to learn.

Kevin


Hi Kevin,

thanks for your help. I am actually reading p 378 of the book you
mentioned above but could not visualize it until your pictorial of
which everything fell into place. I have some more questions

1) so p.378 is mixed radix FFT right? It was never explicitly
mentioned in the book
2) based on your inputs,
the one you gave below seem to be the output order for a 5x6 radix
right?
0 5 10 15 20 25
1 6 11 16 21 26
2 7 12 17 22 27
3 8 13 18 23 28
4 9 14 19 24 29

shouldn't radix 5x3x2 output be... (read from left to right)
0 15 5 20 10 25
1 16 6 21 11 26
2 17 7 22 12 27
3 18 8 23 13 28
4 19 9 24 14 29

thanks for your help again!
Chris
.

Loading