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.
39
questions
4
votes
3answers
799 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 ...
0
votes
1answer
46 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 ...
0
votes
1answer
44 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 ...
0
votes
0answers
13 views
chromatic and polarization mode dispersion compensation in electrical dmain
I am currently working on adaptive compensation of chromatic and polarization dispersions in the electric domain using LMS (least squares method) and CMA (constant module algorithm) algorithms.
I am ...
4
votes
0answers
50 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 ...
0
votes
0answers
125 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 ...
0
votes
1answer
113 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 ...
1
vote
1answer
212 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 ...
2
votes
0answers
55 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:
\...
1
vote
1answer
295 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 ...
2
votes
1answer
274 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 ...
2
votes
0answers
97 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 $...
3
votes
1answer
269 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 ...
3
votes
0answers
67 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 ...
1
vote
1answer
128 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 ...
1
vote
2answers
551 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....
0
votes
2answers
79 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 ...
0
votes
1answer
996 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 ...
1
vote
1answer
66 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 ...
8
votes
5answers
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 ...
0
votes
1answer
241 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
0answers
40 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 ...
0
votes
2answers
385 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 ...
2
votes
2answers
244 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 ...
2
votes
3answers
432 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 ...
6
votes
2answers
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;
...
0
votes
1answer
230 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
0answers
656 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 ...
2
votes
2answers
238 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 ...
2
votes
2answers
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 ...
1
vote
2answers
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.
...
0
votes
2answers
304 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 ...
0
votes
0answers
518 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$ ...
3
votes
2answers
3k 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 ...
1
vote
1answer
158 views
Method for modifying frequency-domain signal to produce predetermined time-domain signal
We are performing a convolution of audio signal, with 511th order FIR
filters, using fast convolution methods: overlap-add or overlap-save.
Filters are being designed in frequency domain several ...
1
vote
1answer
260 views
Using Fast Convolution to apply HRIR to soundwave
I have a dozen source sound waves; each is about one second duration. I want to put each one through a digital filter (I'm truncating it to 128 taps).
Currently I'm doing this with a bog standard ...
2
votes
3answers
1k views
Other techniques like overlap save/overlap add
I know overlap save and overlap add are used for long data sequence filtering. Are there any other similar or better techniques like these?
5
votes
3answers
14k views
Beginner Attempting FFT Signal Filtering With Numpy
I've tried looking around for information on this, but I'm really out of my league here. I'm a guy who likes to fool around with Python, and I wanted to make a program that would filter an audio file. ...
25
votes
2answers
16k views
Overlap-Add versus Overlap-Save
What differences or other criteria can be used to help decide between using overlap-add and overlap-save for filtering? Both overlap-add and overlap-save are described as algorithms for doing FFT ...
