Phase/twiddle factors calculations

Hi all

Ive decided to take the plunge and try to figure out how actually the FFT
works by doing my own implmentation. DSP isnt my area and I am having a
couple of problems understanding exactly what goes on under the hood. 

The main point that Im struggling with at the moment is the twiddle
factors, namely how to calculate them within the butterfly loop in a real,
in-place, DIT FFT.

My understanding is that the twiddle factor is 
 
 nk
W
 N

where N is the number of samples in the input data
      k is the frequency bin that the current calculation goes into
      n is the sample number

the part that im unsure about is the n term and possibly the k. 

so say i have an 8 sample bit reversed input array that ive already
recombined so that it currently consists of 2 four point dft's, to compute
the final dft;

[a][b][c][d][e][f][g][h]
combines into

[a+(Wkn)e][b+(Wkn)f][c+(Wkn)g][d+(Wkn)h][a-(Wkn)e][b-(Wkn)f][c-(Wkn)g][d-(Wkn)h]
             
             kn
where Wkn = W
             N

so N = 8, k = index of the frequency bin(?) and n = not sure, possibly the
sample number of the term multiplied by Wnk?

Im sure Im misinterpreting something about the twiddle factors thats
affecting my understanding of exactly whats happening and hence my ability
to implement it. Its a basic question but any
help/clarification/corrections greatly appreciated!

thanks in advance

take a look at this thread:

http://groups.google.com/group/comp.dsp/browse_thread/thread/f5cf80ff9a8a820e/9618b0c210804570#9618b0c210804570

dunno if Dr. FFTW would agree or not (and i gladly defer to him as the
FFT expert here) but for my money, it was easier for me to deal with
the radix-2 DIF Cooley-Tukey FFT than the DIT.  with DIF, you split the
DFT summation into two halves with the earlier indices in one and the
latter indices in the other (whereas the DIT puts the evens indices in
one and the odds in another).  the data goes into the DIF FFT in normal
order and comes out in bit-reversed order whereas for the DIT it's the
other way around.

a long time ago i wrote an FFT (using DIF) and an iFFT (using DIT) in C
so that the first took normal order data and returned bit-reversed and
the latter took bit-reversed order data and returned normal order.  i
used this in a so-called "fast convolution", and i thought that this
was sorta optimal because the transfer function H[k] would also be
pre-calculated and pre-bit-reversed, so that there was no bit reversing
done in the fast-convolution itself.  i once posted the code, it's
pretty simple but not hyper-optimzed like FFTW is.

r b-j

robert bristow-johnson wrote:
> but for my money, it was easier for me to deal with
> the radix-2 DIF Cooley-Tukey FFT than the DIT.

Since DIT and DIF algorithms are simply transposes of one another, they
can always be implemented with essentially the same amount of code and
should be the same difficulty.  You essentially just reverse the steps
to get DIT from DIF or vice versa.

stevenj@alum.mit.edu wrote:
> robert bristow-johnson wrote:
> > but for my money, it was easier for me to deal with
> > the radix-2 DIF Cooley-Tukey FFT than the DIT.
>
> Since DIT and DIF algorithms are simply transposes of one another, they
> can always be implemented with essentially the same amount of code and
> should be the same difficulty.  You essentially just reverse the steps
> to get DIT from DIF or vice versa.

no dispute with that, Steven.  i just meant that, conceptually or
pedagogically, it's easier for me to start with the simple DFT
definition and fanagle that into the DIF algorithm.

r b-j

Many thanks Rob and Steve for replying so soon.

I had a look at that link and it did clear up a couple of things for me. I
understand the difference between DIF and DIT approaches and I think Ive
made a bit of progress. I now believe the twiddle factors are calcuated as
follows (still using the DIT approach)

where
WX = W(N) ^ X, (N) being a subscript to W

n = sample number, k = frequency bin

2 point dft's - N = 2
[] []  [] []
00 11  00 11
nk nk  nk nk
W0 W1  W0 W1

4 point dft's - N = 4
[] [] [] []  [] [] [] []
00 01 02 03  10 11 12 13
nk nk nk nk  nk nk nk nk
W0 W0 W0 W0  W0 W1 W2 W3

8 point dft's - N = 8
[] [] [] [] [] [] [] []  [] [] [] [] [] [] [] []
00 01 02 03 04 05 06 07  10 11 12 13 14 15 16 17
nk nk nk nk nk nk nk nk  nk nk nk nk nk nk nk nk
W0 W0 W0 W0 W0 W0 W0 W0  W0 W1 W2 W3 W4 W5 W6 W7

and so forth. Im still a bit shoddy on the physical interpretation of the
twiddle factors, but I believe one way of looking at them is a result of
shifting the odd samples in the time domain to facilitate the
recombination, this shift being essentally a convolution with a shifted
impulse/delta function, and hence the frequency domain equivalent being
the multiplication of the spectrum by a sinusoid.

Please feel free to correct any mistakes or misconceptions in the above or
to add anything.

Thanks again!

SeanOg wrote:


> Im still a bit shoddy on the physical interpretation of the
> twiddle factors, but I believe one way of looking at them is a result of
> shifting the odd samples in the time domain to facilitate the
> recombination, this shift being essentally a convolution with a shifted
> impulse/delta function, and hence the frequency domain equivalent being
> the multiplication of the spectrum by a sinusoid.
> 
> Please feel free to correct any mistakes or misconceptions in the above or
> to add anything.
> 
>

SeanOg,
That is one way of looking at it, but there is a relatively simple 
physical interpretation of the fiddle-factor which I would like to add.

I will consider the final stage of a decimation-in-time FFT where two 
N/2-length FFTs are combined to form one N-length FFT.

One N/2-length FFT will have been been generated from the 'even' 
time-domain samples and the other from the 'odd' samples.  The set of 
time-domain samples contributing to the 'odd' N/2-length FFT has a delay 
of one sample-period relative the 'even' set, and this introduces an 
increasing phase-offset into each of the 'odd' frequency components. 
This phase-offset is proportional to the frequency of the component.

When the two half-length FFTs are combined to form a single full-length 
FFT, an increasing phase-adjustment must be made to the frequency 
components from the 'odd' FFT before summing them with their 'even' 
counterparts.  This adjustment is done by multiplying each 'odd' 
component by a complex factor having unit-amplitude and a phase-angle 
which varies from zero up to 2*pi*(N-1)/N radian.  The complex 
phase-adjustment factors are known as the 'twiddle' factors.

Conceptually, two 'sweeps' through the N/2-length FFTs are necessary to 
generate N output components, but the FFT Butterfly applies some cunning 
trigonometry so that only one sweep is needed and that only N/2 complex 
phase-adjustment factors are needed.

A similar analysis to the above can be applied to the second-last stage 
and so on, working back from the FFT's last stage.

Regards,
John

Many thanks for that great explaination John, makes a lot of sense. 

Ive the algorithm implemented and its doing what I want it to do so the
programming is fine, however im getting some strange results so one of my
steps is incorrect conceptually, so Ill probally be back to pick your
brains some more!

thanks again

SeanOg wrote:
> Many thanks for that great explaination John, makes a lot of sense. 
> 
> Ive the algorithm implemented and its doing what I want it to do so the
> programming is fine, however im getting some strange results so one of my
> steps is incorrect conceptually, so Ill probally be back to pick your
> brains some more!
> 
> thanks again


I'm glad you found it useful SeanOrg, and I would be glad to help 
further if possible.

Regards,
John

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). 
I am aware that for a DIF radix-2 FFT the total number of butterflies is
N/2LogN. The total number of twiddle factors involved is ( N/2 - 1). 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
calculate the values for the twiddle factors (cos ra + j sin ra) for the
entire range and relate that to each stage and butterfly.
Any clarifications, pointers on this would be great!
Cheers





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

On Fri, 18 May 2007 08:59:40 -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). 
>I am aware that for a DIF radix-2 FFT the total number of butterflies is
>N/2LogN. The total number of twiddle factors involved is ( N/2 - 1). 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
>calculate the values for the twiddle factors (cos ra + j sin ra) for the
>entire range and relate that to each stage and butterfly.
>Any clarifications, pointers on this would be great!
>Cheers

Hello Mahesh,
  I didn't see your post until now.
If you're still interested, you can 
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.

The answer to your problem is far too involved
to try to decribe it here in ASCII text.

Good Luck,
[-Rick-]