Lecture

Fast Fourier Transform: Basics and Applications

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

EE-350: Signal processing

Dans ce cours, nous présentons les méthodes de base du traitement des signaux. ...

Description

This lecture covers the basics of the Fast Fourier Transform (FFT) algorithm, which is used to efficiently calculate the Discrete Fourier Transform (DFT). Starting with the definition of FFT and its significance in signal processing, the instructor explains the process of dividing a signal into two sequences and recursively applying FFT. The lecture also delves into the steps involved in FFT, illustrating with an example of order N=8. Furthermore, the complexity of correlation and convolution of signals of length N is discussed, highlighting the advantages of FFT over direct calculation methods.

Instructors (2)

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Jean-Philippe Thiran

Jean-Philippe Thiran was born in Namur, Belgium, in August 1970. He received the Electrical Engineering degree and the PhD degree from the Université catholique de Louvain (UCL), Louvain-la-Neuve, Belgium, in 1993 and 1997, respectively. From 1993 to 1997, he was the co-ordinator of the medical image analysis group of the Communications and Remote Sensing Laboratory at UCL, mainly working on medical image analysis. Dr Jean-Philippe Thiran joined the Signal Processing Institute (ITS) of the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in February 1998 as a senior lecturer. He was promoted to Assistant Professor in 2004, to Associate Professor in 2011 and is now a Full Professor since 2020. He also holds a 20% position at the Department of Radiology of the University of Lausanne (UNIL) and of the Lausanne University Hospital (CHUV) as Associate Professor ad personam. Dr Thiran's current scientific interests include Computational medical imaging: acquisition, reconstruction and analysis of imaging data, with emphasis on regularized linear inverse problems (compressed sensing, convex optimization). Applications to medical imaging: diffusion MRI, ultrasound imaging, inverse planning in radiotherapy, etc.Computer vision & machine learning: image and video analysis, with application to facial expression recognition, eye tracking, lip reading, industrial inspection, medical image analysis, etc.

Official source

Ontological neighbourhood

Information engineering

Signal processing: Fourier analysis

Related concepts (32)

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 Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies.

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical.

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 transform is a complex-valued function of frequency. The term Fourier transform refers to both this complex-valued function and the mathematical operation. When a distinction needs to be made the Fourier transform is sometimes called the frequency domain representation of the original function.

Non-uniform discrete Fourier transform

In applied mathematics, the nonuniform discrete Fourier transform (NUDFT or NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discrete-time Fourier transform, but in which the input signal is not sampled at equally spaced points or frequencies (or both). It is a generalization of the shifted DFT. It has important applications in signal processing, magnetic resonance imaging, and the numerical solution of partial differential equations.

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.

Related lectures (64)

Properties of Time-Frequency Domain Signals

Covers the main properties of time-frequency domain signals and their limitations.

Signal Processing Fundamentals

Covers signal processing, electric circuits, Fourier Transform, Kirchhoff's laws, and practical applications in various fields.

Signal Processing Fundamentals

Explores signal processing fundamentals, including discrete time signals, spectral factorization, and stochastic processes.

Signal Processing Fundamentals

Covers the basics of signal processing and electric circuits.

Fast Fourier Transform

Explains the Fast Fourier Transform, a fast algorithm for calculating the Discrete Fourier Transform.

Related concepts (32)

Discrete Fourier transform

Fast Fourier transform

Fourier transform

Non-uniform discrete Fourier transform

Discrete-time Fourier transform