Forums

Beating Nyquist?

Started by Andor July 25, 2007
On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:
> Rune Allnor wrote: > > On 25 Jul, 15:57, Steve Underwood <ste...@dis.org> wrote: > >> Rune Allnor wrote: > >>> I don't like "random" algorithms which work "on average." > >>> Maybe the claim that random sampling works "on average" > >>> can be formally justified; I don't have the competence > >>> to comment on such a *formal* claim either way. > >> Aren't algorithms that work statistically the very essence of signal > >> processing? :-\ > > > No. They play a large part -- adaptive DSP and model-based > > DSP based on parameter estimation, come to mind -- but all > > suffer from the same weakness: They only work to whatever > > extent the statistical model fit reality. Or, alternatively, > > to the extent the signal fits the model. > > > As long as there is a certain degree of match between signal > > and statistsical model, OK, the algorithms work. The problems > > occur when the mismatch becomes large and go undetected. > > Are these instances acceptable "on average" or does the > > application require *guaranteed* worst-case behaviour? > > Pretty much anything in comms is statistical.
You know a few things: - Transmitter frequency - Transmitter bandwidth - Modulation scheme - Codebook Given these deterministic basics, the statistics amounts to handle additive noise and determining exactly which of these deterministic codes appear when in the signal.
> Pretty much anything in sensing is statistical.
You know a few things: - Transmitter frequency - Transmitter bandwidth - Modulation scheme - Codebook Given these deterministic basics, the statistics amounts to handle additive noise and determining exactly when these deterministic codes appear in the signal.
> I thought you'd worked in acoustic sensing. That's a very statistical area.
Correct. I have learned the hard way to be as conservative as possible when working outside purely academic contexts. Data sampling is a bit too fundamental to mess up; the vessels I work on cost on the order of $100000 per day to keep in the field. If you have access to one of those, you want to play it safe and get some guaranteed performance. Anything else would be gambling, both with the client's $$ as well as your own reputation. And professional future. Of course, one you have sampled the data, you can start playing with statistics. As long as you have a backup which provides some guaranteed worst-case performance which can answer certain very specific questions. Rune
On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:
> > >> Aren't algorithms that work statistically the very essence of signal > > >> processing? :-\ > > Pretty much anything in comms is statistical.
Pretty much anything dealing with the real world is statistical (QM and thermodynamics, etc. as well as failure rates, humans, and "unexpected" accidents.) Deterministic engineering usually just renames all the statistically outlying events as outside the assumptions for the system.
> You know a few things: > > - Transmitter frequency
Assuming a solder joint near the xtal or some other component didn't go bad... or the janitor hit the wrong button when turning out the lights, etc. etc. In a few comms fields, human interface design as well as failure or even disaster mitigation are part of the design process. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
On Jul 25, 2:24 am, Andor <andor.bari...@gmail.com> wrote:
> Friends, > > just now I stumbled upon this webpage: > > http://www.edi.lv/dasp-web/ > > Specifically, in this chapter > > http://www.edi.lv/dasp-web/sec-5.htm > > they state that they can sample a 1.2GHz signal using a pseudo-random > sampling instants with an average rate of 80MHz (in the last line of > section "5.2 Aliasing, how to avoid it").
What this paper seems to show is that traditional image aliases that would go undetected by strictly periodic sampling would be detected by some sampling jitter. What they do not say is whether some other other type of alias waveform (fractal maybe?) could still be aliased in their reconstruction. Bandlimiting allows a clean definition of the types of waveform which would alias in a periodic sampling scheme. My guess is that random sampling merely makes it harder to define the types of waveforms which would cause aliasing, making them much harder or impossible to remove. But if you rename these aliases "noise", then you might be able, in return, to detect the more cleanly defined "bands" of traditionally aliased spectrum (e.g. an interfering carrier, etc.). IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Fred Marshall wrote:
(snip, and previously snipped discussion about Nyquist, aliasing,
and non-uniform sampling)

> Without studying it too hard it looks to me like the proposed approach tends > to spread the spectrum of the aliases - generating what looks more like > noise. Thus creating a tradeoff between having aliases and noise. Seems > like it would depends on lot on the nature of the signal for it to work. > Periodic waveforms might work fine while more random waveforms might not - > because how do you differentiate between "signal" and "noise" in that latter > case?
It seems to be popular now to dither the clocks on processors to "reduce" RFI. Presumably this just spreads out the RFI so that instead of a sharp peak at some frequencies it is smaller peaks at more frequencies.
> I'm not endorsing the claim, just pondering it.
> Knowing the sample times precisely only positions the samples for > reconstruction. Pure sinc reconstruction (or lowpass filtering of > precisely-placed samples) works fine for the fundamental components. But, > for higher frequency components that would alias, the dithering might spread > their spectrum, would't it?
Isn't the traditional Nyquist limit only good for an infinitely long signal? The one I used to consider was N sample points over a time T, with the signal zero at t=0 and t=T. Considering a basis of sin(wt) and cos(wt), and with the signal zero at t=0, only sin(wt) terms are allowed. Zero at t=T allows only discrete frequencies, and with a band-limited signal, the appropriate Nyquist limit is found. In that case, the N samples result in an N equations with N unknowns at reconstruction, which works as long as the matrix is not singular.
> Here's another way of looking at it - a thought experiment: > Assume a really high sample rate that is equivalent to the temporal > resolution of the samples to be taken "randomly". Surely there is a time > grid that must underlie the method - for example, on which to place the > reconstructing waveforms (e.g. sincs). > This creates a sample rate that is (by definition) "high enough" for the > actual bandwidth and Nyquist.
With non-uniform sampling the reconstruction isn't a sinc, but if the sample points are rational then a finer grid will exist. It they are irrational then no such grid exists, but non-uniform sampling still works the same way.
> Sample at this rate. You know what the spectrum will look like > if you know the signal being sampled.
For a quantized signal you get quantization noise in the reconstruction. Uniform sampling minimizes the peaks in the quantization noise.
> Then, decimate but randomly. That is, decimate (but not regularly) so that > the average sample rate is what you wanted in the first place. Note that > this is a nonlinear operation so familiar methods of analysis don't work.
> Now, use a test signal that is above the "new" fs/2. > It seems to me that the randomized sample points will modulate the heck out > of a higher-frequency sinusoid - turning its samples into what looks like > random noise - because of the rather drastic phase hops between samples.
> Thus, no "alias" tonals in the result - but, more noise.
It looks that way to me, too.
> If you switch the input to a test signal that is below the "new" fs/2 then > there will be no modulation (spectral spreading) because of the careful > temporal registration of the samples and the reconstructing sincs. Well, > that's an arm-waving description and I'm sure others can do a better, more > thoughtful, job of explaining why this might be.
Not counting quantization noise. (snip)
> OK - I thought about it some more... > The "nonlinear" step above can be replaced with a linear step. > Create the desired sample points in time. By definition they align on the > fine temporal grid. Note that the gross view of these samples looks like > they are regularly spaced. But they aren't of course - on purpose.
Unless the sample points are irrational.
> Because the temporal location will be dithered at decimation, using a new > set of sample points, there is a spectrum of this lower-frequency unit > sample train that's not the typical picket fence repeating at fs. Rather, > there's a broader clump at fs - the width determined by how much temporal > deviation is built in between the samples.
Yes, I agree. The same way that clock dithering spreads out the RFI of clock frequencies and their harmonics. -- glen
On 25 Jul, 20:35, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote: > > > >> Aren't algorithms that work statistically the very essence of signal > > > >> processing? :-\ > > > Pretty much anything in comms is statistical. > > Pretty much anything dealing with the real world is > statistical (QM and thermodynamics, etc. as well as > failure rates, humans, and "unexpected" accidents.)
That's a fatalist's attitude. "It was by sheer bad luck that car ran off the road and hit the tree!" Have a look at the F1 accident record over the past 50 years, and see how the fatality rate is correlated with the track safety zones and car designs. The occurence of cars running off track might be random, but the concequences of it happening is all but mitigated. That's due to deterministic factors of track design.
> Deterministic engineering usually just renames all > the statistically outlying events as outside the > assumptions for the system.
There are assumptions and there is knowledge. If you are happy with designing a speech processing system under the *assumption* that the human voice has its main spectral content in the range 1.3804 MHz - 22.78 GHz, then by all means, go ahead and design and market your system. Just be prepared to answer to whoever funded your project, after your project has gone bankrupt.
> > You know a few things: > > > - Transmitter frequency > > Assuming a solder joint near the xtal or some other > component didn't go bad... or the janitor hit the > wrong button when turning out the lights, etc. etc. > In a few comms fields, human interface design as well > as failure or even disaster mitigation are part of > the design process.
Exactly. "Design" is all about handling certain key aspects of the system in a very deterministic way, as opposed to leaving them to chance. In my book -- if not in yours -- the sampling period is one of those factors concerning DSP which should *not* be left to chance. A high risk -- be it national security or mere $$ -- tends to bring most competent project managers to their senses. Rune
On 25 Jul, 23:47, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

> Isn't the traditional Nyquist limit only good for an infinitely > long signal?
No. Sample a sinusoidal for arbitrary length of time (N > 1) and you will find aliasing to be an issue.
> The one I used to consider was N sample points over a time T, with the > signal zero at t=0 and t=T. Considering a basis of sin(wt) and > cos(wt), and with the signal zero at t=0, only sin(wt) terms are > allowed. Zero at t=T allows only discrete frequencies, and > with a band-limited signal, the appropriate Nyquist limit is > found. In that case, the N samples result in an N equations > with N unknowns at reconstruction, which works as long as the > matrix is not singular.
Nope. The problem is that the identity sin(2*pi*f*n) = sin(2*pi*f*n + 2*pi*p), p integer always holds; you can not find a unique value for p. Rune
On Jul 25, 1:59 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 Jul, 20:35, "Ron N." <rhnlo...@yahoo.com> wrote: > > > On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote: > > > > >> Aren't algorithms that work statistically the very essence of signal > > > > >> processing? :-\ > > > > Pretty much anything in comms is statistical. > > > Pretty much anything dealing with the real world is > > statistical (QM and thermodynamics, etc. as well as > > failure rates, humans, and "unexpected" accidents.) > > That's a fatalist's attitude. "It was by sheer bad luck > that car ran off the road and hit the tree!" Have a look > at the F1 accident record over the past 50 years, and > see how the fatality rate is correlated with the track > safety zones and car designs. The occurence of cars > running off track might be random, but the concequences > of it happening is all but mitigated. That's due to > deterministic factors of track design.
I would hesitate to call it deterministic unless you can predict which driver on which day at which turn will run off the track. If not, you are merely dealing with statistical safety issues, (e.g. doing this to that turn will reduce the expected accident rate from x per year to y per year, on average and rarely exactly.) ...
> > > You know a few things: > > > > - Transmitter frequency > > > Assuming a solder joint near the xtal or some other > > component didn't go bad... or the janitor hit the > > wrong button when turning out the lights, etc. etc. > > In a few comms fields, human interface design as well > > as failure or even disaster mitigation are part of > > the design process. > > Exactly. "Design" is all about handling certain key > aspects of the system in a very deterministic way, as > opposed to leaving them to chance.
I think we may just be calling the same (good) engineering process by two different names.
> In my book -- if > not in yours -- the sampling period is one of those > factors concerning DSP which should *not* be left > to chance.
If you can. An if the solution to the more tractable resulting situation is the desired one. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Rune Allnor wrote:

> On 25 Jul, 23:47, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>>Isn't the traditional Nyquist limit only good for an infinitely >>long signal?
> No. Sample a sinusoidal for arbitrary length of time (N > 1) > and you will find aliasing to be an issue.
I meant it the other way around. That for finite length (and non-periodic) signals, you can't exactly reproduce them with a finite number of samples.
>>The one I used to consider was N sample points over a time T, with the >>signal zero at t=0 and t=T. Considering a basis of sin(wt) and >>cos(wt), and with the signal zero at t=0, only sin(wt) terms are >>allowed. Zero at t=T allows only discrete frequencies, and >>with a band-limited signal, the appropriate Nyquist limit is >>found. In that case, the N samples result in an N equations >>with N unknowns at reconstruction, which works as long as the >>matrix is not singular.
> Nope. The problem is that the identity
> sin(2*pi*f*n) = sin(2*pi*f*n + 2*pi*p), p integer
> always holds; you can not find a unique value for p.
Again the other way around. The signal is known to be band limited which selects the appropriate p. The reconstruction has to be done with the selected p. -- glen
On 25 Jul, 23:38, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Jul 25, 1:59 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > Pretty much anything dealing with the real world is > > > statistical (QM and thermodynamics, etc. as well as > > > failure rates, humans, and "unexpected" accidents.) > > > That's a fatalist's attitude. "It was by sheer bad luck > > that car ran off the road and hit the tree!" Have a look > > at the F1 accident record over the past 50 years, and > > see how the fatality rate is correlated with the track > > safety zones and car designs. The occurence of cars > > running off track might be random, but the concequences > > of it happening is all but mitigated. That's due to > > deterministic factors of track design. > > I would hesitate to call it deterministic unless you > can predict which driver on which day at which turn > will run off the track.
That particular aspect is random. The chain of events when it happens, is more or less deterministic: The gravel pits and grass slow the sliding car down, the tire stacks by the wall and crumble zones built into the car bring it to a final halt in a way that is survivable to the driver. The goal in DSP, as far as I can see, is to use deterministic models whereever possible, and resort to statistics only reluctantly. I analyzed real-life data for my PhD thesis using statistical fits to deterministic models, Prony's method to be precise. Prony's method is a way to determine the parameters in a D-component sum-of-sines data model, D x[n] = sum A_d sin(w_d n) [1] d=1 (note that the model contains no noise terms) The first account of Prony's method I read was Kay & Marple: "Spectrum Analysis - A modern perspective" Proc IEEE October 1981. I had just taken a DSP course where AR methods, whitening filters, innovation processes and all that had been covered. The basic idea behind Prony's method was easily covered, assuming that the model contained N sinusoidals and one had N data samples available, i.e. D = N in [1]. I remember noting that Kay and Marple were very meticulous in the phrasing of certain sentences concerning the case when one has N data samples available but one does not know the exact number of sinusoidals, D, present. Since there is no noise, one can not talk about a "prediction error", as we had just done in the course I had taken merely months before; rather, they talked about "model mismatch." Kay and Marple made some more or less ad hoc remarks that the phrasing did not matter, since one used more or less the same methods for minimizing the *model* error as one would do to minimize the *prediction* error in other applications. So I proceeded using this no-noise, deterministic model to analyze noisy measured data. A couple of years later I found a different approach to the same problem, in the article Tufts & Kumaresan: "Estimation os frequencies of sinusoids: Making linear prediction behave like Maximum Likelihood" Proc. IEEE, September 1982. Those guys started from the same model but derived a different numerical routine to do the job. Tufts and Kumaresan used a Singular Value Decomposition with some dimension reduction steps. Their rationale was that these computations introduce numerical errors, and introducing the dimension reduction step improved the numerical properties of the routine. So I implemented their method and saw dramatic improvements in my results. Now, at that stage I had several issues to deal with while analyzing my data: 1) Model mismatch: The sum-of-sines model was positively wrong, since the data could formally be described as spherical Bessel functions, culindrical Bessel functions or exp(x)/x type functions, at various ranges. 2) Incomplete model knowledge: I did not know what model order (the number of sinusoidals present) in the data 3) Errors introduced by numerical issues of computer computations 4) Additive noise in the measurements Of these issues, only issue 4, additive noise, is truly "random" in the sense that the numbers could be generated by rolling dice [*]. Nevertheless, the "statistical" approach to problem-solving did handle all these issues, simply because errors don't come with tags as to their causes. As far as I am concerned, the ideal is to use deterministic models wherever possible. That's an ideal which is not easily met, so one needs to deal with all these issues as best one can, more often than not using statistical methods. Rune [*] Strictly speaking, that's true for numerical errors as well. However, the terminology and approach to handle numerical errors is a bit different than the terminology and approach dealing with measurement noise.
On Jul 25, 5:24 am, Andor <andor.bari...@gmail.com> wrote:
> Friends, > > just now I stumbled upon this webpage: > > http://www.edi.lv/dasp-web/ > > Specifically, in this chapter > > http://www.edi.lv/dasp-web/sec-5.htm > > they state that they can sample a 1.2GHz signal using a pseudo-random > sampling instants with an average rate of 80MHz (in the last line of > section "5.2 Aliasing, how to avoid it"). > > I know that for nonuniform sampling, a generalization of the Sampling > Theorem has been proved [1], which states that a bandlimited signal > maybe reconstructed from nonuniformly spaced samples if the "average" > sampling rate is higher than twice the bandwidth of the signal. > > This doesn't immediately contradict the claim above - it just says > that if the average sampling rate exceeds a certain limit, it can be > shown that the samples are sufficient for reconstruction. It might > well be that if the average rate is below the limit, reconstruction is > still possible. However, the claim still seems like magic to me, > specifically in the light that the sampled signals underlie no > restrictions (apart from the 1.2GHz bandwidth). > > Comments? > > Regards, > Andor > > [1] F. J. Beutler, "Error-free recovery of signals from irregularly > spaced > samples," SIAM Rev., vol. 8, pp. 328-335, July 1966.
Hello Andor, This is quite intriguing! I wonder besides using a psuedorandom (which gets around Rune's objection of sometimes failing to meet some critical threshold such as always having a mean sampling rate high enough) sequence if a sequence that resembles the spacing of the nodes in a Gauss-Legendre integration scheme would have this property. And of course what are the different allowable sample distributions that minimize the number of samples verses a nonaliased bandwidth? Radio astronomers have played around with putting the telescopes on points that correspond to the "inch marks" on a giant Golomb ruler. Hence maximizing the number of different spacings between telescopes given a fixed number of them. Even some cell towers have the antennas for a given sector set up on the marks of a Golomb ruler. I see some similarities in the ideas behind these applications of nonlinear sampling (whether temporal or spatial) even if the math works out to be a little different. Having the sample times obey a pseudorandom or other deterministic sequence keeps one from needing to store all of the sample times, as they can be reconstructed at will. Clay