Embedded Correlation Function

Question

I'm trying to write a correlation function on an embedded device. Because its embedded, I need to make sure that the memory/CPU usage is minimum.

Here's the deal: - I have a saved waveform sampled at 1 MHz - I have timing info for the waveform - I am going to be taking a new waveform at 200 kHz with new timing info - The timing info for both waveforms is comparable, neither of them start at zero - I want to determine the delay between one waveform and the next precise to 1 us.

The method I was going to use to do this was: - Find the maximum of each waveform (there should only be 1 peak in each, and they should match up) - Set the indexes of each array so that the maximums of the waveforms match up. I'll save the amount of clock cycles that I am shifting in order to do this. - Then I will correlate this and shift a few samples in each direction and correlate as well. The highest correlation value corresponds to the correct amount of delay, and I will keep this value.

The problem is that my array manipulation skills are limited. I'm struggling when trying to implement this algorithm, especially because one of the waveforms is sampled at 5X the other. Does anybody have any references for this or knows how I can achieve this easily?

The specific problems I'm running into are: - How do I set the indexes differently so that the maximums match up? I don't want to write a new register because this takes up memory and takes a long time in terms of read/write cycles. - How do I compensate for the different sampling frequencies? I could fill the 200 kHz waveform with zeros (which won't affect the correlation) but this will take up more memory with no real purpose. - The timing info isn't precise, in that they don't necessarily line up perfectly. For example, the timing numbers "10000, 10020, 10040, 10060, 10080, and 10100" for the 1MHz signal doesn't necessarily match up with "10000, 10100" for the 200 kHz signal. So I can't rely on using the timing numbers as an index very easily.

If what I am asking isn't very clear, I can try to embellish a little on requests, but I don't want this to be too long.

Answer 1

How fast is the signal you are trying to analyze? The maximum theoretical frequency you can handle is going to be 100KHz (sampling rate / 2). Giving a "true" answer with 1 usec resolution is not possible with a 1MHz sampling rate. Practically this may not matter.

Without specific timing constraints it is hard to give a good answer. To get your signals to have the same sampling rate you can do linear interpolation between the points of your slow data or average your fast data.

I recommend averaging your fast data. If you are working in counts from an ADC summing 5 of the fast samples and dividing by 5 will be fast. Your compiler will likely use reciprocal multiplication to avoid the division operation.

Trying to line up the signals based on a single peak is likely to give incorrect results. An alternative method is to maintain an auxiliary array with a selection of the N highest peaks stored. Do not simply get the N largest points; they will likely be clustered together and will not give a good result. Instead track the largest point and do not allow a new peak unless the signal has dropped below some threshold value (say 90% of the peak) to introduce hysteresis. The exact number of peaks should be chosen on based on the shape of your data and the desired level of confidence as well as memory and CPU time.

To match the peaks scan through the second data set maintaining a best fit offset. When you find a possible match to the first peak (a value within some tolerance) you can then compare the "future" peaks. Finding the offset with minimal error for the N peak points is not too onerous (sqrt((x_1 - xbar)^2 + ... (x_n - xbar)^2)).

This can be done in only one pass through each of the data sets with only the extra memory required being the auxiliary array that keeps the N peak points.