🚀 go-pugleaf

If you have available the exact x values where the samples are taken,
and your signal is band-limited, you can reconstruct exactly the
continuous-time signal.  Let x[n] be the space coordinate of the nth
sample; let y[n] be the measured value of the signal at that time.
First, consider a function that is zero for all x except at the
x[n] values, and has a Dirac delta function of height y[n] at
x = x[n].  Pass this signal through an ideal low-pass filter corresponding
to the band limit, and you have the continuous-time signal.  This
reconstruction works if the highest frequency in the data, f, is
less than 1/2T, where T is the maximum spacing between samples.
For this to work right at the boundary f = 1/2T you must have no
noise.  I think you could tolerate noise if you oversampled by a
good deal, so the LPF would take it out.

You can then resample the continuous-time signal at your desired
rate.

I recommend that you simulate this procedure before actually relying
on it.





--
Joe Buck
jbuck@galileo.berkeley.edu	 {uunet,ucbvax}!galileo.berkeley.edu!jbuck	

In <11145@pasteur.Berkeley.EDU> jbuck@galileo.berkeley.edu (Joe Buck) writes:
>If you have available the exact x values where the samples are taken,
>and your signal is band-limited, you can reconstruct exactly the
>continuous-time signal.  Let x[n] be the space coordinate of the nth

Uhm, no, I don't think so...  We proved in class that the sampling
theorem holds when the pulse spacing is irregular *but periodic*.
I am working with aperiodic sample spacing in which the (average) sampling
frequency is not constant.  A simple counterexample serves to show
that one cannot recover the underlying signal without compensating
for sampling frequency changes: DC.

Update:  the name for the class of problems to which mine belongs
seems to be "Multirate Filtering".  I've found a book on the subject
and will be wrapping my head around it.

>You can then resample the continuous-time signal at your desired rate.

Part 2 of my problem is to compute the samples directly, rather than
go through an intermediate.  Particularly not an analog intermediate.
I suppose that may be obvious, but the quoted line makes me fear
I failed to make myself clear.

I also misspelled "spatial".  Sigh.


-- 
Steve Nuchia	      South Coast Computing Services      (713) 964-2462
	"Innocence is a splendid thing, only it has the misfortune
	 not to keep very well and to be easily misled."
	    --- Immanuel Kant,  Groundwork of the Metaphysic of Morals

In article <1991Feb16.160801.7117@nuchat.sccsi.com> steve@nuchat.sccsi.com (Steve Nuchia) writes:
>In <11145@pasteur.Berkeley.EDU> jbuck@galileo.berkeley.edu (Joe Buck) writes:
>>If you have available the exact x values where the samples are taken,
...stuff deleted
>>You can then resample the continuous-time signal at your desired rate.
>
>Part 2 of my problem is to compute the samples directly, rather than
>go through an intermediate.  Particularly not an analog intermediate.

Just for clarity I would like to point out that resampling does not require 
an analog intermediate but simply resampling of the resulting digital 
output...

BTW, can anyone recall the discussion on applying similar interpolation 
to a sampled EKG some time ago? I believe someone wanted to reconstruct a
complete EKG waveform from sampled data, and was actually testing these 
digital techniques and reporting results here?  Perhaps I am incorrect but
I beleive many of these ideas were tossed about then ...

  
-----------------------------------------------------------------------------
john f andrews                SYSOP           The Biomedical Engineering BBS
    24 hrs                300/1200/2400               (201) 596-5679
-----------------------------------------------------------------------------
INTERNET jfa0522@hertz.njit.edu    LabRat@faraday.njit.edu    CIS 73710,2600
-----------------------------------------------------------------------------

I once used the method you suggest for filtering a non-uniformly sampled
signal (compensating the gain by also filtering the sampling function).
It works pretty well, but not perfectly.  If the sample rate changes
instantaneously and dramatically (like 10x), then the distortion is clearly
visible.  However, for "reasonable" non-uniformities the distortion is not
visibly perceptible, and that was good enough for my needs.

You do need to make sure that the filter's impulse response width is at
least several times the the maximum sampling interval.

Unfortunately, I don't have the math expertise to rigorously analyze this
technique -- I got by on intuition and simulation.  If you do find a
thorough analysis, please post it.

- David Clark
  Hewlett-Packard Co.
  Santa Clara, CA

 In a previous article, steve@nuchat.sccsi.com (Steve Nuchia) writes:
>2) I'm trying to analyse the following situation:
>
>	A package of measureing instruments (we can assume the
>	singular without loss of generality) traverses some
>	physical environment at an unregulated speed, with
>	its position indirectly measured.
>
>	The instruments are sampled at intervals.  Some instruments
>	are designed for fixed-frequency sampling, others are sampled
>	on a temporal basis for historical reasons, and still others
>	are sampled on a very roughly spacial basis (first opportunity
>	following floor(pos/interval) changes, usually).
>
>	The underlying phenomena are assumed to be spacially band-limited.
>
>	Output samples of an estimate of the underlying phenomena are
>	required at regular spacial intervals, in real time (but a
>	constant lag is OK -- phase linear filters and all that)
>
>	I want to understand the theory well enough to make a sound
>	recomendation on the design of digital filters (to be implemented
>	on a general purpose CPU in real time) to compute the estimate samples
>	from the available sample data.
>
>Anyway, I'm thinking of proceeding like this:  Normalize all cases
>to depth-referenced samples on a fine (high spacial frequency) comb.
>The synthetic sampling spacial frequency would be selected based on
>the output spacial frequency -- say 2x? 1x? 4x?

First off, I assume that you KNOW the time at which samples were taken with
a 'large' (relative to the overall system) degree of accuracy.  Your problem
is that you just can't control WHEN the samples are taken.  The data you take
(in terms of the measured position) is also of sufficient accuracy that you
don't have to worry about positional uncertainty.  For the sake of argument
you 'know' with infinite precision both the time at which a sample was taken
and the position of the sample.

Next, I assume you wish to synthesize some time/position related output data
of what happened between samples.  This may mean that you wish to
guess-timate the position at any time between two samples, or you may wish
to calculate velocity at some point in time (or space) of the thing begin
sampled.  Assuming that you can guess-timate the position at any desired
time, I assume you can extrapolate any other desired information such
as velocity or acceleration.  I also assume that if some of your measurements
are taken as velocity, others are acceleration measurements, and still others
are displacement measurements, you can convert (with enough math) to
a consistent base for the problem.  From here on, I will assume you can
convert to or have taken all measurements in terms of displacment.

Finally, we shall assume that you have enough time between measurements and
enough CPU horsepower to do a reasonable amount of calculations and are
therefore able to obtain the desired answers quickly enough to be useful.
I'm not sure how many measurements per second you are taking, but I assume
it is not more than about 500 or 1000 samples per second, probably much
less than this.  For the sake of argument, I'm going to assume that you
have something on the order of a 80386 (or larger) available to do your
desired math, and all the I/O hardware and instrumentation required to take
the samples, timestamp them, feed them to the CPU, and then distribute the
results in whatever form you need.  I also assume that you don't need
answers with 16 digits of precision and that your data doesn't span several
orders of magnitude in range.

If any of my assumptions or problem re-statements above are wrong, please
let me know.  I'm having a bit of trouble trying to visualize just
exactly what you are trying to accomplish.  I think I understand, but
I am not certain.

I would say that it is quite possible for you to get good results with
your synthetic sampling interval approach.  It strikes me that the spacing
between points that you wish to synthesize should be as small as the
shortest time between sample points.  Since this approach will lead to
most of your synthetic samples (the ones you create to just 'fill' sample
points you don't know between the ones you do know) being zero, you will
be able to write a smart/fast enough program to ignore multiplication by
zero and save lots of CPU time.  One problem with this is that if your
samples are more-or-less evenly spaced but are not exact multiples of each
other, you could end up generating lots of synthetic samples that will later
need to be discarded.  An example of this is if you have samples that are
sometimes .9 seconds apart, sometimes 1 second apart, and sometimes 1.05
samples apart, you would either need to wave your hands and just assume that
all are 1 second apart (generating the least synthetic samples but losing the
most amount of information), assume that all samples should occur at
.1 second intervals (thus saving more information on about your data but
forcing you to make the decision as to whether 1.05 second samples get
binned up to 1.1 seconds or down to 1.0 seconds) or assume that all samples
should occur at .05 second intervals (thus extracting the most information
from your data at the expense of more CPU time required to crunch numbers).
Your synthetic sample interval period will also be dictated by your output
data requirement.  In the above example, what should you use if you need to
know the position estimate at every .025 seconds?  I guess the answer is,
"It depends."  (It depends on your other system requirements, which I don't
really know).  In this case, you can probably get by with
just using the standard 'sync' function method of reconstructing data
between known sample points.  This method is outlined in the book,
"Digital Signal Processing" by Oppenheim & Schafer on page 29.  This is
esentially creating a low pass filter and passing your data thru it by
convolution.  This can be done in the time domain and is fairly
straightforward.  You need to pick a finite number of filter points that
will give you good results.  Without knowing the nature of your data, I
haven't a clue as to how many that is.  I would suggest if you do
pick this approach that you use an appropriate windowing function to
smooth the sync filter function before you pass your data thru it.  I have
found that with a finite number of points in the sync function, the output
results look MUCH better when the sync function has been windowed.

One other approach you may wish to think about instead of using filtering
is that of curve fitting.  It can be done quite quickly and is pretty good
and interpolation if your data can be made to fit onto a smoothly varying
curve.  Curve fitting is somewhat of an art, and there are many tricks to
getting good results.  I know one or two just by having observed a few
masters at the art, but it generally boils down to knowing something about
the nature of your data.  If (for example) you can expect all of your data
to fit a logrithmic curve, there are tricks to play that will give you
optimal results for that type of curve.  This works quite well with things
like temperature sensors that exhibit general responses that fit on a
log curve but need to be corrected based on a few know sample points taken
at calibration time.  The tricks you pick all depend on your expectation of
what your data will look like.  Anyway, curve fitting to interpolate between
data points may be what you need, but I can't say for sure without more info.

>One could dynamically adjust the implicit scale of the
>FIR function, withing limits, to at least partially compensate for
>changes in instrument velocity.

You lost me on this one.  Are you saying that you are trying to take
measurements that aren't time-invariant?  This could be big problems.
It seems to me that if your instrument passes point A at one velocity
and you take a measurement, you better have the ability to pass point A
at a different velocity later and measure the same position.  If you
don't then you will need to record the velocity (or temperature, or direction,
or whatever affects your position measuring) and filter that out before
you ever begin.


>Am I even asking the right questions?  Should I be thinking IIR?
>Should I just hook the plotter up to a canned demo data stream?  [:-)]

You should definately test drive any approach you come up with against
a known (and repeatable!) data set so you can test different approaches.
Having some way to play back the same data into different systems and
comparing it with known-good results always gives you ideas of how you
can make your system better.

I'm sure I have missed a few (or more) points you think I should know.
Please post to comp.dsp or e-mail me directly and I'll give you my input.

>-- 
>Steve Nuchia	      South Coast Computing Services      (713) 964-2462

   -dave

-- 
Dave McMahan                            mcmahan@netcom.com
					{apple,amdahl,claris}!netcom!mcmahan

The Nyquist theorem does not require equal spaced points.  Equal
spacing is convenient, and good in terms of S/N ratio.  If your
samples are infinitely narrow (points in time), then, theory says 
that if you multiply each point by a dirac delta function centered
at that time, and filter it through the appropriate band limiting
filter, you will get the same result as the original signal 
through such band limiting filter.  If the points are not equally
spaced, then errors in the position of those points are magnified
in the final result.  If you have velocity or acceleration,
you use first or second derivative of the dirac delta function,
I believe.  (I have never actually tried this.)  

As a side thought, if you know all the derivatives of a function
at a single point in time, you can find the value of the
function for all times.  The problem is you have to know them
exactly.

>  As a side thought, if you know all the derivatives of a function at a
>  single point in time, you can find the value of the function for all times.

This statement is only true if the function is so-called "real-analytic,"
which is more restrictive than even "smooth" (C-infinity).  Admittedly,
functions which are not real-analytic are "pathological," particularly in a
"real-world" setting.

Ironically (since the subject is sampling theory), it turns out that the
examples of functions whose Taylor series representations do not converge,
even though all their derivatives exist everywhere, are constructed using
Fourier methods -- essentially by taking advantage of "Gibb's phenomenon" to
produce non-convergence.  (Even "almost everywhere", if I remember correctly.)

An interesting counter-example!



                                       Greg Jumper
                                       TRW Data Systems Center

                                       jumper@spf.trw.com

In article <27CD919E.5D23@deneva.sdd.trw.com> jumper@spf.trw.com (Greg Jumper) writes:
[The attribution for the original posting seems to have been lost in the
follow-up-- DH]
>>  As a side thought, if you know all the derivatives of a function at a
>>  single point in time, you can find the value of the function for all times.
>
>This statement is only true if the function is so-called "real-analytic,"
>which is more restrictive than even "smooth" (C-infinity).  Admittedly,
>functions which are not real-analytic are "pathological," particularly in a
>"real-world" setting.
>
>Ironically (since the subject is sampling theory), it turns out that the
>examples of functions whose Taylor series representations do not converge,
>even though all their derivatives exist everywhere, are constructed using
>Fourier methods -- essentially by taking advantage of "Gibb's phenomenon" to
>produce non-convergence.  (Even "almost everywhere", if I remember correctly.)
>
>An interesting counter-example!

As is         
              / exp(-1/x^2)    x <> 0
      f(x) = <
              \ 0              x = 0


The original statement, even as qualified, is not precisely true, as it
assumes an infinite radius of convergence for the Taylor series.

*D*