**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Discrete-time Fourier transform

Summary

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

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (39)

Loading

Loading

Loading

Related people (6)

Related concepts (29)

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time F

Fourier transform

In physics and mathematics, the Fourier transform (FT) is a transform that converts a function into a form that describes the frequencies present in the original function. The output of the transfo

Convolution theorem

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms

Related courses (33)

This class teaches the theory of linear time-invariant (LTI) systems. These systems serve both as models of physical reality (such as the wireless channel) and as engineered systems (such as electrical circuits, filters and control strategies).

Ce cours aborde la théorie des systèmes linéaires discrets invariants par décalage (LID). Leurs propriétés et caractéristiques fondamentales y sont discutées, ainsi que les outils fondamentaux permettant de les étudier (transformée de Fourier et transformée en Z).

This course teaches the students practical skills needed for solving modern physics problems by means of computation. A number of examples illustrate the utility of numerical computations in various domains of physics.

Related lectures (80)

Related units (5)

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.

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.

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.