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


von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

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

Beitrag #5433625 wurde von einem Moderator gelöscht.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.