Editing Fourier analysis (section)

===Discrete Fourier transform (DFT)===
{{main|Discrete Fourier transform}}

Similar to a Fourier series, the DTFT of a periodic sequence, <math>s_{_N}[n],</math> with period <math>N</math>, becomes a Dirac comb function, modulated by a sequence of complex coefficients (see {{slink|DTFT|Periodic data}})''':'''

:<math>S[k] = \sum_n s_{_N}[n]\cdot e^{-i2\pi \frac{k}{N} n}, \quad k\in\Z,</math> &nbsp; &nbsp; (where <math>\sum_{n}</math> is the sum over any sequence of length <math>N.</math>)

The <math>S[k]</math> sequence is customarily known as the '''DFT''' of one cycle of <math>s_{_N}.</math> It is also <math>N</math>-periodic, so it is never necessary to compute more than <math>N</math> coefficients. The inverse transform, also known as a [[discrete Fourier series]], is given by''':'''

:<math>s_{_N}[n] = \frac{1}{N} \sum_{k} S[k]\cdot e^{i2\pi \frac{n}{N}k},</math> &nbsp; where <math>\sum_{k}</math> is the sum over any sequence of length <math>N.</math>

When <math>s_{_N}[n]</math> is expressed as a [[periodic summation]] of another function''':'''

:<math>s_{_N}[n]\, \triangleq\, \sum_{m=-\infty}^{\infty} s[n-mN],</math> &nbsp; and &nbsp; <math>s[n]\, \triangleq\, T\cdot s(nT),</math>

the coefficients are samples of <math>S_\tfrac{1}{T}(f)</math> at discrete intervals of <math>\tfrac{1}{P} = \tfrac{1}{NT}</math>''':'''

:<math>S[k] = S_\tfrac{1}{T}\left(\frac{k}{P}\right).</math>

Conversely, when one wants to compute an arbitrary number <math>(N)</math> of discrete samples of one cycle of a continuous DTFT, <math>S_\tfrac{1}{T}(f),</math> it can be done by computing the relatively simple DFT of <math>s_{_N}[n],</math> as defined above. In most cases, <math>N</math> is chosen equal to the length of the non-zero portion of <math>s[n].</math> Increasing <math>N,</math> known as ''zero-padding'' or ''interpolation'', results in more closely spaced samples of one cycle of <math>S_\tfrac{1}{T}(f).</math> Decreasing <math>N,</math> causes overlap (adding) in the time-domain (analogous to [[aliasing]]), which corresponds to decimation in the frequency domain. (see {{slink|Discrete-time Fourier transform|2=L=N×I}}) In most cases of practical interest, the <math>s[n]</math> sequence represents a longer sequence that was truncated by the application of a finite-length [[window function]] or [[FIR filter]] array.

The DFT can be computed using a [[fast Fourier transform]] (FFT) algorithm, which makes it a practical and important transformation on computers.

See [[Discrete Fourier transform]] for much more information, including''':'''
* transform properties
* applications
* tabulated transforms of specific functions