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". Jun 10, 2019 at 14:18

Let the input signal $$x[n]$$ has a legth of $$N=50$$ samples, and the filter $$h[n]$$ has a length of $$M=10$$ samples, then the output $$y[n]$$ (by linear conv) will have a length of $$L = N+M-1=59$$ samples.

If you use time-domain convolution, then the number of real MACS can be seen to be $$N \cdot M = 50 \times 10 = 500$$.

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 $$Y[k]$$ to get the output $$y[n]$$.

Each $$R$$-point FFT (and IFFT) requires about $$\frac{1}{2} R \cdot \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 more efficient than an FFT based implementation.

• 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, 2019 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. Jun 9, 2019 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, 2019 at 11:04
• @MJ13 yes that's right... Jun 9, 2019 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, 2019 at 11:10