Signal Processing Stack Exchange
Signal Processing Stack Exchange

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.

Fast convolution is using the Fast Fourier Transform (FFT), multiplication in the frequency domain, and inverse FFT to perform the convolution of a long signal with a long FIR. The "Overlap-Add" (OLA) and "Overlap-Save"(OLS) techniques are the two currently known basic methods.

The FFT is an efficient (or "fast") method to compute the Discrete Fourier Transform (DFT). Using the DFT performs circular convolution because of the inherent periodic nature of the DFT and OLA or OLS are techniques to use the circular convolution tool to accomplish the task of linear convolution.

50 questions
27
votes
2 answers

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 based fast convolution of data streams with FIR…
hotpaw2
  • 33,409
  • 7
  • 40
  • 88
9
votes
5 answers

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 code: from scipy.signal import convolve,…
user541686
  • 473
  • 3
  • 11
6
votes
1 answer

Implementing Convolution in Frequency Domain?

Suppose, we have a bitmap image represented as a 2D integer array, int [,] image2D; whose FFT is Complex[,] fftImage2D; Suppose, we have an kernel represented as a 2D integer array, int [,] kernel2D; whose FFT is Complex[,] fftKernel2D; We know…
user18425
6
votes
3 answers

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. I'm using Python and NumPy, with the…
SolarLune
  • 189
  • 1
  • 1
  • 3
5
votes
2 answers

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 Representations for Convolutional Neural…
Eduardo Reis
  • 303
  • 2
  • 8
5
votes
0 answers

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 this field and I'm still confused about some of…
QuinnFreedman
  • 151
  • 1
5
votes
1 answer

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 separable it is possible to do fast correlation…
Pedro Henrique Monforte
  • 165
  • 5
4
votes
2 answers

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 a few output values are needed, and can only output float arrays (int or object array…
orbit
  • 85
  • 4
4
votes
3 answers

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 N = 20N\quad\text{floating point…
Izzo
  • 697
  • 4
  • 19
3
votes
1 answer

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

def fft_convolution(image, kernel): imageC = image.copy() kSize = (kernel.size // 2)+1 kernelShape = tuple(ti//2 for ti in kernel.shape) centery ,centerx = kernelShape imagePad = np.pad(image, kSize, mode = "edge") imageC =…
Simon Balfe
  • 71
  • 1
3
votes
0 answers

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 discrete-time signal by the sequence: $$[1, 1,…
Olli Niemitalo
  • 12,226
  • 1
  • 25
  • 54
3
votes
2 answers

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 working proof of concept, but I am struggling to…
Mark
  • 215
  • 2
  • 8
3
votes
2 answers

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 calculate required padding size? should it be power of…
mrgloom
  • 540
  • 5
  • 17
3
votes
2 answers

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 Padding to length: x1.length() + x2.length() FFT…
christopo
  • 31
  • 1
  • 3
2
votes
3 answers

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?
Harvey
  • 23
  • 3
1
2 3 4