Fast Fourier Transformation in Java

[novak]

Hallo!

Als Teil eines FH-Projekt sollen wir in kürze eine Fast Fourier Transformation in Java implementieren.

Mithilfe von Wikipedia habe ich die rekursive Methode auch schon erfolgreich Umgesetzt.

Da das Teil aber mal auf einem Android-Handy laufen soll, würde ich auch gerne die (angeblich schnellere)
zweite, nicht rekursive Variante umsetzen.

Ich versuche, erstmal genau das zu schreiben, was Wiki an dieser Stelle vorschlägt. Hier mein aktueller Stand:

public static Complex[] doLoopFFT(int samples, Complex[] f){
        
        int links = 0;
        int rechts = 0;
        int anzEbenen = 10;
        Complex expPow = new Complex(0.0, 0.0);
        Complex faktor = new Complex(0.0, 0.0);
        Complex summand = new Complex(0.0, 0.0);
        
        Complex[] fSort = new Complex[samples];
        Complex[] fFinal = new Complex[samples];
        
        for(int i=0; i<samples; i++){
            fSort[i] = f[(int)(Integer.reverse(i))>>>shiftStep];
        }
        
        for(int ebene=0; ebene<anzEbenen; ebene++){
            
            for(int abschnitt=0; abschnitt<(Math.pow(2.0, (anzEbenen-ebene-1))); abschnitt++){
                
                for(int elementDesAbschnitts=0; elementDesAbschnitts<(int)Math.pow(2.0, ebene); elementDesAbschnitts++){
                    
                    links = (int)Math.pow(2.0, (ebene + 1)) * abschnitt + elementDesAbschnitts;
                    rechts = links + (int)Math.pow(2.0, ebene);
                
                    expPow = new Complex(0.0, (-Math.PI * ((double)elementDesAbschnitts / (Math.pow(2.0, (double)ebene)))));
                    faktor = Complex.exp(expPow);
                    summand = Complex.mul(fSort[links], faktor);
                    
                    fFinal[links] = Complex.sub(fSort[rechts], summand);
                    fFinal[rechts] = Complex.add(fSort[rechts], summand);

                }
            }
        }
        
        return fFinal;
    }

Ich berechne zum Testen jeweils 1024 Abtastwerte, daher die anzEbenen = 10; noch hard gecodet, was bei Wiki N entsprechen sollte.
Alle anderen Variablen sollten so benannt sein wie auf Wiki, durch ihren Namen selbstbezeichnend sein. Die eigentliche Berechnung habe ich, um Fehler auszuschließen, mal soweit wie möglich "aufgedröselt". Die Klasse Complex für die Rechnung mit komplexen Zahlen habe ich von http://www.it-host.de/jserv/java-tools/complex/html/download.html

Mein Problem: Ich erhalte falsche Ergebnisse. Mehr kann ich leider nicht dazu sagen. Hab den Code schon oft nach Fehlern durchforstet. Ich denke, ich habe einfach irgendwo ein Verständnisproblem.

Vielleicht sieht ja jemand den Fehler und kann mir helfen.

Die Funktion spuckt, nach einer entsprechenden Auswertung, welche mit der Rekursiven Methode richtige Ergebnisse liefert, folgendes aus:

 

[knalli]

Auf den ersten Blick hast du den Pseudocode so übernommen. Tipp: Rechne den ersten Durchlauf bzw. einen Teil mit/nach, dabei entweder Debuggen (über den Debugger) oder einfach nur entsprechend gut mitloggen.

Zwei Dinge bzgl. Performance: Sofern kein Compiler deinen Code umbaut, bedeutet beispielsweise die Zeile

for(int abschnitt=0; abschnitt<(Math.pow(2.0, (anzEbenen-ebene-1))); abschnitt++){

dass bei *jedem* Durchlauf *dieser* Schleife die Variable "abschnitt" mit einem *neuen* Ergebnis des Ausdrucks verglichen wird. Wesentlich effektiver ist hier also ein

for(int abschnitt=0, abschnitte = (Math.pow(2.0, (anzEbenen-ebene-1))); abschnitt < abschnitte; abschnitt++){

und vergleichbares.

Ansonsten: Schritt für Schritt durch gehen, ob der Code-Abschnitt wirklich das macht, was er soll.. etwa: Bit-Shifting.

Da mir dieser Algorithmus speziell nicht untergekommen ist (es waren mehr Graphenalgorithmen von Ford & Co.) habe ich mal etwas gestöbert: http://www.cs.princeton.edu/introcs/97data/InplaceFFT.java.html Falls ich die richtige Variante gefunden habe: Dort wird ein andere Variante des Bitshiftings genutzt.