[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer r

From: Jeff Long
Subject: Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate
Date: Mon, 1 Jan 2018 13:40:23 -0500
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0

(and if I'd actually read Andy's last post carefully ...)

On 01/01/2018 01:32 PM, Jeff Long wrote:
As Eugene suggests, the fractional resampler can be handled by doing a linear mapping from the input to the output of a single work call. Wouldn't this work with most or all blocks? There would also need to be an offset in order to handle history. Then, there wouldn't be a need to use higher precision counters.

On 01/01/2018 11:24 AM, Jeff Long wrote:
I think the reason rate changes are difficult for tags is that the block executor tries to guess what a block is doing based on its long-term or static rate change. The block itself knows exactly how input items relate to output items, and maybe certain blocks need to provide more feedback than just a rate. In those cases, the executor could use the exact translation provided by the block, and in tamer cases the rate can still be used.

On 01/01/2018 10:53 AM, Andy Walls wrote:
Hi Marcus:

On Sun, 2017-12-31 at 15:09 +0000, Müller, Marcus (CEL) wrote:
Hi Andy, hi Eugene

Hm, coming back to an idea I had not so long ago:

tag offset should not be 64bit unsihned integers only, but also have
64 bit fractional part.

That would not immediately solve the computational inaccurracy during
resampling, but would at least for multi (as in >2) rate systems (eg.
rational resampling for sample rate reduction, arbitrary resampling
clock recovery) at least give the option of having consistent

IMO, adding a fractional part does not solve the problem at hand -
correct tag propagation through 1 block - but it probably is required
for precise propagation through multiple rate changing blocks.

I'm keeping it in mind, but I want to avoid changing existing
interfaces right now.  I.e. get_tags_in_[range|window]() runs into a
backward compatability issue for a tag that comes < 0.5 samples before
the beginning of the requested range: should the tag offset -0.49
samples realtive to the start of the window be returned or not?

Personally, my gut feeling is that for this kind of divisional math,
floating point is not the number format of choice


  (for multiple (as in
2) reasons).

This actually doesn't apply to the arbitrary resampling case as much,
but the d_relative_rate property of a block shouldn't be a floating

Internal to the gnuradio-runtime there are a number of places where,
for estimating, using a floating point d_relative_rate is just fine.
It is expedient and avoids the problem of interger overflow for cases
where one has large integer interpolation and decimation factors.

but a ratio of two integers, one of them being signed. Maybe I
should be adding a set_relative_rate(int64_t numerator, uint_64_t
denominator) to block, and make set_relative_rate(double) a wrapper
that (and of course change the block_executor to do fractional rather
than floating point math);

So that's what my change does. :)  I also changed all the blocks, that
could easily easily call the integer version of
set_relataive_rate(interpolation, decimation), to do so.

To avoid integer overflow, I picked an algoritm in the new
set_relative_rate(double) wrapper, to convert the relative rate to a
ratio of two integers that got within 1 ppm of the passed in relative
rate.  Because sane users only use relative rates of 1/25 or 1001/1000
or 255/256 or 2/3 or something like that, and whacky relative rates
using large (>16 bit) integers in the ratio are just a product of
rounding, right?  Well I was wrong. :(

Unfortunately, the fractional resampler is a corner case that actually
uses the rounded (in binary) version of the resampling rate, that the
user specifies, in its actual operation. Computing exact integer ratios
to represent the double can lead to 53 bit numbers (IIRC), which can
lead to integer overflows when multiplying uint64_t's together. :(

So what I'm left with are two broad options to deal with handling a
double relative rate (like the fractional resampler uses):

1. Implement an method like Eugene suggests: do a double multiply, get
a rounded result, do a double division to get back to an initial
offset, subtract off that initial offset, do a double multiply again,
and then a final add.


2. Allow and compute large, exact integer ratios of
interpolation/decimation rate and use multiple precision (128 bit)
arithmetic when overflow out of 64 bits is possible.
Maybe using boost::multiprescision with the MIPR library on the
(MPIR is supposedly better for Windows compatability than GMP.)

I'm leaning towards option 2.

I find that I never calculate a rate other
than by calculating the floating point approximation of a fraction of
integers, and that there's always been subtle problems when running
ratios for prolonged times.

Technically a finite precision double can always be represented by a
ratio of integers, but those integers can be very (2^53-ish) large.

Thanks for the feedback.


Best regards,

On Sat, 2017-12-30 at 18:24 -0500, Andy Walls wrote:
Hi Eugene:

On Wed, 2017-12-27 at 16:18 -0500, Andy Walls wrote:
Hi Eugene

From:     Eugene Grayver
Date:     Thu, 9 Nov 2017 19:52:35 +0000

There is a major problem with the way tags are propagated in
with non-integer relative rate. If the ratio is not a power of
the numerical accuracy of the floating point will cause the
tags to diverge from the input tags.  Consider the fractional
resampler. It accumulates the timing offset in the range of 0
However tag propagation multiplies the ratio by the sample
the sample number grows the LSB accuracy of the ratio gets
the ever larger value. For a ratio of 1.001 we saw divergence
1000s of samples over a few minutes at 10msps.

Could you please test the following branch to see if it fixes the
problem?  Maybe test something simple first, like an FIR filter
decimating by 5 or 3?

https://github.com/awalls-cx18/gnuradio.git branch: tag_fix3

Don't bother testing.  See below.

Or if you have a GRC or python script I can use myself for
that would be great.

  I rewrote tag propagation for the resampler but did not rework
generic logic. I think the key point is to use the delta
and written items to take out the large integer difference and
apply the scaling to a local delta within the current window.

The fix that I have made stores the relative_rate as an integer
numerator and an integer denominator, and it uses integer
propagate tags. (Except if enable_update_rate() is True, in which
precision tag placement was abandonded by the block author

So this fix makes the fraction resampler tag propagation actually
perform worse.  The reason appears to be that, at least for
resamp_ratios very close to 1.0, the fractional resampler isn't
running at the requested rate, but some rounded (in binary) rate.

So I have a test flowgraph with a single fractional respampler in
with a resample ratio of 1.001 specified.  Here are the parameters
reported by my patched GNURadio:

     [    address@hidden grcs]$ ./tag_prop_test.py
     Fractional Resampler resamp ratio:  1.00100004673
     Block relative rate:  0.999000952364
     Block relative rate i:  1000
     Block relative rate d:  1001

So we can see that the block is really running with a resampling
of 1.00100004673.  The relative rate of 0.999000952364 does appear
be the correct reciprocal of 1.00100004673.  My patch's back-
of a relative rate of 1000/1001 (= 0.999000999 = 1/1.001) is in
what the user wanted.  But when propagating tags using those
tags start sliding very soon, since 0.999000999 is not the
0.999000952364 that the block is actually operating at.

I'll have to think about how to deal with this sort of situation.


Discuss-gnuradio mailing list

Discuss-gnuradio mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]