FFT-Algorithmus Bug

Question

Versuch, den FFT-Algorithmus in Python zu implementieren und einen Fehler zu treffen, den ich nicht herausfinden kann.

Hier ist mein 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 

wenn ich

laufen

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

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

ich:

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

So für den Index 1 und Index 3, es ist das komplexe Konjugat. Irgendwelche Ideen?

Answer 1

The definition of the forward Discrete Fourier Transform used by np.fft.fft ist gegeben durch:

sollten Sie das negative Vorzeichen in das Argument der komplexen exponentiellen bemerken.

In Ihrer Implementierung verwenden Sie dagegen ein positives Vorzeichen für die Vorwärtstransformation, und eine solche Umkehrung im Vorzeichen der Argumente für die komplexe Exponentialfunktion führt zur Konjugation des Frequenzspektrums.

Also, für Ihre Implementierung die gleichen Ergebnisse wie np.fft.fft erhalten müssen Sie einfach mit den Zeichen der Vorwärts- und Rückwärtstransformationen invertieren:

z = +1 if inverse else -1 

(statt z = -1 if inverse else 1).