# Discrete Fourier Transform (DFT)
# FB - 20141227
import random
import math
import cmath
pi2 = cmath.pi * 2.0
def DFT(fnList):
N = len(fnList)
FmList = []
for m in range(N):
Fm = 0.0
for n in range(N):
Fm += fnList[n] * cmath.exp(- 1j * pi2 * m * n / N)
FmList.append(Fm / N)
return FmList
def InverseDFT(FmList):
N = len(FmList)
fnList = []
for n in range(N):
fn = 0.0
for m in range(N):
fn += FmList[m] * cmath.exp(1j * pi2 * m * n / N)
fnList.append(fn)
return fnList
# TEST
print "Input Sine Wave Signal:"
N = 360 # degrees (Number of samples)
a = float(random.randint(1, 100))
f = float(random.randint(1, 100))
p = float(random.randint(0, 360))
print "frequency = " + str(f)
print "amplitude = " + str(a)
print "phase ang = " + str(p)
print
fnList = []
for n in range(N):
t = float(n) / N * pi2
fn = a * math.sin(f * t + p / 360 * pi2)
fnList.append(fn)
print "DFT Calculation Results:"
FmList = DFT(fnList)
threshold = 0.001
for (i, Fm) in enumerate(FmList):
if abs(Fm) > threshold:
print "frequency = " + str(i)
print "amplitude = " + str(abs(Fm) * 2.0)
p = int(((cmath.phase(Fm) + pi2 + pi2 / 4.0) % pi2) / pi2 * 360 + 0.5)
print "phase ang = " + str(p)
print
### Recreate input signal from DFT results and compare to input signal
##fnList2 = InverseDFT(FmList)
##for n in range(N):
## print fnList[n], fnList2[n].real
