Number of complex calculations in FFT and inverse FFT

[Jimmy Johnson]

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]
Nlog₂N

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) = 4log₂4 = 8
x2(n) = 5log₂5 = 11.61

product of both created an 8 length vector

8log₂8 = 24Do I add these? The 5 one doesn't seem correct, something about it being a prime factor that doesn't hold for the equation?

 

[DrClaude]

Homework Equations

[/B]
Nlog₂N

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.

 

[Jimmy Johnson]

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?

 

[DrClaude]

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?