44

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


13

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


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

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

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

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

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

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


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

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

The definition of the autocorrelation function $R_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$$...


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

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

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


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

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

The autocorrelation function is the inverse Fourier Transform of the power spectrum. I have no idea where you got your formula from or what your calculation is meant to be doing. Are you sure that you are reading the book/journal article/application note/website/Wikipedia or whatever correctly? In any case, if you want to compute an autocorrelation as an ...


5

For a time limited window of sampled data, you can derive the autocorrelation from the DFT, but not vice-versa. Therefore the DFT contains more information about that time window of data.


5

The value of the peak of the autocorrelation function (maximum) is not really important - though it can be used as a basic feature for voiced/unvoiced classification or more generally for "pitchedness". What matters is the index at which the function takes its maximum (arg-maximum). This is very intuitive to understand: if the signal has a period of $\tau$ ...


5

In principle you are doing the right thing. Step 4 should produce a real result unless there is a coding error. Sometimes you add up some residual imaginary part due to numerical noise but, if any, that should be very small. Here is an example %% random signal of length n n = 128; x = rand(n,1); % zero pad x = [x; zeros(n,1)]; % fft fx = fft(x); % mag ...


5

There is a vast literature on this subject. In particular, deleting one bit (the leading bit in one specific implementation) from each of the Walsh-Hadamard sequences and applying a permutation to the remaining $2^n-1$ bits will result in $2^n$ sequences of length $2^n-1$ that consist of (i) the all-zeroes sequence (ii) the $2^n-1$ cyclic shifts of a ...


5

Knowing the energies of $x_1$ and $x_2$ is not sufficient for determining the energy of $x_3=x_1x_2$. What you can do is determine an upper bound for the energy of $x_3$ given the energies of $x_1$ and $x_2$ and their maximum values: $$E_3=\sum_{k}\big|x_1[k]x_2[k]\big|^2\le\begin{cases}\max_k\big|x_1[k]\big|^2\sum_k\big|x_2[k]\big|^2=\max_k\big|x_1[k]\big|^...


5

The general topic of finding similarities between signals is wide ranging: are the signals of same sampling, length, offset, shift or scale? where do they take their values (discrete, real, complex)? are they stationary? noisy? what do you consider similar (whole signals, chunks, specific features)? which are the invariances looked for? and most important:...


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