In [1]:

    

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


    

In [2]:

    

#esse bloco tem funções a serem utilizadas nos blocos seguintes

#transformação discreta de Fourier no modo convencional
def DFT(x):
    N = x.shape[0] #quantidade de elementos
    n = np.arange(N)
    k = n.reshape((N, 1)) #transposição de n
    M = np.exp(-2j * np.pi * k * n / N)
    return np.dot(M, x)
    
#FFT implementado
#fonte https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/
def FFT(x):
    """A vectorized, non-recursive version of the Cooley-Tukey FFT"""
    x = np.asarray(x, dtype=float)
    N = x.shape[0]

    if np.log2(N) % 1 > 0:
        x = padFFT(x)
        N = x.shape[0]

    # N_min here is equivalent to the stopping condition above,
    # and should be a power of 2
    N_min = min(N, 32)
    
    # Perform an O[N^2] DFT on all length-N_min sub-problems at once
    n = np.arange(N_min)
    k = n[:, None]
    M = np.exp(-2j * np.pi * n * k / N_min)
    X = np.dot(M, x.reshape((N_min, -1)))

    # build-up each level of the recursive calculation all at once
    while X.shape[0] < N:
        X_even = X[:, :X.shape[1] / 2]
        X_odd = X[:, X.shape[1] / 2:]
        factor = np.exp(-1j * np.pi * np.arange(X.shape[0])
                        / X.shape[0])[:, None]
        X = np.vstack([X_even + factor * X_odd,
                       X_even - factor * X_odd])

    return X.ravel()


    

In [3]:

    

#quantidade de passos de simulação
n = 9
t1 = np.zeros((n, 1))
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
    N = 2 ** i
    x = np.linspace(0, 2*np.pi, N)
    y = np.sin(x)

    #simular DFT
    t0 = time.time()
    f1 = DFT(y)
    tf = time.time()
    t1[i] = tf - t0

    #simular FFT implementado
    t0 = time.time()
    f2 = FFT(y)
    tf = time.time()
    t2[i] = tf - t0

    #simular FFTPACK
    t0 = time.time()
    f3 = np.fft.fft(y)
    tf = time.time()
    t3[i] = tf - t0


    

    




/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

In [4]:

    

#graficar tempo de execução
plt.plot(t1*100, '+-', label='DFT')
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos ($2^n$)', fontsize = 20)
plt.legend()
plt.show()


    

In [5]:

    

#graficar resultados
plt.plot(np.square(np.abs(f1/N)), '+-', label='DFT')
plt.plot(np.square(np.abs(f2/N)), '+-', label='FFT')
plt.plot(np.square(np.abs(f3/N)), '+-', label='FFTPACK')
plt.xlim(0, 2**(n-3))
plt.title("Resultado das transformadas de Fourier (último passo)", fontsize = 24)
plt.ylabel("$|Y|^2$", fontsize = 20)
plt.xlabel("Hz", fontsize = 20)
plt.legend()
plt.show()


    

In [6]:

    

n = 9
t1 = np.zeros((n, 1))
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
    N = 2 ** i
    x = np.linspace(0, 2*np.pi, N)
    y = np.sin(x) + 2*np.sin(5*x) + 3*np.sin(15*x)

    t0 = time.time()
    f1 = DFT(y)
    tf = time.time()
    t1[i] = tf - t0

    t0 = time.time()
    f2 = FFT(y)
    tf = time.time()
    t2[i] = tf - t0

    t0 = time.time()
    f3 = np.fft.fft(y)
    tf = time.time()
    t3[i] = tf - t0


    

    




/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

In [7]:

    

#graficar tempo de execução
plt.plot(t1*100, '+-', label='DFT')
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos ($2^n$)', fontsize = 20)
plt.legend()
plt.xlim(0, n-1)
plt.show()


    

In [8]:

    

#graficar resultados
plt.plot(np.square(np.abs(f1/N)), '+-', label='DFT')
plt.plot(np.square(np.abs(f2/N)), '+-', label='FFT')
plt.plot(np.square(np.abs(f3/N)), '+-', label='FFTPACK')
plt.xlim(0, 2**(n-3))
plt.title("Resultado das transformadas de Fourier (último passo)", fontsize = 24)
plt.ylabel("$|Y|^2$", fontsize = 20)
plt.xlabel("Hz", fontsize = 20)
plt.legend()
plt.show()


    

In [9]:

    

n = 20
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
    N = 2 ** i
    x = np.linspace(0, 2*np.pi, N)
    y = np.sin(x) + 2*np.sin(5*x) + 3*np.sin(15*x)


    t0 = time.time()
    f2 = FFT(y)
    tf = time.time()
    t2[i] = tf - t0

    t0 = time.time()
    f3 = np.fft.fft(y)
    tf = time.time()
    t3[i] = tf - t0


    

    




/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

In [10]:

    

#graficar tempo de execução
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos ($2^n$)', fontsize = 20)
plt.legend()
plt.xlim(0, n-1)
plt.show()


    

In [ ]: