Comparing arithmetic complexity of FFT radix-2 and convolution

Question

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?

Answer 1

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.