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.
33
questions
0
votes
1answer
59 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 ...
0
votes
1answer
88 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
44 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:
\...
0
votes
1answer
112 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
141 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
90 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 $...
1
vote
1answer
163 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
58 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
102 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
491 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
74 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
648 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
62 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
760 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
195 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
38 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
336 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 ...
0
votes
2answers
171 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
355 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 ...
5
votes
2answers
3k 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
214 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
617 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 ...
1
vote
2answers
215 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
946 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 ...
0
votes
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
280 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
484 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
157 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
246 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
13k 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. ...
24
votes
1answer
15k 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 ...
