# Tag Info

42

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]$$ ...

16

pichenettes is right, of course. The FFT implements a circular convolution while the xcorr() is based on a linear convolution. In addition you need to square the absolute value in the frequency domain as well. Here is a code snippet that handles all the zero padding, shifting & truncating. %% Cross correlation through a FFT n = 1024; x = randn(n,1); % ...

13

I can recommend you two books about DSP for C language. Embree P. M. - C Language Algorithms for Digital Signal Processing It is old and you can easily get it second-hand for a decent price. It covers pretty much all 4 topics that you described. The other one I recommend is: Malepati H. - Digital Media Processing: DSP Algorithms Using C It covers ...

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 ...

11

According to your definition of autocorrelation, the autocorrelation is simply the covariance of the two random variables $Z(n)$ and $Z(n+\tau)$. This function is also called autocovariance. As an aside, in signal processing, the autocorrelation is usually defined as $$R_{XX}(t_1,t_2)=E\{X(t_1)X^*(t_2)\}$$ i.e., without subtracting the mean. The ...

10

Are you looking for a formal proof or the intuition behind this? In the later case: "Nothing can be more similar to a function than itself". Autocorrelation at lag $\tau$ measures the similarity between a function $f$ and the same function shifted by $\tau$. Note that if $f$ is periodic, $f$ shifted by any integer multiple of $\tau$ and $f$ coincide, so the ...

10

I've never seen the word "Formula" with "AMDF". My understanding of the definition of AMDF is $$Q_x[k,n_0] \triangleq \frac{1}{N} \sum\limits_{n=0}^{N-1} \Big| x[n+n_0] - x[n+n_0+k] \Big|$$ $n_0$ is the neighborhood of interest in $x[n]$. Note that you are summing up only non-negative terms. So $Q_x[k,n_0] \ge 0$. We call "$k$" the "lag". clearly if ...

9

You are right that the repetition is around 650 by how exactly do I compute that automatically? Seems like a peak-picking problem to me? Or is there some other methods that can be used? Yes, it's just peak-picking. Your period is the x value of the first strong peak: Your peaks are all similar in height, probably because you're doing the autocorrelation ...

8

Autocorrelation is not about finding the distance between individual peaks. It is more about finding those lag distances that minimize the averaged squared delta between everything, all the peaks, all the valleys, all the flat spots, all in combination, and etc. Because of this averaging over the entire window, the lag distance may not correspond to the ...

8

The autocorrelation matrix is diagonalized by sinusoids when the process is stationary, this follows from the fact that the covariance operator is a convolution for a stationary process. A more rigorous proof is that $$f(t,s)=Cov(X(t),X(s))=Cov(X(t-u),X(s-u))=f(t-u,s-u)$$ which in particular means that $f(t,s)=f(t-s,0)$ which is also a positive ...

7

For starters, autocorrelation is a function of the relative time only for WSS processes, otherwise it depends on the absolute times: $\mathrm R_X(t_1,t_2) \equiv \mathbb E[X(t_1)^* X(t_2)]$ Secondly, it is wrong to say "time is just inverse frequency" because frequency is a characteristic of periodic processes. The autocorrelation is not generally a ...

7

You can think of linear-least squares in single dimension. The cost function is something like $a^{2}$. The first derivative (Jacobian) is then $2a$, hence linear in $a$. The second derivative (Hessian) is $2$ - a constant. Since the second derivative is positive, you are dealing with convex cost function. This is eqivalent to positive definite Hessian ...

7

Matlab's xcorr computes a $2N - 1$ FFT, where $N$ is the length of the input data (ie, the input is padded with $N - 1$ zeros). This avoids the circularity problem.

7

Suppose you have signals $x(t)$ and $y(t)$ whose cross-correlation function $R_{x,y}(t)$ is not something you like; you want $R_{x,y}$ to be impulse-like. Note that in the frequency domain, $$\mathcal{F}[R_{x,y}] = S_{x,y}(f) = X(f)Y^*(f).$$ So you filter the signals through linear filters $g$ and $h$ respectively to get $\hat{x}(t) = x*g$, $\hat{X}(f) = ... 7 Pre-whitening can be done by filtering with a transfer function that is roughly the inverse of the power spectrum of the signal. Let's say you have an audio signal that's roughly pink. In order to whiten that, you would apply an inverse pink filter (frequency response rises by 3 dB per octave). However, I'm not sure whether this will help with your issue. ... 7 The autocorrelation function of an aperiodic discrete-time finite-energy signal is given by $$R_x[n] = \sum_{m=-\infty}^{\infty}x[m]x[m-n]~~~~ \text{or}~~~ R_x[m] = \sum_{m=-\infty}^{\infty}x[m](x[m-n])^*$$ for real signals and complex signals respectively. Restricting ourselves to real signals for ease of exposition, let us consider the summand$x[m]x[m-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 I'd recommend Introduction to Signal Processing by S.J. Orfanidis. It's a great book with a good mix of theory and practice, and it also has code examples in C and Matlab. Once you've worked through it you'll know enough to carry on by yourself. 7 Cons: Not as accurate This is just compared to the other methods. I was measuring frequency very accurately to look for clock drift, etc: 1000.000004 Hz for 1000 Hz, for instance. For guitar pitch detection it will be fine. doesn't work for inharmonic things like musical instruments I should have said "it can't find an accurate fundamental if there is ... 7 Let$\theta_a$and$\theta_c$respectively denote the maximum magnitudes of the off-peak or out-of-phase periodic autocorrelation functions and the periodic crosscorrelation functions of a set of$K$sequences of length$N$and energy$\sum_{n=0}^{N-1}|x[n]]|^2 = N. In a seminal paper published in 1974, Welch proved that $$\max\big(\theta_a, \theta_c\big)\... 7 No. Quoting Wikipedia's article Independence (probability theory): If X and Y are independent random variables, then the expectation operator \operatorname{E} has the property$$\operatorname{E}[X Y] = \operatorname{E}[X]\operatorname{E}[Y].$$Consider your X(t_1) and Y(t_2) as X and Y in this answer. If both \operatorname{E}[X] \ne ... 6 Radians are considered to be dimensionless. See Are angles dimensionless? and Dimensionless quantity. They are considered to be pure numbers like pi. So \alpha is in Hz, which is a measure of 1/second, and s is also considered to be measured per second. 6 One would expect such a sequence to have a spectrum consisting of lines, as it is almost periodic (if it was periodic, it would have a Fourier series representation, even though it is not sinusoidal). As a quick example: load raw1.mat % calculate "unbiased" normalized cross-correlation; adjusted for % regions where there isn't full overlap corr = xcorr(... 6 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 ... 6 A synchronization sequence generally needs the property that its autocorrelation function resembles an impulse. There are two possible autocorrelation functions that can be considered. For a (real-valued) sequence x of length N, the periodic autocorrelation function is$$R_x[n] = \sum_{k=0}^{N-1}x[k]x[k+n]$$where the sequence is assumed to extend ... 6$$\begin{align} R_x(\tau) &=\int_{-\infty}^\infty x(t)x^*(t-\tau)\,\mathrm dt\\ &= \int_{-\infty}^\infty \left[\int_{-\infty}^\infty X(f)e^{j2\pi ft}\,\mathrm df\right]x^*(t-\tau)\,\mathrm dt\\ &= \int_{-\infty}^\infty X(f) \left[\int_{-\infty}^\infty x^*(t-\tau) e^{j2\pi ft}\,\mathrm dt\right]\,\mathrm df\\ &= \int_{-\infty}^\infty X(f) \... 6 The definition of the autocorrelation functionR_x(\tau)$depends on the nature of your$x$. If$x$is a deterministic signal with finite energy then: $$R_x(\tau)=\int_{-\infty}^{+\infty}x(t)x^*(t-\tau)dt$$ If$x$is a deterministic signal with finite average power$^{(1)}$then: $$R_x(\tau)=\lim_{T\to+\infty}\frac{1}{T}\int_{-T/2}^{+T/2}x(t)x^*(t-\tau)dt$$... 6 Let's look at the case$x[n] \in \mathbb{R}$, where$x[n]$is real. Autocorrelation is basically convolution of the signal with it's time inverse. This can be easily expressed in the frequency domain. $$\mathscr{F}\Big\{ r_{xx}[n] \Big\} = \mathscr{F}\Big\{ x[n] \Big\} \cdot \mathscr{F}\Big\{ x[-n] \Big\}$$$\$R_{xx}(\omega) = X(\omega)\cdot X^*(\...

5

Some "gut-level" reasons why it is better to work with the autocorrelation matrix instead of a matrix with your observations: If you want to take into account all your observations and you have a lot of data, you'll end up manipulating (inverting, multiplying) fairly large matrices. If you work with the autocorrelation matrix, you "summarize" your data once ...

5

Ok, in the context of one specific application: If you're trying to find the frequency of a waveform, you can calculate it similarly from the position of the peak in a Fourier transform or the peak of an autocorrelation. (And the autocorrelation can be calculated efficiently using the Fourier transform, so I don't know why everyone is naysaying "they're ...

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