# Thread: Twiddle Factors in DFT

1. ## Twiddle Factors in DFT

Could someone kindly explain to me how to calculate the Fourier Transform with Twiddle Factors?

2. Originally Posted by Sling434
Could someone kindly explain to me how to calculate the Fourier Transform with Twiddle Factors?
You are asking about the detail of implementation of a FFT, your best resource is a text.

CB

3. Given a finite sequence $x(n)$ , $n=0,1,\dots, N-1$, its DFT is by definition the finite sequence...

$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...

$W_{N}^{kn} = e^{-i 2 \pi \frac{kn}{N}}$, $n=0,1,\dots, N-1$ , $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

$\chi$ $\sigma$

4. Originally Posted by chisigma
Given a finite sequence $x(n)$ , $n=0,1,\dots, N-1$, its DFT is by definition the finite sequence...

$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...

$W_{N}^{kn} = e^{-i 2 \pi \frac{kn}{N}}$, $n=0,1,\dots, N-1$ , $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

$\chi$ $\sigma$
You might as well have told them to look at the Wikipedia page, or their textbook, they would learn more that way (specifically how to do their own research)

CB

5. Originally Posted by CaptainBlack
You might as well have told them to look at the Wikipedia page, or their textbook, they would learn more that way (specifically how to do their own research)

CB

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?

6. Originally Posted by chisigma
Given a finite sequence $x(n)$ , $n=0,1,\dots, N-1$, its DFT is by definition the finite sequence...

$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...

$W_{N}^{kn} = e^{-i 2 \pi \frac{kn}{N}}$, $n=0,1,\dots, N-1$ , $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

$\chi$ $\sigma$
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!

7. Originally Posted by Sling434
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?
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

8. 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.

9. 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

$\chi$ $\sigma$

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# properties of twiddle factor in dft

Click on a term to search for related topics.