FFT twiddle calculation and evaluation

[mahesh_u2]

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
radix-2 form. Also the last stage involves multiplication by a twiddl
factor of 1. Could this be illustrated for an 8 point FFT for the
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 th
interconnections between each stage more complex is there a pattern tha
can be established for the DIF radix-2 version.
I am currently implementing this in VHDL to generate the equivalen
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 ?

[glen herrmannsfeldt]

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

[robert bristow-johnson]

On May 21, 4:43 pm, glen herrmannsfeldt <[email protected]> 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

[Andor]

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

[mahesh_u2]

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 fo
some method of associating the various twiddle factors with th
butterflies in each stage.
e.g. For an 8 point DIF radix-2. We know there will be only 4 uniqu
weights: w0,w1,w2,w3. These can be derived from the FFT equation wit
different values of k. The last stage (3rd) values would be multiplied b
1. Stage 1 and 2 remain with the interconnections between these bein
predetermined from what i understand. So from literature twiddles
w0,w1,w2,w3 are all used in the first stage. The second stage the
utilises twiddles: w0,w2 twice. What i'd like to be able to do is work ou
what weights each stage utilises and which butterfly would use each weight


Cheers
Mahesh



>On May 21, 4:43 pm, glen herrmannsfeldt <[email protected]> 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 o
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 ?

[mahesh_u2]

Hi all,
I think looking at my post again I need to clarify why i need to find ou
if there is a method of deriving the relationship between the FF
butterflies for the 8 point DIF case. I would like to extend thi
relationship for larger groupings i.e. 512 point(9 stages; 256 comple
twiddles), 1024 point (10 stages; 512 complex twiddles) whereby I can wor
out for a fixed number of butterflies how each intermediate value is fe
into the next stages butterfly with the respective twiddle values. As ha
been mentioned; the twiddle factors are reused in particular sequences fo
each stage. Would there be any literature showing how this can be worke
out for larger stages (given a particular FFT lenght) or if there is
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 lookin
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 multiplie
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 wor
out
>what weights each stage utilises and which butterfly would use eac
weight.
>
>
>Cheers
>Mahesh
>
>
>
>>On May 21, 4:43 pm, glen herrmannsfeldt <[email protected]> wrote:
>>> mahesh_u2 wrote:
>>> > I would be grateful if more info on the above could be provide
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]

Hi all,
I think looking at my post again I need to clarify why i need to find ou
if there is a method of deriving the relationship between the FF
butterflies for the 8 point DIF case. I would like to extend thi
relationship for larger groupings i.e. 512 point(9 stages; 256 comple
twiddles), 1024 point (10 stages; 512 complex twiddles) whereby I can wor
out for a fixed number of butterflies how each intermediate value is fe
into the next stages butterfly with the respective twiddle values. As ha
been mentioned; the twiddle factors are reused in particular sequences fo
each stage. Would there be any literature showing how this can be worke
out for larger stages (given a particular FFT lenght) or if there is
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 lookin
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 multiplie
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 wor
out
>what weights each stage utilises and which butterfly would use eac
weight.
>
>
>Cheers
>Mahesh
>
>
>
>>On May 21, 4:43 pm, glen herrmannsfeldt <[email protected]> wrote:
>>> mahesh_u2 wrote:
>>> > I would be grateful if more info on the above could be provide
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 ?

[glen herrmannsfeldt]

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

[robert bristow-johnson]

On May 24, 5:53 pm, glen herrmannsfeldt <[email protected]> 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

[Rick Lyons]

On Mon, 21 May 2007 13:43:05 -0500, "mahesh_u2"
<[email protected]> 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-]