Analog domain and aliasing

[petert]

Hello all,

I have been having this question for a while, and haven't found a convincing explanation or proof yet.

When digitizing a signal, you should stay under the Nyquist frequency to avoid aliasing, that easily makes sense when looking at examples.
But is there really no aliasing or similar effect in analog components?

There are phase shifts and dampening of frequencies in filters, but why no aliasing?

Couldn't certain physical properties of materials cause similar effects? Rasterizing effect or "jumps" and similar patterns can occur in mechanical systems (think of a clock that translates continuous rotation or pendulum movement to step wise rotation of the clock's hands). Jumps/discrete steps also appear as discrete energy levels in Bohr's atom model (I know it has been superseded by Quantum mechanics, but it still describes the process quite accurately for hydrogen).

How do we know that analog components are really continuous and how much might it affect/add noise similar to aliasing to a signal as it gets processed by those components?
How can we know they really do not behave frequency dependent, beyond dampening and phase shifting?

[JohnnyMalaria]

Aliasing is the false assignment of a frequency due to sampling. There is no sampling in the analog domain. Analog signals are continuous as you say. The main issue with analog is random noise. In theory, if you could observe analog signals using a non-sampling technique (e.g., CRT scope) on extremely short timescales (say picoseconds) then you may start to observe quantum effects but in our worldly domain an analog signal is continuous.

[petert]

Thanks.

Aliasing is the false assignment of a frequency due to sampling.

What about the clock example which translates continuous to step-wise? Couldn't there be similar unintended effects in analog components that cause such interrupted/step-wise behavior and consequently aliasing?

on extremely short timescales (say picoseconds) then you may start to observe quantum effects but in our worldly domain an analog signal is continuous.

If I knew more, I would give other examples. But let's stay with quantum effects. Couldn't these aliasing effects propagate into the macroscopic world, since the alias frequency would be much lower?

[JohnnyMalaria]

With something like clock signal (e.g., a square wave), the major unwanted effects come from the finite time it takes to make the step change and also the bandwidth of the circuit plus other things. You may see distortions on the signal such as ringing or overshoot. But what in an analog clock is being sampled? Nothing. Aliasing is a phenomenon due to digital sampling of an analog signal (or synthesis of an analog signal from a digital signal).

EDIT: Re my comment about very short timescales etc, all kinds of weird stuff happens that inherently cannot be measured.

[vk6zgo]

Sampling is very similar to mixing, & yes, it is possible with analog sig "to end up with signals which are translated into the wrong part of a band of frequencies.
I started to write a long screed about this, but gave up.

Hint:- if in a mixer f1 is the higher frequency input, f2 the lower,
we would normally want to use f1- f2, or f1+f2, what would we get from f2-f1?

[tggzzz]

When digitizing a signal, you should stay under the Nyquist frequency to avoid aliasing, that easily makes sense when looking at examples.
But is there really no aliasing or similar effect in analog components?

Aliasing is sometimes inherent to the operation of a circuit. One easy example is "Tayloe mixer". I used the phenomena in 1979 to create an analogue bandpass filter with a Q of 4000 using 20% capacitors and 10% resistors. I "nicked" the concept from a Bell System Technical Journal article from April 1960.

One analogy for aliasing in the analogue domain is mixers.

[MattHollands]

Couldn't certain physical properties of materials cause similar effects? Rasterizing effect or "jumps" and similar patterns can occur in mechanical systems (think of a clock that translates continuous rotation or pendulum movement to step wise rotation of the clock's hands).

A mechanical clock is not analog. You’re taking an analog signal (the swinging pendulum), and creating a clock pulse and then counting the pulses. This is the electrical equivalent of passing a sine wave through a comparator and then passing those pulses to a counter chip. The system stops being analog once it enters the comparator.

Generally speaking, an important concept to understand is linear systems - most things in ordinary operation are linear systems. Among other things this means that a sine wave input will result in a sine wave output of the same frequency but potentially different phase and magnitude.

[JanJansen]

Try  drawing a saw wave in a limited ammount of blocks.
Now try that with a different frequency, you see it wont get exact to the top.
With square wave its different without aliasing, you can only get frequencys that fall exact in your blocks ( samplerate ).
The trick is to use sinewaves, they always go to top and bottom of your waveform.

[SiliconWizard]

Aliasing per se is a term usually associated with sampling.

That said, there are many ways you can get frequency shifts in the analog domain. Amplitude or frequency modulation, for instance. Non-linear distortion (think of intermodulation distortion for instance).

[NorthGuy]

Sampling per-se doesn't create aliasing. Aliasing requires regular sampling. Cannot get it otherwise.

For example, there were no moire effects in photography before digital cameras. This is because the sensor's matrix is regular. Before digital, irregular sampling with grains on the film couldn't create it.

[petert]

Many good replies, thank you all. It is really appreciated.

For example, there were no moire effects in photography before digital cameras. This is because the sensor's matrix is regular. Before digital, irregular sampling with grains on the film couldn't create it.

That's a very good analogy, interesting.
Ofc I have to keep playing devil's advocate and keep pushing this idea. So assuming the granularity of the medium was limited, as it is also in a photographic film, and it was in a regular pattern, you would get aliasing? So in theory, similar effects could happen with "granular" material in capacitors, depending on how they were produced, I suppose.

Is there an inherent physical phenomenon that makes it unlikely a sufficiently regular "matrix" or pattern would happen in production processes of electrical components?

So in the end it is not only about under sampling (at some point the information is too few, and therefore ambiguous such that the real information cannot be restored), but it is also about randomness of sampling.

If it's random sampling you still might get errors as well, but since they are not regular, the faults do not repeat in regular patterns either. Therefore those random errors blend in more as evenly dispersed noise over your signal, instead of periodic one (=waves). So it would become grainy instead of leading to clearly identifiable Moiré patterns?

[T3sl4co1l]

To clarify:

1. Analog does it just fine; it's a mixing process.  Mixers, samplers, bucket-brigade devices, switched-capacitor filters, etc. are excellent practical examples.

2. It's a mixing process.  Namely, the product of the input signal with the sampling aperture.  The aperture has a short duration, approximated by a periodic impulse function.  The product of this signal, with an arbitrary input signal, is to copy the spectrum of the input signal around each harmonic of the impulse signal.

If the input signal has BW > Fs/2, then it will overlap itself (BW above a given harmonic, BW below the following harmonic, the harmonics being Fs apart), which is ambiguous.

Aliasing isn't a problem, in and of itself, but ambiguous signals are a problem.  The sampling theorem says that a signal can be reconstructed exactly when the signal is bandlimited to Fs/2.  If you don't need an exact reconstruction, you don't need this condition.

An interesting special case is equivalent time sampling: the input is not reconstructed exactly -- in fact (for an incremental-delay, triggered sample) it is divided.  The waveform is reconstructed, but at a rate below Fs/2 -- the bandwidth limitation is not violated, nor is the sampling theorem (you clearly have not reconstructed the original waveform one-to-one!).

3. Pedantic but important point -- sampling is analog or digital, it doesn't matter.  The domain of sampling is called discrete time.

(Incidentally, where continuous-time signals are typically transformed with the Laplace or Fourier transform, discrete-time signals are transformed with the Z transform (whereas s or j*w means frequency, Z simply means... delay one sample!).  Interestingly, there is a direct correspondence between these transforms, so that all our continuous-time tools still work, under a fairly simple mapping.)

Ofc I have to keep playing devil's advocate and keep pushing this idea. So assuming the granularity of the medium was limited, as it is also in a photographic film, and it was in a regular pattern, you would get aliasing? So in theory, similar effects could happen with "granular" material in capacitors, depending on how they were produced, I suppose.

You would get aliasing if the signal has more bandwidth than the film, yes.

This doesn't usually happen, because optics just aren't that great.  Even with very good optics, the scene's depth of field may frustrate that (even if stopped down very far).

In this case, we're talking spacial frequency -- sharpness, resolution.  It works exactly the same -- whereas an electronic signal is a function of time t, an image is a function of position (x, y).

An extreme example is photolithography (the process by which semiconductors are made), which is presently pushing ten nanometers.  Obviously, it helps that the exposed medium is a molecular resin; on this scale, a film emulsion looks like the Himalayas.

You can imagine, if a wafer were coated with a very regular colloid, so that a regular hexagonal monolayer sits on it, and that colloid were exposed to the patterns used to create CPUs, you would end up with a very strange image, as some particles are exposed while others are not; in fact, you would end up with Moire patterns (assuming a regular pattern of transistors) -- optical aliasing.

Is there an inherent physical phenomenon that makes it unlikely a sufficiently regular "matrix" or pattern would happen in production processes of electrical components?

It's always there, but whether you see a pattern, depends on whether that pattern is present in both signals (the image and the sensor, in this case).  If both are uncorrelated, then no correlation is observed at a large scale.  To observe a Moiré pattern of, say, 1mm pitch, one needs an image of, say, 0.01mm and a sensor pitch of 0.0101mm, and for that pattern to be regular (say, 1.0 +/- 0.1 mm), both pitches need to be accurate to as many decimal places -- that is, 0.01000 and 0.01010 respectively.

Moiré is a remarkable phenomenon for two reasons: one, order is not often seen in the world ("nature abhors a straight line"), let alone the long-distance regularity required to observe a large pattern; and two, when viewed from two locations (binocular vision!), a pattern formed from two screens (say), is very different from those two locations; they're very eye-catching.

Of course, the change in contrast over an aliased image, or the fluctuating intensity of an aliased signal, is nearly as jarring.

Tim

[dmills]

The aliasing you see at the movies is the wagon wheels seeming to rotate backwards in the old cowboy films.... The sampling is the 24FPS that the film is exposed at, and the signal is the angle of the spokes.

Aliasing is an artefact of sampling not quantisation (Two different processes).

Regards, Dan.

[SiliconWizard]

Yes. Sampling is discretization, not quantization, so it's not specifically digital. (This whole thread doesn't really belong here in fact.)

Aliasing *will* occur whenever the signal you're trying to represent has frequency components which frequency exceeds what the "canvas" you're using to represent it with can "store" (as an information) and from which the original signal can be reconstructed from. It can still happen with non-regular sampling.

Regular period sampling will just create regular patterns (which can be seen as moire in images, or typical frequency foldback sounds in audio), whereas with random or pseudo-random sampling, the patterns will be much less noticeable if at all, but there's still aliasing. It's just a lot less distracting for us humans because we can't notice the patterns, especially when dealing with images or audio.

Sampling is somewhat akin to amplitude modulation, it's the multiplication of a signal by a non-continuous function.

[NorthGuy]

Aliasing *will* occur whenever the signal you're trying to represent has frequency components which frequency exceeds what the "canvas" you're using to represent it with can "store" (as an information) and from which the original signal can be reconstructed from. It can still happen with non-regular sampling.

Regular period sampling will just create regular patterns (which can be seen as moire in images, or typical frequency foldback sounds in audio), whereas with random or pseudo-random sampling, the patterns will be much less noticeable if at all, but there's still aliasing. It's just a lot less distracting for us humans because we can't notice the patterns, especially when dealing with images or audio.

I would disagree with that. Aliasing requires regularity in both the signal and sampling. Say you sample a high-frequency sine wave using too low a frequency for your sampling, the frequencies get subtracted and you see a lower-frequency sine wave, which appears as a perfect sine wave, and there's no way for you to tell if this is the sine wave you see or it is an aliased sine wave of  higher frequency. Hence, you need a Nyquist filter to remove everything which can alias, thus giving you the certainty that you see the real thing.

If you sample white noise you will never get any aliasing no matter how low your sampling frequency is - you'll get the white noise anyway.

If you sample a perfect sine wave at random sampling intervals, you will see the sine wave if your sampling density is high enough. As your sampling density gets lower you will lose the ability to distinguish the sine wave and it'll eventually turn into white noise. However, there will be no aliasing - you will never see a sine wave of wrong frequency (except by pure coincidence as with monkey which can type encyclopedia by randomly banging a typewriter).

[RoGeorge]

How do we know that analog components are really continuous?

Many times, analog signals are not continuous, but jumps in the input signal doesn't matter.
It's the time jumps what creates the aliasing in digital domain.

Time is continuous in analog domain, and quantized in digital domain.

More intuitively said (for an infinitely long observation in time domain):

• If all you have are just snapshots of your world (like in digital domain), then you can never know for sure what happened between those snapshots. You simply don't have that information. For the particular case of a periodic signal faster than your snapshots, you will have aliasing.
• If you watch your world all the time (like in analog domain), then you know it all, there is no way to be tricked by faster signals, so aliasing won't happen.

Later edit:
-----------
Other more philosophical way to say that is:
What makes us unsure about the real frequency of a periodic signal (aliasing) is caused by the lack of complete information about that signal, and not by the shape of the input signal (like in your example with the energy levels jumps in the atom).

As an extension of the lack of complete information idea, if you can not see the whole spectrum, then you can have aliasing problems in analog domain, too. (i.e. if you have an analog modulator with an analog filter at output - so incomplete information about the spectrum - then you will not know if what you see at output is Fsignal+Fosc, or Fsignal-Fosc, so you can say it's a form of aliasing in analog domain, but it's the lack of information that makes us trouble, not the input signal).

[rhb]

Sampling is the multiplication of an analog signal by an analog  spike series.  In the frequency domain this is a convolution.  The Fourier transform of a regular spike series in time  is a regular spike series in the frequency domain.

Mixers are analog multipliers.

Aliasing occurs if the bandwidth of the analog signal is greater than the spacing of the spikes in the frequency domain.  This is why equivalent time sampling works.

If the the sampling spikes are random, then the Fourier transform is a single spike.  As a consequence, there is no aliasing.  This is a significant factor in why compressive sensing works.  TANSTAFL.  This requires that one compute the Fourier transform using least summed absolute error (L1) rather than least summed squared error (L2).  L2 has the property that it smears things in the process of finding the transform.  All conventional numerical Fourier transforms are L2.  L1 is much more compute intensive. So until recently it was not practical.

You can find a lot more on the subject in  the papers by Emmanuel Candes and David Donoho at statweb.stanford.edu. However, you'll need to understand Wiener, Shannon, Nyqist et al plus a good bit more to make sense of it.

The canonical work is, "Extrapolation, Interpolation and Smoothing of Stationary Time Series" by Norbert Wiener.  It appeared during WW II in a yellow cover indicating it was classified and was widely known as "the yellow peril" for the difficulty of the mathematics.

The best modern treatment is "Random Data" by Bendat and Piersol.

[T3sl4co1l]

Many times, analog signals are not continuous, but jumps in the input signal doesn't matter.
It's the time jumps what creates the aliasing in digital domain.

Time is continuous in analog domain, and quantized in digital domain.

No -- digital can be continuous-time as well.  Phase detectors are a simple example; they can't work otherwise!  There are unclocked CPU cores out there.  A lot of single-cycle instruction sets use the same techniques, then latch the result with a clock, probably mainly to get repeatable performance and to interface with clock-driven buses and peripherals.

The only reason clocked logic is so common, is because state machines are so easy to synthesize.

Tim

[JohnnyMalaria]

No -- digital can be continuous-time as well.  Phase detectors are a simple example; they can't work otherwise!
Tim

I'm very curious about this. An instrument I have built samples an analog photodetector signal at a fixed clock rate and uses one of two ways to determine phase (multiplication with a reference signal that has either been synthesized or from an analog reference digitized at the same rate as the signal using a SS&H ADC; or simply a digital equivalent of traditional phase sensitive detection).

[rhb]

Physical time is continuous.  Once you convert an analog signal to discrete samples, you have done the multiplication and you have the inevitable consequences of doing that.

An analog phase detector produces an analog output.  The phase difference between two sine waves is a  voltage which varies with the phase difference.  If the phase difference is constant, the voltage is DC.  This was how microwave measurements were done in the 30's and 40's and well into the 60's.   

There is no such thing as a continuous time digital signal. That is an oxymoron.

[JohnnyMalaria]

An analog phase detector produces an analog output.  The phase difference between two sine waves is a  voltage which varies with the phase difference.  If the phase difference is constant, the voltage is DC.  This was how microwave measurements were done in the 30's and 40's and well into the 60's.

Indeed.

Recently, I decided to do the blasphemous thing and choose analog detection over digital. I use two 4-quadrant multiplier/dividers to generate the I and Q components, filter the outputs and then digitize them. I'm much happier with this approach. The ADC demands are much less as are the subsequent numerical steps. When I did this originally 30 years ago, I used an EE&G-Princeton Applied Tech LIA. Nevertheless, the digital detection yields very good results.

Funny story (to me anyway). Someone patented a variant of my technique and said words to the effect, "Miller was an idiot for not using an all-digital design". Well, the instrument I built way back still beats the crapola out of existing commercial variants.

[T3sl4co1l]

There is no such thing as a continuous time digital signal. That is an oxymoron.

A continuous time digital signal is one where transitions happen at any function of real-valued time t.

A discrete time digital signal is one where the instantaneous value of a discrete time digital signal is an array X[ i ], for time indices i.  Alternately, a function where transitions only happen at integer-valued times t * Tclk, and there is no change inbetween.

The former can only be Fourier transformed.  The latter can be Z- or Fourier- (using the stepwise format) transformed.

Note that a quantized digital signal is also an analog signal plus quantization noise; this remains true even if the signal is a single bit.  There is never a case where digital signals are not analog; we can take analytical shortcuts with them (event-driven logic analysis, Z transform, binary math, etc.), as long as the assumptions hold; but digital signals never cease being analog.  Digital is a subset.

Tim

[T3sl4co1l]

No -- digital can be continuous-time as well.  Phase detectors are a simple example; they can't work otherwise!
Tim

I'm very curious about this. An instrument I have built samples an analog photodetector signal at a fixed clock rate and uses one of two ways to determine phase (multiplication with a reference signal that has either been synthesized or from an analog reference digitized at the same rate as the signal using a SS&H ADC; or simply a digital equivalent of traditional phase sensitive detection).

Somewhat as a matter of definition, that is.  Suppose you have two arbitrary digital signals, coming into a Moore type state machine.  If the signals are clocked through latches to synchronize clock domains, heh, well... oops, right?

Which isn't to say it's not possible.  If you maintain independent clock domains (using a count from one to latch a count from the other), you get a frequency detector (very common in real systems).  The output is then a digital number, as continuous as you can get here; though the resolution-bandwidth is quite poor (to get N bits of resolution, you need 2^N counts).

Note that the analog PFD yields nearly Fclk bandwidth, full resolution, and some delay -- assuming a very good loop filter, of course (which is where most of the delay would be incurred, say, a few cycles worth of group delay for a sharp cutoff at Fclk/2).

Even with the latched inputs, you can still do something; that's essentially the huff-puff control loop.  If one input leads the other, the latched values no longer match, and the control slews away; if one input lags the other, the opposite happens.  As a result, the control huffs and puffs at the difference frequency.  This works even if the clock frequency itself is very low -- the, guess what -- aliasing(!) can be used, for example, to discipline a radio to discrete channel frequencies, while tuning continuously between them.

Tim

[ejeffrey]

I would disagree with that. Aliasing requires regularity in both the signal and sampling. Say you sample a high-frequency sine wave using too low a frequency for your sampling, the frequencies get subtracted and you see a lower-frequency sine wave, which appears as a perfect sine wave, and there's no way for you to tell if this is the sine wave you see or it is an aliased sine wave of  higher frequency. Hence, you need a Nyquist filter to remove everything which can alias, thus giving you the certainty that you see the real thing.

If you sample white noise you will never get any aliasing no matter how low your sampling frequency is - you'll get the white noise anyway.

That is absolutely not true.  I mean, it is true that you get white noise out (assuming perfect delta function sampling), but that noise is aliased down into the nyquist band and reduces your SNR.  After the aliasing happens, you can't fix it, as the higher frequency noise is indistinguishable from the lower frequency signal you care about.

If you sample a perfect sine wave at random sampling intervals, you will see the sine wave if your sampling density is high enough. As your sampling density gets lower you will lose the ability to distinguish the sine wave and it'll eventually turn into white noise. However, there will be no aliasing - you will never see a sine wave of wrong frequency (except by pure coincidence as with monkey which can type encyclopedia by randomly banging a typewriter).

This is more a matter of nomenclature.  Aliasing usually refers to the effect with periodic sampling, which is very simple where all signals are folded down into the first nyquist band.  Random sampling doesn't have a simple behavior in frequency space, but the same basic affect applies: for any given record of samples there are multiple analog waveforms that could have given rise to that, and you can't tell them apart.  They are just not related by a simple frequency shift.  If you have spectrally narrow high frequency signals, random sampling will spread them out which may be desirable.  However, the signal power is still there, just spread out differently. 

[ejeffrey]

There is no such thing as a continuous time digital signal. That is an oxymoron.

Except for comparators, most classic logic gates including AND, OR, NOT, NAND, XOR, and R-S latches, and PWM drives. PWM can actually be continuous or discrete or both (where the rising edge is triggered by a clock but the falling edge can happen any time).  You can even make a continuous time sigma-delta modulator if you want to.

Unless by digital you mean "stored on a computer" in which case of course you are right, but most people consider logic gates pretty much the definition of digital, and they don't require a clock in sight.

[T3sl4co1l]

There is no such thing as a continuous time digital signal. That is an oxymoron.

Except for comparators, most classic logic gates including AND, OR, NOT, NAND, XOR, and R-S latches, and PWM drives. PWM can actually be continuous or discrete or both (where the rising edge is triggered by a clock but the falling edge can happen any time).  You can even make a continuous time sigma-delta modulator if you want to.

Unless by digital you mean "stored on a computer" in which case of course you are right, but most people consider logic gates pretty much the definition of digital, and they don't require a clock in sight.

Indeed, the continuity of (combinatorial) logic is the very problem -- propagation delays must be fully accounted for, before the state machine is latched.  This is what limits the clock speed of your CPU.

Tim

[rhb]

Fair enough, but logic gates are analog circuits which operate over a limited range.  I generally take "digital" to mean discretized, i.e. sampled.  Probably because logic gates have become so scarce.  I wish that were not the case as sometimes you really want fast bistate analog circuits.  Of course, we do have FPGAs, but those are more work to configure.

I designed a single fast pulse generator using a 7400 to turn itself off, so the pulse length was the propagation delay through the gates.  my MSOX3104T shipped today, so I'll see if I can find the thing and measure the pulse.  I was working on a cable tester to test cables for shorts and wanted a way to generate a really short pulse to test the circuit.  Building tools to build tools to build tools to .....

[rhb]

If you sample a perfect sine wave at random sampling intervals, you will see the sine wave if your sampling density is high enough. As your sampling density gets lower you will lose the ability to distinguish the sine wave and it'll eventually turn into white noise. However, there will be no aliasing - you will never see a sine wave of wrong frequency (except by pure coincidence as with monkey which can type encyclopedia by randomly banging a typewriter).

This is what I should have said if asked until about five years ago.  As it turns out, you can randomly  sample at about 1/5 of Nyquist and exactly recover multiple sine waves of different frequencies.   Moreover, aliasing does not take place because the transform of a random series of spikes is a single spike.  Very much counterintuitive.    You can arrive at the transform of the random spike series by considering the series terms pairwise.  Each pair produces a sine or cosine in the frequency domain which are only in phase at one point.  It really blows your mind to see a demonstration.  A friend showed me the Lena image with every other sample deleted. Then he showed me the image with 80% of the remaining samples randomly deleted.  It wasn't as good as the original, but *very* close.

Compressive sensing is a hot topic in academia.  I am working on implementing it on a Zynq based DSO.

https://statweb.stanford.edu/~donoho/Reports/2004/CompressedSensing091604.pdf

If you want to know why it works, be warned, the math is very complex.  In one of Donoho's papers the proof of theorem one is 15 pages! Fortunately, the other two theorems are 2-3 sentences.

The important mathematical aspect of this is presented in this paper:

https://statweb.stanford.edu/~donoho/Reports/2004/l1l0EquivCorrected.pdf

There are also proofs via regular polytopes in N dimensional space.  That was a *real* mind bender.

As a practical matter you set up Ax=y and attempt to solve it via a least absolute error (L1) method.  Linear programming is easy as you can use GLPK.  If it works, it is provably correct.  There is a very small possibility it will not work in most cases.  But it depends upon the signal being sparse in some domain so if the signal is sufficiently broadband it fails.  The requirements are that any combinations of  the columns of A have negligible crosscorrelation and that most of the elements of x are zero.  The first requirement is called the "Restricted Isometry Property" .  It's NP-hard, so you can't test it.  Solving Ax=y is also NP-hard, but if the conditions are met, an L1 algorithm will find the L0 solution.  I consider the work of Emmanuel Candes and David Donoho to be the most significant advance in applied mathematics since Wiener and Shannon.  For an old  research level reflection seismologist to say that is a *big* deal.

The entire subject is summarized in "A Mathematical Introduction to Compressive Sensing" by Foucart and Rauhut, Birkhauser 2013.

[ejeffrey]

This is what I should have said if asked until about five years ago.  As it turns out, you can randomly  sample at about 1/5 of Nyquist and exactly recover multiple sine waves of different frequencies.   Moreover, aliasing does not take place because the transform of a random series of spikes is a single spike.  Very much counterintuitive.   

Compressive sensing is a hot topic in academia.  I am working on implementing it on a Zynq based DSO.

This isn't quite true.  Random sampling still has aliases.  That is: there are multiple possible waveforms that will produce the same set of samples.  The difference is, most of those aren't a sine wave.  So if you know you are looking for one or a handful of sine waves, then you can reconstruct the signal with very low sample rates.  In a trivial limiting case, if you have a single sine wave with no noise you can reconstruct it by almost any three samples.  They can be hundreds of cycles apart, or all withing a fraction of a cycle.  All you do is standard curve fitting.

This is generally the case with compressed sensing: the signals don't have to be sine waves, but you have to have a strong prior about plausible signals.  The goal of randomized sampling is to prevent multiple plausible signals from aliasing onto each other.

[rhb]

This is what I should have said if asked until about five years ago.  As it turns out, you can randomly  sample at about 1/5 of Nyquist and exactly recover multiple sine waves of different frequencies.   Moreover, aliasing does not take place because the transform of a random series of spikes is a single spike.  Very much counterintuitive.   

Compressive sensing is a hot topic in academia.  I am working on implementing it on a Zynq based DSO.

This isn't quite true.  Random sampling still has aliases.  That is: there are multiple possible waveforms that will produce the same set of samples.  The difference is, most of those aren't a sine wave.  So if you know you are looking for one or a handful of sine waves, then you can reconstruct the signal with very low sample rates.  In a trivial limiting case, if you have a single sine wave with no noise you can reconstruct it by almost any three samples.  They can be hundreds of cycles apart, or all withing a fraction of a cycle.  All you do is standard curve fitting.

This is generally the case with compressed sensing: the signals don't have to be sine waves, but you have to have a strong prior about plausible signals.  The goal of randomized sampling is to prevent multiple plausible signals from aliasing onto each other.

Sorry, but I have to call you on the assertion that random sampling has aliases. It *does* not for precisely the reason I stated, the Fourier transform of a random spike series asymptotically approaches a spike at DC.  Five years prior to running into sparse L1 pursuits I spent a month or two studying the dissertation Bin Liu wrote under Mauricio Sacchi at Alberta on minimum weighted norm regularization.  I decided against implementing it because I couldn't figure out what the Fourier transform of a random spike series was.  And I was a year or two into compressive sensing before I finally got it.

Candes' original experiment was to recover a random combination of sine waves and impulses.  Read this:

http://statweb.stanford.edu/~candes/papers/ExactRecovery.pdf

You do not need priors.  The result is a consequence of sparsity and convex optimization.  It took me 3 years and 3000 pages to get my head around what was going on.  It's quite amazing and I think will be of equal or greater impact than Wiener's work.

Yes, it turns the world as we were taught inside out, but it's true.  I suffered through reading Foucart and Rauhut twice before I stated reading the original papers.

[NorthGuy]

This isn't quite true.  Random sampling still has aliases.  That is: there are multiple possible waveforms that will produce the same set of samples.

You need to distinguish aliases and sampling errors. For example, you're measuring 100MHz sine wave with regular sampling, but your clock is off, and it comes out as 99.95MHz sine wave. This is not aliasing. This is a consequence of various sampling errors. If you had better clock, you could've distinguished 99.95 from 100MHz just fine.

Aliasing occurs when there are two or more different waveforms which are indistinguishable in the absence of errors. In fact, errors, such as clock jitter, may make the aliased waveforms distinguishable from each other in practical terms.

If you consider random sampling, you cannot have two different waveforms which are theoretically indistinguishable. To distinguish them, you only need more sampling or more precise sampling.

[rhb]

[
Aliasing occurs when there are two or more different waveforms which are indistinguishable in the absence of errors. In fact, errors, such as clock jitter, may make the aliased waveforms distinguishable from each other in practical terms.

Aliasing is a consequence of multiplication in time being a convolution in frequency and the fact that a regular spike series in one domain is a regular spike series in the other domain.  If the spikes in the frequency domain are more closely spaced than the BW of the signal aliasing will occur.

[ejeffrey]

Sorry, but I have to call you on the assertion that random sampling has aliases. It *does* not for precisely the reason I stated, the Fourier transform of a random spike series asymptotically approaches a spike at DC.

As I explained further up thread, they aren't conventional aliases i.e., translated in frequency by a multiple of the sample rate, but the same phenomena absolutely exists.  For any particular record of samples, there are many possible analog waveforms which could generate it. This is trivially true: draw dots on a piece of paper and connect them any way you like.  There are infinitely many possibilities. If you want to interpret/treat the samples as representing a continuous analog signal, you have to decide which one you think it is.  For conventional sampling, we usually are assuming that the signal is band limited below Fs/2.  With random sampling you have to assume that the signal + noise is sufficiently sparse.

[NorthGuy]

For any particular record of samples, there are many possible analog waveforms which could generate it. This is trivially true: draw dots on a piece of paper and connect them any way you like.  There are infinitely many possibilities. If you want to interpret/treat the samples as representing a continuous analog signal, you have to decide which one you think it is.

But what if we continue sampling (assuming we have a repeatable waveform)? The random sampling will be able to reconstruct the underlying waveform better and better. Given enough time, you can reconstruct any curve, no matter how the original dots are connected.

This is not the case with conventional sampling. Additional sampling will eventually stop providing new information. In extreme case, if you sample a sine wave with sampling rate matching the frequency, the inflow of new information will stop after only one sample, and all the other samples will be exactly the same to the rest of eternity.

[rhb]

For any particular record of samples, there are many possible analog waveforms which could generate it. This is trivially true: draw dots on a piece of paper and connect them any way you like.  There are infinitely many possibilities. If you want to interpret/treat the samples as representing a continuous analog signal, you have to decide which one you think it is.

But what if we continue sampling (assuming we have a repeatable waveform)? The random sampling will be able to reconstruct the underlying waveform better and better. Given enough time, you can reconstruct any curve, no matter how the original dots are connected.

This is not the case with conventional sampling. Additional sampling will eventually stop providing new information. In extreme case, if you sample a sine wave with sampling rate matching the frequency, the inflow of new information will stop after only one sample, and all the other samples will be exactly the same to the rest of eternity.

The quotation attributed to me above is incorrect.  I did not write that.

As for what follows, it has nothing to do with compressive sensing.  The random sampling technique described was used in sampling scopes particularly for microwave when ADCs had no hope of keeping up.  It worked because the signal was periodic.

The extreme case cited above violates the Nyquist criterion.  But a sinusoid can be completely described with 3 samples.

Compressive sensing works by finding the Fourier transform using an L1, rather than the traditional L2 method.  Once one has the transform one does an inverse transform using a conventional FFT to recover the time domain signal at regular sample spacing.

[NorthGuy]

The quotation attributed to me above is incorrect.  I did not write that.

I'm sorry. I messed up the quotes again. I fixed the original post.

[SiliconWizard]

For any particular record of samples, there are many possible analog waveforms which could generate it. This is trivially true: draw dots on a piece of paper and connect them any way you like.  There are infinitely many possibilities. If you want to interpret/treat the samples as representing a continuous analog signal, you have to decide which one you think it is.

But what if we continue sampling (assuming we have a repeatable waveform)? The random sampling will be able to reconstruct the underlying waveform better and better. Given enough time, you can reconstruct any curve, no matter how the original dots are connected.

Absolutely, and I think this is where we were probably not all talking about the same thing. Given a periodic signal and infinite time, random-spaced sampling will lead to perfect reconstruction, whereas evenly spaced sampling won't if the Nyquist principle is not met. You're right.

Now on arbitrary signals (non periodic) and unsufficient sampling density, randomly spaced or not, you will get aliasing of some sort in the general case.

[rhb]

If you sample any arbitrary signal and perform an FFT, you are getting the discrete Fourier transform of a  signal which is periodic  over the period of the record.  This is inherent in the definition of the discrete Fourier transform.

For the continuous Fourier transform, the limits of integration are +/- infinity.  This imposes some constraints on what functions have Fourier transforms.

Random sampling of a periodic signal as was done in some early sampling oscilloscopes is not the same as random sampling as it applies to compressive sensing.

For any arbitrary signal which is periodic with a period equal to the length of the series.  That is, for which you accept the constraint of the discrete Fourier transform ,the discrete Fourier transform can be perfectly recovered with 10-20% of Nyquist sample density if two conditions are met.  The sampling intervals are random and the signal is sparse in the frequency domain.  Except for Gaussian noise,  most signals of interest are sparse in the frequency domain.  Were this not the case, image and audio compression would not be possible.

What Donoho proved was that it is not necessary to acquire data at Nyquist rates.  This is currently being done routinely at Stanford Medical Center for MRI data as it gives a factor of 5-10x reduction in data acquisition time and makes possible things like real time MRI imaging, albeit at the price of a lot of computer resources.  The reduction in data acquisition time was initially of most benefit with pediatric patients who tended to fidget.

You do not get "aliasing" in the Nyquist sense that a frequency above 1/2 the sampling rate appears in the data as a lower frequency in the case of random sampling unless the "random" sampling is not actually random.  You do get a convolution in the frequency domain.   But the Fourier transform of the random sequence is a spike at DC and very low amplitude white noise at every other  frequency.  If the series is infinitely long it converges to a Dirac function which is convolved with the true spectrum of the signal yielding the true spectrum of the signal without any aliasing.  This applies to *any* arbitrary signal.

In physically realizable implementations time is quantized.  This imposes some constraints on the bandwidth that can be acquired by compressive sensing as does the length of the series.  This is discussed to some degree in Foucart and Rauhut, but i still find the matter a bit opaque.  Experience has shown that a 5-10x increase in bandwidth relative to the number of samples collected is typically possible.

None of this in any way contradicts Wiener, Shannon and Nyquist.  It's merely a special case which was not explored until recently because sufficient computer resources were not available.  Compressive sensing can  also be set up to suppress noise in the input data in the same manner that can be done by applying a threshold to the eigenvalues in a K-L transform.

[SiliconWizard]

Yes, I've read the paper and it's interesting, although pretty hairy. It's quite a bit more involved than just taking some samples in the time domain at random intervals. So again, I'm not sure we are all exactly thinking of this in the same manner nor for the same practical applications.

In all cases, and as some have mentioned, even though it may sound too trivial, if your time-domain samples happen to lie outside of some chunks of signal, you're just going to lose this information. Let's say we have a portion of signal that is zero everywhere except there is just a short pulse in between. Let's say all the random samples happen to lie only on zero. No way you're going to reconstruct the lost "pulse". Now if you can repeat random sampling on the same chunk of signal (window) enough times, you will eventually get enough samples. But for a *one-shot* record of limited density samples, you can't guarantee that. I think that is mostly what some of us meant. Now if you happen to know approximately where the information of interest will lie time-wise, that's a different story. Also, if you consider your signal in the frequency domain rather than in the time domain, it's also a bit different. But you'd have to get the spectrum first. Back to square one.

We are also confusing exact reconstruction of a bandwith-limited signal with lossy compression. Although both can lead to useful results, those are not exactly the same in the general case. It's sometimes more useful to know beforehand what you're going to lose spectral-wise than to know that what you're going to lose shouldn't matter much. Different use cases, although admittedly both can be close enough under specific assumptions. Of course I'm simplifying the concept but it's just to provoke some thoughts.

Also, in practice, getting randomly-distributed samples is not possible. You can just hope to approach randomness. And if you are in the digital domain, it will be pseudo-random anyway, given that you always deal with finite time resolution, even if you can get random generators from sophisticated analog stuff. Might be good enough, but it's not quite the theoretical randomness.

Anyway, looks like it has been discussed before in the following thread: https://www.eevblog.com/forum/projects/shannon-and-nyquist-not-necessary/

For those interested, some papers:

https://statweb.stanford.edu/~donoho/Reports/2004/CompressedSensing091604.pdf
https://www.researchgate.net/publication/268747805_Reconstruction_of_Sub-Nyquist_Random_Sampling_for_Sparse_and_Multi-Band_Signals

[rhb]

Yes, I've read the paper and it's interesting, although pretty hairy. It's quite a bit more involved than just taking some samples in the time domain at random intervals. So again, I'm not sure we are all exactly thinking of this in the same manner nor for the same practical applications.

In all cases, and as some have mentioned, even though it may sound too trivial, if your time-domain samples happen to lie outside of some chunks of signal, you're just going to lose this information. Let's say we have a portion of signal that is zero everywhere except there is just a short pulse in between. Let's say all the random samples happen to lie only on zero. No way you're going to reconstruct the lost "pulse". Now if you can repeat random sampling on the same chunk of signal (window) enough times, you will eventually get enough samples. But for a *one-shot* record of limited density samples, you can't guarantee that. I think that is mostly what some of us meant. Now if you happen to know approximately where the information of interest will lie time-wise, that's a different story. Also, if you consider your signal in the frequency domain rather than in the time domain, it's also a bit different. But you'd have to get the spectrum first. Back to square one.

We are also confusing exact reconstruction of a bandwith-limited signal with lossy compression. Although both can lead to useful results, those are not exactly the same in the general case. It's sometimes more useful to know beforehand what you're going to lose spectral-wise than to know that what you're going to lose shouldn't matter much. Different use cases, although admittedly both can be close enough under specific assumptions. Of course I'm simplifying the concept but it's just to provoke some thoughts.

Also, in practice, getting randomly-distributed samples is not possible. You can just hope to approach randomness. And if you are in the digital domain, it will be pseudo-random anyway, given that you always deal with finite time resolution, even if you can get random generators from sophisticated analog stuff. Might be good enough, but it's not quite the theoretical randomness.

Anyway, looks like it has been discussed before in the following thread: https://www.eevblog.com/forum/projects/shannon-and-nyquist-not-necessary/

For those interested, some papers:

https://statweb.stanford.edu/~donoho/Reports/2004/CompressedSensing091604.pdf
https://www.researchgate.net/publication/268747805_Reconstruction_of_Sub-Nyquist_Random_Sampling_for_Sparse_and_Multi-Band_Signals

Take a regularly sampled series which is zero everywhere except for a single one.  Phase shift it by half a sample interval and look at it in the time domain.  You will see a sinc(t) function.  The only reason it looks like a spike is that all the zeros of the sinc(t) coincide with the other regular samples.

With random sampling, the sinc(t) will be recoverable just as readily as with regular sampling.

It's a *lot* more involved than just taking random samples in the time domain.  The randomness is essential to being able to solve an L0 problem in L1 time.  It's also essential to suppressing aliasing which I suspect is the reason it was done with sampling scopes.

I can't speak for others, but I'm not confusing lossy compression with exact recovery.  Exact recovery has been demonstrated in the noise free case.  In the real world noise is always present.  Do you really want to keep the noise?  Or do you want to eliminate terms which are 120 dB down from the largest component?