mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik [RFC] Sinus-Berechnung per Butterfly-Algorithmus?


Autor: Johann L. (gjlayde) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

ich mache mir gerade Gedanken, welche Möglichkeites es gibt, effektiv 
die Werte von Sinus und Cosinus zu berechnen.

Neben den Standard-Verfahren (Taylorreihe, CORDIC, Lookup-Tabelle) 
müsste das doch auch effektiv mit einer inversen FFT zu bewerkstelligen 
sein?

Idee ist folgende: Man nimmt ein Frequenzspektrum, in dem nur die 
Grundschwingung vorhanden ist, und macht darauf eine inverse DFT 
(Diskrete Fourier-Trafo). Mit einer 2-Potenz als Dimension kann man die 
inverse DFT effektiv berechnen per FFT. Bei der FFT sind die Ein- und 
Ausgebewerte auf ne bestinnte Art vernetzt -- dem s.g. 
Schmetterlingsgraph:
   http://de.wikipedia.org/wiki/Schmetterlingsgraph

Durch die inverse DFT auf der Grundwelle erzeugt man im Urbilbereich 
eine Basisfunktion des Funktionenraumes; im vorliegenden Fall also den 
Sinus (je nach Wahl auch höhere Basisfunktionen oder eben Cosinus).

Wenn man nun berücksichtigt, daß im Frequenzspektrum alle Frequenzen 
ausser der Grundfrequenz 0 sind (weiß übermalt in der Grafik) und im 
Urbilbereich nur ein Wert gesucht wird (unbenutze Werte schwarz übermalt 
in der Grafik), dann ergibt sich im Schmetterlingsgraph ein Pfad von der 
Grundfrequenz zu dem gesuchten Sinus- bzw. Cosinuswert. Die meisten 
Berechnungen können entfallen weil sie nicht benötigt werden, und viele 
Berechnungen vereinfachen sich weil die benötigten Knoten als einen 
Eingang die Null haben.

Gibt's sowas schon? Wäre sowas praktikabel? Das Schema lässt vermuten, 
daß für eine Sin-Berechnung mit einer Auflösung von 2^{-n} etwa n 
Rechenschritte notwendig sind. Man muss sich durch den Graph 
durchfinden, was i.W. wohl an der Binärentwicklung von x/(2Pi) 
geschieht.

Mit so einem Verfahren lässt sich auch einfach eine Tabellierung für den 
Sinus erstellen. In dem Falle setzt man die weissen Werte auf 0 und 
verwendet auch alle schwarzen, welche die Lookup-Tabelle darstellen. 
Damit kann mit einem recht kompakten Algorithmus (iFFT) zur Startup-Zeit 
ne Lookup-Tabelle im RAM initialisiert werden, aus der die Anwendung 
sehr schnell benötigte Sin-Werte abfragen kann.

Bin gespannt auf eure Kommentare.

Johann

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.