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.

  • 2
    $\begingroup$ How are you hoping to achieve 1 µs accuracy if the test waveform is only sampled at 200 kHz ? $\endgroup$
    – Paul R
    Commented Jul 3, 2013 at 6:43
  • $\begingroup$ It is hard to answer since this is all too abstract. I'm guessing you would want to locate the peak for each waveform and use that as index 0, as this seems to be the only thing common. You could compensate for the different sample frequencies by storing both waves in the same kind of arrays, apply some digital filter (moving average or similar) on the 5 samples you get from the fast one, then "round it" down. $\endgroup$
    – Lundin
    Commented Jul 3, 2013 at 11:58
  • $\begingroup$ @PaulR - it is certainly possible to get that kind of resolution by using all of the data and not just the peak, though the result may be a bit noisy. The first step would probably be to upsample the 200 KSPS signal to 1 MSPS, using an appropriate lowpass filter to interpolate. For a simple minded approach, once could then do a sliding correlation over the entire signal (literally try every possibility) and find the best match. This will have an output resolution of the reciprocal of the sample rate - ie, 1 uS, but accuracy will depend on signal quality. $\endgroup$
    – Chris Stratton
    Commented Jul 3, 2013 at 14:14
  • 2
    $\begingroup$ And sometimes it is worth building the simple minded version first, and run it on your PC against recorded data, to decide if the results are useful - then you can decide if it's worth optimizing the implementation, or if you need to rethink the entire system. $\endgroup$
    – Chris Stratton
    Commented Jul 3, 2013 at 14:16
  • $\begingroup$ @Chris: resolution != accuracy - OP says he wants 1 µs precision, not 1 µs resolution. $\endgroup$
    – Paul R
    Commented Jul 3, 2013 at 14:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.