Winograd-Algorithmus

[Erich S. (braid)]

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)]

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.

[Erich Studer (Gast)]

So. Und jetzt noch die hilfreichen...

[Christoph db1uq K. (christoph_kessler)]

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

[Erich Studer (Gast)]

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.

[Christoph Kessler (db1uq) (Gast)]

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

[Erich Studer (Gast)]

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.

[Erich Studer (Gast)]

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