# Comparing arithmetic complexity of FFT radix-2 and convolution

Let's assume we have a discrete linear time invariant system and we have a real signal $$x[n]$$ with length N=50 as input for the system.

The impulse response $$h[n]$$ of the system is considered to be also a real signal with length M=10.

We want to calculate the output signal $$y[n]$$.

There are two ways we can do this: We can either convolute the signals $$x[n]$$,$$h[n]$$ in the time domain or use FFT radix-2 and work on the frequency domain.

I want to compare the arithmetic complexity of these two methods in number of real multiplications.I know that the arithmetic complexity of convolution is $$N \cdot M$$ since $$N \cdot M$$ real multiplications are required in order to calculate $$y[n]$$. However, I am bit confused with FFT-radix 2.

I know that it requires $$μ(Ν) = \frac{N}{2}\log _{2}N$$ complex multiplications. Every complex multiplication is equivelant to 4 real multiplications. So how many real multiplications are required to calculate $$y[n]$$? Do I have to calculate first both $$X[k]$$ and $$H[k]$$ by using $$\frac{50}{2}\log _{2}50 + \frac{10}{2}\log _{2}10$$ real multiplications? And if so, how do I go on?

• If you have an input signal that's substantially longer then the filter, the best way to go is often "overlap add", i.e. you break it down into a set of smaller FFTs instead one large one. In your example, this won't make much of a difference since both signal and impulse response are "short". – Hilmar Jun 10 at 14:18

Signal $$x[n]$$ has $$N=50$$ samples and the filter $$h[n]$$ has $$M=10$$ samples. The output $$y[n]$$ (by linear conv) will have length $$L = N+M-1=59$$ samples.

If you use time domain convolution, for each output sample (except the edges) you will be making $$M=10$$ real MACs. And this makes the number of total real MACs as $$K = L \cdot M = 59 \times 10 = 590$$. The actual number is less than this due to edges requiring less number of MACs. Inded the exact number of real MACS is $$N \cdot M$$ referring to input signal length instead of the output.

If you want to use radix-2 FFT to implement the linear convolution result, then you should select a length of $$R = 64$$ for FFTs. And you will 1- convert $$x[n]$$ and $$h[n]$$ into $$X[k]$$ and $$H[k]$$ by two $$R$$ point FFTS, 2- multiply the results to get $$Y[k] = X[k]H[k]$$ and 3- apply inverse FFT of $$R$$ point on the multiplication to get the output $$y[n]$$.

Each $$R$$ point FFT (and IFFT) requires about $$0.5 R \log_2(R)$$ complex MACs. One complex MAC is 4 real MACs therefore this is equivalent to $$2 R \log_2(R) = 128 \log_2(64) = 128 \times 6 = 768$$ real MACs. And the total of two FFTs and one inverse FFT requires about $$3 \times 768 = 2304$$ real MACs. The intermediate multiplication also requires $$4 \times R = 256$$ real MACs and hence FFT based implementation requires a total of $$2560$$ real MACs...

So in this case time domain convolution is (approx) about 80 % more efficient compared to FFT based filtering.

• Thanks for your answer!It is really helpful!However,If the length $R$ of FFTs is not specified and I want to make a comparison about the complexity of these two methods (knowing only the lengths of $x[n]$ and $h[n]$ as in it is in this example) which is the appropriate value for the FFT length $R$ ? I mean if I want to make a general comparison between these two methods by knowing only the lengths of input signal and impulse response signal which is a correct estimation for the value of $R$?Cause in this case we got that $R=64$ in order to decide which method is more efficient – MJ13 Jun 9 at 10:57
• For radix-2 FFT the best R that yields minimum number of MACs is R = 64. For non radix-2 FFT then the minimum R that yields the output $y[n]$ without aliasing is $R = 59$. However the formula $0.5 R \log_2(R)$ is valid for radix-2 FFT complexity computation. Non radix-2 FFT compexity is larger than radix-2 case. – Fat32 Jun 9 at 11:00
• So if I get it right, in my case, I can assume that $R=64$ and make the calculations as u did, right? – MJ13 Jun 9 at 11:04
• @MJ13 yes that's right... – Fat32 Jun 9 at 11:09
• Ok...Just one thing I don't get...Doesn't the length $R$ of the FFTs have to be smaller or equal to the length of the sequences? I mean input signal sequence $x[n]$ has length $N=50$. How can we apply a DFT of $R$ samples? What am I missing? – MJ13 Jun 9 at 11:10