The Fast Fourier Transform fizik ödevi ders notları


The Fast Fourier Transform

Ayrık fourier transform bir karmaşık n vektörü başka bir n vektöre çevirir. Transformu yerine getirmek için her parçanın sıfır değerde olduğu hayal edilir.

 

Tanım: Ayrık fourier transform ve matris Fn

n ³ 1 için w, 1 sayısının nth dereceden kökü olsun, Fn ¦ij=wij giriş değerleri ile n x n bir matris olsun. N vektörün ayrık fourier transformu P=(p0, p1, … , pn-1,) ile FnP hesap edilir.

 

FnP nin bileşenleri şunlardır.

 

w0p0+w0p1+ … + w0pn-2+w0pn-1

w0p0+wp1+ … + wn-2pn-2+wn-1pn-1

.

.

.

w0p0+wip1+ … + wi(n-2)pn-2+wi(n-1)pn-1

.

.

w0p0+wn-1p1+ … + w(n-1)(n-2)pn-2+w(n-1)(n-1)pn-1

 

Başka bir formda yazılmak istenirse;

 

pn-1(wi)n-1 + pn-2(wi)n-2 + … + p1wi + p0

 

yukarıdaki polinominal denklem aslında

pn-1xn-1+ pn-2xn-2+ … + p1x + p0 denklemidir. w0, w, w1, w2, … , wn-1

 

Bu problemi çözmek için divide and conquer algoritması kullanılarak eşitlik daha küçük parçalara bölünerek çözülmeye çalışılır.