FPGA Central

Hi Folks,

I am collecting hours of data from multiple sensors at tens of kil
samples per second. Eventually I'll want to correlate between pairs o
sensors, and when I do, I'll do it through the freqeuncy domain (where fo
compatibilty with legacy code and CPU power I'll work with 1K, 2K, 4K or 8
blocks).

But my question to you all originates with the time domain. As a though
experiement, if I was to cross correlate there would it make sense to A
do linear correlation, B) do cyclic correlation, or C) buffer incomin
blocks and apply some sort of overlap and save calculation? If it wa
just two sequences (say 1K each) being compared I'd say linea
correlation. But it's not and by implicitly saying the data for on
period covers say, 1K samples, it seems like it should be circula
correlation. But that's not reality either, so I'm lead to the thir
approach -- but I don't think that's what anyone does so I'm suspicious o
that choice. In the end I can't decide what's really correct.

Any help, thoughts or insights would be greatly appreciated

Mikial

On 28 Jan, 20:55, "Mikial Chubarov" <mikialchuba...@ieee.org> wrote:
> Hi Folks,
>
> I am collecting hours of data from multiple sensors at tens of kilo
> samples per second.

Gigs of data...?

>*Eventually I'll want to correlate between pairs of
> sensors, and when I do, I'll do it through the freqeuncy domain (where for
> compatibilty with legacy code and CPU power I'll work with 1K, 2K, 4K or 8K
> blocks).
>
> But my question to you all originates with the time domain. *As a thought
> experiement, if I was to cross correlate there would it make sense to A)
> do linear correlation, B) do cyclic correlation, or C) buffer incoming
> blocks and apply some sort of overlap and save calculation?

Those questions can't be answered unless you state what you
want to achieve by the analysis. Why do you correlate? What
are you looking for? How do the references look like? Like
in radar and sonar, one usually knows the pulse waveform
that was transmitted, and one looks for the same signal in
the recieved data.

Rune

"Rune Allnor" <[email protected]> wrote in message
news:[email protected]...
On 28 Jan, 20:55, "Mikial Chubarov" <mikialchuba...@ieee.org> wrote:
> Hi Folks,
>
> I am collecting hours of data from multiple sensors at tens of kilo
> samples per second.

Gigs of data...?

> Eventually I'll want to correlate between pairs of
> sensors, and when I do, I'll do it through the freqeuncy domain (where for
> compatibilty with legacy code and CPU power I'll work with 1K, 2K, 4K or
> 8K
> blocks).
>
> But my question to you all originates with the time domain. As a thought
> experiement, if I was to cross correlate there would it make sense to A)
> do linear correlation, B) do cyclic correlation, or C) buffer incoming
> blocks and apply some sort of overlap and save calculation?

Those questions can't be answered unless you state what you
want to achieve by the analysis. Why do you correlate? What
are you looking for? How do the references look like? Like
in radar and sonar, one usually knows the pulse waveform
that was transmitted, and one looks for the same signal in
the recieved data.

Rune

**************

Right. Another way to frame the question is to ask: "over what time period
do you want to correlate?" If you correlate over the entire time period
then you wash out any short-term situations that may be of interest. If you
correlate with a relatively short sequence from A but over the entirety of
another sequence B then you may be wasting compute time because the
correlation opportunities cannot be so far apart as the computation would
suggest.

So, the general design is to pick a sequence length to use for correlation
and to pick a correlation span over which to compute the correlation (since
correlation implements a sliding multiply between the two sequences).

Once you have these parameters well in mind then you can better decide which
implementation is best for you.
- Linear correlation is easiest to code.
- Circular correlation is generally faster in execution. Sometimes much,
much faster!! It's relatively faster as the sequence lengths get bigger.

Fred

Rune, Fred, thank you.

The purpose of the correlation is to use multiple sensors to estimat
bearing using received broadband energy generated by the target itself.
The data is sampled at about 8K samples per second and I'm limited t
working with 2K real blocks from each sensor to get the real-tim
throughput I need (and for reasons of compatibiliy with legacy code).
Actually, I have already implemented the necessary code using fas
(frequency domain) correlation and the results are satisfactory.

If I didn't make it clear enough, my question is really just for m
edification. It's not a matter of "how can I make this work?", but
question of "am I thinking about this correctly?"

Since I have a long, long stream of input data it doesn't seem right t
use linear correlation which treats the inputs as finite sequences an
means my data is in effect truncated when it actually extends well beyon
the blocks being slid past one another -- so even if I did use thi
approach I think I would need to scale each discrete output by the numbe
of products that comprise it since sliding one sequence past the othe
results in sums (outputs) made up of increasing (at the beginning) the
decreasing (at the end) numbers of products.

Circular correlation seems better because it "wraps around" while sliding
But even this does not seem ideal since it imposes a periodicity on th
data that may not be there.

It seems to me that a better method than either of these might be t
buffer enough data so that I can do linear correlation using a sort o
overlap and save approach so that I avoid the "end effects" that come wit
linearly correlating two (truncated) sequences.

What do you think?

Thanks

Mikial

On 30 Jan, 19:03, "Mikial Chubarov" <mikialchuba...@ieee.org> wrote:
>*It's not a matter of "how can I make this work?", but a
> question of "am I thinking about this correctly?"
>
> Since I have a long, long stream of input data it doesn't seem right to
> use linear correlation which treats the inputs as finite sequences and
> means my data is in effect truncated when it actually extends well beyond
> the blocks being slid past one another

You hesitate because you will necessarily have to implement
a discrete-domain finite-length correlator?

What are the alternatives? To process infinite amounts of data?
To process continuous-domain data? Neither is feasible using
a digital computer. You have to accept that you need to work
on finite amounts of discrete data. From there on, it's a matter
of damage control.

> -- so even if I did use this
> approach I think I would need to scale each discrete output by the number
> of products that comprise it since sliding one sequence past the other
> results in sums (outputs) made up of increasing (at the beginning) then
> decreasing (at the end) numbers of products.

Sure. That's part of the game. One can't avoid it, and one
needs to deal with the consequences. One has a choise between
a biased estimator for the correlation sequence, with well-behaved
variance. Or one can use an unbiased estimate for the correlation
sequence where the variance grows fast as the number of samples
diminishes.

Choosing which one to use is part of the damage control.
You as designer needs to find out the effects of these
various factors in your particular application, and decide
which method (if any) causes acceptable degradation.
These sorts of analyses are the reason why the engineering
profession exists at all. If there were clear-cut answers
to these questions, they would be listed in some sort of
encyclopedia.

> Circular correlation seems better because it "wraps around" while sliding.
> *But even this does not seem ideal

Deja vu all over again: One method has one set of properties,
another method to do the same has another. It is up to you
to sort out the differences, and evaluate the impact on any
particular application.

> since it imposes a periodicity on the
> data that may not be there.

A processing method does not *impose* any property on the data.
What hapepns is that imperfect processing methods don't comply
to the context where the data were recorded, and a mismatch
occurs.

A practical application monitors some data stream which
(conceptually) is of infinite duration. Since one can process
only finite amounts of data, a mismatch occurs.
An infinitely long data stream just can't be processed
correctly when the processor is confined to work on
a finite amount of data. The key is to understand
the nature of the mismatches, and thus understand
what information is lost and what information is
preserved during the processing.

When people talk about 'periodic extensions' and all that,
that has to be interpreted as 'this out-of-context finite-
buffersize N processing method would have produced the
correct result if the infinitely long data sequence was
periodic with period N.'

Rune