Covolution von zwei diskreten Fourier-Transformationen

Question

Gegeben zwei endliche Sequenzen x (i) und y (i), i = 1 ... n. I bekannt, daß der diskreten Fourier-Transformation (DFT) des punktuellen Produkt xy gleich zwischen zwei DFT von x und y einer Faltungs:

DFT(x.y) = (DFT(x) * DFT(y))/n 

Jetzt I-Test in Python diesen einfachen Code:

import numpy as np 
x = np.array([1,2,3]) 
y = np.array([0.1, 1, 0.5]) 

Dftxy = np.fft.fft(x*y) # DFT(x.y) 

Dftx = np.fft.fft(x) 
Dfty = np.fft.fft(y) 
CDftxy = np.convolve(Dftx,Dfty,'same')/3 # (DFT(x)*DFT(y))/n 

das Ergebnis ist:

Dftxy = [3.60+0.j, -1.65-0.4330127j, -1.65+0.4330127j] 
CDftxy = [-2.10-0.40414519j, -1.65+0.4330127j, 0.40+0.j] 

die Werte von Dftxy und CDftxy unterschiedlich sind. Gibt es einen Fehler in meinem Code?

Answer 1

Sie haben es zu verwandeln zurück:

recovered_vector = np.fft.ifft(CDftxy) 

aber ja, periodische Randbedingungen .. Sie werden nichts vernünftig für drei glied Vektor

Answer 2

Sie haben Null-pad Ihre FFTs wenn Sie sehen, wollen, dass Ihre schnellen Faltungsergebnisse zu einem linearen Faltungsergebnis führen. Andernfalls, wenn Sie Pad nicht zerlegen, erhalten Sie eine kreisförmige Faltung (Ende Faltung Ergebnisse wrap around und Summe mit der Front) von der elementweisen Multiplikation von 2 FFTs.