Discrete Fourier Transform

DFT.py

"""
    Discrete Fourier Transform
"""
import math
import numpy as np
import matplotlib.pyplot as plt

N = 200                 #sample size
x = np.cos(range(N))    #create a periodic cyclic function
r = np.random.random(N) #create some noise
r -= r.mean()           #centring noise
r /= r.std()
x += r                  #adding noise to the function
x = list(x)             #making x as a "normal" python list

def mod(cmplx):
    return math.sqrt(cmplx.real ** 2 + cmplx.imag ** 2)

def dft(x):
    N = len(x)
    X = [0] * N
    
    for k in range(N):
        X[k] = sum([x[n] * math.e ** (-1j * 2 * math.pi * k * n / float(N)) for n in range(N)])

    return X

def idft(X):
    N = len(X)
    x = [0] * N

    for n in range(N):
        x[n] = sum([X[k] * math.e ** ((1j * 2 * math.pi * k * n) / float(N)) for k in range(N)]) / float(N)

    return x


X = dft(x)
#X = map(mod, X) #making real numbers from complex ones
y = idft(X)
y = map(mod, y)

    
    
plt.plot(x)
plt.show()

plt.plot(y)
plt.show()