Forums

Fundamental Sampling Theory and Real-time Constraints

Started by WaveRider October 28, 2012
Hi everyone,

I'm new to the arena of DSP and have arrived at a bit of a sampling-based
conundrum. I'm wondering if anyone here can help me out with possible
solutions, or can simply set my understanding straight.

I have an application where my signal of interest has a bandwidth of 500Hz.
At Nyquist, I'd be sampling at 1 kHz. Of course, I could oversample by this
by some factor and filter it down in digital, but at the end of the day I
have a bandwidth of 500 Hz. 

I have a constraint on my system: I must produce a result from my DSP
within 300 ms of a change to the input. At worst case, then, I assume that
it must be within 300ms of getting a new sample. However, if I sample and
subsequently clock the DSP system at 1 kHz, my clock period is 1 ms. If I
were to then, say, collect 1024 samples for an algorithm I've already taken
over a second! Now, I could pipeline my samples through my DSP path.
However, I still pay the price in latency. There will still be a delay from
the change in signal to the final output that would be unacceptable.

So I suppose my question is, if I were to massively oversample my signal,
would I be able to avoid this latency cost or am I ultimately bounded by
the bandwidth of the signal of interest? ie. Will my oversampled processing
be "useless"? Could I sample at nyquist and run the actual processing at a
faster rate?

One thing to consider is that part of my DSP path is the discrete wavelet
transform, which itself deals with rate conversion. Do my samples have to
be at nyquist to take advantage of the wavelet transform? It would seem
so.

I'd appreciate any insight into this. Thanks!

>Hi everyone, > >I'm new to the arena of DSP and have arrived at a bit of a sampling-based >conundrum. I'm wondering if anyone here can help me out with possible >solutions, or can simply set my understanding straight. > >I have an application where my signal of interest has a bandwidth of
500Hz.
>At Nyquist, I'd be sampling at 1 kHz. Of course, I could oversample by
this
>by some factor and filter it down in digital, but at the end of the day I >have a bandwidth of 500 Hz. > >I have a constraint on my system: I must produce a result from my DSP >within 300 ms of a change to the input. At worst case, then, I assume
that
>it must be within 300ms of getting a new sample. However, if I sample and >subsequently clock the DSP system at 1 kHz, my clock period is 1 ms. If I >were to then, say, collect 1024 samples for an algorithm I've already
taken
>over a second! Now, I could pipeline my samples through my DSP path. >However, I still pay the price in latency. There will still be a delay
from
>the change in signal to the final output that would be unacceptable. > >So I suppose my question is, if I were to massively oversample my signal, >would I be able to avoid this latency cost or am I ultimately bounded by >the bandwidth of the signal of interest? ie. Will my oversampled
processing
>be "useless"? Could I sample at nyquist and run the actual processing at
a
>faster rate? > >One thing to consider is that part of my DSP path is the discrete wavelet >transform, which itself deals with rate conversion. Do my samples have to >be at nyquist to take advantage of the wavelet transform? It would seem >so. > >I'd appreciate any insight into this. Thanks!
You have conflated two distinctly different things - sampling rate and processing period. In the great majority of cases, if you have a latency problem it is due to your algorithms, and not your sampling rate. Most signal processing algorithms work over an interval, rather than a specific number of samples. If you up the sampling rate, you increase the computation, but you still need to work over the same period. If you have a latency problem you need to look at algorithms which incur less delay, and at implementation which incur the minimum buffering. Steve
On Sun, 28 Oct 2012 10:59:02 -0500, WaveRider wrote:

> Hi everyone, > > I'm new to the arena of DSP and have arrived at a bit of a > sampling-based conundrum. I'm wondering if anyone here can help me out > with possible solutions, or can simply set my understanding straight. > > I have an application where my signal of interest has a bandwidth of > 500Hz. > At Nyquist, I'd be sampling at 1 kHz. Of course, I could oversample by > this by some factor and filter it down in digital, but at the end of the > day I have a bandwidth of 500 Hz. > > I have a constraint on my system: I must produce a result from my DSP > within 300 ms of a change to the input. At worst case, then, I assume > that it must be within 300ms of getting a new sample. However, if I > sample and subsequently clock the DSP system at 1 kHz, my clock period > is 1 ms. If I were to then, say, collect 1024 samples for an algorithm > I've already taken over a second! Now, I could pipeline my samples > through my DSP path. However, I still pay the price in latency. There > will still be a delay from the change in signal to the final output that > would be unacceptable. > > So I suppose my question is, if I were to massively oversample my > signal, would I be able to avoid this latency cost or am I ultimately > bounded by the bandwidth of the signal of interest? ie. Will my > oversampled processing be "useless"? Could I sample at nyquist and run > the actual processing at a faster rate? > > One thing to consider is that part of my DSP path is the discrete > wavelet transform, which itself deals with rate conversion. Do my > samples have to be at nyquist to take advantage of the wavelet > transform? It would seem so. > > I'd appreciate any insight into this. Thanks!
First, as SteveU pointed out, you're conflating sampling rate and bandwidth. They _are_ related, they _are not_ the same thing. Second, you're making a common error about Nyquist rates, which is going to lead you to severe aliasing if you don't change your ways: http://www.wescottdesign.com/articles/Sampling/sampling.pdf Third, a bandwidth of 500Hz suggests that all the interesting stuff can be settled and done with in 2ms on a good day. So what are you doing that's going to take 300ms? Forth, I would expect that your algorithm is going to take the sum of whatever real-world time it was going to take anyway, plus one or two sample times. If you need 1000 samples to do something meaningful at a sampling rate of 1kHz, that's because you need one second's worth of data -- not because 1000 samples taken at a sampling rate of 1MHz would be sufficient. I deduce that your problem is of detection and estimation. Perhaps if you told us more about your _actual issue_ we could help you. I can already tell you what it's going to boil down to: either your signal is going to give you worthwhile information within 300ms of whatever event you're trying to detect, or it won't. In the first case you have a chance of doing something useful. In the second case, you're out of luck. Since you're not letting us know what you're _actually_ trying to do, there's not much help that I (or, I suspect) the rest of us can give you, unless you give more info. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
>On Sun, 28 Oct 2012 10:59:02 -0500, WaveRider wrote: > >> Hi everyone, >> >> I'm new to the arena of DSP and have arrived at a bit of a >> sampling-based conundrum. I'm wondering if anyone here can help me out >> with possible solutions, or can simply set my understanding straight. >> >> I have an application where my signal of interest has a bandwidth of >> 500Hz. >> At Nyquist, I'd be sampling at 1 kHz. Of course, I could oversample by >> this by some factor and filter it down in digital, but at the end of
the
>> day I have a bandwidth of 500 Hz. >> >> I have a constraint on my system: I must produce a result from my DSP >> within 300 ms of a change to the input. At worst case, then, I assume >> that it must be within 300ms of getting a new sample. However, if I >> sample and subsequently clock the DSP system at 1 kHz, my clock period >> is 1 ms. If I were to then, say, collect 1024 samples for an algorithm >> I've already taken over a second! Now, I could pipeline my samples >> through my DSP path. However, I still pay the price in latency. There >> will still be a delay from the change in signal to the final output
that
>> would be unacceptable. >> >> So I suppose my question is, if I were to massively oversample my >> signal, would I be able to avoid this latency cost or am I ultimately >> bounded by the bandwidth of the signal of interest? ie. Will my >> oversampled processing be "useless"? Could I sample at nyquist and run >> the actual processing at a faster rate? >> >> One thing to consider is that part of my DSP path is the discrete >> wavelet transform, which itself deals with rate conversion. Do my >> samples have to be at nyquist to take advantage of the wavelet >> transform? It would seem so. >> >> I'd appreciate any insight into this. Thanks! > >First, as SteveU pointed out, you're conflating sampling rate and >bandwidth. They _are_ related, they _are not_ the same thing. > >Second, you're making a common error about Nyquist rates, which is going >to lead you to severe aliasing if you don't change your ways: >http://www.wescottdesign.com/articles/Sampling/sampling.pdf > >Third, a bandwidth of 500Hz suggests that all the interesting stuff can >be settled and done with in 2ms on a good day. So what are you doing >that's going to take 300ms? > >Forth, I would expect that your algorithm is going to take the sum of >whatever real-world time it was going to take anyway, plus one or two >sample times. If you need 1000 samples to do something meaningful at a >sampling rate of 1kHz, that's because you need one second's worth of data
>-- not because 1000 samples taken at a sampling rate of 1MHz would be >sufficient. > >I deduce that your problem is of detection and estimation. Perhaps if >you told us more about your _actual issue_ we could help you. I can >already tell you what it's going to boil down to: either your signal is >going to give you worthwhile information within 300ms of whatever event >you're trying to detect, or it won't. In the first case you have a >chance of doing something useful. In the second case, you're out of
luck.
> >Since you're not letting us know what you're _actually_ trying to do, >there's not much help that I (or, I suspect) the rest of us can give you,
>unless you give more info. > >-- >Tim Wescott >Control system and signal processing consulting >www.wescottdesign.com >
Hi Tim, I'm trying to do some simple myoelectric-based control. To restore the spectral content of the signal that has been attenuated by human skin, I'd like to implement a whitening filter based on Burg AR estimation. To converge to a better estimate of the AR process affecting my signal, this typically needs more samples to work on than less. This module will then update a pre-whitening FIR's coefficients with its estimates. If I do it in a periodic "burst" fashion I suspect I may be able to get around this timing problem of 1 second, especially since I don't expect the estimate to vary greatly. On the other hand, I'll also be trying to detect features using the Discrete Wavelet Transform and 256-pt FFT followed by several estimator modules that work on windows of samples. I'm doing this all in hardware (Verilog) and so I can leverage true parallelism. So I get that my sampling rate can be much, much lower than my processing rate. However, that means anything working on the samples themselves will do no meaningful work until the next sample arrives, right? In that case I'll need to come up with an enabling scheme I suppose so that the various elements in the chain power-down once they've done their number crunching until the next valid sample arrives. The wavelet transform somewhat troubles me here, however. If I oversample this 500 Hz bandwidth signal by some factor, and then filter it down in digital, my initial detail coefficient levels will be junk, right? Unless the low-pass/high-pass filters for the first iteration aren't half-band but instead are designed to segment my real signal band within the much larger oversampled band in half. Am I getting this right? This is probably my most important question.
WaveRider <60208@dsprelated> wrote:

(snip)

>>> I have an application where my signal of interest has a bandwidth of >>> 500Hz. >>> At Nyquist, I'd be sampling at 1 kHz. Of course, I could oversample by >>> this by some factor and filter it down in digital, but at the end of >>> the day I have a bandwidth of 500 Hz.
(snip)
>>First, as SteveU pointed out, you're conflating sampling rate and >>bandwidth. They _are_ related, they _are not_ the same thing.
>>Second, you're making a common error about Nyquist rates, which is going >>to lead you to severe aliasing if you don't change your ways: >>http://www.wescottdesign.com/articles/Sampling/sampling.pdf
(snip)
> I'm trying to do some simple myoelectric-based control.
> To restore the spectral content of the signal that has been attenuated by > human skin, I'd like to implement a whitening filter based on Burg AR > estimation. To converge to a better estimate of the AR process affecting my > signal, this typically needs more samples to work on than less. This module > will then update a pre-whitening FIR's coefficients with its estimates. If > I do it in a periodic "burst" fashion I suspect I may be able to get around > this timing problem of 1 second, especially since I don't expect the > estimate to vary greatly.
Your latency has to be at least as long as the length of the FIR, but I don't see why it should be much longer than that.
> On the other hand, I'll also be trying to detect features using the > Discrete Wavelet Transform and 256-pt FFT followed by several estimator > modules that work on windows of samples. I'm doing this all in hardware > (Verilog) and so I can leverage true parallelism.
Well, that is a little more interesting as far as delay. Do you want the DWT and FFT of the last 256 samples at every sample point?
> So I get that my sampling rate can be much, much lower than my processing > rate. However, that means anything working on the samples themselves will > do no meaningful work until the next sample arrives, right? In that case > I'll need to come up with an enabling scheme I suppose so that the various > elements in the chain power-down once they've done their number crunching > until the next valid sample arrives.
Traditional CMOS has low quiescent current, with current proportional to the number of transistors switching (or average rate over some time period). Newer CMOS (smaller feature size and thinner gate oxide) has a significant tunneling (quiescent) current. Is the application especially power sensitive? (Battery powered.) Anyway, you should be able to run a systolic array and get a new result every cycles. At lower frequencies you can reuse (time multiplex) the logic.
> The wavelet transform somewhat troubles me here, however. If I oversample > this 500 Hz bandwidth signal by some factor, and then filter it down in > digital, my initial detail coefficient levels will be junk, right? Unless > the low-pass/high-pass filters for the first iteration aren't half-band but > instead are designed to segment my real signal band within the much larger > oversampled band in half. Am I getting this right? This is probably my most > important question.
There is an initial transient in all filters. You do have to wait for that to die out. -- glen
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
> [...] > Your latency has to be at least as long as the length of the FIR,
Did you mean "half the length of the FIR?" -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Randy Yates <yates@digitalsignallabs.com> wrote:
> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: >> [...] >> Your latency has to be at least as long as the length of the FIR,
> Did you mean "half the length of the FIR?"
Not the way I count them, how do you count them? -- glen
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> Randy Yates <yates@digitalsignallabs.com> wrote: >> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: >>> [...] >>> Your latency has to be at least as long as the length of the FIR, > >> Did you mean "half the length of the FIR?" > > Not the way I count them, how do you count them?
You can do things sample-by-sample in a circular buffer, no? Let's say you have an FIR with 15 coefficients and a 16-sample circular buffer: #include <stdint.h> #define N 15 #define BUFFERSIZE 16 int16_t coefficients[N] = {...}; uint16_t nextInp; int16_t buffer[BUFFERSIZE]; /* bufferSize is assumed to be a power of two */ int16_t Filter(int16_t* inp, nInp) { uint16_t n; uint32_t sum; sum = 0; for (n = 0; n < N; n++) { sum += *(inp + ((nInp - n) & (bufferSize - 1))) * *(coefficients + n) >> something; } return sum >> somethingElse; } int main(int argc, char* argv[]) { nextInp = 0; while; } void interrupt NewSample(void) { buffer[nextIn] = ADCRead; doSomethingWithThis = Filter(buffer, nextInp); nextInp++; nextInp &= (BUFFERSIZE - 1); } In this way you have a 1-sample delay to get the ADC value in and an N/2 sample group delay. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Randy Yates <yates@digitalsignallabs.com> wrote:
> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: >> Randy Yates <yates@digitalsignallabs.com> wrote: >>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>>>> Your latency has to be at least as long as the length of the FIR,
>>> Did you mean "half the length of the FIR?"
>> Not the way I count them, how do you count them?
> You can do things sample-by-sample in a circular buffer, no? Let's say > you have an FIR with 15 coefficients and a 16-sample circular buffer:
(snip)
> In this way you have a 1-sample delay to get the ADC value in and an N/2 > sample group delay.
OK, I think I agree. I like to design one directional systolic arrays, such that the output depends on the previous N samples. If you aren't clocking so fast, though, you should be able to do other ways of multiplying and adding. I think a bidirectional systolic array will do what you say. Still, I would put one more register on it, so N/2+1, but yes. -- glen
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> Randy Yates <yates@digitalsignallabs.com> wrote: >> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: >>> Randy Yates <yates@digitalsignallabs.com> wrote: >>>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > >>>>> Your latency has to be at least as long as the length of the FIR, > >>>> Did you mean "half the length of the FIR?" > >>> Not the way I count them, how do you count them? > >> You can do things sample-by-sample in a circular buffer, no? Let's say >> you have an FIR with 15 coefficients and a 16-sample circular buffer: > > (snip) >> In this way you have a 1-sample delay to get the ADC value in and an N/2 >> sample group delay. > > OK, I think I agree. > > I like to design one directional systolic arrays, such that the output > depends on the previous N samples.
Huh? The method I described does depend on the previous N - 1 samples plus the current sample.
> If you aren't clocking so fast, though, you should be able to do other > ways of multiplying and adding. > > I think a bidirectional systolic array will do what you say.
I've always heard the term "systolic array" but never understood what it meant.
> Still, I would put one more register on it, so N/2+1, but yes.
Good - glad we agree. I was beginning to think that you were referring to the startup transient, which is length N - 1, but that would be present no matter how you do things. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com