Welchen FFT-Algorithmus verwendet dieser Code?

Question

Ich habe es online gefunden und es gibt keine Kommentare.

Es kommt mit einer Complex.class, die im Grunde komplexe Zahlen und ihre Operationen simuliert.

Ich möchte es selbst kommentieren, aber ich kann wirklich nicht identifizieren, welcher Algorithmus verwendet wird. Ich ging online und fand heraus, dass der Cooley-Tukey-Algorithmus am weitesten verbreitet ist, aber ich bin nicht sicher, ob dieser Code ihn benutzt.

private $dim; 
private $p; 
private $ind; 
private $func; 
private $w1; 
private $w1i; 
private $w2; 

public function __construct($dim) { 
    $this->dim = $dim; 
    $this->p = log($this->dim, 2); 
} 


public function fft($func) { 
    $this->func = $func; 

    // Copying func in w1 as a complex. 
    for ($i = 0; $i < $this->dim; $i++) 
     $this->w1[$i] = new Complex($func[$i], 0); 

    $w[0] = new Complex(1, 0); 
    $w[1] = new Complex(cos((-2 * M_PI)/$this->dim), sin((-2 * M_PI)/$this->dim)); 

    for ($i = 2; $i < $this->dim; $i++) 
     $w[$i] = Complex::Cmul($w[$i-1], $w[1]); 

    return $this->calculate($w); 
} 

private function calculate($w) { 
    $k = 1; 
    $ind[0] = 0; 

    for ($j = 0; $j < $this->p; $j++) { 
     for ($i = 0; $i < $k; $i++) { 
      $ind[$i] *= 2; 
      $ind[$i+$k] = $ind[$i] + 1; 
     } 
     $k *= 2; 
    } 

    for ($i = 0; $i < $this->p; $i++) { 
     $indw = 0; 
     for ($j = 0; $j < pow(2, $i); $j++) { 
      $inf = ($this->dim/pow(2, $i)) * $j; 
      $sup = (($this->dim/pow(2, $i)) * ($j+1)) - 1; 
      $comp = ($this->dim/pow(2, $i))/2; 

      for ($k = $inf; $k <= floor($inf+(($sup-$inf)/2)); $k++) 
       $this->w2[$k] = Complex::Cadd(Complex::Cmul($this->w1[$k], $w[0]), Complex::Cmul($this->w1[$k+$comp], $w[$ind[$indw]]));  

      $indw++; 

      for ($k = floor($inf+(($sup-$inf)/2)+1); $k <= $sup; $k++) 
       $this->w2[$k] = Complex::Cadd(Complex::Cmul($this->w1[$k], $w[$ind[$indw]]), Complex::Cmul($this->w1[$k-$comp], $w[0])); 

      $indw++; 
     } 

     for($j = 0; $j < $this->dim; $j++) 
      $this->w1[$j] = $this->w2[$j]; 
    } 

    for ($i = 0; $i < $this->dim; $i++) 
     $this->w1[$i] = $this->w2[$ind[$i]]; 

    return $this->w1; 
} 

Answer 1

Dies ist eine FFT-Implementierung radix 2 basierend auf dem Cooley-Tukey-Algorithmus, mit der Arbeit in der Funktion "Compute" getan. Es wird nur mit FFT-Längen arbeiten, die eine Potenz von 2 sind, obwohl ich in der Funktion selbst keine Parameterüberprüfung sehe.

$ i iteriert über die mehreren FFT-Durchläufe (von denen log2 (N) ist, wobei N die Länge der FFT ist), und in jedem Durchlauf werden die in $ w gespeicherten Drehfaktoren mit der Ausgabe multipliziert von der vorherigen Stufe vor dem Finden der komplexen Summe und Differenz.

Es gibt viel bessere Implementierungen von FFTs wie FFTW, die einen Mixed-Radix-Ansatz implementieren, der es erlaubt, eine beliebige Länge der FFT zu berechnen.