Algorithme FFT Bogue

Question

Tentative de mise en œuvre de l'algorithme FFT en python, et modification d'un bogue que je n'arrive pas à comprendre.

Voici mon code:

def FFT(co, inverse=False): 
    if len(co) <= 1: 
    return co 

    even = FFT(co[::2], inverse) 
    odd = FFT(co[1::2], inverse) 

    y = [0] * len(co) 
    z = -1 if inverse else 1 

    for k in range(0, len(co)//2): 
    w = np.round(math.e**(z*1j*math.pi*(2*k/len(co))), decimals=10) 
    y[k] = even[k] + w*odd[k] 
    y[k + len(co)//2] = even[k] - w*odd[k] 

return y 

quand je lance

x1 = FFT([1, 1, 2, 0]) 
print x1 

print np.fft.fft([1, 1, 2, 0]) 

Je reçois:

[(4+0j), (-1+1j), (2+0j), (-1-1j)] 
[ 4.+0.j -1.-1.j 2.+0.j -1.+1.j] 

donc pour l'index 1 et l'index 3, il est le complexe conjugué. Des idées?

Answer 1

Le definition of the forward Discrete Fourier Transform used by np.fft.fft est donné par:

Vous devriez remarquer le signe négatif dans l'argument de l'exponentielle complexe. D'autre part, dans votre implémentation, vous utilisez un signe positif pour la transformée directe, et une telle inversion dans le signe des arguments de l'exponentielle complexe conduit à conjuguer le spectre de fréquence.

Ainsi, pour votre mise en œuvre pour obtenir les mêmes résultats que np.fft.fft il vous suffit d'inverser le signe des avant et arrière avec des transformations:

z = +1 if inverse else -1 

(au lieu de z = -1 if inverse else 1).