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