NCO precision plans

[vsergeev]

I use the NCO module as an acceleration option for complex mixing in LuaRadio and noticed that the module removed support for the sin/cos computation LIQUID_VCO mode in 60f4d7efbac1e9b32b659b945f90284d5f2154a6, and now defaults to the lookup table LIQUID_NCO mode. This increased performance for the frequency translator block on my machine by about 60% (50 MS/s to 80 MS/s), but at the cost of some precision, as the error epsilon also increased by about 2 orders of magnitude from before in my unit tests.

I was wondering if you were planning on re-implementing the more precise oscillator in the future, or perhaps as a middle ground, allow the user to size the lookup table to select their desired level of precision.

Thanks for the great work!

[JayKickliter]

I’ve also noticed some pretty bad phase noise of the NCO object in the past.

[jgaeddert]

There is definitely a trade-off between speed and accuracy, and there's a fine balance to be made there. I've had several thoughts on how to address this. One option would be to specify the look-up table used for the sin/cos values. Another would be to allow interpolation (linear or perhaps quadratic) between values. The most precise would be to use the native sinf/cosf libmath functions, but that's the slowest. I don't have any great ideas on how to allow these options to be used, but my initial thought was to change the create() method (or have additional ones). That would of course change the API which would break functionality for some people.

[ArtemPisarenko]

Hi all. Firstly, I would like to thank @jgaeddert for such wonderful library. I'm newbie in DSP and current NCO object precision lead me to think that it's absolutely fine until I learned the subject a little deeper...

It turns out that significantly better precision might be achieved with almost same costs and without changes in API (almost). See how float-precision NCO implemented in GNU Radio: interface header, fixed point 2*PI interface, fixed point 2*P implementation, script used to generate sine table. It generates almost perfect signal of any frequency using pre-generated lookup-table of 1024 pairs of floats and interpolation. This is the worst case how it look like:

I don't understand math theory behind it but I was able to adapt this implementation for several possible modifications of liquid-dsp depending on design goals and trade-offs I would like to discuss.

Option 1. Generate fixed 1024-lookup-table in nco_create() or at compile time, modify nco_sin()/nco_cos()/nco_sincos() functions. Doesn't break API and implementation looks similar, but decreases performance of each value generation step because of interpolation which adds two floating point operations: multiplication and addition.

Option 2. Modify nco_create() to just init values, modify nco_set_frequency()/nco_adjust_frequency() to generate custom interpolated 1024-lookup-table. Doesn't break API but greatly decreases performance of frequency setup/modification and decreases precision of phase (resulting in modified actual generated frequency).

Option 3. Modify nco_create() to just init values, add nco_set_frequency()/nco_adjust_frequency() variants for type==LIQUID_VCO accepting phase value as fraction defined by two integer values n and m (i.e. 2*PI * n / m) and generating custom interpolated m-lookup-table. Or introduce brand new VCO object. Breaks API and decreases performance of frequency setup/modification proportional to m value.

All of them give same worst-case spectrum picture shown above. I would personally prefer option 3, because I've come to conclusion that it isn't possible to achieve high precision in any way without API change, and this specific change is most optimal one (introducing VCO object looks better). Also option 2 looks dreadful for me (although, theoretically there are might be some rare cases where frequency precision loss is acceptable). Some common notes about options:

• lookup-table generation in options 1 and 2 is slower than current liquid-dsp one, but I'm sure it isn't issue and whatever fixed/constant generation should be moved to compile-time anyway (like it done in gnuradio);
• decreased speed of frequency setup/modification is acceptable in many cases;
• option 3 gives user fair balance between freedom to define frequency and optimize speed/memory on its setup (i.e. it may make hardware decisions based on software aspects first),
• option 3 frequency setup/modification may implement relatively cheap optimization of actual n and m values used to generate table, by finding common denominators with popular bases 10 and 2 and reducing values, e.g. user may simply define phase as n = target_frequency = 48000 (Hz), m = sample_rate = 768000 (Hz) which results in actual n = 3, m = 48 (well, adding less popular base 3 allows getting even better n = 1, m = 16).

These are only main options, giving directions for design choices. I wouldn't like to prepare any specific patch until some specific design will be chosen first. Also there are might be some license issues with my draft code because I've just stealed gnuradio implementation. :))) Not sure it can be named such, because it's heavily modified/combined/splitted, but anyway it cannot be used as is (especially for option 3), keeping copyright headers. Although, it might be ok provided that some reference to gnuradio authorship will be given in some form... I'm sure they've just implemented some known and patent-free math apparatus. I just don't know how to deal it properly at now...

Anyway, current documentation and interface doesn't match implementation because type LIQUID_VCO just being silently ignored which leads to confusion (especially among newbies). If implementation will be left as is then type should be removed. Yes, this breaks API compatibility, but otherwise it just lies to old user code expecting to have high-precision, so it breaks its functionality instead. I consider it's much worse.

[ArtemPisarenko]

Forgot about large downside of option 3. Lookup table is very large for very low frequencies. Seems like there are no simple and universal solution (except for option 1)...

[ArtemPisarenko]

You may take a look at my current implementation

[ArtemPisarenko]

I've got lot of free time and improved my implementation, so it almost ready for pull request. I think now it provides best compromise ever possible between API compatibility, documented promise, performance considerations and freedom of user choice.

The only issues left:

• output range overflow in LIQUID_VCO_INTERP type being derived from original implementation, and I wasn't able to compensate it like I did it for LIQUID_VCO_DIRECT type, so I posted issue at gnuradio;
• strange "appropriate" rounding behavior in NCO(_index);
• LIQUID_VCO_DIRECT type with parameters n=-1, m=2 computes sine output sequence 0.5;0.5 instead of 0;0

[brian-armstrong]

It's worth noting that, with your having admitted being tainted by GPL code, you probably shouldn't be committing anything to this issue now. This repo's license is quite handy and GPL people don't tend to have much understanding about this stuff, and better safe than sorry.

[JayKickliter]

It's worth noting that, with your having admitted being tainted by GPL code, you probably shouldn't be committing anything to this issue now.

@ArtemPisarenko please heed @brian-armstrong's advice.

Funnily enough, I once did the same thing for DSP.jl by cribbing some LiquidDSP code before Liquid was converted to MIT, and got the same recommendation. Which led me to open #6.

[ArtemPisarenko]

I wasn't committed/pulled anything to this project yet. Just referenced my fork at this moment, because I'm aware of this issue is still open. But I think it isn't much big deal. I'm not expert in GPL, but as far as I understand term "freedom" in its roots, it means sharing work for "good" intentions. I've referenced original authorship and not going to sell it or exploit for any purpose considered "bad". Although it indirectly may be finally used by someone in such purposes (possibly allowed by liquid-dsp license?), it shouldn't make these intentions "bad", because liquid-dsp was created with "good" intention - share knowledge with people. So, I cannot imagine GPL folks claiming against such commitment or taking offence, because it would make them behave like evil they fight against (copyright/patent holders). In same way, I cannot imagine this small issue cannot be resolved in any way, leading me to trying to obfuscate or hide in some way the fact that it's derived work, or learn problem being solved to completely and deeply understand math behind this algorithm (and, most likely, meaning of life additionally) in order to implement it another way (which, I'm sure, make source code differ not much more from what it looks now), thus effectively turning "good" job to patent fighting... It's just absurd and contradicts with goals for whose good GPL stand for, doesn't it ? I'm sure it's the only question of how properly reference copyright (oops, copyleft!) or ask gnuradio granting permission for specific use of just specific code fragments, or something like that... We are all good guys, right? :)

[brian-armstrong]

It isn't worth the risk IMO. What you're talking about, hoping for the best outcome, isn't how the law works. It would be better to just have someone who isn't tainted by the GPL code to do a clean room implementation with proper attribution. At this point you've even said that you started with tainted code so all bets are off.

[ArtemPisarenko]

I wonder how GPL become some bad guy with lawyers and association with code it covers now sounds as "tainted" (I'm not native english speaker and this word translated to my language has negative tone)... Nevertheless, ok. I'm just interested what means "clean room implementation" and which attribution is proper? Does it simply mean to happily find anywhere a person who solved exactly same (or more generic) problem but didn't publicitly said anywhere "Look, I got an idea from !" ? I guess final outcome of this approach would be to spend a lot of time on hard work which will not make happy neither us, nor supposed folks from gnuradio/GPL. Maybe I'm so naive and gnuradio aren't "good" guys? Sorry, if my words may offended anyone, but I just don't understand situation. Honestly.

[vsergeev]

@ArtemPisarenko, thanks for looking into this thoroughly. I like the direction of your proposed changes. As for the copyright discussion, I think by "tainted" @brian-armstrong and @JayKickliter are just saying that GPL is a contagious license, unlike the MIT license, and they're concerned it could infect liquid-dsp. This would be a problem for closed source commercial use, as incorporating GPL licensed code obligates a company to GPL license and publish all associated project code, whereas the MIT license does not. That being said, I think most people here probably agree there is a bit of objective absurdity to this when it comes to something like mathematical routines, but that doesn't mean it's worth the risk. I'm not sure the best way to proceed -- ultimately, it's up to @jgaeddert.

[ArtemPisarenko]

Ok. And just few more thougths on absurdity of this situation and related risks. As far as I understand clean room design, it's a techique used to deal with copyright rather than copyleft we concerned with. So here are no intellectual property infringement. What I actually did are reverse-engineering and own implementation, not copying. While this may sound as argument in favor of copyright infringement, with regards to copyleft it protects my position instead. The only fine line separating reverse-engineering from copying in this case is that I don't have complete understanding of its core math formulas, but I wouldn't consider such subjective fact being allowed to finally obligate resulted implementation with that strange "freedom" restriction GPL declares of. Well, I would agree that some core math formulas was copied rather than source code ... but I wouldn't call resulting implementation at a whole as derivative work in the meaning of GPL terms. I would take these formulas from anywhere (other "free" software, scientific article, as a result of long education, etc...). And gnuradio just made my efforts easier and we woulld appreciate authors for their work done (or they copied formulas too? ;) ). And attribution statement I made is exactly that appreciation. Isn't it enough? The only objective participant who may judge "ok, no problem, use it" is gnuradio. Why just don't ask them explicitly? Otherwise, it may seem like I "tainted" the whole world just because already referenced gnuradio, and since this discussion and gnuradio source code are publicitly accessible, no "clean room" possible by anybody since now, so the whole solution of NCO problem is fated to never be solved "in clean way". Furthermore, this discussion leaves me in even worse feeling of that "tainting" now applied to my person at a whole and now every my contribution to both projects might be looking suspicious. Hope, things are not so bad. Otherwise, I have to ask Richard Stollman to clean "tainting" epidemy I started :) The funny thing is that I declared attribution to gnuradio driven by "good" intentions, which finally caused such bad consequenses.

[brian-armstrong]

Well put @vsergeev and sorry for my brusqueness @ArtemPisarenko . Your enthusiasm for getting this fixed is admirable, and I should have replied more positively. However I still do think that in general the possibility of licensing issues with GPL code are real. In my experience GPL can be more dogmatic than pragmatic.

[ArtemPisarenko]

No problem. Anyway I don't like this implementation... So I'm on the way to finishing completely new one from scratch! It turned out to be much easier than I expected. It's based on trivial and intuitive math (no reverse engineering of anything ever), has almost same characteristics (and even faster calculation of lookup table for LIQUID_VCO_DIRECT type), and has no issues I listed above. Now I'm trying to find what's the catch...

[ArtemPisarenko]

Ready. Now I'm sure there are absolutely no issues left.