In effect, modern information-capture devices, such as audio recorder, camera or telephone, include an analog-to-digital converter (ADC) — a circuit converting the fluctuating voltages of analog signals into ones and zeroes.
However, nearly all commercial ADCs have voltage limits. When this limit is exceeded by an incoming signal, the ADC cuts it off or flatlines it at the maximum voltage. This event is well known as the skips and pops of a “clipped” audio signal, or as “saturation” in digital images, for example, when a sky that seems blue to the naked human eye, looks white when captured on camera.
In the past week, at the International Conference on Sampling Theory and Applications, Scientists from MIT and the Technical University of Munich demonstrated a method known as unlimited sampling that has the ability to precisely digitize signals with voltage peaks considerably greater than the voltage limit of an ADC.
The result could be cameras with the ability to capture all the gradations of color that can be seen by the naked human eye, audio that does not skip and medical and environmental sensors with the ability to control long low-activity periods and the unexpected signal spikes that are mostly of interest.
However, the most significant outcome of the paper is theoretical. The Researchers deduce a lower bound of the rate at which an analog signal that has large voltage fluctuations ought to be measured, or “sampled,” to make sure that it can be precisely digitized. Thus, their study furthers one of the various seminal outcomes of longtime MIT Professor Claude Shannon’s revolutionary 1948 paper titled “A Mathematical Theory of Communication,” the Nyquist-Shannon sampling theorem.
Ayush Bhandari who is a Graduate Student of Media Arts and Sciences at MIT is the first author on the paper. He has collaborated with Ramesh Raskar, his Thesis Advisor as well as an Associate Professor of Media Arts and Sciences, as well as Felix Krahmer, an Assistant Professor of Mathematics at the Technical University of Munich.
The study carried out by the research team was motivated by an innovative kind of experimental ADC that captures the “modulo” of a signal and not its voltage. While considering the new ADCs, modulo is nothing but the remainder obtained while dividing voltage of an analog signal by the maximum voltage of the ADC.
The idea is very simple. If you have a number that is too big to store in your computer memory, you can take the modulo of the number. The act of taking the modulo is just to store the remainder. The modulo architecture is also called the self-reset ADC. By self-reset, what it means is that when the voltage crosses some threshold, it resets, which is actually implementing a modulo. The self-reset ADC sensor was proposed in electronic architecture a couple years back, and ADCs that have this capability have been prototyped.
Ayush Bhandari, Graduate Student of Media Arts and Sciences, MIT
One such prototype was developed to capture information related to firing of neurons inside the brain of mouse. Compared to the baseline voltage of a neuron which is low, the unexpected voltage spikes at the time of neuron firing are considerably higher. It is challenging to develop a sensor with adequate sensitivity to recognize the baseline voltage but without getting saturated during the voltage spikes.
If the voltage limit of a self-reset ADC is exceeded by a signal, it is cut off and it restarts at the minimum voltage of the circuit. Likewise, if the signal falls short of the minimum voltage of the circuit, it gets reset to the maximum voltage. In case the peak voltage of the signal is multiple times the voltage limit, the signal will have the ability to wrap around itself repeatedly.
This causes difficulties in digitization, which is the process of sampling an analog signal — typically, carrying out numerous discrete measurements of its voltage. The Nyquist-Shannon theorem deduces the number of measurements that are mandatory for precise reconstruction of the signal.
However, prevalent sampling algorithms presume that the signal continuously fluctuates up and down. In actuality, if a self-reset ADC’s signal is sampled just prior to exceeding the maximum, and once more immediately after the circuit is reset, the standard sampling algorithm assumes it to be a signal with a voltage that gets decreased between the two measurements, as against a signal with increasing voltage.
Bhandari and his team were inquisitive to know the number of samples needed to resolve this ambiguity and to know the technique for reconstructing the original signal. They discovered that the number of samples proposed by the Nyquist-Shannon theorem, multiplied by Euler’s number e and pi, or approximately 8.5, will assure reliable reconstruction.
The reconstruction algorithm developed by the research team is dependent on certain competent mathematics. In the case of a self-reset ADC, the modulo of the true voltage is equal to the voltage sampled following a reset. Thus, recovery of the true voltage is achieved by adding numerous times the maximum voltage of ADC (or M) to the sampled value. However, the exact value of that multiple (i.e. M, 2M, 5M, 10M, etc.) is not known.
The derivative is the most fundamental concept in calculus, and provides a formula for computing the slope of a curve at any given point. However, in the case of computer science, arithmetic approximation of derivatives is largely prevalent. For example, assume that there is a series of samples from an analog signal, and take the difference between samples one and two and store it.
Subsequently, take the difference between samples two and three, and store it. Repeat the same for samples three and four, and so forth. The end outcome will be a series of values that round off the derivative of the sampled signal.
Thus, the derivative of the true signal sent to a self-reset ADC is equal to the sum of the derivative of its modulo and the derivative of a set of multiples of the threshold voltage, (i.e. the Ms, 2Ms, 5Ms, etc.). However, the derivative of multiples of M is in itself regularly a series of multiples of M. This is because the difference between two consecutive multiples of M is always equal to another multiple of M.
At this point, taking the modulo of both derivatives into account, all the multiples of M vanish as they do not generate any remainder upon being divided by M. Thus, the modulo of the true signal derivative is equal to the modulo of the modulo signal’s derivative.
Moreover, inversion of the derivative is one of the fundamental operations in calculus. However, deducing the original signal mandates the addition of a multiple of M with an unknown value that has to be deduced. Luckily, if an inaccurate multiple of M is used, it results in largely improbable signal voltages. The proof of the theoretical result proposed by the research team included an argument related to the number of samples required to ensure that the correct multiple of M is deduced.
“If you have the wrong constant, then the constant has to be wrong by a multiple of M,” stated Krahmer. “So if you invert the derivative, that adds up very quickly. One sample will be correct, the next sample will be wrong by M, the next sample will be wrong by 2M, and so on. We need to set the number of samples to make sure that if we have the wrong answer in the previous step, our reconstruction would grow so large that we know it can’t be correct.”
Unlimited sampling is an intriguing concept that addresses the important and real issue of saturation in analog-to-digital converters. It is promising that the computations required to recover the signal from modulo measurements are practical with today’s hardware. Hopefully this concept will spur the development of the kind of sampling hardware needed to make unlimited sampling a reality.
Richard Baraniuk, One of the Co-Inventors of the single-pixel camera and a Professor of Electrical and Computer Engineering, Rice University