n-fold FFT convolution and circular overlap

1
votes

Problem description

I have employed the convolution theorem to calculate convolutions efficiently. Suppose there are two real signals s1 and s2 of length N each. Then I can obtain the convolution from

import numpy as np
import numpy.fft as fft

size = len(s1)
fft_size = int(2 ** np.ceil(np.log2(2 * size - 1))) #The size for the FFT algorithm

S1 = fft.rfft(s1, fft_size) #Take FTs
S2 = fft.rfft(s2, fft_size)

convolution = fft.irfft(S1 * S2) #Take IFT

However, if I have a k singals the fft_size must be modified to read

fft_size = int(2 ** np.ceil(np.log2(k * size - 1)))

in order to avoid circular overlap.

Unfortunately, I do not know k a priori. One option is to choose a maximum value k_max but I would prefer to not have to use large amounts of memory if not absolutely necessary and I would prefer to not evaluate the FT again every time k changes.

Question

Is it possible to do one of the following

  • Take the FFT of the signal for k=1 and "zero pad in Fourier space" as necessary?
  • Prevent circular wrapping in the FFT?
1
pythonfftconvolution

1 Answers

1
votes

  1. Zero-padding in the frequency domain is possible, but requires far more computational effort (flops) than doing it in the time domain. It would likely be faster to IFFT, zeropad, and re-FFT to create "room" for each additional fast convolution.

  2. The longer result of a complete convolution has to go somewhere, so no, it's not possible to prevent circular convolution when using FFTs. Even zero-padding doesn't prevent the computation of circular overlap, it just makes sure that the overlapping in the result is equivalent to the addition of zero.