Application of the Shift Theorem to FFT Windows

The Fourier Theorems

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 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 . 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.

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
convolution, the FFT is approximately 300 times faster in Octave, and
30 times faster in Matlab. (The `conv` routine is much faster
in Matlab.)

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.10}In this software environment, the FFT 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
[62, 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).

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

Dual of the Convolution Theorem

Application of the Shift Theorem to FFT Windows

The Fourier Theorems

``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 ©

W3K Publishing,