CODEWITHSUNDEEP
arrayssignal-processingfftconvolution
ACCurrent
ACCurrent

Reputation: 385

How to implement convolutions using DFT?

So from my understanding it is possible to perform convolutions via the Discrete Fourier Transform. From what I read around the process simply involves mutliplying the DFT of both the kernel and the input. However, I am at a loss to understand how to implement the actual multiplication of the spectra as the DFT of two arrays of different sizes would be different.

So in psuedocode imagine I have an array arr of length 1024 and kernel kern of length 8.

To get the convolution of arr and kern I perform:

IDFT(DFT(arr)*DFT(kern))

However DFT(arr) is an array of length 1024 and DFT(kern) is an array of length 8. So how are they multiplied?

Upvotes: 0

Views: 1039

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

To do a convolution with the DFT, the size of the DFT has to be at least as big as the convolution result -- your kernel size PLUS your input size. You zero-pad them both out to this size, and then use the same size for both DFTs and the IDFT.

Note that this is not efficient at all if your kernel is much smaller than your input. In this (the usual) case, you can use the overlap-add or overlap-save method to divide your input up into chunks that are about the same size as your kernel.

See, for example: https://www.youtube.com/watch?v=FPzZj30hPY4

This is still not efficient for really small kernels. If your kernel is really only 8 samples long, then you shouldn't be bothering with any of this stuff. The simple implementation will be faster.

Upvotes: 3

Related Questions