On Unlimited Sampling

Ayush Bhandari, Felix Krahmer, Ramesh RaskararXiv 2017 · DOI · OpenReview

Abstract

Shannon's sampling theorem provides a link between the continuous and the discrete realms stating that bandlimited signals are uniquely determined by its values on a discrete set. This theorem is realized in practice using so called analog--to--digital converters (ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in dynamic range. Whenever a signal exceeds some preset threshold, the ADC saturates, resulting in aliasing due to clipping. The goal of this paper is to analyze an alternative approach that does not suffer from these problems. Our work is based on recent developments in ADC design, which allow for ADCs that reset rather than to saturate, thus producing modulo samples. An open problem that remains is: Given such modulo samples of a bandlimited function as well as the dynamic range of the ADC, how can the original signal be recovered and what are the sufficient conditions that guarantee perfect recovery? In this paper, we prove such sufficiency conditions and complement them with a stable recovery algorithm. Our results are not limited to certain amplitude ranges, in fact even the same circuit architecture allows for the recovery of arbitrary large amplitudes as long as some estimate of the signal norm is available when recovering. Numerical experiments that corroborate our theory indeed show that it is possible to perfectly recover function that takes values that are orders of magnitude higher than the ADC's threshold.

Introduction: Breaking the Dynamic Range Barrier

In digital signal processing, Shannon’s Sampling Theorem dictates the necessary rate to reconstruct a signal perfectly. However, physical Analog-to-Digital Converters (ADCs) are constrained by a fixed dynamic range $[-\lambda, \lambda]$. When a signal exceeds this threshold, the ADC saturates, causing non-linear clipping that permanently destroys information.

Comparison between a traditional ADC (clipping) and a self-reset ADC (modulo folding), with image recovery results.

This paper introduces the "Unlimited Sampling" framework, which utilizes Self-Reset ADCs (SR-ADCs). Instead of clipping, these converters "wrap around" the signal, producing modulo samples. This approach effectively trades sampling frequency for dynamic range, allowing for the recovery of signals with amplitudes far exceeding the hardware threshold.

Methods and Theoretical Framework

The proposed system models the SR-ADC output as $z(t) = \mathcal{M}_\lambda(g(t))$, where $\mathcal{M}_\lambda$ is a modulo operation. The recovery process hinges on two key mathematical insights:

  1. Higher-Order Finite Differences: By sampling a smooth, bandlimited signal at a sufficiently high rate, the difference between adjacent samples becomes smaller than the threshold $\lambda$.
  2. Commutativity: Under specific conditions, the modulo operation and the finite difference operator commute. This allows the algorithm to "unwrap" the signal by calculating underlying changes despite the resets.
Extracted figure from page 4 of On Unlimited Sampling

The authors establish a sufficiency condition for perfect recovery: the sampling period $T$ must satisfy $T \leq \frac{1}{2\pi e}$. This implies that by oversampling by a factor of approximately $2.71$ relative to the Nyquist rate, signals of arbitrary height can be reconstructed.

Key Results and Numerical Validation

The theory was validated using synthetic bandlimited signals and numerical simulations. Key findings include:

  • Machine Precision Recovery: The algorithm achieved reconstruction errors on the order of $10^{-33}$, even for signals 20 times larger than the ADC threshold.
  • Modular Decomposition: The authors proved that any bandlimited signal can be decomposed into its modulo samples plus a step function representing the integer number of resets.
  • Hardware Agnosticism: The "unlimited" property means that the same hardware architecture can handle increasingly large signals simply by increasing the order of finite differences used in the software reconstruction.

Discussion and Future Directions

While the $T \leq \frac{1}{2\pi e}$ bound is mathematically rigorous, empirical evidence suggests it may be conservative, with recovery possible at lower rates. Future work will address the algorithm's sensitivity to high-variance additive noise and its extension to non-bandlimited signals, such as those in shift-invariant spaces. Additionally, while prototype SR-ADCs exist, the practical implementation of high-speed, high-precision self-resetting circuits remains a significant engineering challenge.

Summary updated

Abstract

Shannon's sampling theorem provides a link between the continuous and the discrete realms stating that bandlimited signals are uniquely determined by its values on a discrete set. This theorem is realized in practice using so called analog--to--digital converters (ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in dynamic range. Whenever a signal exceeds some preset threshold, the ADC saturates, resulting in aliasing due to clipping. The goal of this paper is to analyze an alternative approach that does not suffer from these problems. Our work is based on recent developments in ADC design, which allow for ADCs that reset rather than to saturate, thus producing modulo samples. An open problem that remains is: Given such modulo samples of a bandlimited function as well as the dynamic range of the ADC, how can the original signal be recovered and what are the sufficient conditions that guarantee perfect recovery? In this paper, we prove such sufficiency conditions and complement them with a stable recovery algorithm. Our results are not limited to certain amplitude ranges, in fact even the same circuit architecture allows for the recovery of arbitrary large amplitudes as long as some estimate of the signal norm is available when recovering. Numerical experiments that corroborate our theory indeed show that it is possible to perfectly recover function that takes values that are orders of magnitude higher than the ADC's threshold.
BibTeX
@misc{bhandari2017unlimited,
  author = {Ayush Bhandari and Felix Krahmer and Ramesh Raskar},
  title = {{On Unlimited Sampling}},
  year = {2017},
  eprint = {1707.06340},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.06340},
}
Figure