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$
1
  • $\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, 2019 at 14:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
20
  • $\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, 2019 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, 2019 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, 2019 at 11:04
  • $\begingroup$ @MJ13 yes that's right... $\endgroup$
    – Fat32
    Jun 9, 2019 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, 2019 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.