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
>>> a
>>> 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
>>> for
>>> clock recovery) at least give the option of having consistent
>>> tagging.
>>
>> 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
>>
>> Agreed.
>>
>>> (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
>>> point,
>>
>> 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
>>> for
>>> 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.
>>
>> or
>>
>> 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
>> backend.
>> http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index
>> .html
>> http://mpir.org/
>> (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
>>> odd
>>> 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.
>>
>> Regards,
>> Andy
>>
>>> Best regards,
>>> Marcus
>>>
>>> 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
>>>>>> blocks
>>>>>> with non-integer relative rate. If the ratio is not a power of
>>>>>> two,
>>>>>> the numerical accuracy of the floating point will cause the
>>>>>> output
>>>>>> tags to diverge from the input tags. Consider the fractional
>>>>>> resampler. It accumulates the timing offset in the range of 0
>>>>>> to
>>>>>> 1.
>>>>>> However tag propagation multiplies the ratio by the sample
>>>>>> number.
>>>>>> As
>>>>>> the sample number grows the LSB accuracy of the ratio gets
>>>>>> scaled
>>>>>> by
>>>>>> the ever larger value. For a ratio of 1.001 we saw divergence
>>>>>> of
>>>>>> 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
>>>>> testing,
>>>>> that would be great.
>>>>>
>>>>>> I rewrote tag propagation for the resampler but did not rework
>>>>>> the
>>>>>> generic logic. I think the key point is to use the delta
>>>>>> between
>>>>>> read
>>>>>> and written items to take out the large integer difference and
>>>>>> then
>>>>>> 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
>>>>> arithmetic
>>>>> to
>>>>> propagate tags. (Except if enable_update_rate() is True, in which
>>>>> case,
>>>>> precision tag placement was abandonded by the block author
>>>>> anyway.)
>>>>
>>>> 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
>>>> really
>>>> running at the requested rate, but some rounded (in binary) rate.
>>>>
>>>> So I have a test flowgraph with a single fractional respampler in
>>>> it,
>>>> with a resample ratio of 1.001 specified. Here are the parameters
>>>> reported by my patched GNURadio:
>>>>
>>>> [ andy@pinto 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
>>>> ratio
>>>> of 1.00100004673. The relative rate of 0.999000952364 does appear
>>>> to
>>>> be the correct reciprocal of 1.00100004673. My patch's back-
>>>> figuring
>>>> of a relative rate of 1000/1001 (= 0.999000999 = 1/1.001) is in
>>>> fact
>>>> what the user wanted. But when propagating tags using those
>>>> integers,
>>>> 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.
>>>>
>>>> Regards,
>>>> Andy
>>>>
>>>> _______________________________________________
>>>> Discuss-gnuradio mailing list
>>>> Discuss-gnuradio@gnu.org
>>>> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>>
>> _______________________________________________
>> Discuss-gnuradio mailing list
>> Discuss-gnuradio@gnu.org
>> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>>
>
_______________________________________________
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
No comments:
Post a Comment