Discrete Fourier Transform

DISCRETE FOURIER:

The discrete Fourier transform transforms a sequence of N complex numbers  x_{0},x_{1},\ldots ,x_{N-1} into another sequence of complex numbers,  {\displaystyle X_{0},X_{1},\ldots ,X_{N-1},} which is defined by

{\displaystyle {\begin{aligned}X_{k}&=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi kn/N}\\&=\sum _{n=0}^{N-1}x_{n}\cdot [\cos(2\pi kn/N)-i\cdot \sin(2\pi kn/N)],\end{aligned}}}

where the last expression is deduced from the first one by Euler’s formula.

The transform is sometimes denoted by the symbol  {\mathcal {F}}, as in  \mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\} or  {\mathcal {F}}\left(\mathbf {x} \right) or  {\mathcal {F}}\mathbf {x}