2
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Hilmar Jun 10 '19 at 14:18
2
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – MJ13 Jun 9 '19 at 10:57
  • $\begingroup$ 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. $\endgroup$ – Fat32 Jun 9 '19 at 11:00
  • $\begingroup$ So if I get it right, in my case, I can assume that $R=64$ and make the calculations as u did, right? $\endgroup$ – MJ13 Jun 9 '19 at 11:04
  • $\begingroup$ @MJ13 yes that's right... $\endgroup$ – Fat32 Jun 9 '19 at 11:09
  • $\begingroup$ 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? $\endgroup$ – MJ13 Jun 9 '19 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.