# Questions tagged [fast-convolution]

Fast convolution is using the FFT, multiplication in the frequency domain, and inverse FFT to perform convolution of a long signal with a long FIR.

58 questions
Filter by
Sorted by
Tagged with
85 views

### Convolving Image with Kernel with Fourier

I am trying to convolve an image with the code above using Convolution Theory and numpy's Fourier transform. However, my output seems to be slightly different than the result from scipy. I am not sure ...
• 23
87 views

### Avoid circular convolution aliasing in weighted overlap-add (WOLA) method

This link gives the procedure of implementing the WOLA method. It can be summarized briefly as windowing the extractd data frame, FFT, modify the spectrum, IFFT and overlap-add the windowed IFFT ...
• 291
1k views

### FFT-based fast convolution vs IIR filtering

I'm doing an multichannel audio equalizer system on a chip, which is parametric EQ, usually implemented in cascaded biquad IIR filters. My problem is that I use a lot of IIR filters due to multiple ...
• 451
732 views

### Why is sweeping in convolution so confusing

From this formula, I thought that time constant (m or tau) is the variable sweeping from -infinity to infinity. But in this visualisation https://lpsa.swarthmore.edu/Convolution/CI.html, it is t the ...
82 views

### Signature for the kernels in fast-convolution

Continuing the discussion from Convolution kernel in Bluestein's algorithm it has a very specific signature of the kernel ...
• 583
43 views

### circular convolution using fftw: How to make the sequence periodic?

I have a grid size of $(4,4,4)$ as shown the picture below. $G_m$ Each box/group contains $\ell$ samples and each sample is a complex $\mathrm{3d-Vector}$ Now I define $G_m$ for each box/group, ...
• 583
40 views

### How to zero pad a 3d data and apply fast convolution?

I have two sequences, Let $A$ be the first sequence whose dimensions are $(5, 5, 3)$ takes complex values Let $B$ be the second sequence whose dimensions are $(5, 5, 1)$ also takes complex values I ...
• 583
79 views

### What means crop in FFT calculation?

In soapy power manual: Crop: -o PERCENT, --overlap PERCENT percent of overlap when frequency hopping (incompatible with -k) -k PERCENT, --crop PERCENT percent of crop when frequency hopping (...
• 175
1 vote
591 views

### Are there any reasons to use overlap algorithm when one could do ifft(X * Y) from the complete signal as well in similiar time complexity

We learned that overlap add and overlap save are used as fast convolution methods, because they can be applied with fft due to the formula $x[n] * y[n] = \text{IFFT}(X[k] Y[k])$ So now I was wondering ...
1 vote
178 views

### Convolve audio signal with filter with different sampling rates

I would like to convolve two signals: Room impulse response that was obtained by deconvolution, measured at 48 kHz. Truncated to 8192 samples. Anechoic recording (.wav) recorded at 41.1 kHz If I ...
• 13
65 views

### Result of convolution using FFT method not accurate in time

I am trying to implement fast convolution between a signal and complex Morlet wavelets. To make the result equivalent to a linear convolution, I let the MATLAB fft function zero-pad both the signal ...
179 views

...
• 113
59 views

### Subband Tuning in Matlab

Suppose you have an i/q stream with a sample rate of 20 MHz. You want to bandpass filter a 1 MHz bandwidth (ie passband from 5 to 6 MHz). You then want to heterodyne that 1 MHz chunk. How would you do ...
116 views

### FFT for Arbitrary time history

I have two Time-Speed histories one is real ( real measurements) the other is synthetically generated using formula. I need to compare both in the frequency domain using FFT given that: the time step ...
345 views

### Explain the Process of Spectral Pooling and Spectral Activation in the Context of CNN in Frequency Domain

I am reading the paper Design of an energy efficient accelerator for training of convolutional neural networks using frequency Domain Computation: which uses Frequency Pooling, from Spectral ...
• 343
107 views

• 797
1 vote
417 views

### Computing Autocorrelation via FFT

I have seen several methods to calculate Autocorrelations using FFTs, and am confused about why they differ. Zero-Pad it to double its original length.Take the FFT. Then replace all the coefficients ...
73 views

### Confusion regarding plot of linear convolution vs fast convolution via FFT

Question [Example 5.23 of Digital Signal Processing Using MATLAB Third Edition By Vinay K. Ingle and John G. Proakis ] I am not getting same plot/results as book ...
• 973
214 views

### Efficient Convolution Without I/O Delay (Gardner 1995) implementation

I am trying to perform real-time convolution on an audio stream using a fairly large FIR for convolutional reverb. I found a great paper explaining how to do just that: Gardner, 1995. But, I'm new to ...
411 views

### Handling stride>1 in FFT-based convolution

The Fourier transform of the convolution of two signals with stride 1 is equivalent to point-wise multiplication of their individual Fourier transforms. I need to perform stride-'n' convolution using ...
• 71
1 vote
314 views

### How do I pick an optimal window size for overlap add/save method algorithmically

Currently I've implemented an overlap-add method using resources on the internet, but I couldn't find a well documented way to minimize the cost of the method. In other words, how do I pick the window ...
• 111
1 vote
2k views

### How to manually implement convolution with FFTs?

I'm trying to manually implement a convolution using FFTs and it isn't working as expected. I know I'm probably missing some subtlety with padding, shifting, or conjugation, (all of which I've tried ...
• 201
81 views

### Understanding convolution of Chirp z algorithm

I dont´t understand how works the convolution part of the Chirp z. I understand how the DFT is transformed \begin{align*} x(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn} \end{align*} to this expresion: \...
• 31
1 vote
637 views

### How does minimum-latency partitioned convolution reverb work when you receive input samples in chunks, rather than one at a time?

I'm writing a reverb system where I receive an input block of samples 480 elements long, do some operation on them, and pass the block on to the next effect. I've been reading up on partitioned ...
• 27
740 views

### Overlap Add - which length to use?

I am doing realtime audio. Let's say I have a signal $x(n)$ which is passed in blocks of 512 (siobuffer) to the program filter/FFT method. Within this block I want to convolve the signal with the ...
• 71
149 views

• 483
380 views

### Amplitude not attenuated after bandpass filtering?

I want to make a bandpass filter for an IQ signal recorded from an Software Defined Radio with center frequency "Fc" & sampling frequency "Fs". For futhur analysis I wanted to focus upon signal ...
1 vote
41 views

### Can this robot trajectory smoothing function be expressed as a single convolution?

I have an Nx3 matrix of poses (x, y, theta) that I need to apply an algorithm on which will cause the trajectory to be smoothed. I am interested in performance and so would like to improve efficiency ...
• 107
487 views

### Can I compute convolution through the overlap and add method without the IFFT?

So, I'm (I think) aware of how the overlap and add algorithm for linear convolution works, but my question is that, suppose I have a FFT-ed set of sequences that belong to a large sequence. Can I add ...
449 views

### Understanding DFT-ODD operation in Gardner Efficient Convolution paper

As a newbie to DSP I am trying to understand and implement an efficient convolution engine as per JAES V43.3 1995/03 - Gardner - Efficient Convolution without I/O Delay. I'm pretty much there with a ...
• 225
742 views

### Could there be any reason to prefer convolution-based calculation of autocorrelation?

Theoretically both of ways of calculating autocorrelation function are identical: strightforward convolution and Fourier-based method where we use FFT/iFFT in practice. And as it is well known, the ...
• 123
4k views

### Implementing Convolution in Frequency Domain?

Suppose, we have a bitmap image represented as a 2D integer array, int [,] image2D; whose FFT is Complex[,] fftImage2D; ... 310 views

### Slight crackle with overlap-add frequency-domain convolution

I'm trying to make an FFT audio filter using overlap-add but there's some slight rhythmic distortion/crackle in the output. I have an irSize (impulse response size) of 512 samples and a blockSize of ...
1 vote
778 views

### Overlap add / overlap save using FFTW

I'm working on a realtime FFT processing algorithm in C using PortAudio. Currently I'm just trying to test if I can do OLA / OLS in (semi) real time using FFTW. I'm getting some distortion in the ...
• 21
325 views

### Fast convolution with very high order FIR

I am investigating the overlap-add and overlap-save methods for processing an audio signal with a FIR. The FIR is a measured impulse response of a reverberant space and may be of order greater than ...
1k views

### Frequency Domain Filtering with big kernel size

I use FFT to do filtering in frequency domain, but when I use big kernel I got shift on border, I think it's due to nature of cyclical convolution and I need to do more zero padding. But how to ...
• 550