Inverse Discrete Fourier Transform (IDFT)

IDFT - Definition

IDFT transforms a sequence of 𝑁 complex numbers {𝑋₀, 𝑋₁, …, 𝑋_𝑁-1} into another sequence of complex numbers, {𝑥₀, 𝑥₁, …, 𝑥_𝑁-1}, which is defined by:

• $x_k=\frac{1}{N}{\sum }_{n=0}^{N-1}{e}^{\frac{i2\pi }{N}kn}\cdot X_n$

• $\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ ⋮\\ x_{N-1}\end{array}\right]=\left[\begin{array}{ccccc}1& 1& 1& \dots & 1\\ 1& W^1& W^2& \dots & W^{N-1}\\ 1& W^2& W^4& \dots & W^{2(N-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& W^{N-1}& W^{2(N-1)}& \dots & W^{(N-1{)}^2}\end{array}\right]\left[\begin{array}{c}{X}_0\\ X_1\\ X_2\\ ⋮\\ X_{N-1}\end{array}\right]$

where:

• $W=e^{\frac{i2\pi }{N}}$