41
The only difference between cross-correlation and convolution is a time reversal on one of the inputs. Discrete convolution and cross-correlation are defined as follows (for real signals; I neglected the conjugates needed when the signals are complex):
$$
x[n] * h[n] = \sum_{k=0}^{\infty}h[k] x[n-k]
$$
$$
corr(x[n],h[n]) = \sum_{k=0}^{\infty}h[k] x[n+k]
$$
...
40
There's not particularly any "physical" meaning to the convolution operation. The main use of convolution in engineering is in describing the output of a linear, time-invariant (LTI) system. The input-output behavior of an LTI system can be characterized via its impulse response, and the output of an LTI system for any input signal $x(t)$ can be expressed as ...
39
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 ...
28
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-...
27
Essentially, OS is slightly more efficient since it does not require the addition of the overlapping transients. However, you may want to use OA if you need to reuse the FFTs with zero-padding rather than repeated samples.
Here is a quick overview from an article I wrote a while ago
Fast convolution refers to the blockwise use of circular convolution
...
20
A particularly useful intuitive explanation that works well for discrete signals is to think of convolution as a "weighted sum of echoes" or "weighted sum of memories."
For a moment, suppose the input signal to a discrete LTI system with transfer function $h(n)$ is a delta impulse $\delta(n-k)$. The convolution is
\begin{eqnarray}
y(n) &=& \sum_{m=-\...
16
ifft(fft(a) * fft(b)) performs a cyclic convolution, convolve apparently zero-pads the inputs. If you pad both arrays with zeros, the result should be the same:
a = [0,0,0,1+0j, 2+0j,0,0,0]
b = [0,0,0,4+0j, 5+0j,0,0,0]
print list(ifft(fft(a) * fft(b)))
print list(convolve(a, b))
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 (...
14
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 ...
13
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 ...
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
For continuous convolution $$[Hf](x) \equiv f(x) * h(x) \equiv \int\mathrm{d}x' h(x-x')f(x')$$
and continuous cross-correlation $$[Gf](x) \equiv f(x) \star h(x) \equiv \int \mathrm{d}x'h^*(x'-x)f(x')$$
It's easy to show that the cross-correlation operator $G$ is the adjoint operator of the the convolution operator $H$.
Also, the convolution operation is ...
12
Convolution is a mathematical abstraction describing how a linear, time-invariant system affects a signal going through it.
Sometimes one explicitly designs a system to convolve a signal by a predefined impulse response (for example when building a digital filter); but more often than not, convolution is used to model various physical processes involved in ...
12
I've explained it once on StackOverflow.
Your signal can be represented as a vector, and convolution is multiplication with a tridiagonal matrix.
For example:
Your vector/signal is:
V1
V2
...
Vn
Your filter (convolving element) is:
[b1 b2 b3];
So the matrix is nxn: (Let it be called A):
[b2 b3 0 0 0 0.... 0]
[b1 b2 b3 0 0 0.... 0]
[0 b1 b2 b3 ...
11
A good intuitive way of understanding convolution is to look at the result of convolution with a point source.
As an example, the 2D convolution of a point with the flawed optics of Hubble Space Telescope creates this image:
Now imagine what happens if there are two (or more) stars in a picture: you get this pattern twice (or more), centered on each star. ...
10
The difference applies only to the borders of the image.
In the linear convolution you assume the values of pixels beyond the border (examples being mirror of the image pixels, or 50% grey).
In the circular convolution (or DFT, product, IDFT), the pixels beyond the border are the pixels on the other side of the image, just as if you had a repeated tiling ...
10
This is a non-linear filter, the operation being performed is not a convolution and cannot be represented by a filter kernel. It is sometimes called a mode filter, by analogy to the median filter, since the value taken by a pixel is the mode of the distribution of the neighboring values. OpenCV does median filtering (cvSmooth with CV_MEDIAN parameter), I don'...
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
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 ...
9
The transpose (or more generally, the Hermitian or conjugate transpose) of a filter is simply the matched filter. This is found by time reversing the kernel and taking the conjugate of all the values.
Chapter 5 of this book by claerbout has a great discussion of the topic of Adjoint operators (or transpose, or back-projection, or matched filtering). It's in ...
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
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
Let $X(f)$ denote the Fourier transform of $x(t)$ where
$$\begin{align*}
X(f) &= \int_{-\infty}^{\infty} x(t) \exp(-j2\pi ft) \mathrm dt\\
x(t) &= \int_{-\infty}^{\infty} X(f) \exp(+j2\pi ft) \mathrm df
\end{align*}$$
which I will denote via $x(t) \leftrightarrow X(f)$.
The following transform pairs will be needed in what follows.
$$\begin{align*}
\...
8
For simplicity, let's talk about one-dimensional convolutions only.
You need to understand that the result of a convolution is a function and the alleged convolution integral is actually an infinitude of integrals, one for each time instant. By this I mean that to compute the output $y(t)$ of a system with impulse response
$h(t)$ to an input signal at ...
8
A somewhat visual complement to the other answers
You are talking about systems that are linear and time invariant.
Exponential functions have one peculiar property (and can be actually defined by it): doing a time translation results in the same function multiplied by a constant. So
$$ e^{t-t_0}=e^{-t_0}e^t$$
The red exponential could as well be the ...
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
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 $...
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, ...
7
If you have a vector of data, $d$, that is composed of elements $d_1, d_2,... d_N$, then linear convolution operates on them in order, starting with $d_1$ and ending with $d_N$.
Imagine that the data vector $d$ is represented by a slip of paper with the $N$ elements written in order. Now, imagine forming the slip of paper into a circle by touching the end (...
7
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
