Could someone kindly explain to me how to calculate the Fourier Transform with Twiddle Factors?
Given a finite sequence $\displaystyle x(n)$ , $\displaystyle n=0,1,\dots, N-1$, its DFT is by definition the finite sequence...
$\displaystyle X(k)= \sum_{n=0}^{N-1} x(n)\cdot e^{-i 2 \pi \frac{kn}{N}}, k=0,1,\dots,N-1$ (1)
The terms...
$\displaystyle W_{N}^{kn} = e^{-i 2 \pi \frac{kn}{N}}$, $\displaystyle n=0,1,\dots, N-1$ , $\displaystyle k=0,1,\dots,N-1$ (2)
... are called 'Twiddle Factors' and each of them is one of the N roots of order N of the unity...
Kind regards
$\displaystyle \chi$ $\displaystyle \sigma$
Twiddle factor - Wikipedia, the free encyclopedia
^^Not exactly very informative I think you'll agree! There are no entries in the index for 'twiddle factors' in any of the textbooks I have either. I did try to research this and don't about know the resources you may know about, believe it or not good sir.
I need to know how to calculate the DFT equivalent using twiddle factors. It seems that using twiddle factors effectively makes it a FFT?
Er sorry to bring this up but isn't this basically the DFT formula, but with the exponential components called 'W', and then you've labelled them the twiddle factors?
Maybe I'm just being blind but I don't see how this algorithm really differs from the DFT equation!
Granted, twiddle factors are a fairly obscure aspect of Fourier Transform (or so it seems to me) - but that's why I'm resorting to asking on an internet forum!
The reason is that at a top level the twiddle factors appear to be no more than the terms in the transformation matrix defining the DFT. The art in FFTs lies in the efficient accurate calculation of these and the organisation of the rest of the arithmetic.
You probably need to look at a text specifically on the FFT (you will find a number of these construct FFT algorithms without ever using the term Twiddle Factor), it is certainly beyound the scope of MHF for us to derive and or explain the detail of a FFT algorithm.
CB
I have been trying to research this, I have taken two books out of the library, but nothing I can find is helping me with the assignment I have been given.
In this C programming assignment, I need to calculate twiddle factors outside the fourier transform function. I am not able to use exp (ie sin or cos) components within the fourier transform function in the code. I can only call on the twiddle factors as a function input.
There is nothing I can find which is of any use for this in any of the textbooks I can find.
A good enough article on the Twiddle Factors is...
http://iccd.et.tudelft.nl/Proceeding...pers/1.1.1.pdf
... but it requires previous knowledge of the basic Cooley-Tuckey FFT algorithm...
Kind regards
$\displaystyle \chi$ $\displaystyle \sigma$