Convolution Theorem

**Theorem: **For any
,

*Proof: *

This is perhaps the most important single Fourier theorem of all. It
is the basis of a large number of FFT applications. Since an FFT
provides a fast Fourier transform, it also provides *fast
convolution*, thanks to the convolution theorem. It turns out that
using an FFT to perform convolution is really more efficient in
practice only for reasonably long convolutions, such as . For
much longer convolutions, the savings become enormous compared with
``direct'' convolution. This happens because direct convolution
requires on the order of operations (multiplications and
additions), while FFT-based convolution requires on the order of
operations, where denotes the logarithm-base-2 of
(see §A.1.2 for an explanation).

The simple matlab example in Fig.7.13 illustrates how much faster
convolution can be performed using an FFT.^{7.11} We see that for a length convolution,
the `fft` function is approximately 300 times faster in Octave,
and 30 times faster in Matlab. (The `conv` routine is much
faster in Matlab, even though it is a built-in function in both
cases.)

N = 1024; % FFT much faster at this length t = 0:N-1; % [0,1,2,...,N-1] h = exp(-t); % filter impulse reponse H = fft(h); % filter frequency response x = ones(1,N); % input = dc (any signal will do) Nrep = 100; % number of trials to average t0 = clock; % latch the current time for i=1:Nrep, y = conv(x,h); end % Direct convolution t1 = etime(clock,t0)*1000; % elapsed time in msec t0 = clock; for i=1:Nrep, y = ifft(fft(x) .* H); end % FFT convolution t2 = etime(clock,t0)*1000; disp(sprintf([... 'Average direct-convolution time = %0.2f msec\n',... 'Average FFT-convolution time = %0.2f msec\n',... 'Ratio = %0.2f (Direct/FFT)'],... t1/Nrep,t2/Nrep,t1/t2)); % =================== EXAMPLE RESULTS =================== Octave: Average direct-convolution time = 95.17 msec Average FFT-convolution time = 0.32 msec Ratio = 299.20 (Direct/FFT) Matlab: Average direct-convolution time = 15.73 msec Average FFT-convolution time = 0.50 msec Ratio = 31.46 (Direct/FFT) |

A similar program produced the results for different FFT lengths shown
in Table 7.1.^{7.12}In this software environment, the `fft` function is faster
starting with length , and it is never significantly slower at
short lengths, where ``calling overhead'' dominates.

A table similar to Table 7.1 in Strum and Kirk
[77, p. 521], based on the number of real
multiplies, finds that the `fft` is faster starting at length ,
and that direct convolution is significantly faster for very short
convolutions (*e.g.*, 16 operations for a direct length-4 convolution,
versus 176 for the `fft` function).

See Appendix A for further discussion of FFT algorithms and their applications.

[How to cite this work] [Order a printed hardcopy]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

[Automatic-links disclaimer]