Results 1 to 9 of 9

Math Help - Twiddle Factors in DFT

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Twiddle Factors in DFT

    Could someone kindly explain to me how to calculate the Fourier Transform with Twiddle Factors?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Sling434 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by chisigma View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    5
    Quote Originally Posted by CaptainBlack View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    Posts
    5
    Quote Originally Posted by chisigma View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Sling434 View Post
    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
    Last edited by CaptainBlack; November 12th 2009 at 05:46 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2009
    Posts
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. factors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 7th 2010, 08:26 AM
  2. Replies: 1
    Last Post: December 7th 2009, 11:42 AM
  3. sum of factors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 25th 2009, 07:23 AM
  4. Factors of 2310 and Factors of 1365
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 7th 2008, 07:56 PM
  5. Factors
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 4th 2007, 05:37 AM

Search Tags


/mathhelpforum @mathhelpforum