2022 Developer Survey is open! Take survey.

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.

Filter by
Sorted by
Tagged with
4 votes
3 answers
634 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 ...
user avatar
0 votes
3 answers
58 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 ...
user avatar
  • 541
0 votes
0 answers
33 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, ...
user avatar
  • 541
0 votes
1 answer
27 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 ...
user avatar
  • 541
0 votes
1 answer
25 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 (...
user avatar
  • 175
1 vote
3 answers
473 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 ...
user avatar
1 vote
1 answer
59 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 ...
user avatar
  • 13
0 votes
1 answer
46 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 ...
user avatar
4 votes
1 answer
97 views

Dealing with the Cyclic Boundary Conditions of Frequency Domain Convolution in Order to Apply Linear Convolution

...
user avatar
0 votes
0 answers
37 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 ...
user avatar
0 votes
1 answer
58 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 ...
user avatar
  • 1
6 votes
2 answers
204 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 ...
user avatar
2 votes
0 answers
78 views

Multiple 1D gaussian filter

Given $$ \begin{cases} &f_0(x)=1 \\ &f_{n+1}(x)= (\varphi*(f\mathbb{I}_{[a_n,b_n]}))(x)=\int_{-\infty}^{+\infty}\varphi(x-t)f_n(t)\mathbb{I}_{[a_n,b_n]}(t)dt = \int_{a_n}^{b_n}\varphi(x-t)f_n(...
user avatar
  • 143
2 votes
1 answer
222 views

Fast computation of a convolution integral with Gaussian kernel

Given a convolution integral with gaussian kernel $$ g(y) =\int_a^b\varphi(y-x)f(x)dx=\int_{-\infty}^{+\infty}\varphi(y-x)f(x)\mathbb{I}_{[a,b]}(x)dx $$ where $\varphi(x)= \frac{1}{\sqrt{2\pi}}\exp{\...
user avatar
  • 143
2 votes
1 answer
125 views

ringing artifacts using FFT-based gaussian blurring

I'm trying to do an FFT-based gaussian blur on a grayscale image, and it works, however it seems to introduce ringing artifacts to the result when compared to the expected direct filter. What can I do ...
user avatar
-1 votes
3 answers
121 views

Role of windowing in implementing FIR filters using Fast Convolution

In Fast Convolution the filtering is performed by taking FFT of both the signal and impulse response and multiplication in frequency domain using Overlap add/Overlap save method for processing ...
user avatar
  • 320
4 votes
2 answers
122 views

Why is FFT-based convolution efficient only for signals of large size?

According to the documentation of scipy.signal.fftconvolve This is generally much faster than convolve for large arrays (n > ~500), but can be slower when only ...
user avatar
  • 85
4 votes
3 answers
2k views

Can FFT convolution be faster than direct convolution for signals of large sizes?

Let's say I have a 1D signal of size $N$ and am trying to filter it with a 10-tap FIR filter mask. When $N$ is large, the number of multiply-accumulates would approximately equal $$2 \times 10 \times ...
user avatar
  • 737
1 vote
1 answer
258 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 ...
user avatar
0 votes
1 answer
59 views

Confusion regarding plot of linear convolution vs fast convolution via FFT

I am reading Proakis Digital signal processing using Matlab, 3rd edition I am performing example 5.23 but i am not getting same plot/results as book although i am using almost same code First i am ...
user avatar
  • 871
6 votes
0 answers
138 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 ...
user avatar
0 votes
0 answers
336 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 ...
user avatar
  • 111
1 vote
1 answer
262 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 ...
user avatar
  • 111
1 vote
1 answer
1k 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 ...
user avatar
3 votes
0 answers
73 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: \...
user avatar
  • 31
1 vote
1 answer
565 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 ...
user avatar
  • 27
2 votes
1 answer
603 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 ...
user avatar
  • 51
2 votes
0 answers
127 views

Correct way of derivating in frequency domain with FFT

I believe I am very close to the answer and only need a small nudge to get to the answer. What I want: I want to take a signal, use FFT to transform it to the frequency domain (FD), multiply it by $...
user avatar
6 votes
1 answer
432 views

What is the Fastest Way Ever to Do 2D Correlation?

Here is what i gathered so far: Any sliding window classification, image filtering or similar can be fastly done by a FFT (flip the signal and do convolution). Also, if the template/filter kernel is ...
user avatar
3 votes
0 answers
84 views

Convolution of signals sampled on a logarithmic grid

Is there a practical accelerated algorithm or a theoretical discrete (Fourier) transform based method to convolve discrete-time signals sampled on a logarithmic grid? What I mean is representing a ...
user avatar
1 vote
1 answer
174 views

Perform overlap add with available FFT size smaller than filter coefficients

I would like to process 12 to 20 seconds of incoming audio at a sample rate of 44100. I must process this audio in real time in an STM embedded kit (perhaps also an Android Smartphone). I'm trying to ...
user avatar
  • 942
1 vote
2 answers
813 views

Linear Convolution in DSP and Hann window

My understanding is that when dealing with discrete finite sequences, convolution done thru FFT is circular. To obtain linear convolution, one would pad the input with zeros up some appropriate length....
user avatar
0 votes
2 answers
96 views

How to detect a long signal inside an even longer one?

I'm trying to detect a long pattern inside a long recorded audio. In order to do so I am implementing a matched filter in time by performing a FIR filtering using the coefficients of my pattern ...
user avatar
  • 942
1 vote
1 answer
2k views

Decimation and filtering in the frequency domain

I'm working on a Software Defined Radio project where I'd like to low-pass filter and decimate an analytical signal (IQ) sampled at 96ksps. Let's say the low-pass filter has a cutoff at 5kHz and I'd ...
user avatar
1 vote
1 answer
73 views

position of useful filtered data inside DFT based filtered output

I'm trying to filter a 400 samples signal with various bandstop FIR filters (constant group delay), one at a time to see which one gives me the desired result. Every filter was build using the Kaiser ...
user avatar
  • 942
9 votes
5 answers
1k views

Fast & accurate convolution algorithm (like FFT) for high dynamic range?

It seems that FFT-based convolution suffers from limited floating-point resolution due to evaluating everything around the roots of unity, as you can see in the $10^{14}$-factor error in this Python ...
user avatar
0 votes
1 answer
354 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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 107
0 votes
2 answers
458 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 ...
user avatar
3 votes
2 answers
376 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 ...
user avatar
  • 215
2 votes
3 answers
624 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 ...
user avatar
6 votes
1 answer
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; ...
user avatar
0 votes
1 answer
274 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 ...
user avatar
1 vote
0 answers
744 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 ...
user avatar
2 votes
2 answers
304 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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
  • 550
1 vote
2 answers
1k views

direct Frequency domain FIR filtering vs Overlap-add method

I'm trying to do bandpass filtering of a EEG signal samples at 250Hz and benchmarking the following 4 methods of FIR filtering for different filter orders. The length of the signal is 15000 samples. ...
user avatar
  • 496
0 votes
2 answers
374 views

Running an FFT filter on a large data set

I have a non realtime application where I need to run a bandpass FFT filter on a data array of between 5k and 10k data points. Do I break it up into (say) 256 point chunks, run the FFT on that and ...
user avatar
0 votes
0 answers
555 views

Fast convolution with striding step

I want to convolve two discrete functions $f$ and $g$ using convolution stride size $a$ to get the result as $s_{a, i}$: $$s_{i,a} = \sum_i g_k f_{ai-k}$$ I know that simple convolution with $a=1$ ...
user avatar
  • 141
3 votes
2 answers
4k views

Correlation Using FFT / IFFT (Convolution in Frequency Domain) in Java

I try to find about the delay between two audio files using Cross Correlation in Java. I've already done this algorithm so far that i get a idea about how many samples is the delay. FFT x1 -> Zero ...
user avatar