This page is optimized for mobile devices, if you would prefer the desktop version just
click here
We have seen, previously, these four important facts: --the output of infinite-length LTI systems can be found via linear convolution--linear convolution can be found through circular convolution, through zero-padding --there is an equivalence between circular convolution in the signals' time domain and multiplication in their frequency domain--the FFT is an algorithm that can quickly compute a DFT Perhaps at the time it may have seemed that these findings were unrelated to each other. But as we now string them together, you can see the incredibly significant consequence: the output of LTI systems can be computed very efficiently. This truth has supported the incredible advances in signal processing over the past fifty years.
Putting it all together...
Suppose we have an LTI system with an impulse response of $h[n]$ and an input of $x[n]$. We would like to find the output, $y[n]$. We could find this output via linear (infinite length) convolution. If the length of the impulse response is $N_h$ and that of the input signal is $N_x$, then about $N_h N_x$ operations would be required to compute this convolution. It would also be possible to compute the output through circular convolution, by zero-padding each signal to be of length $N_h+N_x-1$, and then circularly convolving the zero-padded signals. This would not save any computational steps, but it is a significant insight because the circular convolution could be performed by using DFTs: simply take the DFT of each zero-padded signal, multiply the two DFTs together, then take the inverse DFT of the result. Again, this does not at first seem to save any computational steps, and in fact seems to add even more, except that we have seen that the FFT is able to perform DFTs in about $N\log N$ operations. What that means is that if we zero-pad $x[n]$ and $h[n]$, then take the DFT of each (using the FFT algorithm), multiply these two together, then take the inverse DFT of the result, we can find the system output in about $2(N_h+N_x-1)\log_2 (N_h+N_x-1)$ operations. As signal lengths increase, this can end up being huge computational savings over the $N_h N_x$ operations it would take to find the output through a convolution sum. Below is a graphical depiction of the steps to quickly find the output, with the help of the FFT:Read also:
OpenStax, Discrete-time signals and systems. OpenStax CNX. Oct 07, 2015 Download for free at https://legacy.cnx.org/content/col11868/1.2
Google Play and the Google Play logo are trademarks of Google Inc.