# Efficient correlation of a low duty cycle training sequence

Is there a way to efficiently correlate a training sequence that is N samples long, framed at M samples where M >> N, with L occurrences of such frames (see below). For the pedants, the training sequence may or may not vary in the L subsequent frames, thus the longer correlation template.

The samples in between the subsequent training sequences would be unknown so they would be 0's in the correlation template. There is a lot of wasted processing with the multiplications/additions of all the 0's. I am wondering what optimizations can be made by taking advantage of such a signal structure.

Example:

<- N ->
_____
|     |         ... repeated L-1 times ...
______|     |_______
<------- M --------->

• That has nothing to do with pedantry: if the sequence is different, you can't consider it a repitition, so this is extremely central to your question: Does the $N$ long sequence repeat or not? Please pick one, the question is broad enough as is. – Marcus Müller Feb 23 '19 at 21:31
• The sequence does not repeat but I’d be interested in both answers as both have applications – BigBrownBear00 Feb 24 '19 at 0:21
• So, I'd recommedn you focus on the non-repeating case, then. It's 1am where I am, but if someone else answers in the meantime, you might be able to infer for the repeating case for that. – Marcus Müller Feb 24 '19 at 0:23
• One thought that’s comes to mind is a gated time domain correlation that may be more efficient than the longer FFT based correlation, but I’m not sure where that break even point is – BigBrownBear00 Feb 24 '19 at 0:44
• but if you could gate your time-domain correlation, you could as well do an FFT-based correlation for each of the intervals, which would be still more efficient. So, that's my question: Does your receiving end already have timing synchronization, i.e. does it know where the zeroes go? – Marcus Müller Feb 24 '19 at 8:35

One way to approach this would be to have a bank of $$L$$ subcorrelators, each of which use the corresponding $$N$$-sample long template. Then, in order to get the effect of correlating against the longer gated sequence, one need simply to sum the outputs of the subcorrelators with the appropriate delays applied. This is equivalent to breaking the long matched filter into a parallel formulation with $$L$$ subfilters.

For instance, assume the output of subcorrelator $$i$$ is $$c_i[n]$$, and that the notional output of the full $$ML$$-sample corelator is $$c[n]$$. The full correlator output is just equal to the sum of the shorter subcorrelators, after taking into account the $$M$$-sample delay between the expected position of each template in the input signal:

$$c[n] = \sum_{i=0}^{L-1} c_i[n-(L-1-i)M]$$

Using this structure, for each output sample, you effectively implement an $$LN$$-tap FIR filter instead of an $$LM$$-tap one. With that said, if any of these numbers are large (greater than 50-60 or so), it's likely more efficient to use FFT-based fast convolution techniques instead. This method is compatible with that; you would simply use fast convolution to calculate each of the short subcorrelator outputs, then perform the delayed sum as described above. I've implemented this very technique before with good success.

There are a couple other things to think about with this approach:

1. The OP suggests that some of the $$L$$ frames may not have distinct patterns from each other. If this is the case, you can achieve some complexity reduction by only implementing the number of unique subpatterns, then tapping the outputs from each subcorrelator appropriately.

2. This sort of technique can run into issues with scalloping loss if the overall length of the correlator ($$LM$$ samples) is large with respect to any carrier frequency uncertainty on the input signal. This is inherent with any kind of coherent correlator structure; the longer you correlate (thus giving you more potential gain), the more frequency selective the correlator is (the more loss you have for a given frequency offset in your signal).

• Ha, I was about to start typing exactly this answer :) One thing to add is that there's potential for small complexity loss when you assume that e.g. the second $N$-burst can't be at the very start of the transmission. Also, a big benefit to fast convolution in this case is that the segmented FFT-ing of the received signal only needs to be done only once for all $L$ subcorrelators! Also, very much depending on the machine and actual lengths involved, and whether you do anything but power detection afterwards, this might be the case where you don't even have to overlap-save / -add individually. – Marcus Müller Feb 24 '19 at 15:03
• @MarcusMüller: Yes, that is a good point. If you're doing fast convolution, you can reuse the forward FFTs for each subcorrelator, since they are operating on the same input signal. – Jason R Feb 24 '19 at 15:08
• and if you end up adding up the backward FFT'ed results with an appropriate lag between each subcorrelator, you might as well do that addition in frequency domain and also only do one reverse FFT – but that requires that you pick your fast-correlation segment and overlap lengths so that you $M$ is an integer multiple of the segments. – Marcus Müller Feb 24 '19 at 15:16
• nice answer. I will prototype this and see if I have any follow up questions! – BigBrownBear00 Feb 24 '19 at 16:26
• update: after implementing this I found that dropping samples from the ith (i>0) subcorrelators provided identical results to using the longer correlation template. – BigBrownBear00 Feb 25 '19 at 4:43