Hallo Hab da mal bei Wikipedia (unter FFT) was über den Winograd-Algorithmus gefunden. Dieser soll auch eine FFT durchführen aber mit weniger Multiplikationen und mehr Additionen. Leider hab ich immer noch nichts darüber gefunden wie der funktioniert. Kennt sich jemand damit aus oder kennt eine gute Seite? Es geht mir mehr um die theoretische Betrachtung. Kennt vielleicht jemand noch einen schnellen DFT-Algorithmus der wenig Multiplikationen verwendet? Oder sonst irgendwie toll ist?? mfg braid
Gast
#463316
Wenn du nicht in der Lage bist, die Referenz auf der Wikipediaseite zu finden, kannst du sicherlich auch mit sonstigen Erkärungen nichts anfangen. Hol dir mal ne Computerbild und lies die Einführung zu google.
Gast
#463840
So. Und jetzt noch die hilfreichen...
Ich habe mal in das Buch "DSP with FPGAs" geschaut, dort ist auch der Winograd-Algorithmus mit anderen FFTs verglichen. Laut einer Kurvenschar (S.277) ist er bezüglich Anzahl der nötigen Multiplikationen der beste, verglichen mit 3 mal "Butterfly" und einer "Good-Thomas"-FFT. An anderer Stelle im Buch wird eine noch schnellere auf "Zahlentheoretischen Transformationen" beruhende FFT beschrieben, es geht immer um die FFT-Programmierung in FPGAs. Aber ich fürchte, da sollte man Mathematiker sein, um so etwas zu kapieren. Einen einfache Schritt-für-Schritt Anleitung findet man nicht in diesem Buch. ISBN-Nummer: 3-540-21119-5
Gast
#465849
Danke erst mal. Genau eine Schritt für Schritt Anleitung ist das was ich suche. Es würde mir aber auch reichen wenn ich nur wüsste wie man den Algorithmus implementieren muss (ohne Herleitung nur die Formel oder so). Den normalen fft Algorithmus hab ich glaube ich recht gut begriffen. Wo liegt dann die weitere Optimierung im Winograd? Was wird anders gemacht? Alles was ich weiss ist, dass da weniger Multiplikationen und mehr Additionen verwendet werden. Also ist er besser für Controller ohne Multiplizierer.
Gast
#467018
Mit Googles Hilfe findet sich doch einiges: http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation#Winograd-Algorithmus Zitate: "..nur eine maximale Blöcklänge von 5040 möglich..."(da steht wirklich Blöck) "Diese Art der schnellen Fourier-Transformation besitzt in praktischen Implementierungen dann Vorteile gegenüber der Radix-2 Methode, wenn der für die FFT verwendete Mikrocontroller, wie beispielsweise der 8051 ohne eigene Multipliziereinheit, für die notwendigen Multiplikationen sehr viel Rechenzeit in Form von Unterprogrammen benötigen würde. In heutigen Signalprozessoren mit eigenen Multipliziereinheiten hat dieser Algorithmus keine wesentliche Bedeutung." http://en.wikipedia.org/wiki/Shmuel_Winograd http://cnx.org/content/m12060/latest/ http://cnx.org/content/m12023/latest/#WFTA
Gast
#468561
Hallo Die Seiten: http://cnx.org/content/m12060/latest/ http://cnx.org/content/m12023/latest/#WFTA waren mir neu. Danke. Aber entweder bin ich jetzt wirklich doof oder das gibts niergends ne beschreibung. Naja ich glaub isch schau mir mal zuerst den primfaktor-algorithmus an.
Gast
#485389
So ich glaub ich hab so ziemlich das ganze internet abgegrast. Die einzige Seite auf der es brauchbare infos gäbe ist die von IEEE, aber dort kostets halt. Bücher hab ich irgendwie auch nichts schlaues gefunden. Im DSP Guide hab ich auch nichts gesehen. Wer kennt sich mit dem Algorithmus aus? Wer kann mir helfen? Vielleicht kennt jemand ein gutes buch? Bin für alles dankbar. mfg erich studer
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.