Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

FFT questions

Tags:
  1. Nov 18, 2016 #1
    1) How many stages are in N numbers for a FFT? I know N=8 has 3 stages and N=4 has 2 stages ?
    2) The DFT formula converts a signal from the time domain in to the frequency domain. Is this done by comparing x[n] against signals known as sinusoidal basis functions? are e-j2 pi kn/N sinusoidal basis functions ? I know it uses Correlation and that mean it compares the variables together but I am not 100% sure how this work ?

    3) In a butterfly diagram the bottom line is alway -1, but why?

    PS, I have been reading and watch videos on the DFT and the FFT and I have learned a lot, but I am just not sure about this questions.
     
  2. jcsd
  3. Nov 19, 2016 #2
    anyone ?
     
  4. Nov 21, 2016 #3

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    It depends ... perhaps that is why no one has replied. If you are doing a radix 2 FFT of [itex]N=2^M[/itex] points then sure, you have [itex]M[/itex] stages. But at the end of the day we all want software that is efficient, and radix 2 isn't always the answer. It doesn't even apply to something like a 100 point FFT. There are a number of different algorithms. Some use prime factors, some don't.

    First, the built-in assumption is that the sequence [itex]x[n][/itex] of [itex]N[/itex] numbers is one period of a periodic sequence. So it is reasonable to try and represent the sequence as a sum of complex exponentials that are consistent with the assumed periodicity of the given sequence. Now look at the formula for the DFT ,
    [tex]
    X_k = \sum_{n=0}^{N-1} x_n e^{-j 2 \pi k n / N}
    [/tex]
    and the inverse,
    [tex]
    x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{j 2 \pi k n / N}
    [/tex]
    I think of this as projecting the sequence [itex]x_n[/itex] onto a set of orthogonal basis functions [itex]e^{j 2 \pi k n /N} [/itex], and the [itex]X_k[/itex] are just the inner product (or dot product) of the sequence and the [itex]k^{th}[/itex] basis function. By orthogonal, I just mean,
    [tex]
    \sum_{k=0}^{N-1} e^{j 2 \pi k_1 n / N} e^{-j 2 \pi k_2 n / N} = N \delta_{k_1,k_2}
    [itex]
    where [itex]\delta_{k_1,k_2}[/itex] is 1 if [itex]k_1\neqk_2[/itex] and 0 if [itex]k_1\neq k_2[/itex].

    The math is the same as representing a vector [itex]v[/itex] in terms of a set of orthogonal basis vectors [itex]w_k[/itex]. The only thing different from what you probably did in basic vector algebra is that our sequence and the complex sinusoids can all be complex, so for the inner product one of the items is conjugated.


    Sorry, I can't help you here. I haven't looked at a butterfly diagram in 20+ years! I do work with folks that implement FFTs in FPGAs and other hardware, and if I had such a job then I would know the butterfly inside and out. Hopefully someone else can help.

    jason
     
  5. Nov 22, 2016 #4
    sorry but I am not really understanding your second answer. Why is it "represent the sequence as a sum of complex exponential "?
     
  6. Nov 24, 2016 #5

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    The IFFT is
    [tex]
    x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{j 2 \pi k n / N}
    [/tex]
    The left hand side is the original sequence; the right side is a sum of complex exponentials.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: FFT questions
  1. FFT question (Replies: 6)

  2. Phase of FFT (Replies: 4)

Loading...