Fundamental Sampling Theory and Real-time Constraints

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