Discrete Fourier Transform implementation using Python

I need to program the Discrete Fourier Transform using python. (I cannot use the numpy function for fft). You can find the numpy fft function in my code, but it is just for verification. Not sure why, but it seems that my code is getting in a infinite loop (I have to Keyboard Interrupt). Any ideas?

import matplotlib.pyplot as plt
import numpy as np
import cmath

Fs = 40000;  # sampling
Ts = 1.0/Fs; # sampling period
t = np.arange(0,1,Ts) # time vector

f = 100;   # frequencia do sinal
x1_n = np.sin(2*np.pi*f*t   0)
f = 1000;
x2_n = np.sin(2*np.pi*f*t   180)

x_n = x1_n   x2_n

n = len(x_n) # signal length
k = np.arange(n) #vetor em k
T = n/Fs
frq = k/T # both sides of the frequency vetor
frq = frq[range(int(n/2))] # one side of the frequency vector

X = np.fft.fft(x_n)/n # fft using numpy and normalization

print("A")
print(X) # printing the results for numpy fft

m = len(x_n)
output = []
for k in range(m):  # For each output element
    s = complex(0)
    for t in range(m):  # For each input element
        angle = 2j * cmath.pi * t * k / m
        s  = x_n[t] * cmath.exp(-angle)
    output.append(s)

print("B") #printing the results for the fft implementation using for loops
print(output)

CodePudding user response：

It's not an infinite loop, but since m = 40000, your inner loop is going to run 1.6 billion times. That's going to take a LOT of time, which is why FFTs are not implemented in Python. On my machine, it does about 5 outer loops per second, so it's going to take 3 hours to run.

CodePudding user response：

You've written a perfectly good implementation of a Fourier transform. You have not written a fast Fourier Transform, which specifically involves a series of techniques to bring the runtime town from O(n^2) to (n log n).

This is what made the FFT so revolutionary when it was discovered. Hard problems that could only be used using a Fourier Transform suddenly became a lot faster.