8 ms·

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

192 points by luu 3y ago

diydsp 3y ago
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 attenuation, with respective to the input signal magnitude at the stopband frequency, or start of the stopband, is the most relevant term for determining the magnitude of noise in the sampled signal. And that is the upper bound on the performance of the downstream algorithm.
- patrakov 3y ago
  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".
  - diydsp 3y ago
    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!
f5ve 3y ago
If you're thinking "The highest rate I need my signal to be able to replicate is X, so I should set my sampling rate to 2X," then you're wrong and this article gives several reasons why. As far as I can tell, though, it doesn't mention what may be the most important reason (especially to the folks here at hackernews): resampling and processing. This is why professional grade audio processing operates at a sample rate many multiples higher than human hearing. It's not because of the quality difference between, say, 192 and 96 kHz, but rather if you're resampling or iterating a process dozens of times at those rates, eventually artifacts will form and make their way into the range of human hearing (20 kHz).
- gumby 3y ago
  Yeah, a lot of people think “Nyquist” is a synonym for 2 and stop thinking further.
  - Espressosaurus 3y ago
    Heh. Then they don't actually understand what it implies. Which makes sense I suppose.
- rcxdude 3y ago
  Not just eventually: many effects, such as basically any non-linear mapping like a distortion, will create overtones that will immediately alias down if you are not oversampling. You either need to use some DSP tricks or oversample (usually a mix of both) to avoid this happening, which often happens in just one step of an effects chain.
  - markkitti 3y ago
    Even the term "oversampling" implies that sampling beyond Nyquist rate is excessive. I think you would agree that one is not being excessive. It is necessary to sample well beyond accepted "Nyquist rate" in order to reconstruct the signal.
    - 3y ago
anonymous-panda 3y ago
It’s interesting to me how frequently people will talk about sampling performance profilers and not know about Nyquist. Given a CPU runs at many GHz but SW sampling profilers run at ~1 or even maximum 10khz, it’s really hard to write software if you’re targeting processing at MHz rates.
- rcxdude 3y ago
  I'm not sure what you mean here, but I would say that sampling profilers are a good example of Nyquist applied correctly for the most part: your signal (the distribution of where your software is spending its time) is likely to have an extremely low bandwidth (as in, it's basically static), so why try to sample super rapidly? It's much more of a question of whether you get enough samples to represent that distribution accurately, not how quickly you get those samples.
  - anonymous-panda 3y ago
    You’re talking about profiling a normal running program. If you’re profiling a benchmark that’s always executing the hot path, where exactly the hot path contribution lies becomes less clear. This is because you run into aliasing with the samples being collected at unhelpful points. Maybe if you run long enough you start to see a picture but at 1khz you’re going to have to run for a very long time. The other way aliasing comes into effect is that it becomes to see the impact of “individually cheap” but often executed pieces of code (eg a simple bounds check may not show up even if it’s responsible for a 20% slowdown because the probability of your sampler hitting it is small when that bounds check takes nanoseconds to execute vs your ms profiler sample rate. Basically a 1ms sampler can pick out a signal that’s 2ms or longer in periodicity if sampled once (all faster signals will get aliased). To get to 1ghz (once a nanosecond) would require capturing 1 million times more samples and you’re still dealing with aliasing screwing up the picture you’re getting (although maybe with stack sampling you get disambiguation to combat aliasing? Not sure).
    - rcxdude 3y ago
      I don't think what you're talking about is aliasing: it's more to do with the statistics of sampling. Though even then I still don't quite get what you mean: if a bounds check is 20% of your runtime then you're going to see it in your samples pretty quickly. If it's a small enough fraction of your runtime that you don't expect to see it in millions of samples, then why is it relevant to your performance? Now, if you're worried about latency outliers, I can see why sampling may not be a useful tool, but again I don't think the reason for that is really aliasing.
rcxdude 3y ago
I have referred so many people to this paper over the years. It does a great job of dispelling a lot of misunderstandings people have about Nyquist's theorem.
nofu7ur3 3y ago
> ...there is no point to distributing music in 24-bit/192kHz format. Its playback fidelity is slightly inferior to 16/44.1 or 16/48.... from "24/192 Music Downloads ...and why they make no sense" (2012) [1] [1] https://people.xiph.org/~xiphmont/demo/neil-young.html https://people.xiph.org/~xiphmont/demo/neil-young.html
- hamstergene 3y ago
  This could be a useful disclaimer, to say "we are talking about recording and processing and NOT about playback". Audiophiles demand streaming services to provide 192/24 because they see the music being originally mastered at high sample rates, and from that conclude that listening to 48/16 is a loss of "original recorded quality". I can totally envision audiophiles picking up the Wescott's article and using it as "scientific" argument to distribute more Hi-Res music, and some half-technical manager buying that. They won't even read it.
- shin_lao 3y ago
  High sample rate isn't useful for playback, but 24-bit is great for nuance in low intensity sound.
  - KeplerBoy 3y ago
    so for stuff which didn't properly use the dynamic range of the standard codecs? Are human ears even capable of hearing 24 bits of dynamic range?
    - FabHK 3y ago
      Rule of thumb: We know that 2^10 ≈ 10^3, so 2^24 ≈ 10^(3/10*24) = 10^7.2. This 7.2 is about amplitude, but what we hear is power which is quadratic in amplitude, so take a factor of 2, and you're talking 14.4 bel, or 144 decibel for 24 bit (and 2/3 of that, 96 db, for 16 bit). (In reality it's a bit more complicated, but that's a good rough guide, see https://en.wikipedia.org/wiki/Audio_bit_depth#Quantization https://en.wikipedia.org/wiki/Audio_bit_depth#Quantization)
  - 3y ago
salty_biscuits 3y ago
The biggest one I have run into is that the bandwith doesn't need to be contiguous. If you know the the important bits of the signal are contained in certain frequency bands then you can get much lower sampling rates. Basically why things like l1 reconstruction work.
- mwbajor 3y ago
  Bandpass sampling is a regular technique used in the RF world to mix down a signal to its final IF or baseband frequency, digitally. In this case, you are undersampling but using a well defined signal that you have apriori knowledge of where it is before and after sampling. https://en.wikipedia.org/wiki/Undersampling#:~:text=In%20signal%20processing%2C%20undersampling%20or,able%20to%20reconstruct%20the%20signal https://en.wikipedia.org/wiki/Undersampling#:~:text=In%20sig....
greesil 3y ago
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 filter on the codec, like 100 taps, because -that- chip had oodles of CPU to spare as it turned out. Why FIR? It had a super sharp cutoff and of course linear phase. If I'd known about Bessel filters at the time I'd have tried those out. Live and learn and ship it.
- anthomtb 3y ago
  To clarify - you were able to run the FIR filter on the codec chip because the main CPU didn't have enough <somthing - clock rate?> to handle the 48kHz input? Nifty story, just wanted to validate my understanding.
  - greesil 3y ago
    Yep that's it. The main cpu was a Cortex M3 or something like this. It's been awhile so my recollection is a little hazy.
- rightbyte 3y ago
  Did you try a simple iir filter and then decimation?
  - greesil 3y ago
    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.
iamcreasy 3y ago
So, we first need to find the highest motion frequency a sensor might experience in the experiment, and then make sure the sampling rate it at least twice that to avoid aliasing? Meaning, if an IMU sensor is mounted on a very slow moving, such as 2cm/s, RC vehicle then the sampling rate can be very slow. But if the sensor is on a fast moving drone, we need to estimate the highest frequency of the motion and make sure our sampling rate is at least double that?
- KeplerBoy 3y ago
  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.
  - iamcreasy 3y ago
    If we are not trying to capture motor rpm vibration - can't we just ignore it?
    - jononor 3y ago
      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.
      - iamcreasy 3y ago
        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?
jeanl 3y ago
For a mini-surprise, check the prime factors of 44100.
- Dylan16807 3y ago
  It's a multiple of 7? It doesn't have big factors? I don't know what I'm supposed to be surprised about.
  - mppm 3y ago
    44100 = 210^2 = (2 * 3 * 5 * 7)^2
    - winternewt 3y ago
      I'm still confused.
      - DSingularity 3y ago
        Multiples and sampling.
      - jeanl 3y ago
        4 first primes each at a power of 2... I did not expect that when I first looked.
    - deleted 3y ago
      [deleted]
- deleted 3y ago
  [deleted]
_kb 3y ago
For anyone interested in an interactive tool for playing with the concepts noted, here’s something I put together a while back for demonstrating to colleagues: https://www.desmos.com/calculator/pma1jpcuv0 https://www.desmos.com/calculator/pma1jpcuv0.
sramsay 3y ago
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. This (11-year-old) video is the gold standard for addressing this concern: https://www.youtube.com/watch?v=cIQ9IXSUzuM https://www.youtube.com/watch?v=cIQ9IXSUzuM Curiously, no one ever seems to mention the actual problems (like aliasing).
- bgnn 3y ago
  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.

192 points by luu 3y ago

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 attenuation, with respective to the input signal magnitude at the stopband frequency, or start of the stopband, is the most relevant term for determining the magnitude of noise in the sampled signal. And that is the upper bound on the performance of the downstream algorithm.

patrakov 3y ago
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".
- diydsp 3y ago
  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!

f5ve 3y ago

If you're thinking "The highest rate I need my signal to be able to replicate is X, so I should set my sampling rate to 2X," then you're wrong and this article gives several reasons why. As far as I can tell, though, it doesn't mention what may be the most important reason (especially to the folks here at hackernews): resampling and processing. This is why professional grade audio processing operates at a sample rate many multiples higher than human hearing. It's not because of the quality difference between, say, 192 and 96 kHz, but rather if you're resampling or iterating a process dozens of times at those rates, eventually artifacts will form and make their way into the range of human hearing (20 kHz).

gumby 3y ago
Yeah, a lot of people think “Nyquist” is a synonym for 2 and stop thinking further.
- Espressosaurus 3y ago
  Heh. Then they don't actually understand what it implies. Which makes sense I suppose.
rcxdude 3y ago
Not just eventually: many effects, such as basically any non-linear mapping like a distortion, will create overtones that will immediately alias down if you are not oversampling. You either need to use some DSP tricks or oversample (usually a mix of both) to avoid this happening, which often happens in just one step of an effects chain.
- markkitti 3y ago
  Even the term "oversampling" implies that sampling beyond Nyquist rate is excessive. I think you would agree that one is not being excessive. It is necessary to sample well beyond accepted "Nyquist rate" in order to reconstruct the signal.
  - 3y ago

anonymous-panda 3y ago

It’s interesting to me how frequently people will talk about sampling performance profilers and not know about Nyquist. Given a CPU runs at many GHz but SW sampling profilers run at ~1 or even maximum 10khz, it’s really hard to write software if you’re targeting processing at MHz rates.

rcxdude 3y ago
I'm not sure what you mean here, but I would say that sampling profilers are a good example of Nyquist applied correctly for the most part: your signal (the distribution of where your software is spending its time) is likely to have an extremely low bandwidth (as in, it's basically static), so why try to sample super rapidly? It's much more of a question of whether you get enough samples to represent that distribution accurately, not how quickly you get those samples.
- anonymous-panda 3y ago
  You’re talking about profiling a normal running program. If you’re profiling a benchmark that’s always executing the hot path, where exactly the hot path contribution lies becomes less clear. This is because you run into aliasing with the samples being collected at unhelpful points. Maybe if you run long enough you start to see a picture but at 1khz you’re going to have to run for a very long time. The other way aliasing comes into effect is that it becomes to see the impact of “individually cheap” but often executed pieces of code (eg a simple bounds check may not show up even if it’s responsible for a 20% slowdown because the probability of your sampler hitting it is small when that bounds check takes nanoseconds to execute vs your ms profiler sample rate. Basically a 1ms sampler can pick out a signal that’s 2ms or longer in periodicity if sampled once (all faster signals will get aliased). To get to 1ghz (once a nanosecond) would require capturing 1 million times more samples and you’re still dealing with aliasing screwing up the picture you’re getting (although maybe with stack sampling you get disambiguation to combat aliasing? Not sure).
  - rcxdude 3y ago
    I don't think what you're talking about is aliasing: it's more to do with the statistics of sampling. Though even then I still don't quite get what you mean: if a bounds check is 20% of your runtime then you're going to see it in your samples pretty quickly. If it's a small enough fraction of your runtime that you don't expect to see it in millions of samples, then why is it relevant to your performance? Now, if you're worried about latency outliers, I can see why sampling may not be a useful tool, but again I don't think the reason for that is really aliasing.

rcxdude 3y ago

I have referred so many people to this paper over the years. It does a great job of dispelling a lot of misunderstandings people have about Nyquist's theorem.

nofu7ur3 3y ago

> ...there is no point to distributing music in 24-bit/192kHz format. Its playback fidelity is slightly inferior to 16/44.1 or 16/48.... from "24/192 Music Downloads ...and why they make no sense" (2012) [1] [1] https://people.xiph.org/~xiphmont/demo/neil-young.html https://people.xiph.org/~xiphmont/demo/neil-young.html

hamstergene 3y ago
This could be a useful disclaimer, to say "we are talking about recording and processing and NOT about playback". Audiophiles demand streaming services to provide 192/24 because they see the music being originally mastered at high sample rates, and from that conclude that listening to 48/16 is a loss of "original recorded quality". I can totally envision audiophiles picking up the Wescott's article and using it as "scientific" argument to distribute more Hi-Res music, and some half-technical manager buying that. They won't even read it.
shin_lao 3y ago
High sample rate isn't useful for playback, but 24-bit is great for nuance in low intensity sound.
- KeplerBoy 3y ago
  so for stuff which didn't properly use the dynamic range of the standard codecs? Are human ears even capable of hearing 24 bits of dynamic range?
  - FabHK 3y ago
    Rule of thumb: We know that 2^10 ≈ 10^3, so 2^24 ≈ 10^(3/10*24) = 10^7.2. This 7.2 is about amplitude, but what we hear is power which is quadratic in amplitude, so take a factor of 2, and you're talking 14.4 bel, or 144 decibel for 24 bit (and 2/3 of that, 96 db, for 16 bit). (In reality it's a bit more complicated, but that's a good rough guide, see https://en.wikipedia.org/wiki/Audio_bit_depth#Quantization https://en.wikipedia.org/wiki/Audio_bit_depth#Quantization)
- 3y ago

salty_biscuits 3y ago

The biggest one I have run into is that the bandwith doesn't need to be contiguous. If you know the the important bits of the signal are contained in certain frequency bands then you can get much lower sampling rates. Basically why things like l1 reconstruction work.

mwbajor 3y ago
Bandpass sampling is a regular technique used in the RF world to mix down a signal to its final IF or baseband frequency, digitally. In this case, you are undersampling but using a well defined signal that you have apriori knowledge of where it is before and after sampling. https://en.wikipedia.org/wiki/Undersampling#:~:text=In%20signal%20processing%2C%20undersampling%20or,able%20to%20reconstruct%20the%20signal https://en.wikipedia.org/wiki/Undersampling#:~:text=In%20sig....

greesil 3y ago

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 filter on the codec, like 100 taps, because -that- chip had oodles of CPU to spare as it turned out. Why FIR? It had a super sharp cutoff and of course linear phase. If I'd known about Bessel filters at the time I'd have tried those out. Live and learn and ship it.

anthomtb 3y ago
To clarify - you were able to run the FIR filter on the codec chip because the main CPU didn't have enough <somthing - clock rate?> to handle the 48kHz input? Nifty story, just wanted to validate my understanding.
- greesil 3y ago
  Yep that's it. The main cpu was a Cortex M3 or something like this. It's been awhile so my recollection is a little hazy.
rightbyte 3y ago
Did you try a simple iir filter and then decimation?
- greesil 3y ago
  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.

iamcreasy 3y ago

So, we first need to find the highest motion frequency a sensor might experience in the experiment, and then make sure the sampling rate it at least twice that to avoid aliasing? Meaning, if an IMU sensor is mounted on a very slow moving, such as 2cm/s, RC vehicle then the sampling rate can be very slow. But if the sensor is on a fast moving drone, we need to estimate the highest frequency of the motion and make sure our sampling rate is at least double that?

KeplerBoy 3y ago
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.
- iamcreasy 3y ago
  If we are not trying to capture motor rpm vibration - can't we just ignore it?
  - jononor 3y ago
    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.
    - iamcreasy 3y ago
      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?

jeanl 3y ago

For a mini-surprise, check the prime factors of 44100.

Dylan16807 3y ago
It's a multiple of 7? It doesn't have big factors? I don't know what I'm supposed to be surprised about.
- mppm 3y ago
  44100 = 210^2 = (2 * 3 * 5 * 7)^2
  - winternewt 3y ago
    I'm still confused.
    - DSingularity 3y ago
      Multiples and sampling.
    - jeanl 3y ago
      4 first primes each at a power of 2... I did not expect that when I first looked.
  - deleted 3y ago
    [deleted]
deleted 3y ago
[deleted]

_kb 3y ago

For anyone interested in an interactive tool for playing with the concepts noted, here’s something I put together a while back for demonstrating to colleagues: https://www.desmos.com/calculator/pma1jpcuv0 https://www.desmos.com/calculator/pma1jpcuv0.

sramsay 3y ago

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. This (11-year-old) video is the gold standard for addressing this concern: https://www.youtube.com/watch?v=cIQ9IXSUzuM https://www.youtube.com/watch?v=cIQ9IXSUzuM Curiously, no one ever seems to mention the actual problems (like aliasing).

bgnn 3y ago
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.