Editing Discrete Fourier transform (section)

==Definition==
The ''discrete Fourier transform'' transforms a [[sequence]] of ''N'' [[complex number]]s <math>   \left \{ \mathbf{x}_n \right \} := x_0, x_1, \ldots, x_{N-1}</math> into another sequence of complex numbers,  <math>\left \{ \mathbf{X}_k \right \} := X_0, X_1, \ldots, X_{N-1},</math> which is defined by:

{{Equation box 1|title=Discrete Fourier transform
|indent =: |cellpadding= 6 |border |border colour = #0073CF |background colour=#F5FFFA
|equation = {{NumBlk|:|
<math>X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi \tfrac{k}{N}n}</math> &nbsp; &nbsp;
|{{EquationRef|Eq.1}}}}
}}

The transform is sometimes denoted by the symbol <math>\mathcal{F}</math>, as in <math>\mathbf{X} = \mathcal{F} \left \{ \mathbf{x} \right \} </math> or <math>\mathcal{F} \left ( \mathbf{x} \right )</math> or <math>\mathcal{F} \mathbf{x}</math>.{{efn-ua|
As a [[linear transformation]] on a [[Dimension (vector space)|finite-dimensional vector space]], the DFT expression can also be written in terms of a [[DFT matrix]]; when scaled appropriately it becomes a [[unitary matrix]] and the ''X''<sub>''k''</sub> can thus be viewed as coefficients of ''x'' in an [[orthonormal basis]].}}

{{EquationNote|Eq.1}} can be interpreted or derived in various ways, for example:{{unordered list|
| It completely describes the [[discrete-time Fourier transform]] (DTFT) of an <math>N</math>-periodic sequence, which comprises only discrete frequency components.{{
efn-ua|The non-zero components of a DTFT of a periodic sequence is a discrete set of frequencies identical to the DFT.
}} ([[Discrete-time Fourier transform#Periodic data|Using the DTFT with periodic data]])
| It can also provide uniformly spaced samples of the continuous DTFT of a finite length sequence.  ({{slink|Discrete-time Fourier transform|Sampling the DTFT|nopage=y}})
| It is the [[cross correlation]] of the ''input'' sequence, <math>x_n</math>, and a complex sinusoid at frequency <math display="inline">\frac{k}{N}.</math> Thus it acts like a [[matched filter]] for that frequency.
| It is the discrete analog of the formula for the coefficients of a [[Fourier series]]:
:<math>C_k = \frac{1}{P}\int_P x(t)e^{-i 2\pi \tfrac{k}{P} t}\, dt.</math>
}}{{EquationNote|Eq.1}} can also be evaluated outside the domain <math>k \in [0,N-1]</math>, and that extended sequence is <math>N</math>-[[periodic sequence|periodic]]. Accordingly, other sequences of <math>N</math> indices are sometimes used,  such as <math display="inline">\left[-\frac{N}{2}, \frac{N}{2} - 1\right]</math> (if <math>N</math> is even) and <math display="inline">\left[-\frac{N-1}{2}, \frac{N-1}{2}\right]</math> (if <math>N</math> is odd), which amounts to swapping the left and right halves of the result of the transform.<ref name="mathworks" />

The inverse transform is given by:
{{Equation box 1|title=Inverse transform
|indent =: |cellpadding= 6 |border |border colour = #0073CF |background colour=#F5FFFA
|equation = {{NumBlk|:|<math>x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i2\pi \tfrac{k}{N} n}</math> &nbsp; &nbsp;
|{{EquationRef|Eq.2}}}}
}}

{{EquationNote|Eq.2}}. is also <math>N</math>-periodic (in index n).  In {{EquationNote|Eq.2}}, each <math>X_k</math> is a complex number whose polar coordinates are the amplitude and phase of a complex sinusoidal component <math>\left(e^{i 2 \pi \tfrac{k}{N}n}\right)</math> of function <math>x_n.</math> (see [[Discrete Fourier series]])  The sinusoid's [[frequency]] is <math>k</math> cycles per <math>N</math> samples.

The normalization factor multiplying the DFT and IDFT (here 1 and <math>\tfrac{1}{N}</math>) and the signs of the exponents are the most common [[sign convention|conventions]]. The only actual requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be <math>\tfrac{1}{N}.</math> An uncommon  normalization of <math>\sqrt{\tfrac{1}{N}}</math> for both the DFT and IDFT makes the transform-pair unitary.