Discrete-time Fourier transform

In mathematics, the discrete-time Fourier transform (DTFT), also called the finite Fourier transform, is a form of Fourier analysis that is applicable to a sequence of values. The DTFT is often used to analyze samples of a continuous function. The term discrete-time refers to the fact that the transform operates on discrete data, often samples whose interval has units of time. From uniformly spaced samples it produces a function of frequency that is a periodic summation of the continuous Fourier transform of the original continuous function. Under certain theoretical conditions, described by the sampling theorem, the original continuous function can be recovered perfectly from the DTFT and thus from the original discrete samples. The DTFT itself is a continuous function of frequency, but discrete samples of it can be readily calculated via the discrete Fourier transform (DFT) (see ), which is by far the most common method of modern Fourier analysis. Both transforms are invertib

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Mikhail Kapralov, Amir Zandieh

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple" Fourier structure - e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.

ASSOC COMPUTING MACHINERY2019

Continuous-Time AR Model Identification: Does Sampling Rate Really Matter?

Hagay Kirshner, Simona Maggio, Michaël Unser

We address the problem of identifying continuous-time auto regressive (CAR) models from sampled data. The exponential nature of CAR autocorrelation functions is taken into account by means of exponential B-splines modelling, allowing one to associate the available digital data with a CAR model. A maximum likelihood (ML) estimator is then derived for identifying the optimal parameters; it relies on an exact discretization of the sampled version of the continuous-time model. We provide both time- and frequency-domain interpretations of the proposed estimator, while introducing a weighting function that describes the CAR power spectrum by means of discrete Fourier transform values. We present experimental results demonstrating that the proposed exponential-based ML estimator outperforms currently available polynomial-based methods, while achieving Cramér-Rao lower bound values even for relatively low sampling rates.

EURASIP2010

A 4.8pJ/b 6Gb/s ADC-Based PAM-4 Wireline Receiver Data -Path with Cyclic Prefix in 14nm FinFET

Cosimo Aprile, Andreas Peter Burg, Alessandro Cevrero, Gain Kim, Lukas Kull, Yusuf Leblebici, Ilter Ozkaya, Thomas Toifl

This work presents an ADC-bascd receiver (RX) data-path for frame-based PAM-4 modulation with a cyclic prefix (CP). Similar to discrete multi-tone (DMT) modulation, a frame of PAM-4 symbols arc protected from the channel delay spread by the CP taps. A PAM-4 frame window including CP taps is viewed as a DMT symbol and is equalized similarly to a DMT signal equalization, based on a discrete-time Fourier transform (DFT) and frequency-domain equalizer (FDE). The RX prototype implemented in 14nm FinFET achieves 56Gb/s datarate at less than 3c-5 pre-FEC BER over a 19dB loss channel at 14GHz dissipating 270mW including the ADC and the DSP data-path excluding the inverse DFT and the BER checker.

IEEE2019

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Mikhail Kapralov, Amir Zandieh

ASSOC COMPUTING MACHINERY2019