FFT twiddle calculation and evaluation

Hi all..

I would be grateful if more info on the above could be provided with
regards the equations to precompute the twiddle factors for each
stage/butterfly in the FFT. This is to enable me write a piece of code to
generate this ( i have not found much on this on the net).
I am aware that for a DIF radix-2 FFT the total number of butterflies is
(N/2 LogN). The total number of twiddle factors involved is ( N/2 ) for a
radix-2 form. Also the last stage involves multiplication by a twiddle
factor of 1. Could this be illustrated for an 8 point FFT for the 3
stages. How can i
allocate the values for the twiddle factors (cos ra + j sin ra) for the
entire range and relate that to each stage and butterfly. While the
interconnections between each stage more complex is there a pattern that
can be established for the DIF radix-2 version. 
I am currently implementing this in VHDL to generate the equivalent
hardware and any clarifications, pointers on this would be great!

Cheers
Mahesh

_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

mahesh_u2 wrote:

> I would be grateful if more info on the above could be provided with
> regards the equations to precompute the twiddle factors for each
> stage/butterfly in the FFT. This is to enable me write a piece of code to
> generate this ( i have not found much on this on the net).

I believe that they can be easily generated using trig. identities.
You have cos(theta) and sin(theta) for some theta, and need
cos(theta/2) and sin(theta/2).

Otherwise, I usually look in Numerical Recipes.

-- glen

On May 21, 4:43 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> mahesh_u2 wrote:
> > I would be grateful if more info on the above could be provided with
> > regards the equations to precompute the twiddle factors for each
> > stage/butterfly in the FFT. This is to enable me write a piece of code to
> > generate this ( i have not found much on this on the net).
>
> I believe that they can be easily generated using trig. identities.
> You have cos(theta) and sin(theta) for some theta, and need
> cos(theta/2) and sin(theta/2).

sounds like generating them in bit-reversed order (which is useful for
certain FFT algs).

r b-j

Mahesh wrote:
> Hi all..
>
> I would be grateful if more info on the above could be provided with
> regards the equations to precompute the twiddle factors for each
> stage/butterfly in the FFT. This is to enable me write a piece of code to
> generate this ( i have not found much on this on the net).
> I am aware that for a DIF radix-2 FFT the total number of butterflies is
> (N/2 LogN). The total number of twiddle factors involved is ( N/2 ) for a
> radix-2 form. Also the last stage involves multiplication by a twiddle
> factor of 1. Could this be illustrated for an 8 point FFT for the 3
> stages.

You can find exactly such an illustration (8-point FFT block diagram)
in Oppenheim / Schafer's classic "Digital Signal Processing". Perhaps
this link also helps you:

http://www.dspguide.com/ch12/2.htm

> How can i
> allocate the values for the twiddle factors (cos ra + j sin ra) for the
> entire range and relate that to each stage and butterfly.

As you wrote, you have to generate N/2 complex twiddle factors

exp(-2 pi j (0:N/2-1)/N )

for the radix 2 FFT. For DIT, you can subsample the twiddles by a
factor of 2^n at each stage. In the last stage, you need all twiddles,
in the second last stage you need every second twiddle, etc.

For hardware implementation, CORDIC seems to be the algorithm of
choice to generate the twiddle factors.

http://www.dspguru.com/info/faqs/cordic.htm

Regards,
Andor

Thanks for the responses so far. While am aware of the formatm(complex)
and the values of the twiddles (after a good look around!) am looking for
some method of associating the various twiddle factors with the
butterflies in each stage.
e.g. For an 8 point DIF radix-2. We know there will be only 4 unique
weights: w0,w1,w2,w3. These can be derived from the FFT equation with
different values of k. The last stage (3rd) values would be multiplied by
1. Stage 1 and 2 remain with the interconnections between these being
predetermined from what i understand. So from literature twiddles:
w0,w1,w2,w3 are all used in the first stage. The second stage then
utilises twiddles: w0,w2 twice. What i'd like to be able to do is work out
what weights each stage utilises and which butterfly would use each weight.


Cheers
Mahesh



>On May 21, 4:43 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>> mahesh_u2 wrote:
>> > I would be grateful if more info on the above could be provided with
>> > regards the equations to precompute the twiddle factors for each
>> > stage/butterfly in the FFT. This is to enable me write a piece of
code to
>> > generate this ( i have not found much on this on the net).
>>
>> I believe that they can be easily generated using trig. identities.
>> You have cos(theta) and sin(theta) for some theta, and need
>> cos(theta/2) and sin(theta/2).
>
>sounds like generating them in bit-reversed order (which is useful for
>certain FFT algs).
>
>r b-j
>
>
>
>



_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

Hi all,
I think looking at my post again I need to clarify why i need to find out
if there is a method of deriving the relationship between the FFT
butterflies for the 8 point DIF case. I would like to extend this
relationship for larger groupings i.e. 512 point(9 stages; 256 complex
twiddles), 1024 point (10 stages; 512 complex twiddles) whereby I can work
out for a fixed number of butterflies how each intermediate value is fed
into the next stages butterfly with the respective twiddle values. As has
been mentioned; the twiddle factors are reused in particular sequences for
each stage. Would there be any literature showing how this can be worked
out for larger stages (given a particular FFT lenght) or  if there is a
simple relationship that am missing with regards this!
Thanks in advance. Mahesh


>
>Thanks for the responses so far. While am aware of the formatm(complex)
>and the values of the twiddles (after a good look around!) am looking
for
>some method of associating the various twiddle factors with the
>butterflies in each stage.
>e.g. For an 8 point DIF radix-2. We know there will be only 4 unique
>weights: w0,w1,w2,w3. These can be derived from the FFT equation with
>different values of k. The last stage (3rd) values would be multiplied
by
>1. Stage 1 and 2 remain with the interconnections between these being
>predetermined from what i understand. So from literature twiddles:
>w0,w1,w2,w3 are all used in the first stage. The second stage then
>utilises twiddles: w0,w2 twice. What i'd like to be able to do is work
out
>what weights each stage utilises and which butterfly would use each
weight.
>
>
>Cheers
>Mahesh
>
>
>
>>On May 21, 4:43 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>>> mahesh_u2 wrote:
>>> > I would be grateful if more info on the above could be provided
with
>>> > regards the equations to precompute the twiddle factors for each
>>> > stage/butterfly in the FFT. This is to enable me write a piece of
>code to
>>> > generate this ( i have not found much on this on the net).
>>>
>>> I believe that they can be easily generated using trig. identities.
>>> You have cos(theta) and sin(theta) for some theta, and need
>>> cos(theta/2) and sin(theta/2).
>>
>>sounds like generating them in bit-reversed order (which is useful for
>>certain FFT algs).
>>
>>r b-j
>>
>>
>>
>>
>
>
>
>_____________________________________
>Do you know a company who employs DSP engineers?  
>Is it already listed at http://dsprelated.com/employers.php ?
>



_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

Hi all,
I think looking at my post again I need to clarify why i need to find out
if there is a method of deriving the relationship between the FFT
butterflies for the 8 point DIF case. I would like to extend this
relationship for larger groupings i.e. 512 point(9 stages; 256 complex
twiddles), 1024 point (10 stages; 512 complex twiddles) whereby I can work
out for a fixed number of butterflies how each intermediate value is fed
into the next stages butterfly with the respective twiddle values. As has
been mentioned; the twiddle factors are reused in particular sequences for
each stage. Would there be any literature showing how this can be worked
out for larger stages (given a particular FFT lenght) or  if there is a
simple relationship that am missing with regards this!
Thanks in advance. Mahesh


>
>Thanks for the responses so far. While am aware of the formatm(complex)
>and the values of the twiddles (after a good look around!) am looking
for
>some method of associating the various twiddle factors with the
>butterflies in each stage.
>e.g. For an 8 point DIF radix-2. We know there will be only 4 unique
>weights: w0,w1,w2,w3. These can be derived from the FFT equation with
>different values of k. The last stage (3rd) values would be multiplied
by
>1. Stage 1 and 2 remain with the interconnections between these being
>predetermined from what i understand. So from literature twiddles:
>w0,w1,w2,w3 are all used in the first stage. The second stage then
>utilises twiddles: w0,w2 twice. What i'd like to be able to do is work
out
>what weights each stage utilises and which butterfly would use each
weight.
>
>
>Cheers
>Mahesh
>
>
>
>>On May 21, 4:43 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>>> mahesh_u2 wrote:
>>> > I would be grateful if more info on the above could be provided
with
>>> > regards the equations to precompute the twiddle factors for each
>>> > stage/butterfly in the FFT. This is to enable me write a piece of
>code to
>>> > generate this ( i have not found much on this on the net).
>>>
>>> I believe that they can be easily generated using trig. identities.
>>> You have cos(theta) and sin(theta) for some theta, and need
>>> cos(theta/2) and sin(theta/2).
>>
>>sounds like generating them in bit-reversed order (which is useful for
>>certain FFT algs).
>>
>>r b-j
>>
>>
>>
>>
>
>
>
>_____________________________________
>Do you know a company who employs DSP engineers?  
>Is it already listed at http://dsprelated.com/employers.php ?
>



_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?

mahesh_u2 wrote:

> I think looking at my post again I need to clarify why i need to find out
> if there is a method of deriving the relationship between the FFT
> butterflies for the 8 point DIF case. I would like to extend this
> relationship for larger groupings i.e. 512 point(9 stages;

They are all sines and cosines of 2pi * successive negative powers
of two.  I would read the description in "Numerical Recipes in (x)"
for any x.  The descriptions should be the same, you may prefer the
examples to be in your favorite language.

-- glen

On May 24, 5:53 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> mahesh_u2 wrote:
> > I think looking at my post again I need to clarify why i need to find out
> > if there is a method of deriving the relationship between the FFT
> > butterflies for the 8 point DIF case. I would like to extend this
> > relationship for larger groupings i.e. 512 point(9 stages;
>
> They are all sines and cosines of 2pi * successive negative powers
> of two.

and remember, when computing/using these twiddle factors
chronologically, it depends on if it's DIT or DIF.  with DIT you will
be using these coefs in "bit-reversed order" (but you could set your
table up so that they are already in bit-reversed order).  and with
DIF, the coefs are in "normal order".

r b-j

On Mon, 21 May 2007 13:43:05 -0500, "mahesh_u2"
<mahesh_susindran@yahoo.co.uk> wrote:

>Hi all..
>
>I would be grateful if more info on the above could be provided with
>regards the equations to precompute the twiddle factors for each
>stage/butterfly in the FFT. This is to enable me write a piece of code to
>generate this ( i have not found much on this on the net).
>I am aware that for a DIF radix-2 FFT the total number of butterflies is
>(N/2 LogN). The total number of twiddle factors involved is ( N/2 ) for a
>radix-2 form. Also the last stage involves multiplication by a twiddle
>factor of 1. Could this be illustrated for an 8 point FFT for the 3
>stages. How can i
>allocate the values for the twiddle factors (cos ra + j sin ra) for the
>entire range and relate that to each stage and butterfly. While the
>interconnections between each stage more complex is there a pattern that
>can be established for the DIF radix-2 version. 
>I am currently implementing this in VHDL to generate the equivalent
>hardware and any clarifications, pointers on this would be great!
>
>Cheers
>Mahesh

Hello Mahesh,
  I didn't see your post until now.
If you're still interested, you may well 
find the answer to your question at:

Lyons, R. "Program Aids Analysis of FFT Algorithms", 
EDN Magazine, Aug. 6, 1987.

or in Section 13.16 of the book:

"Understanding Digital Signal Processing, 2nd edition,
 by R. Lyons.

What I think is the answer to your problem is far too 
involved to try to describe it here in ASCII text.

Good Luck,
[-Rick-]