FFT Zero-Padding Strategies - Introduction

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.

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)