next Dual of the Convolution Theorem
previous Application of the Shift Theorem to FFT Windows
up The Fourier Theorems   Index   Search


Convolution Theorem



Theorem: For any $ x,y\in{\bf C}^N$,

$\displaystyle \zbox {x\ast y \leftrightarrow X\cdot Y.}
$



Proof:

\begin{eqnarray*}
\mbox{\sc DFT}_k(x\ast y) &\isdef & \sum_{n=0}^{N-1}(x\ast y)_...
...ht)Y(k)\quad\mbox{(by the Shift Theorem)}\\
&\isdef & X(k)Y(k)
\end{eqnarray*}

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

The simple matlab example in Fig. 7.11 illustrates how much faster convolution can be performed using the FFT.7.9 We see that for a length $ N=1024$ convolution, the FFT is approximately 300 times faster in Octave, and 30 times faster in Matlab. (The conv routine is much faster in Matlab.)

Figure 7.11: Matlab/Octave program for comparing the speed of direct convolution with that of FFT convolution.

 
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.10In this software environment, the FFT is faster starting with length $ 2^6=64$, and it is never significantly slower at short lengths where ``calling overhead'' dominates.


Table: Direct versus FFT convolution times in milliseconds (convolution length = $ 2^M$) using Matlab 5.2 on an 800 MHz Athlon Windows PC.
M Direct FFT Ratio
1 0.07 0.08 0.91
2 0.08 0.08 0.92
3 0.08 0.08 0.94
4 0.09 0.10 0.97
5 0.12 0.12 0.96
6 0.18 0.12 1.44
7 0.39 0.15 2.67
8 1.10 0.21 5.10
9 3.83 0.31 12.26
10 15.80 0.47 33.72
11 50.39 1.09 46.07
12 177.75 2.53 70.22
13 709.75 5.62 126.18
14 4510.25 17.50 257.73
15 19050.00 72.50 262.76
16 316375.00 440.50 718.22


A table similar to Table 7.1 in Strum and Kirk [62, p. 521], based on the number of real multiplies, finds that the FFT is faster starting at length $ 2^7=128$, 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).

See Appendix A for further discussion of the FFT and its applications.


next Dual of the Convolution Theorem
previous Application of the Shift Theorem to FFT Windows
up The Fourier Theorems   Index   Search

``Mathematics of the Discrete Fourier Transform (DFT), with Music and Audio Applications'', by Julius O. Smith III, W3K Publishing, 2003, ISBN 0-9745607-0-7.

(Browser settings for best viewing results)
(How to cite this work)
(Order a printed hardcopy)

Copyright © 2004-09-24 by Julius O. Smith III
W3K Publishing,
World Wide Web of Knowledge