Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

wescottdesign.com

Post reply on HN
Print view View original

71–79 of 79 posts

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#71

Post by greesil »

rightbyte wrote: post #68
greesil wrote: post #26

I ran into this problem with a codec chip. We had to run the output at 48 khz, and the input and output clock had to be the same. Well we didn't have enough CPU to process the input at 48 khz, we only cared about 8 khz bandwidth for human speech. Boxcar averaging then decimating produced way too much aliasing, so much that the ML classifiers wouldn't work. The solution was putting a honking large FIR anti aliasing fi…

Did you try a simple iir filter and then decimation?

I could have done that and moved the cutoff frequency back to, oh let's say 4khz but then I'm adding attenuation at the higher end of the band and nonlinear group delay. That's maybe fine if that's how we processed the training data, but I don't want us to retrain the classifier every time I change the anti aliasing filter.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#72

Post by bigbillheck »

anonymous-panda wrote: post #70
bigbillheck wrote: post #55

Earlier quoted context omitted.

I wonder if we're talking about different things. It sounds like one of your concerns is being catastrophically unlucky with the sampling rate: > This is because you run into aliasing with the samples being collected at unhelpful points. I interpret this as you saying "we sample at times T, 2T, ..., but there's a hotspot that hits at T+0.001, T+0.003, ..., T+0.999, 2T+0.001, ..., and we never get to visit it". I'll g…

It’s not about being unlucky, it’s the second thing you point out. It’s not the difference between 100khz and 100.001khz. You’re going to roughly alias at multiples of the sampling frequency, so you can’t tell between 2khz, 10khz, and 100khz which means that even if you collect enough signal, your 1Mhz signal with code running at 1ghz is going to potentially look like a 10khz signal leading you to make the wrong conc…

> so you can’t tell between 2khz, 10khz, and 100khz

Only when your sample rate is perfect!

Let's say we have a 1GHz system, one instruction per Hz, a signal at 1MHz and we're measuring at 1kHZ. If we're rock-solid at 1kHz then, as you said, we can't distinguish 1MHz from 2kHz, but if we're off by a little bit, then things change.

Let's say the 1MHz events are at times 50, 1050, 2050, and so on, and the 1kHz sample rate triggers at 0, 1000000, 2000000, and so on. You'll obviously never see that event.

But suppose there's a little bit of noise in the sample rate timing and we're just under 1kHz, so now the samples are 0, 1000001, 2000001, 3000005, etc. Sooner or later we're going to hit that 1MHz event, and we're not going to hit it at the same rates as we would a 2kHz event, a 10kHz event, and so on.

We might not hit it that often, but we'll hit it sooner or later, and we'll also hit a lot of its neighbors.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#73

Post by diydsp »

patrakov wrote: post #62
diydsp wrote: post #2

Many brilliant points. Particularly about Bessel filters instead of Butterworth. And also about lowering Fc and increasing Fs, rather than increasing order. And also about considering time domain as well as frequency domain. The dense interview question I use to assess this area of knowledge: "How do you choose the stopband attenuation of a filter?" You can assess a lot from the interviewee's response. Stopband atten…

My response would be: "to validate the chosen stopband attenuation, compare the unwanted signal or interference that passes through the filter with the noise that you already have or with other factors that would make this unwanted signal or interference unnoticeable".

That's a good way of looking at it. The "unnoticeable" part is where more can be teased out:

That is, to expect a specification for the desired S/N (signal-to-noise) ratio and bandwidth, and/or bit rate at which the downstream algorithm is expected to work. This doesn't have to be a perfect estimate/evaluation/measurement, but it helps to get the ballpark amount of computation power, delay, etc. needed to actually make the system work. All too often I see people react to a noisy signal, by "putting a filter on it," without knowing how much attenuation/gain/phase shift, etc. are actually needed to make the system work acceptably.

E.g. You don't want to spend too long designing the perfect filter... And you want to know if there's any hope at all cleaning up the signal to make use of it!

Good luck with your filtering projects!

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#75

Post by anonymous-panda »

bigbillheck wrote: post #72
anonymous-panda wrote: post #70

Earlier quoted context omitted.

It’s not about being unlucky, it’s the second thing you point out. It’s not the difference between 100khz and 100.001khz. You’re going to roughly alias at multiples of the sampling frequency, so you can’t tell between 2khz, 10khz, and 100khz which means that even if you collect enough signal, your 1Mhz signal with code running at 1ghz is going to potentially look like a 10khz signal leading you to make the wrong conc…

> so you can’t tell between 2khz, 10khz, and 100khz Only when your sample rate is perfect! Let's say we have a 1GHz system, one instruction per Hz, a signal at 1MHz and we're measuring at 1kHZ. If we're rock-solid at 1kHz then, as you said, we can't distinguish 1MHz from 2kHz, but if we're off by a little bit, then things change. Let's say the 1MHz events are at times 50, 1050, 2050, and so on, and the 1kHz sample ra…

You’re not describing anything different from how Nyquist pops up in analog signals either - sampling and signal will always have jitter and noise. I would recommend reading the linked pdf if you haven’t done so as it gives a number of examples of how Nyquist can screw up your intuition.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#76

Post by bigbillheck »

anonymous-panda wrote: post #75
bigbillheck wrote: post #72

Earlier quoted context omitted.

> so you can’t tell between 2khz, 10khz, and 100khz Only when your sample rate is perfect! Let's say we have a 1GHz system, one instruction per Hz, a signal at 1MHz and we're measuring at 1kHZ. If we're rock-solid at 1kHz then, as you said, we can't distinguish 1MHz from 2kHz, but if we're off by a little bit, then things change. Let's say the 1MHz events are at times 50, 1050, 2050, and so on, and the 1kHz sample ra…

You’re not describing anything different from how Nyquist pops up in analog signals either - sampling and signal will always have jitter and noise. I would recommend reading the linked pdf if you haven’t done so as it gives a number of examples of how Nyquist can screw up your intuition.

I read it when it was first posted, and skimmed it again just now to be sure, and my conclusion is unchanged: Nyquist has nothing useful to say about sampling profilers. I think the author would agree with me. See, for example, the discussion of EKG signals, or this bit from the intro:

> The difficulty with the Nyquist-Shannon sampling theorem is that it is based on the notion that the signal to be sampled must be perfectly band limited. This property of the theorem is unfortunate because no real world signal is truly and perfectly band limited.

whose relevance I'll get to below.

(I'm assuming that by "sampling profiler" you mean the usual practice of recording on a cadence the call stack / program counter / etc of some code; if this is not what you meant please clarify)

If you approach sampling profiling from a signals viewpoint, what's the signal that you're sampling? I see it as a collection of pulse waves of varying (and irregular!) duty cycles, each pulse wave corresponding to a yes/no answer to "is the program inside this function / executing this instruction / etc". At any given sample we collect our data and that tells us which waves are high; all others will be low.

Nyquist, as the above quote points out, only applies to perfectly band limited signals. Not only are pulse waves not perfectly band limited, they're actually extremely not band limited, with energy at harmonics going all the way up. Right away that should tell you that Nyquist is the wrong way to be thinking about things!

And furthermore, Nyquist tells you what you need if you want to reconstruct the original signal, but why do you want to do that in the first place? Do you actually care about the phase of the wave and the timings of the pulses, or do you just care about how often the wave is high? (i.e. how often any bit of code is executed). I don't think I've ever cared about the phase and timings when profiling, but I do care very much about how often the wave is high.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#77

Post by jononor »

iamcreasy wrote: post #67
KeplerBoy wrote: post #30

Earlier quoted context omitted.

Yes, pretty much, but it depends. Your 2 cm/s RC vehicle might still experience high-frequency vibrations (in the range of the motor rpm) and you might want to sample that.

If we are not trying to capture motor rpm vibration - can't we just ignore it?

Whether it is signal of interest or not, if above the sampling rate it will be aliased down into lower frequencies. So all energy above the sampling rate should be removed to avoid this disturbance.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#78

Post by bgnn »

sramsay wrote: post #56

This is the most lucid explanation of aliasing I think I've ever read. I mostly deal with this stuff in the realm of audio where the matter of analog vs digital rages regularly. The reason one hears "Nyquist says" so often from people defending digital audio is that the pro-analog people are imagining stair-stepped signals in which the information that is "lost" results in a noticeable degradation in sound quality. T…

That depends on the profession I think. If you are designing A/D or D/A converters, you know sampling and all the artefacts by heart. Nyquist criterion is extremely important, but it is simplistic. You need to consider a lot of other stuff like out-of-band noise and harmonics, reconstruction filters etc etc.

We have periodic steady state analysis to simulate sampled systems and harmonic transfer functions by the way. It is extremely useful especially to stimulate noise aliasing.

Re: Sampling: What Nyquist didn't say, and what to do about it (2018) [pdf]

#79

Post by iamcreasy »

jononor wrote: post #77
iamcreasy wrote: post #67

Earlier quoted context omitted.

If we are not trying to capture motor rpm vibration - can't we just ignore it?

Whether it is signal of interest or not, if above the sampling rate it will be aliased down into lower frequencies. So all energy above the sampling rate should be removed to avoid this disturbance.

So low pass filter is always mandatory? For example, in this RC car case - lets say we are sampling at 1Hz and the signal appears to be clean. But we still have to run a low pass filter of ensure the motor vibrations are removed?
Post reply on HN