mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Winograd-Algorithmus


Autor: Erich Studer (braid)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Erich Studer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So. Und jetzt noch die hilfreichen...

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Erich Studer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit Googles Hilfe findet sich doch einiges:

http://de.wikipedia.org/wiki/Schnelle_Fourier-Tran...
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

Autor: Erich Studer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Erich Studer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.