Backward Induction - A blog by Oliver Stollmann

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.