FFT Zero-Padding Strategies - Introduction
FFT-based convolution can be performed faster by using a different zero-padding strategy than what is commonly used.
It is widely known that FFTs can be used to compute convolution. Depending on the sizes of the inputs, an FFT-based convolution method can be faster, sometimes substantially faster, than a direct implementation of the convolution sum.
This post is the first in a short series that will present an implementation of FFT-based convolution that is faster than what is typically done in MATLAB. The improvement is achieved by using a different zero-padding strategy than what is commonly used.
Table of Contents
Using FFTs to compute convolution
Common zero-padding strategies
Basic FFT function syntaxes
If the vector x
has $k$ elements, then fft(x)
computes the $k$ -point FFT. The output has the same length as the input. For example:
x = [1 2 3];
fft(x)
ans = 1x3 complex
6.0000 + 0.0000i -1.5000 + 0.8660i -1.5000 - 0.8660i
The fft
function has another syntax, fft(x,n)
. With this syntax, fft
computes the $n$ -point FFT. Typically, this syntax has the effect of zero-padding x
so that it has length $n$ and then computing the $n$ -point FFT of the zero-padded vector. For example:
X1 = fft(x,5)
X1 = 1x5 complex
6.0000 + 0.0000i -0.8090 - 3.6655i 0.3090 + 1.6776i 0.3090 - 1.6776i -0.8090 + 3.6655i
That computation is equivalent to:
X2 = fft([x 0 0])
X2 = 1x5 complex
6.0000 + 0.0000i -0.8090 - 3.6655i 0.3090 + 1.6776i 0.3090 - 1.6776i -0.8090 + 3.6655i
isequal(X1,X2)
ans = logical
1
Using FFTs to compute convolution
One application of zero-padded FFTs is using FFTs to compute convolution. If the vector x
has $K$ points and the vector h
has $L$ points, then the convolution of x
and h
has $K+L-1$ points. FFTs can be used to compute this convolution, but only if x
and h
are zero-padded to have at least $K+L-1$ points in the FFT computation. The code would look something like this:
x = [1 -1 0 4];
h = [1 0 -1];
K = length(x);
L = length(h);
N = K + L - 1
N = 6
X = fft(x,N); % Computes N-point zero-padded FFT
H = fft(h,N); % Computes N-point zero-padded FFT
y = ifft(X .* H)
y = 1x6
1.0000 -1.0000 -1.0000 5.0000 -0.0000 -4.0000
Common zero-padding strategies
You can zero-pad more and still get the same result (except perhaps for some floating-point round-off differences). The code below zero-pads to length 10 instead of 6:
X = fft(x,10);
H = fft(h,10);
y = ifft(X .* H);
y = y(1:6) % Extract the first 6 elements
y = 1x6
1.0000 -1.0000 -1.0000 5.0000 0.0000 -4.0000
When I see MATLAB implementations of FFT-based convolution, I typically see one these two implementation strategies:
- Use $n=K+L-1$ as the transform length.
- Use the smallest power of two that is greater than or equal to $K+L-1$ as the transform length.
I don't use either method. I have a third way of picking the zero-padded transform length.
Next time, I'll explain this third method and why I think it is generally better.
If you'd like a preview, check out my new FFT Transform Length submission on the File Exchange. (File Exchange link, GitHub link)