# Question on threshold mathematics in correlate\_and\_sync block

**URL:** <https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652>\
**Category:** GNU Radio\
**Created:** [December 31, 2014, 8:01pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652 "2014-12-31T20:01:40Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![addis\_a](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c4cdca/32.png) [@addis\_a](https://www.ruby-forum.com/u/addis_a)\
**Post date:** [December 31, 2014, 8:01pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/1 "2014-12-31T20:01:40Z")

</div>

Hi.

Can someone give me a brief clue about the threshold testing in the  
correlate\_and\_sync block?

In the constructor:

```
  for(size_t i=0; i < d_symbols.size(); i++)
    corr += abs(d_symbols[i]*conj(d_symbols[i]));
  d_thresh = 0.9*corr*corr;

```

corr looks like the value (at offset 0) of the discrete autocorrelation  
of the matched filter.

d\_thresh looks like 90% of the value of the autocorrelation of the  
matched filter squared.

So far this makes sense to me.

Then in the work function (corr is a totally different array variable  
here):

```
  // Calculate the correlation with the known symbol
  d_filter->filter(noutput_items, in, corr);

  // Find the magnitude squared of the correlation
  std::vector<float> corr_mag(noutput_items);
  volk_32fc_magnitude_squared_32f(&corr_mag[0], corr, 

```

noutput\_items);

```
  int i = d_sps;
  while(i < noutput_items) {
    if((corr_mag[i] - corr_mag[i-d_sps]) > d_thresh) {

```

This “if” test confuses me slightly. We check to see if the value of  
the output of the matched filtering has crossed the threshold relative  
to one symbol previous? Why not just check relative to 0?

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [December 31, 2014, 9:49pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/2 "2014-12-31T21:49:50Z")

</div>

On Wed, 2014-12-31 at 14:00 -0500, Andy W. wrote:

> here):  
> if((corr\_mag[i] - corr\_mag[i-d\_sps]) \> d\_thresh) {
> 
> This “if” test confuses me slightly. We check to see if the value of  
> the output of the matched filtering has crossed the threshold relative  
> to one symbol previous? Why not just check relative to 0?

An additional note: The “if” test doesn’t work too well, if the preamble  
sequence is “101010101010…”, since then the correlation will have  
peaks at the symbol spacing, d\_sps. Maybe

if((corr\_mag[i] - corr\_mag[i-d\_sps/2]) \> d\_thresh) {

would be better, since the correlation should sag at the half symbol?

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 2, 2015, 2:58pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/3 "2015-01-02T14:58:44Z")

</div>

On Wed, 2014-12-31 at 15:48 -0500, Andy W. wrote:

> On Wed, 2014-12-31 at 14:00 -0500, Andy W. wrote:
> 
> > Hi.
> > 
> > Can someone give me a brief clue about the threshold testing in the  
> > correlate\_and\_sync block?

I found my answer in this post:

[https://gnuradio.org/redmine/projects/gnuradio/wiki/Hackfest1310](https://gnuradio.org/redmine/projects/gnuradio/wiki/Hackfest1310)

“The correlation peak is tested by first observing that the width of the  
correlation peak will be sps number of samples wide. So we look at  
sample i and sample (i-sps). If the difference between these two symbols  
is greater than the threashold we calculated in the constructor, we  
declare a correlation.”

That probably works for most preambles.

Unfortunately it becomes a problem with the data sequence  
“101010101010…” and a rectangular pulse filter, as the absolute value  
(magnitude) peaks of the correlation increase somewhat linearly as the  
sequences align, and there will be a peak at every sps samples. Thus  
the threshold test won’t trigger as expected.

The correlation absolute value peak happens every sps samples because,  
using NRZ bit mapping (0 =\> -1, 1 =\> 1), the positive correlation is  
about as strong as the neighboring negative correlation that is sps  
samples away.

I’m not sure if I should file a bug report for this corner case or not.

I’m writing my own correlator block based on the correlate\_and\_sync  
block; except that it works on real, not complex, input samples. For  
myself, I just use the unmodified output of the real valued correlation  
filter and just set the threshold test to be relative to 0.

> > 
> 
> sequence is “101010101010…”, since then the correlation will have  
> peaks at the symbol spacing, d\_sps. Maybe
> 
> if((corr\_mag[i] - corr\_mag[i-d\_sps/2]) \> d\_thresh) {
> 
> would be better, since the correlation should sag at the half symbol?

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 2, 2015, 5:08pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/4 "2015-01-02T17:08:15Z")

</div>

On Fri, 2015-01-02 at 09:57 -0500, Tom R. wrote:

> ```
> Unfortunately it becomes a problem with the data sequence
> I'm not sure if I should file a bug report for this corner case or not.
> 
> I'm writing my own correlator block based on the correlate_and_sync
> block; except that it works on real, not complex, input samples. For
> myself, I just use the unmodified output of the real valued correlation
> filter and just set the threshold test to be relative to 0.
> 
> ```

Hi Tom,

> Andy,
> 
> Thanks for the reports and details. I can definitely see the problem  
> with the situation you’re describing. We obviously weren’t considering  
> that case when we designed the block. We were really expecting any  
> preamble/access code that we were using would have good  
> autocorrelation statistics. From that perspective, the 10101…  
> pattern is pretty silly, but hey, it is used.

Yeah.

> Right now, you’re probably best off redoing your own block as you say  
> to deal with the specifics of your case. However, I’d like us to think  
> about how we can abstract this concept within the current block so  
> that we can more easily provide the behavior we’d like to see, such as  
> the correlation and detection logic, and the filter design. I know  
> Nick F. has thoughts on this, too, with his work on GMSK signals.

Yes, I leveraged Nick’s msk\_correlate\_and\_sync as well. 🙂

For visualizing the scenario I mentioned, see the attached “Clock  
pattern correlation.png”. I took the “corr” output of my custom block  
and plotted its abs() along with the baseband input. My custom block  
picked the two large positive correlation peaks and ignores the nearby  
negative ones. With my particular real, baseband input, I’m guaranteed  
not to have any sign ambiguity in the baseband input; so I could ignore  
that wrinkle.

There is another problem which prevents proper correlation: the end of  
work coming mid-burst. See the attached “End of work mid-corr.png”  
which shows an end of work tag with the value of noutput\_items. I’m not  
sure how to handle this is the general case, except for burst energy  
detection. But burst energy detection won’t work for CDMA-like things,  
where the signal might be buried in the noise.

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 2, 2015, 3:58pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/5 "2015-01-02T15:58:51Z")

</div>

On Fri, Jan 2, 2015 at 8:57 AM, Andy W. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> (magnitude) peaks of the correlation increase somewhat linearly as the  
> I’m writing my own correlator block based on the correlate\_and\_sync  
> block; except that it works on real, not complex, input samples. For  
> myself, I just use the unmodified output of the real valued correlation  
> filter and just set the threshold test to be relative to 0.

Andy,

Thanks for the reports and details. I can definitely see the problem  
with  
the situation you’re describing. We obviously weren’t considering that  
case  
when we designed the block. We were really expecting any preamble/access  
code that we were using would have good autocorrelation statistics. From  
that perspective, the 10101… pattern is pretty silly, but hey, it is  
used.

Right now, you’re probably best off redoing your own block as you say to  
deal with the specifics of your case. However, I’d like us to think  
about  
how we can abstract this concept within the current block so that we can  
more easily provide the behavior we’d like to see, such as the  
correlation  
and detection logic, and the filter design. I know Nick F. has  
thoughts  
on this, too, with his work on GMSK signals.

Tom

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 2, 2015, 6:57pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/6 "2015-01-02T18:57:54Z")

</div>

> > with the situation you’re describing. We obviously weren’t considering  
> > that we can more easily provide the behavior we’d like to see, such as  
> > not to have any sign ambiguity in the baseband input; so I could ignore  
> > that wrinkle.
> 
> There is another problem which prevents proper correlation: the end of  
> work coming mid-burst. See the attached “End of work mid-corr.png”  
> which shows an end of work tag with the value of noutput\_items. I’m not  
> sure how to handle this is the general case, except for burst energy  
> detection. But burst energy detection won’t work for CDMA-like things,  
> where the signal might be buried in the noise.

I’m in the middle of generalizing correlate\_and\_sync\_cc to allow use  
with  
any candidate vector you want (although I hadn’t considered the  
real-only  
case). It’s working now, and just this morning I encountered the same  
thing  
you’re seeing. Of interest to me is the loop:

\<…\>  
d\_filter-\>filter(noutput\_items, in, corr);  
\<…\>  
int i = d\_sps;  
while(i\<noutput\_items) {  
\<…\>

…with set\_history(d\_filter-\>ntaps()) in the constructor, we should  
probably be running the filter against the entire input vector  
_including_ history,  
and copying to the output the part relevant to the current work call.  
Or,  
only running the work function up to (noutput\_items - d\_filter-\>ntaps())  
items. Right?

–n

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 3, 2015, 11:28pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/7 "2015-01-03T23:28:29Z")

</div>

On Fri, 2015-01-02 at 09:56 -0800, Nick F. wrote:

> ```
> problem
> 
> > Nick F. has thoughts on this, too, with his work on GMSK
> picked the two large positive correlation peaks and ignores
> mid-corr.png"
> 
> ```
> 
> with any candidate vector you want (although I hadn’t considered the
> 
> …with set\_history(d\_filter-\>ntaps()) in the constructor, we should  
> probably be running the filter against the entire input vector  
> including history, and copying to the output the part relevant to the  
> current work call. Or, only running the work function up to  
> (noutput\_items - d\_filter-\>ntaps()) items. Right?
> 
> –n

Hi Nick,

Here’s what I just got working for me. In my block’s constructor I do  
this:

```
    // Correlation filter
    d_filter = new filter::kernel::fft_filter_fff(1, d_symbols);

    // Per comments in 

```

gr-filter/include/gnuradio/filter/fft\_filter.h,  
// set the block output multiple to the FFT filter kernel’s  
internal,  
// assumed “nsamples”, to ensure the scheduler always passes a  
// proper number of samples.  
int nsamples;  
nsamples = d\_filter-\>set\_taps(d\_symbols);  
set\_output\_multiple(nsamples);

```
    // It looks like the kernel::fft_filter_fff stashes a tail 

```

between  
// calls, so that contains our history maybe? The  
fft\_filter\_fff  
// block (which calls the kernel::fft\_filter\_fff) sets the  
history  
// to 1, so let’s follow its lead. I’m not sure if this is  
right  
// though.  
set\_history(1);  
//set\_history(d\_filter-\>ntaps());

```
    // Setting the alignment multiple for volk causes problems with 

```

the  
// expected behavior of setting the output multiple for the FFT  
filter.  
// Don’t set the alignment multiple for now, until we figure out  
// another way to ensure the output multiple provided by the  
// scheduler.  
//const int alignment\_multiple =  
// volk\_get\_alignment() / sizeof(float);  
//set\_alignment(std::max(1,alignment\_multiple));

See the attached “Correlator end of work OK.png” to see the correlator  
output looking reasonable across calls to work.

Nick and Tom,

Unfortunately there is still the problem of correlation tags that cannot  
be set back on the beginning of a preamble that spans 2 consecutive  
calls to work(). Compare the left (good) and right (bad) baseband pulse  
tagging in “Correlater cant set tag back in previous work call.png”.

Energy detection of the pulse might be one way to deal with this  
problem. Another might be to stash the last d\_symbols.size() samples in  
each call to work(), so the next call to work() can look back upon them,  
if needed. There are probably more graceful things to do.

-Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 2, 2015, 7:17pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/8 "2015-01-02T19:17:42Z")

</div>

On Fri, 2015-01-02 at 09:56 -0800, Nick F. wrote:

> ```
> CDMA-like things,
> 
> ```
> 
> d\_filter-\>filter(noutput\_items, in, corr);  
> (noutput\_items - d\_filter-\>ntaps()) items. Right?
> 
> –n

I haven’t worked through all that yet, myself. 🙂

I do know with my differential input signal, I have to run the  
subtraction through all the history and the output items to get the  
proper baseband input vector. Here’s what I’m doing currently in that  
start of work():

```
    memcpy(out_p, in_p, sizeof(float)*noutput_items);
    memcpy(out_n, in_n, sizeof(float)*noutput_items);

    // Compute the unequalized baseband input
    volk_32f_x2_subtract_32f(d_in, in_p, in_n, noutput_items + 

```

(history()-1));

```
    // Calculate the correlation with the known symbols
    d_filter->filter(noutput_items, d_in, corr);

```

I was _assuming_ the d\_filter-\>filter() call was sucking in the proper  
amount of history it need for noutput\_items based on d\_filter-\>ntaps()  
since it already knows ntaps().

My possibly flawed understanding of history() is that the actual size of  
the incoming buffer is at least noutput\_items + (history()-1), and that  
in[0] points to the oldest sample in the history.

I thought the discontinuity in the output of the correlation at the  
beginning of the next work call looked odd. So maybe I’ve got  
something wrong.

-Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 5, 2015, 2:02pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/9 "2015-01-05T14:02:25Z")

</div>

On Fri, 2015-01-02 at 09:56 -0800, Nick F. wrote:

> I’m in the middle of generalizing correlate\_and\_sync\_cc to allow use  
> with any candidate vector you want (although I hadn’t considered the  
> real-only case).

> –n

Hi Nick,

Since you’re reworking the correlate and sync block, I thought you might  
want to address some additional things I’ve found regarding the matched  
filter generation. I’ve noticed 1 end-user pitfall that you may want to  
document and 1 bug in how the matched filter is generated.

1. Pitfall: The pulse filter tap specification requirments are not  
obvious. In my experimentation over the weekend, the pulse filter taps  
have to be generated assuming a rate of:

nfilts samples/symbol, or equivalently  
(nfilts \* symbol\_rate) samples/second

where

nfilts is the number of filters in the polyphase resampler  
symbol\_rate is the symbol rate in symbols/second

regardless of the user’s “sps” (samples/symbol) value.

This is certainly the case for the real rectangular pulse with no ISI  
and real half-sinusoid pulse with no ISI, with which I was playing.

So, if nfilts = 32, these are my proper pulse filter taps specifications  
in python:

rectangular: [1.0]_nfilts  
half-sinusoid: [math.sin(math.pi_float(i)/float(nfilts)) for i in  
range(nfilts)]

even though my sps = 13.3333.

This was very non-intuitive and should be documented for the end-user.

1. Bug: The generated matched filter appears to be short a symbol.  
Using my real variant of correlate\_and\_sync, I specified the following:

symbols: [1,0]_10 + [1,0,1,1,1,1] (block converts these to  
NRZ)  
pulse filter taps: [math.sin(math.pi_float(i)/float(32)) for i  
in range(32)]  
samples/symbol: 13.3333333333  
nfilts: 32

and the block generates the matched filter in the attached PNG. The  
missing final symbol from the start of the filter is obvious. Since my  
block is a very closely cut-and-paste clone of  
correlate\_and\_sync\_impl.cc and msk\_correlate\_impl.cc, the bug probably  
exists in them as well.

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 5, 2015, 6:11pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/10 "2015-01-05T18:11:17Z")

</div>

On Mon, Jan 5, 2015 at 5:00 AM, Andy W. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> Since you’re reworking the correlate and sync block, I thought you might  
> want to address some additional things I’ve found regarding the matched  
> filter generation. I’ve noticed 1 end-user pitfall that you may want to  
> document and 1 bug in how the matched filter is generated.

Great! Thanks!

> ```
> nfilts is the number of filters in the polyphase resampler
> rectangular: [1.0]*nfilts
> half-sinusoid: [math.sin(math.pi*float(i)/float(nfilts)) for i in
> 
> ```
> 
> range(nfilts)]
> 
> even though my sps = 13.3333.
> 
> This was very non-intuitive and should be documented for the end-user.

Yeah, this annoyed me, too. The new system actually takes in unmodulated  
symbols, modulates them with the modulator of your choice, and then  
applies  
the (non-polyphase) filter taps of your choice to the modulated symbols.  
This way, you can pass the same symbols into (for instance) a GMSK  
modulator with the shaping filter taps set to [1] since GMSK typically  
needs no additional post-modulation filter, a PSK modulator with RRC  
taps  
for the channel, etc. The correlate\_and\_sync block in my branch doesn’t  
take in symbols, but bits, and lets a modulator block (passed into it as  
an  
argument) handle the modulating. I’m avoiding the polyphase filter  
because  
I don’t have to do resampling in the correlate\_and\_sync block. The  
caveats  
are:

1. Every digital modulator in GNURadio seems to use its own input data  
format – packed or unpacked bits, signed vs. unsigned, NRZ or straight  
binary, etc. Your input vector has to be constructed to match the format  
the modulator expects.
2. Many of the modulators don’t support fractional samples per symbol.  
There are of course workarounds, but I consider this a bug.

> ```
> samples/symbol: 13.3333333333
> nfilts: 32
> 
> ```
> 
> and the block generates the matched filter in the attached PNG. The  
> missing final symbol from the start of the filter is obvious. Since my  
> block is a very closely cut-and-paste clone of  
> correlate\_and\_sync\_impl.cc and msk\_correlate\_impl.cc, the bug probably  
> exists in them as well.

Pretty sure my changes have obviated this bug but I’ll check it out.

My branch has bugs right now (mostly in tag alignment) but you can see  
it  
at [GitHub - bistromath/gnuradio at msk\_from\_master · GitHub](https://github.com/bistromath/gnuradio/tree/msk_from_master).  
Suggestions  
and improvements of course welcome. Seems to me that we should  
collaborate  
on this, using my branch as a starting point. Still need to redo the  
test  
case and example, too. Attached is a working example showing the  
misalignment. Probably something simple but I was pulled away from  
working  
on it this weekend.

–n

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 6, 2015, 3:30pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/11 "2015-01-06T15:30:04Z")

</div>

On Mon, 2015-01-05 at 09:09 -0800, Nick F. wrote:

> My branch has bugs right now (mostly in tag alignment) but you can see  
> it at [GitHub - bistromath/gnuradio at msk\_from\_master · GitHub](https://github.com/bistromath/gnuradio/tree/msk_from_master).  
> Suggestions and improvements of course welcome. Seems to me that we  
> should collaborate on this, using my branch as a starting point.

Sounds good. Give me a few days to get setup to where I can test your  
branch.

Thanks for your work on this.

Regards,  
Andy

---

<div class="post-metadata">

**Author:** ![andywatts](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d78d45/32.png) [@andywatts](https://www.ruby-forum.com/u/andywatts)\
**Post date:** [January 5, 2015, 3:33pm UTC](https://www.ruby-forum.com/t/question-on-threshold-mathematics-in-correlate-and-sync-block/233652/12 "2015-01-05T15:33:41Z")

</div>

On Mon, Jan 5, 2015 at 8:00 AM, Andy W. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> ```
> (nfilts * symbol_rate) samples/second
> 
> nfilts: 32
> 
> ```

Andy,

You’re finding some stuff out here and pointing out bugs and  
documentation  
issues. I really appreciate the bug reports on our Issues page, but this  
would be a lot easier if you would also provide patches, since I’m  
assuming  
you’re doing this for yourself, anyways. Since you’re actively working  
on  
it and learning, I think you’re more qualified to provide the added  
documentation and these bug fixes right now. When you’re done going  
through  
this, please put together a pull request for us that addresses these  
issues.

Thanks!  
Tom