High School Student - cross correlation on radio data

Hey, I'm a high school student and sort of new to cross correlation.  I'm
doing a computer science project that creates interference fringes from
the input from two radio JOVE antennas seperated by a fixed distance, say
D.  

For now, however, I'm trying to get the software aspect of this project. 
I need to perform cross correlation on the data coming in, as it comes in.
 So far, through my research, I can only find ways of cross-correlating two
series that are static (meaning, they don't gain new points as time
increases) or that can be represented as functions.  Unfortunately, my
input is neither static (since new data is constantly being received) nor
representable by functions.  In that case, any suggestions how I might be
able to carry out the fastest possible cross correlation algorithm?  IT's
also important that the speed is relatively fast.  I'm willing to try
anything, even if it takes a little research.  But please, considering my
skill level, it would be nice to provide some explanation with your
answers, thanks!

Oh yeah, so far, what I've tried to do is seperate my continuous stream of
data into buffers of length L.  Then, I perform cross correlation on each
buffer from source 1 and 2.  So, I correlate buffer L1 (source 1) and L1
(source 2), then add that to buffer L2 and L2, then L3 and L3... However,
I don't think this is the same as cross correlating (source 1)(L1 +L2 + L3
+ L4...) and (source 2)(L1 + L2 + L3 + L4...)

"vnshaolin" <vnshaolin@gmail.com> wrote in message
news:xqGdnQ71J7eQgCXenZ2dnUVZ_sadnZ2d@giganews.com...
> Hey, I'm a high school student and sort of new to cross correlation.  I'm
> doing a computer science project that creates interference fringes from
> the input from two radio JOVE antennas seperated by a fixed distance, say
> D.
>
> For now, however, I'm trying to get the software aspect of this project.
> I need to perform cross correlation on the data coming in, as it comes in.
>  So far, through my research, I can only find ways of cross-correlating
two
> series that are static (meaning, they don't gain new points as time
> increases) or that can be represented as functions.  Unfortunately, my
> input is neither static (since new data is constantly being received) nor
> representable by functions.  In that case, any suggestions how I might be
> able to carry out the fastest possible cross correlation algorithm?  IT's
> also important that the speed is relatively fast.  I'm willing to try
> anything, even if it takes a little research.  But please, considering my
> skill level, it would be nice to provide some explanation with your
> answers, thanks!
>
> Oh yeah, so far, what I've tried to do is seperate my continuous stream of
> data into buffers of length L.  Then, I perform cross correlation on each
> buffer from source 1 and 2.  So, I correlate buffer L1 (source 1) and L1
> (source 2), then add that to buffer L2 and L2, then L3 and L3... However,
> I don't think this is the same as cross correlating (source 1)(L1 +L2 + L3
> + L4...) and (source 2)(L1 + L2 + L3 + L4...)
>
>
The fastest way is to use FFTs but for high-school it takes a little
explaining. What's your hardware like?

Tam

Yeah, I've read up a little on FFT's too.  The major requisite of the
program is to show mastery of computer concepts (like encapsulation, and
so forth).  So, I don't have to truly understand FFT on an intuitive
level.  Just knowing the algorithm for it would work as far as my project
goes.  Of course, it would help me personally if you can explain it in
terms of achieving my goal.  

In addition, the hardware I have is not very sophisicated.  The input from
the two radio JOVES are coming in through a soundcard on the computer. 
Thus, the data will be represented as a series of audio bytes.  This can,
of course, be converted to understand data quite easily.  

So, can you explain how you would perform FFT on a data set?  For my first
milestone, all I'm concerned with is having it work with sample data, so
hardware is not a major issue.

"vnshaolin" <vnshaolin@gmail.com> wrote in message
news:Gpadnc0Cwvtd3SXeRVn-rg@giganews.com...
> Yeah, I've read up a little on FFT's too.  The major requisite of the
> program is to show mastery of computer concepts (like encapsulation, and
> so forth).  So, I don't have to truly understand FFT on an intuitive
> level.  Just knowing the algorithm for it would work as far as my project
> goes.  Of course, it would help me personally if you can explain it in
> terms of achieving my goal.
>
> In addition, the hardware I have is not very sophisicated.  The input from
> the two radio JOVES are coming in through a soundcard on the computer.
> Thus, the data will be represented as a series of audio bytes.  This can,
> of course, be converted to understand data quite easily.
>
> So, can you explain how you would perform FFT on a data set?  For my first
> milestone, all I'm concerned with is having it work with sample data, so
> hardware is not a major issue.
>
Ok so you need to know your sampling rate. It will be 44.1kHz or half that
or half again. The signals should be stereo and 8 or 16 bits. The FFT is a
fast way of performing a Discrete Fourier Transform (DFT). You will need to
write code or copy it from elsewhere to do an FFT. You need two FFTs - one
perchannel. I am a little confused as to what you are sampling - on a PC you
can only handle audio signals  - if you use a sound card. Are you sampling
the audio from the two radios and calculating the time-delay?

Tam

>Ok so you need to know your sampling rate. It will be 44.1kHz or half
that
>or half again. The signals should be stereo and 8 or 16 bits. The FFT is
a
>fast way of performing a Discrete Fourier Transform (DFT). You will need
to
>write code or copy it from elsewhere to do an FFT. You need two FFTs -
one
>perchannel. I am a little confused as to what you are sampling - on a PC
you
>can only handle audio signals  - if you use a sound card. Are you
sampling
>the audio from the two radios and calculating the time-delay?
>
>Tam
>
>
>

How do you know that it's going to be 44.1 khz or half that or half again?
 Also, yeah, I consider that it might be stereo.  But of course, depending
on how the hardware is considered, it could just be two seperate incoming
audio stream (I'm using JAVA, but I won't go into specifics here).  But as
far as what you are saying with FFT's, I'm trying to perform constructive
interference on two incoming signal sources (represented as audio data, of
course).  I don't fully understand what FFT is suppose to do, so, is it the
right thing to choose for my project? 

Right now, my program operates on two possibilities: Two separate audio
streams are coming in through the sound card, and my program is going to
cross-correlate them (either through FFT, or otherwise, this is where I
need help).  Another possibility is that both sources will be represented
as stereo (so, source 1 is left channel, and source 2 is right channel). 
This just means I need to separate the channels, and perform
cross-correlation(either through FFT or some other method).  Thus, my main
question is, how do I go about performing cross-correlation on STREAMING
DATA?  The ultimate goal is interference.  Thanks for your help thus far!

"vnshaolin" <vnshaolin@gmail.com> writes:

> Hey, I'm a high school student and sort of new to cross correlation.  I'm
> doing a computer science project that creates interference fringes from
> the input from two radio JOVE antennas seperated by a fixed distance, say
> D.  
>
> For now, however, I'm trying to get the software aspect of this project. 
> I need to perform cross correlation on the data coming in, as it comes in.
>  So far, through my research, I can only find ways of cross-correlating two
> series that are static (meaning, they don't gain new points as time
> increases) or that can be represented as functions.  Unfortunately, my
> input is neither static (since new data is constantly being received) nor
> representable by functions.  In that case, any suggestions how I might be
> able to carry out the fastest possible cross correlation algorithm?  IT's
> also important that the speed is relatively fast.  I'm willing to try
> anything, even if it takes a little research.  But please, considering my
> skill level, it would be nice to provide some explanation with your
> answers, thanks!
>
> Oh yeah, so far, what I've tried to do is seperate my continuous stream of
> data into buffers of length L.  Then, I perform cross correlation on each
> buffer from source 1 and 2.  So, I correlate buffer L1 (source 1) and L1
> (source 2), then add that to buffer L2 and L2, then L3 and L3... However,
> I don't think this is the same as cross correlating (source 1)(L1 +L2 + L3
> + L4...) and (source 2)(L1 + L2 + L3 + L4...)

Two points:

1. What is your definition of cross-correlation? The definition that
I think you want is at

  http://astronomy.swin.edu.au/~pbourke/other/correlate/

2. It is quite unusual to attempt to compute a cross-correlation of
two sequences that continue indefinitely. We may be able to get a
better grasp on your problem if back up and explain to us *why* you
are attempting to perform a cross-correlation in this manner.
-- 
%  Randy Yates                  % "Midnight, on the water... 
%% Fuquay-Varina, NC            %  I saw...  the ocean's daughter." 
%%% 919-577-9882                % 'Can't Get It Out Of My Head' 
%%%% <yates@ieee.org>           % *El Dorado*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

"vnshaolin" <vnshaolin@gmail.com> wrote in message
news:QPWdnbRzZI5VCiXeRVn-rg@giganews.com...
> >Ok so you need to know your sampling rate. It will be 44.1kHz or half
> that
> >or half again. The signals should be stereo and 8 or 16 bits. The FFT is
> a
> >fast way of performing a Discrete Fourier Transform (DFT). You will need
> to
> >write code or copy it from elsewhere to do an FFT. You need two FFTs -
> one
> >perchannel. I am a little confused as to what you are sampling - on a PC
> you
> >can only handle audio signals  - if you use a sound card. Are you
> sampling
> >the audio from the two radios and calculating the time-delay?
> >
> >Tam
> >
> >
> >
>
> How do you know that it's going to be 44.1 khz or half that or half again?
>  Also, yeah, I consider that it might be stereo.  But of course, depending
> on how the hardware is considered, it could just be two seperate incoming
> audio stream (I'm using JAVA, but I won't go into specifics here).  But as
> far as what you are saying with FFT's, I'm trying to perform constructive
> interference on two incoming signal sources (represented as audio data, of
> course).  I don't fully understand what FFT is suppose to do, so, is it
the
> right thing to choose for my project?
>
> Right now, my program operates on two possibilities: Two separate audio
> streams are coming in through the sound card, and my program is going to
> cross-correlate them (either through FFT, or otherwise, this is where I
> need help).  Another possibility is that both sources will be represented
> as stereo (so, source 1 is left channel, and source 2 is right channel).
> This just means I need to separate the channels, and perform
> cross-correlation(either through FFT or some other method).  Thus, my main
> question is, how do I go about performing cross-correlation on STREAMING
> DATA?  The ultimate goal is interference.  Thanks for your help thus far!

Sound cards (the majority) only sample at the rates I gave above.
Cross correlation is done in batches and continuously updated. This is done
in acoustic source finding for example.
To use FFTs you will need to compute the inverse FFT of cross-spectral
density.(CSD). CSD can be found for a frame i from

CSD(i)=beta x CSD(i-1)+(1-beta) x X(i)Y(i)*

where * is  complex conjugate and beta is a forgetting factor.(say 0.9). X
and Y are the frequency vectors obtained from the FFTS of the two channels.
Ypu won't get brilliant results  with ordinary cross correlations as it only
works well when the signals are white. It should do for your project though.
The improved version uses Generalized cross correlation.

Tam

I may be missing something.  I don't think that the correlation you're 
interested in doing can be properly accomplished using the detected output 
from a radio receiver.  I think that it must be done at the carrier frequency. 
 Once the signal has been detected, the high resolultion information is gone.  
You can hetrodyne the carrier down to a lower frequency to make the processing 
easier if the hetrodyning signals are identical in frequency and phase.

In article <QPWdnbRzZI5VCiXeRVn-rg@giganews.com>, "vnshaolin" 
<vnshaolin@gmail.com> wrote:
>>Ok so you need to know your sampling rate. It will be 44.1kHz or half
>that
>>or half again. The signals should be stereo and 8 or 16 bits. The FFT is
>a
>>fast way of performing a Discrete Fourier Transform (DFT). You will need
>to
>>write code or copy it from elsewhere to do an FFT. You need two FFTs -
>one
>>perchannel. I am a little confused as to what you are sampling - on a PC
>you
>>can only handle audio signals  - if you use a sound card. Are you
>sampling
>>the audio from the two radios and calculating the time-delay?
>>
>>Tam
>>
>>
>>
>
>How do you know that it's going to be 44.1 khz or half that or half again?
> Also, yeah, I consider that it might be stereo.  But of course, depending
>on how the hardware is considered, it could just be two seperate incoming
>audio stream (I'm using JAVA, but I won't go into specifics here).  But as
>far as what you are saying with FFT's, I'm trying to perform constructive
>interference on two incoming signal sources (represented as audio data, of
>course).  I don't fully understand what FFT is suppose to do, so, is it the
>right thing to choose for my project? 
>
>Right now, my program operates on two possibilities: Two separate audio
>streams are coming in through the sound card, and my program is going to
>cross-correlate them (either through FFT, or otherwise, this is where I
>need help).  Another possibility is that both sources will be represented
>as stereo (so, source 1 is left channel, and source 2 is right channel). 
>This just means I need to separate the channels, and perform
>cross-correlation(either through FFT or some other method).  Thus, my main
>question is, how do I go about performing cross-correlation on STREAMING
>DATA?  The ultimate goal is interference.  Thanks for your help thus far!

>Sound cards (the majority) only sample at the rates I gave above.
>Cross correlation is done in batches and continuously updated. This is
done
>in acoustic source finding for example.
>To use FFTs you will need to compute the inverse FFT of cross-spectral
>density.(CSD). CSD can be found for a frame i from
>
>CSD(i)=beta x CSD(i-1)+(1-beta) x X(i)Y(i)*
>
>where * is  complex conjugate and beta is a forgetting factor.(say 0.9).
X
>and Y are the frequency vectors obtained from the FFTS of the two
channels.
>Ypu won't get brilliant results  with ordinary cross correlations as it
only
>works well when the signals are white. It should do for your project
though.
>The improved version uses Generalized cross correlation.
>
>Tam
>
>
>

Okay, so let me just put everything in perspective.  I have streams of
data coming in from sourceA and sourceB.  Since the data is continuous, my
program will read it in buffers of length L.  In order to do
cross-correlation "indefinetely", I'll have to do it by batches of these
buffers, like, the 1st for source A and B, then the 2nd for source A and
B.  My question:  do I add up the resulting cross correlation "signal"
with the other cross correlation "signals" derived from the other buffers?


Okay, and with your answer concerning CSD, what exactly is the complex
conjugate X(i)Y(i) term, and how am I suppose to find it?  The information
I have for the signals are as follows (as can be obtained from the JAVA
library): bigEndian or not, # of channels, frame rate, frame size, sample
rate, sample size in bits.  I guess my main question is, if X and Y are
the frequency vectors of FFTS of the two channels, how am I suppose to get
them? If you can help me out, or point me somewhere where it provides more
information, it'll be appreciated.  I tried googling the new information
you gave me, but most of the sites that came up were too technical for me
to understand.

"John Herman" <John_W_Herman@yahoo.com> wrote in message
news:Fecuf.10055$hI1.6094@tornado.socal.rr.com...
> I may be missing something.  I don't think that the correlation you're
> interested in doing can be properly accomplished using the detected output
> from a radio receiver.  I think that it must be done at the carrier
frequency.
>  Once the signal has been detected, the high resolultion information is
gone.
> You can hetrodyne the carrier down to a lower frequency to make the
processing
> easier if the hetrodyning signals are identical in frequency and phase.
>
>
Yes I was wondering about that as well and I am sure you are right. This
makes it harder than expected and a bit above the scope of a high-school
project. You will need to do some sums and ask your teacher for furtehr
information.
As for complex conjugate - for a complex number A+JB it is A-JB.

Tam