Python implementation of the Discrete Fourier Transform and its Inverse
Fourier transformations are exceptionally useful for signal analysis. Here is a python implementation of the discrete fourier transform and it's inverse.
Note: computing fourier transforms like this is not efficient. If you actually need to compute fourier tranforms consider using fast fourier transforms.
import cmath
# Discrete fourier transform
def dft(x):
t = []
N = len(x)
for k in range(N):
a = 0
for n in range(N):
a += x[n]*cmath.exp(-2j*cmath.pi*k*n*(1/N))
t.append(a)
return t
# Inverse discrete fourier transform
def idft(t):
x = []
N = len(t)
for n in range(N):
a = 0
for k in range(N):
a += t[k]*cmath.exp(2j*cmath.pi*k*n*(1/N))
a /= N
x.append(a)
return x
Note: I have only tested this in python 3.
Backward Induction
A blog by Oliver Stollmann
oliver@stollmann.net
