Signal Processing

Questions tagged [fast-convolution]

Ask Question

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.

44 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
4
votes
2answers
110 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 ...
2
votes
0answers
49 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(...
2
votes
1answer
61 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{\...
2
votes
1answer
61 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 ...
-1
votes
3answers
76 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 ...
4
votes
2answers
62 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 ...
4
votes
3answers
1k 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
131 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
53 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 ...
5
votes
0answers
78 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
237 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 ...
1
vote
1answer
178 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
508 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
58 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
435 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
417 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
107 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 $...
4
votes
1answer
344 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
75 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
153 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
675 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
88 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 ...
1
vote
1answer
1k 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
70 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
291 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
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 ...
0
votes
2answers
434 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 ...
3
votes
2answers
290 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
503 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
1answer
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
243 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
693 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
267 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 ...
3
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
342 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
543 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
162 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 ...
2
votes
1answer
284 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. ...
26
votes
2answers
17k 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 ...

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.