42

Convolution is correlation with the filter rotated 180 degrees. This makes no difference, if the filter is symmetric, like a Gaussian, or a Laplacian. But it makes a whole lot of difference, when the filter is not symmetric, like a derivative. The reason we need convolution is that it is associative, while correlation, in general, is not. To see why this ...


33

Adapted from an answer to a different question (as mentioned in a comment) in the hope that this question will not get thrown up repeatedly by Community Wiki as one of the Top Questions.... There is no "flipping" of the impulse response by a linear (time-invariant) system. The output of a linear time-invariant system is the sum of scaled and time-...


15

The Idea of Convolution My favorite exposition of the topic is in one of Brad Osgood's lectures on the Fourier Transform. The discussion of convolution begins around 36:00, but the whole lecture has additional context that's worth watching. The basic idea is that, when you define something like the Fourier Transform, rather than working directly with the ...


15

If you want the shifted output of the IFFT to be real, the phase twist/rotation in the frequency domain has to be conjugate symmetric, as well as the data. This can be accomplished by adding an appropriate offset to your complex exp()'s exponent, for the given phase slope, so that the phase of the upper (or negative) half, modulo 2 Pi, mirrors the lower ...


15

One of the definitive features of LTI systems is that they cannot generate any new frequencies which is not already present in their inputs. Please note that in this context a frequency refers to signals of the type $x(t)=e^{j\Omega_0 t}$ or $\cos(\Omega_0 t)$ which are of infinite duration, and are also referred to as eigenfunctions of LTI systems (...


13

One reason you see people designing FIR filters, rather than taking a direct approach (like both 1 and 2) is that the direct approach usually fails to take into account the periodicity in the frequency domain, and the fact that convolution implemented using an FFT is circular convolution. What does this mean? Suppose you have a signal $x = [ 1, 2, 3, 4]$ ...


12

There is probably a bit of a misconception here. In many application the signal is runnning all the time or is VERY long: modem, audio stream, video etc. In this case you can't really define the "length" of the signal. The relevant metric is here "number of operations per input sample" not the "total number of operations". If ...


11

Real-time low-latency partitioned convolution reverb with a long impulse response works by dividing the impulse response into unequally sized partitions. The shortest partitions (blocks) are at the beginning of the impulse response, and the partition length grows towards the end of the impulse response: Each partition length can be processed separately, ...


11

Turns out that convolution and correlation are closely related. For real signals (and finite energy signals): Convolution: $\qquad y[n] \triangleq h[n]*x[n] = \sum\limits_{m=-\infty}^{\infty} h[n-m] \, x[m]$ Correlation: $\qquad R_{yx}[n] \triangleq \sum\limits_{m=-\infty}^{\infty} y[n+m] \, x[m] = y[-n]*x[m]$ Now, in metric spaces, we like to use this ...


11

When talking about modeling, there are two things that usually get modeled: 1. the guitar amp, and 2. the speaker cabinet. Only the latter is modeled by an impulse response, which means that the cabinet is simply represented by an LTI system and implemented by convolution. This is of course an approximation but it works fairly well. You can find a lot of ...


10

One problem is dealing with infinite length transforms that wrap-around when using a finite length FFT. The Fourier transform of a finite length frequency response is an infinite length impulse response or filter kernel. Most people would like their filter to finish before they die or run out of computer memory, so need tricks to produce shorter FIR ...


10

Is there any trade-off in numerical precision or speed? Yes. For delays that are integer multiples of the sampling period method 1 is far superior: it's computationally efficient, it's bit-exact, it's easy to implement and it's almost fool proof. Method 2 is computationally expensive, you need to pick an FFT length (which is not trivial) it's subject to ...


9

Think of this... Imagine a drum which you are beating repeatedly to hear the music right? Your drum stick will land on the membrane for the first time and due to the impact it will vibrate. When you strike for the second time, the first impact's vibration has already decayed, to some extent. So whatever sound you will hear is the current beating and sum of ...


9

Yes, you are correct. Multiplication in time domain means convolution in frequency domain and vice versa. Multiplying your signals $x[n]$ and $y[n]$ will give an output: \begin{align} z[n]&=\{2\cdot 5, 4\cdot 1, 1\cdot 8\}\\ &= \{10, 4, 8\}\end{align} Remember that this output is in time domain. When you convolve $x[n]$ and $y[n]$, you will get $...


9

Since convolution describes the operation of a linear time-invariant (LTI) system, the question is if the effect of an LTI system can be compensated by another LTI system. In the discrete-time domain you can use the $\mathcal{Z}$-transform to analyze LTI systems. If a signal $x(n)$ (with $\mathcal{Z}$-transform $X(z)$) is filtered by a system with impulse ...


9

Convolution in the time domain is equivalent to multiplication in the frequency domain. If you window two sinusoids in the time domain to get finite length waveforms, and the two sinusoids are exactly integer periodic in the window width, then the DFT will be impulses. If the frequencies are different, the impulses in the two DFT will be disjoint, and ...


9

You can make a simple algebraic argument, given the premise that you provided. If: $$ Y(\omega) = X(\omega) H(\omega) $$ where $X(\omega)$ is the spectrum of the input signal and $H(\omega$) is the frequency response of the system, then it's obvious that if there is some $\omega$ in the input signal for which $X(\omega) = 0$, then $Y(\omega) = 0$ as well; ...


9

Given a discrete time LTI system with impulse response $h[n]$, one can compute its response to any input $x[n]$ by a convolution sum: $$y[n] = x[n] \star h[n] = \sum_{k=-\infty}^{\infty} {h[k]x[n-k]} \tag{1}$$ Without anything further stated, above definition is for the linear convolution (aperiodic convolution) between $h[n]$ and $x[n]$, which are ...


9

The proof of associativity of discrete convolution relies on the assumption that multiple infinite sums can be evaluated in any order. This is not true if some of the involved sequences do not converge absolutely, which is the case for the given sequences $x_1[n]$ and $x_2[n]$. Note that the convolution sum $x_1\star x_2$ does not converge, i.e., $x_3\star (...


8

As a student I was involved in the same problem as you are. Let me explain to you in the simplest words without any math. Convolution: It is used to convolute two function. May sound redundant but I´ll put an example: You want to convolute (in a non math term to "combine") a unit cell (which can contain anything you want: protein, image, etc) and a ...


8

What's not clear to me is what the fundamental difference (if any) is between simulating an analog filter and making a digital filter. Either way, these functions will produce "ba" transfer function outputs, but the b and a are totally different. For a 2nd-order filter, for instance, b = [b0, b1, b2] and a = [a0, a1, a2]. These are the coefficients of the ...


8

Whether the direct convolution or the FFT/IFFT method is faster depends on the length of the impulse response, $N_\mathrm{i}$ and the signal length $N_\mathrm{s}$. With the formulas taken from here I've created a small Matlab script that calculates the required number of real multiplications and additions for the direct convolution and FFT/IFFT method, ...


8

If you're an EE student, you will have encountered the term LTI System (or you certainly will soon enough!): A system that, no matter the absolute time, outputs, given the same input, the same output; if you scale the input by a factor, the output is scaled by the same factor. Linear, time-invariant, so to speak. LTI systems can be applied to time-domain ...


7

Flipping the impulse response is really just a matter of perspective. The LTI system doesn't care about perspective. In any case, here is a graphic showing a system that takes an input of color weighted impulses.


7

Linear convolution is the basic operation to calculate the output for any linear time invariant system given its input and its impulse response. Circular convolution is the same thing but considering that the support of the signal is periodic (as in a circle, hance the name). Most often it is considered because it is a mathematical consequence of the ...


7

Be careful, a median filter cannot be expressed as a convolution, and thus is not considered a kernel in this respect. This is because the median filter is based on order statistics of an image patch, and the resulting pixel at the output of a median filter is not a linear combination of other pixels within a patch. Otherwise, you are right, kernels are ...


7

Multiplication in your first sentence is term-by-term multiplication: $z[n] = x[n]y[n]$ for all $n$. Convolution, for discrete-time sequences, is equivalent to polynomial multiplication which is not the same as the term-by-term multiplication. Convolution also requires a lot more calculation: typically $N^2$ multiplications for sequences of length $N$ ...


7

I can tell you of at least three applications related to audio. Auto-correlation can be used over a changing block (a collection of) many audio samples to find the pitch. Very useful for musical and speech related applications. Cross-correlation is used all the time in hearing research as a model for what the left and ear and the right ear use to figure ...


7

Let me clarify some definitions first. There is no such thing as a "passive impulse response", there are only passive systems. If you like, you can call the impulse response of a passive LTI system "passive", but that's not common usage. From what I understand from your question, you probably mean by a "passive impulse response" an impulse response $h[n]$ ...


7

Normally, the variables $t$ and $f$ are used for continuous time and frequency. But from your question I understand that you're talking about discrete time and frequency, and their relation via the Discrete Fourier Transform (DFT). If you have discrete-time sequences $a[n]$ and $b[n]$ and their DFTs $A[k]$ and $B[k]$, then the DFT of the linear convolution $...


Only top voted, non community-wiki answers of a minimum length are eligible