1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of complex calculations in FFT and inverse FFT

  1. Jan 26, 2015 #1
    1. The problem statement, all variables and given/known data

    Calculate the total number of compex multiplications required for the calculation in (b) when FFTs are used to perform the Discrete Fourier Transforms and Inverse Discrete Fourier Transforms.

    There were two FFT multiplied together and one inverse FFT of that product to solve B.

    x1(n) = [1, 0, −1, 1]

    x2(n) = [2, 3, 2, 0, 1

    2. Relevant equations

    Nlog2N

    3. The attempt at a solution

    The vectors were padded with zeros but I'm working under the assumption that can be negated.

    x1(n) = 4log24 = 8
    x2(n) = 5log25 = 11.61

    product of both created an 8 length vector

    8log28 = 24


    Do I add these? The 5 one doesn't seem correct, something about it being a prime factor that doesn't hold for the equation?
     
  2. jcsd
  3. Jan 26, 2015 #2

    DrClaude

    User Avatar

    Staff: Mentor

    Note that the FFT algorithm scales as ##O(N \log_2 N)##, not that the number of operations is exactly ##N \log_2 N## (I don't know if this is relevant to your problem, because I don't know how your teacher presented the material).

    Why? What is the computer actually calculating?


    You probably only learned about an algorithm that works for ##2^N## data points. Therefore an FFT on length 5 doesn't make any sense.
     
  4. Jan 26, 2015 #3
    What is the O on that scale equation?

    The calculation is the circular convolution of the x1(t) and x2(t) through ifft(fftx1padded)*(fftx2padded), so the padding was adding zeroes to the vector so that it was the same length and therefore achievable in matlab? after convolution a length 8 was determined and x1&2(t) are 4&5 length vectors respectively?

    So would my data points actually be 2^4 and 2^5?
     
  5. Jan 26, 2015 #4

    DrClaude

    User Avatar

    Staff: Mentor

    It's big O notation. It tells you how an algorithm scales when you change the size of the data. If an algorithm is of order ##O(n^2)##, then doubling the number of data points will result in about 4 times the number of operations. But it doesn't mean that it will perform exactly ##n^2## operations. The actual number of operations could be ##4 n^2 + 2 n##.

    Why is padding necessary? What do you think matlab is doing with these zeros?
     
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: Number of complex calculations in FFT and inverse FFT
  1. FFT - Special exercise (Replies: 6)

  2. Units of FFT in matlab (Replies: 6)

  3. FFT vs Filon's rule (Replies: 0)

Loading...