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)