Cross correlation in C

Did someone has experience on implementation of cross correlation in C on
CCS? I want to realise the cross correlation in frequency domain by FFT.
Until now the Real time FFT is done. The question is that my input signal
is two random signals from two infrared sensors, how random signal is
calculated by cross correlation?  

On 10/19/2010 1:26 AM, hyd198471 wrote:
> Did someone has experience on implementation of cross correlation in C on
> CCS? I want to realise the cross correlation in frequency domain by FFT.
> Until now the Real time FFT is done. The question is that my input signal
> is two random signals from two infrared sensors, how random signal is
> calculated by cross correlation?

You'll probably have better luck here by parsing this question:
C and CCS are probably not pertinent to the core question so set that 
aside for now.
That the signals are random are probably not pertinent to the core 
question so that that aside also.
That leaves:
1) How do I do cross correlation?
2) How do I do cross correlation in the frequency domain?

I don't understand:
"Until now the Real time FFT is done."
combined with
"I want to realize the cross correlation in frequency domain by FFT".
The first one seems to indicate that something is already being done but 
the latter not.

Fred

>On 10/19/2010 1:26 AM, hyd198471 wrote:
>> Did someone has experience on implementation of cross correlation in C
on
>> CCS? I want to realise the cross correlation in frequency domain by
FFT.
>> Until now the Real time FFT is done. The question is that my input
signal
>> is two random signals from two infrared sensors, how random signal is
>> calculated by cross correlation?
>
>You'll probably have better luck here by parsing this question:
>C and CCS are probably not pertinent to the core question so set that 
>aside for now.
>That the signals are random are probably not pertinent to the core 
>question so that that aside also.
>That leaves:
>1) How do I do cross correlation?
>2) How do I do cross correlation in the frequency domain?
>
>I don't understand:
>"Until now the Real time FFT is done."
>combined with
>"I want to realize the cross correlation in frequency domain by FFT".
>The first one seems to indicate that something is already being done but 
>the latter not.
>
>Fred
>
Yeah I think I need to clarify my question. I want to know the exact
procedure how to calculate the time delay between two sensor signals by
applying cross correlation. I have already implemented a real time FFT
according to the code "FFTr2" from book "Digital Signal Processing and
Applications with TMS320C6713 and TMS320C6416 DSK" and the next step is to
implement a cross correlation.

>On 10/19/2010 1:26 AM, hyd198471 wrote:
>> Did someone has experience on implementation of cross correlation in C
on
>> CCS? I want to realise the cross correlation in frequency domain by
FFT.
>> Until now the Real time FFT is done. The question is that my input
signal
>> is two random signals from two infrared sensors, how random signal is
>> calculated by cross correlation?
>
>You'll probably have better luck here by parsing this question:
>C and CCS are probably not pertinent to the core question so set that 
>aside for now.
>That the signals are random are probably not pertinent to the core 
>question so that that aside also.
>That leaves:
>1) How do I do cross correlation?
>2) How do I do cross correlation in the frequency domain?
>
>I don't understand:
>"Until now the Real time FFT is done."
>combined with
>"I want to realize the cross correlation in frequency domain by FFT".
>The first one seems to indicate that something is already being done but 
>the latter not.
>
>Fred
>
Yeah I think I need to clarify my question. I want to know the exact
procedure how to calculate the time delay between two sensor signals by
applying cross correlation. I have already implemented a real time FFT
according to the code "FFTr2" from book "Digital Signal Processing and
Applications with TMS320C6713 and TMS320C6416 DSK" and the next step is to
implement a cross correlation.

hyd198471 wrote:


> Yeah I think I need to clarify my question. I want to know the exact
> procedure how to calculate the time delay between two sensor signals by
> applying cross correlation.

My dear inqusitive friend,

There are two kinds of procedures to implement a cross correlation: it 
is "do it yourself" procedure and "hire a professional" procedure. 
Neither of those procedures is very difficult, and people were doing it 
for ages. So I think you could cope with it.

> I have already implemented a real time FFT
> according to the code "FFTr2" from book "Digital Signal Processing and
> Applications with TMS320C6713 and TMS320C6416 DSK" and the next step is to
> implement a cross correlation.

Ay, incredible. You are doing great [and all other supportive words that 
courteous people say in those cases].


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

hyd198471 wrote:
> Yeah I think I need to clarify my question. I want to know the exact
> procedure how to calculate the time delay between two sensor signals by
> applying cross correlation.

A few minutes Googling the problem might help.  Perhaps you would have
found the following:

http://www.scribd.com/doc/25334405/The-Discrete-Fourier-Transform-Part-6-Cross-Correlation

You can also 'search this group' at Google Groups for cross-
correlation (1030 hits).

In the above link, the author shows a cross-correlation in the time
domain (note minor error just above Fig. 1, where he says that the 'Y'
sequence is 3201, but he shows it as 3202 in the example).  Then, in
eq. 6, he notes that cross-correlation in the time domain is
equivalent to multiplying the transform of one signal times the
conjugated transform of the second signal in the frequency domain, and
then inverse transforming.

What it means is this:  get the FFT of signal 1, e.g.: X(0), X(1) ...
X(N-1), and the FFT of signal 2:  Y(0), Y(1) ... Y(N-1), conjugate one
of them (say, the Y output), and multiply them, point by point (X(0)
times conjugated Y(0), X(1) times conjugated Y(1), etc.).  Then
inverse transform.  Use the real (not imaginary) FFT outputs to
represent the results of the cross-correlation.

The above will give you what is known as a 'circular' cross-
correlation of N points. If you want to do a 'linear' cross-
correlation, just zero pad each of your N point signals to 2N before
getting their FFTs.  Then conjugate/multiply/inverse transform as
before.  This will give you 2N points in the result.

If your signals are indeed correlated, you should see a peak in the
real part of the FFT output that corresponds to the delay between the
two signals.  See the following for some graphs (the author does it in
the time domain, and he normalizes results to be between +/-1):

http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/correlate/

I don't know if that FFT routine you mentioned is going to work.  Make
sure that it's for complex inputs.  If it's for real inputs only,
you'll have to find something else.  FFT routines for real valued
inputs presume that the imaginary inputs are zero.

Kevin McGee

>
>hyd198471 wrote:
>> Yeah I think I need to clarify my question. I want to know the exact
>> procedure how to calculate the time delay between two sensor signals by
>> applying cross correlation.
>
>A few minutes Googling the problem might help.  Perhaps you would have
>found the following:
>
>http://www.scribd.com/doc/25334405/The-Discrete-Fourier-Transform-Part-6-Cross-Correlation
>
>You can also 'search this group' at Google Groups for cross-
>correlation (1030 hits).
>
>In the above link, the author shows a cross-correlation in the time
>domain (note minor error just above Fig. 1, where he says that the 'Y'
>sequence is 3201, but he shows it as 3202 in the example).  Then, in
>eq. 6, he notes that cross-correlation in the time domain is
>equivalent to multiplying the transform of one signal times the
>conjugated transform of the second signal in the frequency domain, and
>then inverse transforming.
>
>What it means is this:  get the FFT of signal 1, e.g.: X(0), X(1) ...
>X(N-1), and the FFT of signal 2:  Y(0), Y(1) ... Y(N-1), conjugate one
>of them (say, the Y output), and multiply them, point by point (X(0)
>times conjugated Y(0), X(1) times conjugated Y(1), etc.).  Then
>inverse transform.  Use the real (not imaginary) FFT outputs to
>represent the results of the cross-correlation.
>
>The above will give you what is known as a 'circular' cross-
>correlation of N points. If you want to do a 'linear' cross-
>correlation, just zero pad each of your N point signals to 2N before
>getting their FFTs.  Then conjugate/multiply/inverse transform as
>before.  This will give you 2N points in the result.
>
>If your signals are indeed correlated, you should see a peak in the
>real part of the FFT output that corresponds to the delay between the
>two signals.  See the following for some graphs (the author does it in
>the time domain, and he normalizes results to be between +/-1):
>
>http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/correlate/
>
>I don't know if that FFT routine you mentioned is going to work.  Make
>sure that it's for complex inputs.  If it's for real inputs only,
>you'll have to find something else.  FFT routines for real valued
>inputs presume that the imaginary inputs are zero.
>
>Kevin McGee

Hey!

My 20 cents contribution: depending on the sampling frequency and taking
into account that the real peak could be between two consecutive samples,
it may be interesting to obtain a more accurate result (in terms
of time delay, not in number of sampling periods) by interpolating the
region closer to the peak you have obtained. This interpolation
(assuming ou are using a proper sampling frequency) can be carried out, for
instance, using cubic splines such as in the Matlab code below:

 % assume you have the cross correlation in rx1x2
 [trash,nmax] = max(rx1x2);
 ni = (nmax-1:0.00001:nmax+1);
 ri = spline(nmax-1:nmax+1,rx1x2(nmax-1:nmax+1),ni);
 [booo,tau] = max(ri);
 delay = tau/fs; % fs = sampling frequency

José, from Red Beach, Rio de Janeiro.

>>Thanks for your hint
I manage to measure the speed curve by applying the cross correlation
I use median filter in matlab to smooth my curve. 
>>hyd198471 wrote:
>>> Yeah I think I need to clarify my question. I want to know the exact
>>> procedure how to calculate the time delay between two sensor signals
by
>>> applying cross correlation.
>>
>>A few minutes Googling the problem might help.  Perhaps you would have
>>found the following:
>>
>>http://www.scribd.com/doc/25334405/The-Discrete-Fourier-Transform-Part-6-Cross-Correlation
>>
>>You can also 'search this group' at Google Groups for cross-
>>correlation (1030 hits).
>>
>>In the above link, the author shows a cross-correlation in the time
>>domain (note minor error just above Fig. 1, where he says that the 'Y'
>>sequence is 3201, but he shows it as 3202 in the example).  Then, in
>>eq. 6, he notes that cross-correlation in the time domain is
>>equivalent to multiplying the transform of one signal times the
>>conjugated transform of the second signal in the frequency domain, and
>>then inverse transforming.
>>
>>What it means is this:  get the FFT of signal 1, e.g.: X(0), X(1) ...
>>X(N-1), and the FFT of signal 2:  Y(0), Y(1) ... Y(N-1), conjugate one
>>of them (say, the Y output), and multiply them, point by point (X(0)
>>times conjugated Y(0), X(1) times conjugated Y(1), etc.).  Then
>>inverse transform.  Use the real (not imaginary) FFT outputs to
>>represent the results of the cross-correlation.
>>
>>The above will give you what is known as a 'circular' cross-
>>correlation of N points. If you want to do a 'linear' cross-
>>correlation, just zero pad each of your N point signals to 2N before
>>getting their FFTs.  Then conjugate/multiply/inverse transform as
>>before.  This will give you 2N points in the result.
>>
>>If your signals are indeed correlated, you should see a peak in the
>>real part of the FFT output that corresponds to the delay between the
>>two signals.  See the following for some graphs (the author does it in
>>the time domain, and he normalizes results to be between +/-1):
>>
>>http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/correlate/
>>
>>I don't know if that FFT routine you mentioned is going to work.  Make
>>sure that it's for complex inputs.  If it's for real inputs only,
>>you'll have to find something else.  FFT routines for real valued
>>inputs presume that the imaginary inputs are zero.
>>
>>Kevin McGee
>
>Hey!
>
>My 20 cents contribution: depending on the sampling frequency and taking
>into account that the real peak could be between two consecutive samples,
>it may be interesting to obtain a more accurate result (in terms
>of time delay, not in number of sampling periods) by interpolating the
>region closer to the peak you have obtained. This interpolation
>(assuming ou are using a proper sampling frequency) can be carried out,
for
>instance, using cubic splines such as in the Matlab code below:
>
> % assume you have the cross correlation in rx1x2
> [trash,nmax] = max(rx1x2);
> ni = (nmax-1:0.00001:nmax+1);
> ri = spline(nmax-1:nmax+1,rx1x2(nmax-1:nmax+1),ni);
> [booo,tau] = max(ri);
> delay = tau/fs; % fs = sampling frequency
>
>José, from Red Beach, Rio de Janeiro.
>
>
>
>