Editing Discrete Fourier transform (section)

{{Short description|Function in discrete mathematics}}
{{distinguish|text=the [[discrete-time Fourier transform]]}}
{{Fourier transforms}}

[[File:From Continuous To Discrete Fourier Transform.gif|class=skin-invert-image|thumb|400px|Fig 1: Relationship between the (continuous) [[Fourier transform]] and the discrete Fourier transform.{{br}}'''Left:''' A continuous function (top) and its Fourier transform (bottom).{{br}}'''Center-left:''' [[Periodic summation]] of the original function (top).  Fourier transform (bottom) is zero except at discrete points.  The inverse transform is a sum of sinusoids called [[Fourier series]]. {{br}}'''Center-right:''' Original function is discretized (multiplied by a [[Dirac comb]]) (top).  Its Fourier transform (bottom) is a periodic summation ([[Discrete-time Fourier transform|DTFT]]) of the original transform.{{br}}'''Right:''' The DFT (bottom) computes discrete samples of the continuous DTFT.  The inverse DFT (top) is a periodic summation of the original samples.  The [[Fast Fourier transform|FFT]] algorithm computes one cycle of the DFT and its inverse is one cycle of the DFT inverse.]]

[[File:Fourier transform, Fourier series, DTFT, DFT.svg|class=skin-invert-image|thumb|400px|Fig 2: Depiction of a Fourier transform (upper left) and its periodic summation (DTFT) in the lower left corner.  The spectral sequences at (a) upper right and (b) lower right are respectively computed from (a) one cycle of the periodic summation of s(t) and (b) one cycle of the periodic summation of the s(nT) sequence.  The respective formulas are (a) the [[Fourier series]] <u>integral</u> and (b) the '''DFT''' <u>summation</u>.  Its similarities to the original transform, S(f), and its relative computational ease are often the motivation for computing a DFT sequence.]]

In [[mathematics]], the '''discrete Fourier transform''' ('''DFT''') converts a finite sequence of equally-spaced [[Sampling (signal processing)|samples]] of a [[function (mathematics)|function]] into a same-length sequence of equally-spaced samples of the [[discrete-time Fourier transform]] (DTFT), which is a [[complex number|complex-valued]] function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence.{{efn-ua|
Equivalently, it is the ratio of the sampling frequency and the number of samples.}}<ref>Taboga, Marco (2021). "Discrete Fourier Transform - Frequencies", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform-frequencies.</ref>&nbsp; An inverse DFT (IDFT) is a [[Fourier series]], using the DTFT samples as coefficients of [[complex number|complex]] [[Sine wave|sinusoid]]s at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence.  The DFT is therefore said to be a [[frequency domain]] representation of the original input sequence.  If the original sequence spans all the non-zero values of a function, its DTFT is continuous (and periodic), and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

The DFT is used in the [[Fourier analysis]] of many practical applications.<ref name=Strang/> In [[digital signal processing]], the function is any quantity or [[signal (information theory)|signal]] that varies over time, such as the pressure of a [[sound wave]], a [[radio]] signal, or daily [[temperature]] readings, sampled over a finite time interval (often defined by a [[window function]]<ref name=Sahidullah/>). In [[image processing]], the samples can be the values of [[pixel]]s along a row or column of a [[raster image]]. The DFT is also used to efficiently solve [[partial differential equations]], and to perform other operations such as [[convolution]]s or multiplying large integers.

Since it deals with a finite amount of data, it can be implemented in [[computer]]s by [[numerical algorithm]]s or even dedicated [[digital circuit|hardware]]. These implementations usually employ efficient [[fast Fourier transform]] (FFT) algorithms;<ref name=Cooley/> so much so that the terms "FFT" and "DFT" are often used interchangeably. Prior to its current usage, the "FFT" [[initialism]] may have also been used for the ambiguous term "[[Finite Fourier transform (disambiguation)|finite Fourier transform]]".