Question on threshold mathematics in correlate_and_sync block

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

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

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

“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

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. :slight_smile:

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

On Fri, Jan 2, 2015 at 8:57 AM, Andy W. [email protected]
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

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

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

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. :slight_smile:

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

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

On Mon, Jan 5, 2015 at 5:00 AM, Andy W. [email protected]
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.
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

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

On Mon, Jan 5, 2015 at 8:00 AM, Andy W. [email protected]
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