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.
1
vote
1answer
33 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
48 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
63 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
211 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
68 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
217 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 ...
0
votes
0answers
210 views
Circular Convolution with `cuFFT` Significantly Deviates from CPU Result with `scipy.fftpack()` for Large Image Sizes
A circular convolution can be computed as a direct product in fourier space, as follows
...
1
vote
1answer
53 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 ...
7
votes
5answers
453 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
141 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
33 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
243 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
125 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
246 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
2k 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
176 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
512 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
149 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
832 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
931 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
248 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
391 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$ ...
2
votes
2answers
2k 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
151 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
209 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
988 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
12k 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. ...
23
votes
1answer
14k 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 ...
