| Author |
Message |
zzbunker@netscape.net
Guest
|
 Posted:
Wed Nov 16, 2005 9:15 am Post subject:
Re: question about non-uniform sampling? |
|
|
lucy wrote:
| Quote: | Hi all,
Can non-uniform sampled signal be used to perfectly reconstruct the
original continuous time signal?
|
Well yes. Otherwise we wouldn't ask women and musicans that
question.
| Quote: |
What is the Nyquist sampling rate in the non-uniform case?
|
There is no sampling rate in the non-uniform case,
that's why we always idiots like Dan Rather,
60 minutes, mathematicians, and DSP manufactures that question.
|
|
| Back to top |
|
 |
Carlos Moreno
Guest
|
| Posted:
Wed Nov 16, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
It wouldn't have to be anti-causal. A symmetric low-pass FIR filter
| Quote: | with enough taps and bits of precision would work. Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.
I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
|
Now now now, Jerry... Why are you being silly? :-)
Carlos
-- |
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted:
Wed Nov 16, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | I hear you. Nevertheless, when theory predicts a known impossibility,
not merely a counterintuitive result, we need a less simplistic theory.
|
Hmmm... I'd tend to disagree with this, but perhaps it'ssimply that
we're expressing the same idea in different terms...
I tend to see it more like a case where what the theory predicts has
no analogy in the practical/real world.
It's not really an impossibility, because no-one is talking about
signals in the real world. So, it's not a matter of "predicting"
something that we know is not possible; it's a matter of producing
one result that is correct, but that does not represent any entity
from our physical world.
There are many cases like this, such as complex numbers (they have
no entity in the real world that is *directly* represented by them),
or even the basic Fourier analysis (which deals with the general case
of signals that go from -infinity to +infinity), and sampling, which
does require truly bandlimited signals (something that does not
exist in our physical world).
True: the difference is that all those theoretical results or
concepts do have a direct application to real problems if we
approximate things -- my example (at least the example taken to
the extreme case) does not.
Carlos
-- |
|
| Back to top |
|
|
Ron N.
Guest
|
| Posted:
Wed Nov 16, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | Ron N. wrote:
cs_post...@hotmail.com wrote:
Ron N. wrote:
For this counterexample to work, the response of the lowpass filter
for each sample would have to be over an hours worth of samples wide
...
to which Jerry Avins replied:
What if it's a request show and the second half-hour's music isn't known
until after the sampling stops? Suppose even that the program is known
in advance. Do you suggest that it might be possible to reconstruct the
last movement of Beethoven s 9th Symphony from a gross oversampling of
the first three?
Yes, provided you pass the samples through the anti-causal low pass
filter that Ron postulated.
It wouldn't have to be anti-causal. A symmetric low-pass FIR filter
with enough taps and bits of precision would work. Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.
I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
|
How would the filter have saved any work? If fed a last movement
of silence, that's what would be reproduced, given a few billion bits
of precision per sample and a lowpass filter an equivalent number
of dB down in the stop band.
What you think is the first sample of the first movement, can't be
correctly bandlimited to the precision required unless the low pass
filter is fed the last sample of the last movement.
IMHO. YMMV.
--
rhn A.T nicholson d.O.t C-o-M |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Nov 16, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Ron N. wrote:
| Quote: | cs_post...@hotmail.com wrote:
Ron N. wrote:
For this counterexample to work, the response of the lowpass filter
for each sample would have to be over an hours worth of samples wide
...
to which Jerry Avins replied:
What if it's a request show and the second half-hour's music isn't known
until after the sampling stops? Suppose even that the program is known
in advance. Do you suggest that it might be possible to reconstruct the
last movement of Beethoven s 9th Symphony from a gross oversampling of
the first three?
Yes, provided you pass the samples through the anti-causal low pass
filter that Ron postulated.
It wouldn't have to be anti-causal. A symmetric low-pass FIR filter
with enough taps and bits of precision would work. Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.
|
I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Nov 16, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Carlos Moreno wrote:
| Quote: | Jerry Avins wrote:
It's also a world where signals exist for all time. I doesn't matter
how precisely one can sample and how often, nothing can be known
about a speech yet to be given
If that is the case, then the speech signal is not bandlimited -- and
if that is the case, then you're talking about an entirely different
thing than I was talking about.
I'm talking about precisely what you are. A signal that is truly
bandlimited isn't time limited, and vice versa. In the real world,
signals with finite duration can bandlimited well enough so that we
can deal with them.
Absolutely. And the fact that we *want* to sample them uniformly
because there are endless arguments in favor of it (i.e., there is
an endless list of advantages from both the practical and theoretical
point of view) is an entirely different thing.
When I read the subject of the thread, and the question asked by
the OP, it became more or less clear that we were dealing with the
theoretical/mathematical aspect as much as with the practical one.
In the practical side, there's no question about it -- non-uniform
sampling is virtually an "absolute no-no".
|
I wouldn't go that far. I am ready to believe that a sampling that
averages 2.5 times the signal's bandwidth, with no interval longer than
3 times the average, and each sample time "well enough" known allows
accurate reconstruction of the original.
| Quote: | But on the theoretical side, I find it extremely interesting (and
remarkable!) the results and conclusions that we can reach, even
if they seem unintuitive when contrasted with the practical side.
(no, this is not a case of "in theory, there is no difference
between theory and practice, but in practice, there is" -- it's
simply a case of "this particular result from the theory does not
have a practical situation where it is really applicable")
But when one becomes pedantic about what is theoretically possible, on
must be likewise aware of what is theoretically impossible.
Well, it's not really "pedantic" -- I see it more like a matter
of keeping in mind when some theoretical result has a direct
applicability in the practical world. After all, going back to
the roots, Calculus itself could be accused of "pedantic", in
that the real world is not really how Calculus models it (even
though in the case of Calculus, the *results* are nicely
correlated with the physical world, unlike this issue about
the non-uniform sampling taken to the extreme)
But BTW, your argument does not really contradict my reasoning -- I did
not say (nor the conclusion I presented implies) that you can determine
the hour of speech before it was given. In fact, not even right after
it is given. To *fully* determine/reconstruct the continuous-time
speech signal you have to wait until "t = infinity" to be able to
reconstruct it... (t = infinity is obviously a figure of speech, to
simplify the issue that the signal is given by an infinite sum)
According to the argument you gave, samples from near the end of a
program can be moved to near the beginning, one at a time, without
compromising the reconstructed signal. How long you must have to wait
before the decoding is finished doesn't bear on the claim that you can
reconstruct what was not sampled. Do I not understand what you claimed?
I'm not 100% sure... Maybe you do and you're assuming that I'm
assigning some practical value to it; but perhaps you misinterpreted
what I said.
In the above paragraph, you talk about "samples from near the end of
a program can be moved to near the beginning" -- if by that you mean
the *sampling position* (as in, the value of t at which you take a
sample), then we seem to be in sync.
|
Yes.
| Quote: | Let's say that we have a *perfectly bandlimited* signal between DC
and 0.499999999Hz, so that a sampling period of 1 second allows us
to reconstruct the signal.
If you have an infinite set of samples of that signal, taken at
exactly .... -3s, -2s, -1s, 0s, 1s, 2s, 3s, ..... , then you can,
mathematically speaking, reconstruct the signal at all times, with
100% accuracy.
My claim (or rather, an example that illustrates my claim) is that
if you have all those samples and instead of taking a sample at
t = 0, you take one additional sample at t = -75.45627, you still
have enough information to reconstruct *exactly* the signal at all
values of t (again, mathematically speaking).
Why?
If you had all the values of x(t) at t = k seconds (with k integer),
then you could obtain x(-75.45627), right? (with the reconstruction
formula, using the infinite sum with sinc terms). The relationship
is linear; in particular, the relationship between x(-75.45627) and
x(0) is linear:
x(-75.45627) = sinc(-75.45627) x(0) + B
Where B is the rest of the infinite sum (all the terms except for
k = 0)
So, that means that having x(-75.45627), you can obtain x(0) (since
we know B). But then, as soon as we have x(0), now the "standard"
sampling theorem tells us that the signal can be reconstructed
with 100% accuracy.
What if instead of sampling x at t = 0 and at t = 1, you take two
additional samples, one at t = -75.45627, and another one at
t = -75.512348 ??). These two samples, x(-75.45627) and
x(-75.512348) are related to x(0) and x(1) by a linear relationship;
each one provides one equation; thus, if we want to obtain x(0)
and x(1), we just solve a system of linear equations -- two equations
for the two unknowns, x(0) and x(1).
So, the argument can be extended -- if you do not take any sample
of the signal between t = 0 and t = 1000, and instead you take
samples at t = -0.9, -0.8999, -0.8998, .... and so on, every
tenth of a millisecond, until t = -0.8001, you end up with a
*solvable* system of 1000 linear equations for the 1000 unknowns,
x(0) to x(999). You *can* solve that system, obtain x(0) to x(999),
and now you can recover the signal for all values of t.
Where do you find a flaw in the above reasoning?
Notice that I would never say as little as half a word in defense
of the practical applicability of the above!! For one, the
example is taken to a ridiculous extreme of sensitivity to
numerical accuracy -- the samples taken a tenth of a millisecond
away of each other would lead to a matrix that is sooooooo close
to being singular that I guarantee that it would be next to
impossible to solve the system numerically with any *actual*
computer that we may have.
But that still does not defeat the fact that *mathematically*
speaking, those samples provide sufficient information to
determine the values of the signal at every value of t.
Again: provided that the signal is *truly bandlimited*, which
as we already agreed, implies that it is not time-limited (the
signal goes from -infinity to +infinity).
|
I hear you. Nevertheless, when theory predicts a known impossibility,
not merely a counterintuitive result, we need a less simplistic theory.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
zzbunker@netscape.net
Guest
|
| Posted:
Wed Nov 16, 2005 3:25 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Ron N. wrote:
| Quote: | Jerry Avins wrote:
Ron N. wrote:
cs_post...@hotmail.com wrote:
Ron N. wrote:
For this counterexample to work, the response of the lowpass filter
for each sample would have to be over an hours worth of samples wide
...
to which Jerry Avins replied:
What if it's a request show and the second half-hour's music isn't known
until after the sampling stops? Suppose even that the program is known
in advance. Do you suggest that it might be possible to reconstruct the
last movement of Beethoven s 9th Symphony from a gross oversampling of
the first three?
Yes, provided you pass the samples through the anti-causal low pass
filter that Ron postulated.
It wouldn't have to be anti-causal. A symmetric low-pass FIR filter
with enough taps and bits of precision would work. Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.
I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
How would the filter have saved any work? If fed a last movement
of silence, that's what would be reproduced, given a few billion bits
of precision per sample and a lowpass filter an equivalent number
of dB down in the stop band.
What you think is the first sample of the first movement, can't be
correctly bandlimited to the precision required unless the low pass
filter is fed the last sample of the last movement.
|
Well that's automically incorrect. Given that they the reason even
we invented sampling and electric guitars with feedback pedals
and MTV to begin with was to prove to the idiots in The Filmore
East and West and to the moronic Greatful Dead and Beatles
bandwagon shitheads that there is no such as a first sample
or a first movement.
So we always like to tell the Washingtoon, San Fag ciso and
New York Beatle idiots that when the Band played The Last Waltz,
they didn't actually play The Last Waltz.
They simply played the opening laser riffs of
The Mick Jagger Bagdad Weight. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Wed Nov 16, 2005 4:36 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | Carlos Moreno wrote:
|
(snip)
| Quote: | The reasoning can be extended to any number N, no matter how
large.
I know this is not rigurous -- in particular, this shows that
the trick works for N samples taken at positions other than
the corresponding positions, no matter how large; but this
proves nothing about an "infinity" of samples taken non-
uniformly... Still, the result does suggest that you still
need the amount of samples that totals the same amount of
samples required in uniform sampling (suggesting that your
Nyquist condition is given by the average sampling rate).
|
| Quote: | It doesn't. There's a limit to how non-uniform the sampling can be
allowed to be. The example given above, of an hour's worth of music
sampled for half an hour at twice the minimum rate for the bandwidth, is
an adequate counterexample to what you claim is a general case.
|
Well, he started with an infinite number of samples. If you subtract
any finite number you still have an infinite number of samples, so it
still works. That, and that the samples can't have any quantization error.
-- glen |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Wed Nov 16, 2005 4:42 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | Steve Underwood wrote:
|
(snip)
| Quote: | There is nothing wrong with any
extreme of non-uniformity in a purely mathematical sense. That is in a
world with infinite sampling precision and no noise due to the
converter itself.
It's also a world where signals exist for all time. I doesn't matter how
precisely one can sample and how often, nothing can be known about a
speech yet to be given, even if the mathematics of nonuniform and highly
clumped sampling shows that it can.
|
I am not so sure what quantum mechanics says about this.
Mathematically, I believe that it works just about any time you have an
infinite number of samples. Consider that an infinite number of
derivatives at a single point are also good enough to reconstruct a
function.
All the problems appear when you don't have an infinite number of points
with no noise or other errors in them.
-- glen |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Wed Nov 16, 2005 4:55 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
(snip)
(someone wrote)
| Quote: | But BTW, your argument does not really contradict my reasoning -- I did
not say (nor the conclusion I presented implies) that you can determine
the hour of speech before it was given. In fact, not even right after
it is given. To *fully* determine/reconstruct the continuous-time
speech signal you have to wait until "t = infinity" to be able to
reconstruct it... (t = infinity is obviously a figure of speech, to
simplify the issue that the signal is given by an infinite sum)
According to the argument you gave, samples from near the end of a
program can be moved to near the beginning, one at a time, without
compromising the reconstructed signal. How long you must have to wait
before the decoding is finished doesn't bear on the claim that you can
reconstruct what was not sampled. Do I not understand what you claimed?
|
This reminds me of my first thoughts hearing about FTIR, that is,
Fourier Transform Infra Red spectroscopy. Instead of scanning through
frequency space, as usual for spectroscopy, you measure the output from
a scanning interferometer which gives the FT of the spectrum. What
happens, then, at the points in the transform where the light source
doesn't have any intensity?
Also, at some point the discussion should get to the Kramers-Kronig
relations which for physical systems connect the real and imaginary
parts, as well as time and frequency.
-- glen |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Wed Nov 16, 2005 5:01 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Carlos Moreno wrote:
(snip)
| Quote: | Well, it's not really "pedantic" -- I see it more like a matter
of keeping in mind when some theoretical result has a direct
applicability in the practical world. After all, going back to
the roots, Calculus itself could be accused of "pedantic", in
that the real world is not really how Calculus models it (even
though in the case of Calculus, the *results* are nicely
correlated with the physical world, unlike this issue about
the non-uniform sampling taken to the extreme)
|
If I remember right, it isn't yet determined if quantum mechanics
quantizes time. That may restrict the ability to do limits as delta t
approaches zero, or it may not.
These discussions get much more interesting if you include quantum
mechanics in them. That is, what is actually allowed to be measured.
-- glen |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Wed Nov 16, 2005 5:05 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
(snip)
| Quote: | I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
|
Given all the samples of his work and the first three as input, one
might compute in some weeks the most probable fourth movement.
-- glen |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Nov 16, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Ron N. wrote:
| Quote: | What you think is the first sample of the first movement, can't be
correctly bandlimited to the precision required unless the low pass
filter is fed the last sample of the last movement.
|
There is no such thing as a bandlimited sample. A sample is a scaled
impulse, and an impulse is by definition for all frequencies. |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Nov 16, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Ron N. wrote:
...
| Quote: | I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think how
much work (and time!) such a filter would have saved Beethoven himself!
How would the filter have saved any work? If fed a last movement
of silence, that's what would be reproduced, given a few billion bits
of precision per sample and a lowpass filter an equivalent number
of dB down in the stop band.
What you think is the first sample of the first movement, can't be
correctly bandlimited to the precision required unless the low pass
filter is fed the last sample of the last movement.
|
The hypothesis is that the first three movements were oversampled, using
enough samples to suffice for all four. According to Carlos, it doesn't
matter where the samples are just so long as there are enough of them.
We can deduce from Carlos's claim that the entire symphony was sampled.
If the claim is valid, then the entire symphony can be reconstructed. I
don't suppose that the entire symphony including the choral movement can
be reconstructed from the samples. My intent is /reductio ad absurdam/.
Carlos and I understand the argument, but see it from different vantages.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Nov 16, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
glen herrmannsfeldt wrote:
| Quote: | Jerry Avins wrote:
(snip)
I'd be happy to wait a whole week for a filter to compose the last
movement of Beethoven's Ninth, given only the the first three. Think
how much work (and time!) such a filter would have saved Beethoven
himself!
Given all the samples of his work and the first three as input, one
might compute in some weeks the most probable fourth movement.
|
Including the choral parts, which were unprecedented for a Beethoven
symphony?
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in