Show me the numbers

On Tue, 02 Jun 2015 08:43:59 -0500, "tsd82" <105802@DSPRelated> wrote:

>Kevin wrote:
>Here are the numbers for the zero noise case (bin number, frequency
>estimate, amplitude estimate):
> 7       7.500000000560  1.000000000016
>
>Rick wrote:
>>With a zero-noise FFT input data the 'McEachern Method' 
>>performs quite well.  But when my input sinusoid 
>>had an SNR of less than 50 dB I found that the 
>>'McEachern Method' did not perform as well as 
>>the 'Jacobsen Method'.
>
>Hi Kevin and Rick, 
>I was surprised to see that Kevin got much better result with the 2 bins
>interpolation instead than the 3 bins interpolation that I had tested.
>This leaded me to do some tests, and it appeared that the difference was
>not really in the fact to use 2 or 3 bins (apparently it has no effect),
>but in the gaussian window shape factor (sigma): we did not use the same
>values.
>
>This leaded to other tests, and found some things, maybe you could find
>this interesting. I updated the small note, you can find my humble and
>temporary conclusions page 14 and page 15:
>
>http://www.tsdconseil.fr/log/scriptscilab/festim/freqestim-comp3.pdf
>
>(note: I had to change the pdf file name, because otherwise, I kept
>getting the old file from some cache...)
>
>Rick, 
>Indeed, with the small tests I had done, I observe the same thing,
>McEacern method is generally not as good as Jacobsen method (but the
>former has a free parameter, so if you know in advance your SNR...).
>
>Regards,
>
>Julien

Of the myriad two-term estimators, the gaussian performs well
specifically because it eliminates the nulls between sidelobes that
are present in most windows.   Many of the two-term estimators have
large variance when the frequency is near the bin center as one of the
terms approaches zero.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Eric Jacobsen <eric.jacobsen@ieee.org> wrote:

>On Tue, 02 Jun 2015 08:43:59 -0500, "tsd82" <105802@DSPRelated> wrote:

>>Indeed, with the small tests I had done, I observe the same thing,
>>McEacern method is generally not as good as Jacobsen method (but the
>>former has a free parameter, so if you know in advance your SNR...).

Very tangentially, in cases where algorithms perform better when the
SNR is known, it is often possible to take advantage of this
fact without having any knowledge of the actual SNR by doing the
following:

1) Based on your specification or requirements, determine the
lowest SNR at which your system is required to operate; then

2) Use this value as the "actual" SNR in your algorithm

The idea is at your operating point, you in fact are using
the actual SNR value, so the system performs; and if the
actual SNR is better than the operating point, then it is still likely 
to perform at least as well, except for some truly weird and unlikely 
combinations of algorithm and performance specs.

>Of the myriad two-term estimators, the gaussian performs well
>specifically because it eliminates the nulls between sidelobes that
>are present in most windows.   

Makes sense

>Many of the two-term estimators have
>large variance when the frequency is near the bin center as one of the
>terms approaches zero.

Seems this might also apply to three-term estimators...  that is,
if the frequency is near the center of the middle bin out of three 
consecutive bins, the other two terms approach zero.


Steve

On Tue, 2 Jun 2015 20:33:09 +0000 (UTC), spope33@speedymail.org (Steve
Pope) wrote:

>Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
>>On Tue, 02 Jun 2015 08:43:59 -0500, "tsd82" <105802@DSPRelated> wrote:
>
>>>Indeed, with the small tests I had done, I observe the same thing,
>>>McEacern method is generally not as good as Jacobsen method (but the
>>>former has a free parameter, so if you know in advance your SNR...).
>
>Very tangentially, in cases where algorithms perform better when the
>SNR is known, it is often possible to take advantage of this
>fact without having any knowledge of the actual SNR by doing the
>following:
>
>1) Based on your specification or requirements, determine the
>lowest SNR at which your system is required to operate; then
>
>2) Use this value as the "actual" SNR in your algorithm

>The idea is at your operating point, you in fact are using
>the actual SNR value, so the system performs; and if the
>actual SNR is better than the operating point, then it is still likely 
>to perform at least as well, except for some truly weird and unlikely 
>combinations of algorithm and performance specs.

A good example of that is iterative FEC decoders, especially Turbo
Decoders.   Few implementers bother to compute the SNR, and instead
just set it to the lowest SNR.   Makes very little difference in
performance for most codes.

>>Of the myriad two-term estimators, the gaussian performs well
>>specifically because it eliminates the nulls between sidelobes that
>>are present in most windows.   
>
>Makes sense
>
>>Many of the two-term estimators have
>>large variance when the frequency is near the bin center as one of the
>>terms approaches zero.
>
>Seems this might also apply to three-term estimators...  that is,
>if the frequency is near the center of the middle bin out of three 
>consecutive bins, the other two terms approach zero.

Obviously it's algorithm dependent, but most of the three-term
estimators don't wind up with the denominator approaching zero as the
adjacent samples approach the nulls, so the effect is mitigated much
better.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On 6/2/15 5:25 PM, Eric Jacobsen wrote:
> On Tue, 2 Jun 2015 20:33:09 +0000 (UTC), spope33@speedymail.org (Steve
> Pope) wrote:
>
>> Eric Jacobsen<eric.jacobsen@ieee.org>  wrote:
>>
...
>>
>>> Many of the two-term estimators have
>>> large variance when the frequency is near the bin center as one of the
>>> terms approaches zero.
>>
>> Seems this might also apply to three-term estimators...  that is,
>> if the frequency is near the center of the middle bin out of three
>> consecutive bins, the other two terms approach zero.
>
> Obviously it's algorithm dependent, but most of the three-term
> estimators don't wind up with the denominator approaching zero as the
> adjacent samples approach the nulls, so the effect is mitigated much
> better.

seems to me that, with a gaussian window (which implies a gaussian 
function in the frequency domain) that in the log (dB) domain, the 
quadratic three-point solution should be a perfect fit.

for a two-point estimator, i would think the biggest problem would be 
halfway between points.
knowing the window shape is, i think. a necessity


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

>
>seems to me that, with a gaussian window (which implies a gaussian 
>function in the frequency domain) that in the log (dB) domain, the 
>quadratic three-point solution should be a perfect fit.
>
>for a two-point estimator, i would think the biggest problem would be 
>halfway between points.
>knowing the window shape is, i think. a necessity
>
>
>-- 
>
>r b-j                  rbj@audioimagination.com
>
>"Imagination is more important than knowledge."

If you could go out to infinity, but since the tails are truncated it
seems a little inaccuracy creeps in.  Julien put a lot of effort into just
this issue in his latest upgrade to his write-up.  He has both a 2-bin and
a 3-bin formula in his test suite and a discussion of the impact of the
parameter setting.  He has really done a stellar job.  There is a little
explanation a few posts earlier in this thread as well.

I have converted the code (2-bin McEachern) that Kevin McGee posted to fit
within my bins comparison program.  The results were good enough that I
think I did it right, but not good enough to be sure, given the claims of
exactness.  I have opted not to post the results until I am sure.  I have
sent Kevin an email and haven't received a reply yet.

So as of now, I am still of the opinion that window functions don't add
any value for the task of frequency determination.

Here is the link to find Julien's write-up:
www.tsdconseil.fr/log/scriptscilab/festim/index-en.html

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On Tuesday, June 2, 2015 at 8:05:16 PM UTC-4, robert bristow-johnson wrote:
> On 6/2/15 5:25 PM, Eric Jacobsen wrote:
> > On Tue, 2 Jun 2015 20:33:09 +0000 (UTC), spope33@speedymail.org (Steve
> > Pope) wrote:
> >
> >> Eric Jacobsen<eric.jacobsen@ieee.org>  wrote:
> >>
> ...
> >>
> >>> Many of the two-term estimators have
> >>> large variance when the frequency is near the bin center as one of the
> >>> terms approaches zero.
> >>
> >> Seems this might also apply to three-term estimators...  that is,
> >> if the frequency is near the center of the middle bin out of three
> >> consecutive bins, the other two terms approach zero.
> >
> > Obviously it's algorithm dependent, but most of the three-term
> > estimators don't wind up with the denominator approaching zero as the
> > adjacent samples approach the nulls, so the effect is mitigated much
> > better.
> 
> seems to me that, with a gaussian window (which implies a gaussian 
> function in the frequency domain) that in the log (dB) domain, the 
> quadratic three-point solution should be a perfect fit.
> 
> for a two-point estimator, i would think the biggest problem would be 
> halfway between points.
> knowing the window shape is, i think. a necessity
> 
> 
> -- 
> 
> r b-j                  rbj@audioimagination.com
> 
> "Imagination is more important than knowledge."


>>This is an indication that I have probably misprogrammed the gaussian 
>>method: I will try to improve on this by comparing with your code. 

>>Julien (with an 'e' :-))


Julien (with and 'e' :)})

Sorry - didn't mean to rename you.  As for your programming efforts - very good.

As I mentioned in the tutorial (point #5), McEachern's Gaussian window is actually incorrect.  And the code in the tutorial uses it.  It's not too bad if you have large N, though.  But it is definitely wrong, and it caused me a lot of problems when trying to program a correct Gaussian window.

I've spent a lot of time over the years reading and rereading the classic window paper by Harris.  He makes an effort to point out that many people calculate windows improperly.  It didn't take me too long to see that the McEachern window was wrong - his program code actually computes a Gaussian window for a FIR filter, NOT for an FFT.  As noted in Harris, a window for a FIR filter and a window for an FFT have different symmetries.  I also mention this in the tutorial (point #5).

Years ago, the problem I faced was this: the McEachern window was parameterized by the beamwidth variable 'c.'  But the window didn't have the proper symmetry for an FFT.  On the other hand, the equations in Harris were correct, and the window displayed the proper symmetry.  But his Gaussian window was parameterized by 'alpha.'  If I recall correctly, it took me about a month to figure out the proper relationship between the McEachern variable 'c' and the Harris variable 'alpha' (I made a few calculation mistakes along the way).  But eventually, I got it right, and the Gaussian window code I showed in last night's post was the one I settled on (and note - it's only valid for an even N - the code for an odd N Gaussian window is different, and I've figured that out too).  'c' is also used in the McEachern amplitude calculation.

To sum up - windows are sometimes tough to compute. Many people have done them wrong in the past, and will probably continue to do so in the future.   And Gaussian windows have several different versions (parameterized by 'c' or 'alpha' or 'sigma', and they're different depending on odd or even N).  So it's important to use the right one.

Kevin

On Tue, 02 Jun 2015 20:05:13 -0400, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 6/2/15 5:25 PM, Eric Jacobsen wrote:
>> On Tue, 2 Jun 2015 20:33:09 +0000 (UTC), spope33@speedymail.org (Steve
>> Pope) wrote:
>>
>>> Eric Jacobsen<eric.jacobsen@ieee.org>  wrote:
>>>
>...
>>>
>>>> Many of the two-term estimators have
>>>> large variance when the frequency is near the bin center as one of the
>>>> terms approaches zero.
>>>
>>> Seems this might also apply to three-term estimators...  that is,
>>> if the frequency is near the center of the middle bin out of three
>>> consecutive bins, the other two terms approach zero.
>>
>> Obviously it's algorithm dependent, but most of the three-term
>> estimators don't wind up with the denominator approaching zero as the
>> adjacent samples approach the nulls, so the effect is mitigated much
>> better.
>
>seems to me that, with a gaussian window (which implies a gaussian 
>function in the frequency domain) that in the log (dB) domain, the 
>quadratic three-point solution should be a perfect fit.

That's correct, and that's covered in a few places (books, papers,
etc.).   I think the performance isn't all that great under certain
conditions, though.

>for a two-point estimator, i would think the biggest problem would be 
>halfway between points.
>knowing the window shape is, i think. a necessity

For this case knowing the window is critical.   Many of the
derivations are done assuming a rectangular window since it gives the
best starting resolution, i.e., the narrowest main lobe.   This isn't
a bad assumption for the cases where the DFT in the algorithm does not
need a window for other reasons.   If the purpose is only frequency
estimation, then, certainly, no window.   However, if improved
sidelobe suppression is needed for other reasons (e.g., quality
control to assure no spurs, etc.), then a window may need to be
applied and the algorithm would need adjustment.   There are a few
papers that address this.   Candan recently published a paper in this
context including considerations for non-rectangular windows.

>
>-- 
>
>r b-j                  rbj@audioimagination.com
>
>"Imagination is more important than knowledge."
>
>

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On Mon, 01 Jun 2015 07:27:37 -0500, "tsd82" <105802@DSPRelated> wrote:

>Hi all,
>
>I took some time the previous few days to play with different estimators,
>including Cedron's one, and you can find the results of my "playings" in
>the following small note:
>
>http://www.tsdconseil.fr/log/scriptscilab/festim/freqestim-comp.pdf
>

Supplementing this with the interbin analysis, including Candan's
updated estimator, which Julien hadn't included yet and is the most
relevant benchmark.

http://www.ericjacobsen.org/Files/Jacobsen_2015_estimator_comparison.pdf

As far as I can tell there is no advantage to Cedron's estimator.
Candan's analysis is complete and not approximate and results in a
bias-free estimator even in no-noise conditions.   It's also my
estimator with what boils down to a single additional real-valued
multiply.   So it's nearly as simple as mine with very low complexity
and a trivial additional multiply.   That's kinda hard to beat.   This
is why it's pretty much the gold standard for three-coefficient fine
frequency estimators right now.

There's a fair chance my noise calibration is off by 3dB, but that
doesn't affect the basic results or conclusion.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Eric wrote:
>
>Supplementing this with the interbin analysis, including Candan's
>updated estimator, which Julien hadn't included yet and is the most
>relevant benchmark.
>
>http://www.ericjacobsen.org/Files/Jacobsen_2015_estimator_comparison.pdf
>
>As far as I can tell there is no advantage to Cedron's estimator.
>Candan's analysis is complete and not approximate and results in a
>bias-free estimator even in no-noise conditions.   It's also my
>estimator with what boils down to a single additional real-valued
>multiply.   So it's nearly as simple as mine with very low complexity
>and a trivial additional multiply.   That's kinda hard to beat.   This
>is why it's pretty much the gold standard for three-coefficient fine
>frequency estimators right now.
>
>There's a fair chance my noise calibration is off by 3dB, but that
>doesn't affect the basic results or conclusion.
>
>
>Eric Jacobsen
>Anchor Hill Communications
>http://www.anchorhill.com

Hi Eric,

Many thanks for this great report. 

The historical explanations you give are very useful for me to get an
understanding of how the algorithms originated and to be less confused
about the many technics that exist.

Indeed, for complex tones, and in a large range of SNR (low SNR and up to
60 dB for N = 128, and even higher for higher N), your method is as good
as the more complex ones based on 3 DFT bins (Candan or Cedron one's), and
with a very little complexity.

And for above 60 dB (and at least up to 100 dB, for N = 128), the new
Candan (2013) seems to perform quite well too, for a reasonable complexity
increase.

By the way, I was wondering, does anyone knows about applications
requiring to work at these very high SNR (60 - 100 dB) ? I have no idea
for myself. Maybe very precise frequency measurements for atomic-based
clock?

Kind Regards,

Julien
---------------------------------------
Posted through http://www.DSPRelated.com

On Wed, 03 Jun 2015 05:19:57 -0500, "tsd82" <105802@DSPRelated> wrote:

>Eric wrote:
>>
>>Supplementing this with the interbin analysis, including Candan's
>>updated estimator, which Julien hadn't included yet and is the most
>>relevant benchmark.
>>
>>http://www.ericjacobsen.org/Files/Jacobsen_2015_estimator_comparison.pdf
>>
>>As far as I can tell there is no advantage to Cedron's estimator.
>>Candan's analysis is complete and not approximate and results in a
>>bias-free estimator even in no-noise conditions.   It's also my
>>estimator with what boils down to a single additional real-valued
>>multiply.   So it's nearly as simple as mine with very low complexity
>>and a trivial additional multiply.   That's kinda hard to beat.   This
>>is why it's pretty much the gold standard for three-coefficient fine
>>frequency estimators right now.
>>
>>There's a fair chance my noise calibration is off by 3dB, but that
>>doesn't affect the basic results or conclusion.
>>
>>
>>Eric Jacobsen
>>Anchor Hill Communications
>>http://www.anchorhill.com
>
>Hi Eric,
>
>Many thanks for this great report. 
>
>The historical explanations you give are very useful for me to get an
>understanding of how the algorithms originated and to be less confused
>about the many technics that exist.
>
>Indeed, for complex tones, and in a large range of SNR (low SNR and up to
>60 dB for N = 128, and even higher for higher N), your method is as good
>as the more complex ones based on 3 DFT bins (Candan or Cedron one's), and
>with a very little complexity.
>
>And for above 60 dB (and at least up to 100 dB, for N = 128), the new
>Candan (2013) seems to perform quite well too, for a reasonable complexity
>increase.

>By the way, I was wondering, does anyone knows about applications
>requiring to work at these very high SNR (60 - 100 dB) ? I have no idea
>for myself. Maybe very precise frequency measurements for atomic-based
>clock?

I've wondered that as well.   I'd suspect it would need to be some
ultra-accurate calibration or measurement thingie.   Maybe they do
this sort of thing at places like CERN.

BTW, there was an error in Eq. 3 in the paper that I just fixed.
Updated copy has been uploaded. D'oh.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com