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?

 

[rezeew]

I would like to clarify a few things before providing a response. First, the statement mentions calculating the total number of complex multiplications, but the attempt at a solution only considers the total number of calculations (which includes additions, subtractions, etc.). Is the question specifically asking for the number of complex multiplications, or the total number of calculations?

Secondly, the attempt at a solution uses the equation Nlog2N, which is the theoretical number of calculations for a FFT of length N. However, this is not necessarily the same as the actual number of calculations that would be required for a specific set of data. The actual number of calculations can vary depending on the specific implementation of the FFT algorithm and the data being processed.

Assuming that the question is asking for the total number of complex multiplications, and based on the given vectors, here is a possible response:

To calculate the total number of complex multiplications required for the FFT and inverse FFT in this case, we need to consider the following:
1. Each FFT requires Nlog2N complex multiplications, where N is the length of the input vector.
2. The product of two FFTs (x1(n) and x2(n)) will result in an output vector of length 8, which would require 8log28 = 24 complex multiplications.
3. The inverse FFT of this product would also require 8log28 = 24 complex multiplications.
Therefore, the total number of complex multiplications required for this calculation would be 2(Nlog2N) + (8log28) = 2(4log24) + (8log28) = 16 + 24 = 40 complex multiplications.