Number of complex calculations in FFT and inverse FFT

  • #1

Homework Statement



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.[/B]
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

Homework Equations


[/B]
Nlog2N

The Attempt at a Solution


[/B]
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?
 

Answers and Replies

  • #2
DrClaude
Mentor
7,554
3,894

Homework Equations


[/B]
Nlog2N
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).

The vectors were padded with zeros but I'm working under the assumption that can be negated.
Why? What is the computer actually calculating?


The 5 one doesn't seem correct, something about it being a prime factor that doesn't hold for the equation?
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.
 
  • #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?
 
  • #4
DrClaude
Mentor
7,554
3,894
What is the O on that scale equation?
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##.

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?
Why is padding necessary? What do you think matlab is doing with these zeros?
 

Related Threads on Number of complex calculations in FFT and inverse FFT

  • Last Post
Replies
6
Views
11K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
9
Views
2K
Replies
3
Views
6K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
3K
Top