Discrete Fourier Transform (DFT)

Fast Fourier Transform (FFT)

DFT Formula

$$X(k)=\sum _{n=0}^{N-1}x(n)e^{-j2\pi k(n/N)}k=0,1,..N-1$$

N = len(signal)
X = np.zeros(N)
for k in range(N):
	for n in range(N):
		X[k] += signal[n] * np.exp(-2j * np.pi * k * (n/N))

IDFT Formula

$$\begin{array}{rl}x(n)& =\frac{1}{N}\sum _{k=0}^{N-1}X(k)e^{j2\pi kn/N},n=0,1,..,N-1\end{array}$$

N = len(signal)
x = np.zeros(N)
for n in range(N):
	for k in range(N):
		x[n] += X[k] * np.exp(2j * np.pi * k * (n/N))
x /= N

DFT Effects