In diesem Dokument von AD: https://www.analog.com/en/technical-articles/an-almost-pure-dds-sine-wave-tone-generator.html findet sich ein Hinweis auf eine Sinus-Implementierung in Form einer iterativen Schleife bei denen nur X*X verwendet wird und in der auf sogenannte Koeffizienten von "Cody and Waite" verwiesen wird. Leider ist nirgendwas konkretes dazu zu finden. Laut der angegebenen Formel gibt es wohl deren 7. Was man vereinzelt im Netz findet, ist ein Kontrukt mit 3 Werten. Kennt das jemand?
Erstes Google-Ergebnis für "sine minimax polynomials" gibt: https://gist.github.com/publik-void/067f7f2fef32dbe5c27d6e215f824c91
Ok, sehr interessant. Das hatte ich noch nicht gefunden. Es scheint aber in die richtige Richtung zu gehen. Ich sehe nur nicht die Equivalenz zu den o.g. Parametern. Ich nehme an, es müsste etwas im Bereich "degree 7" oder "degree 15" sein. Den Grafiken zufolge passt der ausgewiesene Fehler aber ungefähr zu der Aussage, dass "ab der 15. Potenz der Fehler < 1/32 Bit ist". Das Verfahren finde ich sehr interessant. Die Methode war mir bisher gänzlich unbekannt. Man braucht aber offenbar einen Real-Wert mit einer Auflösung von 30 Stellen. Nichts für kleine Prozessoren.
Hotte schrieb: > Ok, sehr interessant. Das hatte ich noch nicht gefunden. > Es scheint aber in die richtige Richtung zu gehen. Ich > sehe nur nicht die Equivalenz zu den o.g. Parametern. Ich > nehme an, es müsste etwas im Bereich "degree 7" Nee. > oder "degree 15" sein. Ja. Das Polynom hat 7 Koeffizienten und geht in X^2, das macht Grad 14, und der Faktor X davor gibt Grad 15. > Den Grafiken zufolge passt der ausgewiesene Fehler aber > ungefähr zu der Aussage, dass "ab der 15. Potenz der Fehler > < 1/32 Bit ist". ??? 2^31 ist ungefähr 10^9; der Maximalfehler der Näherung liegt aber bei 10^-14, ist also DEUTLICH besser. > Das Verfahren finde ich sehr interessant. Die Methode war > mir bisher gänzlich unbekannt. Man braucht aber offenbar > einen Real-Wert mit einer Auflösung von 30 Stellen. Ja... BINÄR-Stellen. Von nix kommt nix. Wer 32Bit-Ergebnisse will, muss auch mindestens 32Bit-Koeffizienten verwenden.
Hotte schrieb: > ...findet sich ein Hinweis auf eine Sinus-Implementierung... Das sieht eher danach aus, als ob jemand verzweifelt nach einer Methode gesucht hat, um sowas in ein FPGA zu quetschen. Viele Grafiken und immer wieder der Versuch, den entstandenen Fehler klein zu reden. Nun ja, man bemüht sich, so gut es die Verhältnisse zulassen. Aber das Thema hatten wir hier vor ein paar Jahren schon mal. Und wir sind hier nicht bei den FPGA's, sondern bei den Signalprozessoren. Such mal nach "Sinus nach Pedersen".
1 | sin(x) = x * (K*x^2 + L + M/(x^2 + N)) |
2 | mit
|
3 | K=0.15625 |
4 | L=-11.45242628 |
5 | M = 480.1488517 |
6 | N=38.55864669 |
kostet nur 3 Multiplikationen und 1 Division. Es ist offenbar so, daß niemand die Suchfunktion dieses Forums benutzt und deshalb immer wieder die bereits gelösten Probleme nach Jahren wieder auftauchen. W.S.
W.S. schrieb: > Das sieht eher danach aus, als ob jemand verzweifelt nach einer Methode > gesucht hat, um sowas in ein FPGA zu quetschen. Beim Github, oder dem TE? Also hier lese ich eher heraus, dass es um eine Implementierung geht, die auch einem Sparprozessor läuft. Der Pedersen ist für einen FPGA schon mal nicht so gut :-) Generell muss man sich die Frage stellen, wie genau man einen Sinus überhaupt braucht, wenn man Daten damit bearbeiten will. Das Papier tut das ja auch und schränkt ein, dass der spätere ADC das Problem sein wird, die 50 Stellen hinter dem Komma über die DDS zu transportieren. Für Taschenrechner und Mathematikprogramme ist es aber unerlässlich, sehr genau zu arbeiten und solche Lösungen zu haben.
Hotte schrieb: > Die Methode war mir bisher gänzlich unbekannt. Ich erinnere mich noch ganz dunkel an das dort erwähnte ->Horner-Schema. Das hatten wir irgendwann mal in der Schule - aber ohne es nachzulesen, könnte ich es jetzt auch nicht mehr reproduzieren. Ich erkenne aber in der iterativen Entwicklung Ähnlichkeiten zu meinem Sinusgenerator auf der Basis von Quadrat-Funktionen, die ich in meinem Synth benutze, womit wir doch beim FPGA wären: Man bildet für irgendeinen Phasenwert für den ersten Viertelbogen den Wert im Quadrat und hat dann einen Pseudosinus, wie hier im Artikel Digitale Sinusfunktion. Dann bildet man wieder das Quadrat davon und hat automatisch eine Oberwelle, die man skaliert vom ersten Wert abziehen kann. Das setzt man matrixartig fort und eliminiert so immer wieder die Oberwellen, die das Quadrat gegenüber dem Sinus mitbringt und im Weiteren auch die Oberwelle von der Korrekturwelle, die man ja damit einschleppt und so fort. Für den Sinus braucht man dann die ungeraden- und für den Cosinus die geraden Werte, muss also einmal mit X multiplizieren. Auch das erkennt man in der o.g. Beschreibung, weil einmal noch ein "X1" hinen multipliziert wird, wegen "ungerade Funktion" etc. Die gesamte Mimik kann man dann in einer Tabelle für alle Koeffizienten machen und findet so die Summe der Koeffizienten für die X1, X3, X5, X7, X9 also die Grundwelle und auch die X3, X9, X15, X21 für die 3. Oberwelle und die X5, X15, X25 u.s.w für die 5. Oberwelle, die man miteinander verrechnen kann. Interessant dabei ist, dass sich für alle N*N der Wert 0 ergibt, sodass die X9, die X25, X49 und die X81 etc rausfallen. Beim Cosinus entsprechend X4, X16, X36, X64 usw. > Man braucht aber offenbar einen Real-Wert mit einer > Auflösung von 30 Stellen. Kommt immer auf die Ansprüche an und man kann das auch mit Integer machen, wenn man den Koeffizienten entsprechend auflöst. In einem FPGA hat man z.B. Bits genug und das sehr hoch aufgelöst ganzzahlig zu berechnen. Man muss das auch nicht so iterativ machen, wie im Paper, sondern kann sich darauf beschränken, nur das X immer weiter zu quadrieren und die Koeffizienten separat zu multiplizieren und parallel in die Summe zu schieben, dann setzt sich der Fehler nicht fort und man braucht auch für die kleiner werdenden Anteile der Oberwellen nach oben raus nicht mehr so genaue Koeffizienten. Ich benutze typisch Werte bis zur 23. Oberwelle und muss nur 9 Multiplikationen machen. Das nähert den Sinus ausreichend gut für Audioanwendungen. Fun Fact: Die Schwierigkeit, die ich damals hatte, war es zu plausibilisieren. Ich hatte die erste Tabelle mit Excel 2003 angefertigt und fand heraus, dass es irgendwann Abweichungen zwischen dem hingerechneten und dem "echten" Sinus von Excel gab. In einem späteren Office war das dann anders. Da bin ich erst drauf gekommen, dass ich offenbar die Grenzen von Excel ausgetestet hatte und mein FPGA-Sinus stellenweise schon genauer war. Microsoft hatte offenbar in der späteren Version den Sinus-Algo ausgetauscht. Der Sinus im Excel ist vergleichsweise schlecht, muss man sagen. Nutzt man viele Perioden von PI kommt der irgendwann nicht mal mehr auf 0.
W.S. schrieb: > Das sieht eher danach aus, als ob jemand verzweifelt > nach einer Methode gesucht hat, um sowas in ein FPGA > zu quetschen. ??? Was bitte ist an einer Tschebyscheff-Approximation "verzweifelt"? > sin(x) = x * (K*x^2 + L + M/(x^2 + N)) > mit > K=0.15625 > L=-11.45242628 > M = 480.1488517 > N=38.55864669 > kostet nur 3 Multiplikationen und 1 Division. ...und hat den offenkundigen Nachteil, dass man dividieren muss.
Grummler schrieb: > 2^31 ist ungefähr 10^9; der Maximalfehler der Näherung liegt > aber bei 10^-14, ist also DEUTLICH besser. Ich hab es nochmals nachgelesen, ja, das Dokument sprucht davon, dass die beiden genannten PErsonen nachgewiesen hatten, dass es bis zu e-15 genau sei. Das passt soweit. Grummler schrieb: > Ja... BINÄR-Stellen. Wieso binär? Die Werte in den Tabellen sind in Dezimal und haben teilweise 30 Stellen. Grummler schrieb: > ...und hat den offenkundigen Nachteil, dass man dividieren > muss. Wäre für meinen Fall eventuell noch tolerabel. Wie genau ist diese Funktion? Wie genau müssten die Koeffizienten sein?
Hotte schrieb: > Grummler schrieb: >> 2^31 ist ungefähr 10^9; der Maximalfehler der Näherung >> liegt aber bei 10^-14, ist also DEUTLICH besser. > > Ich hab es nochmals nachgelesen, ja, das Dokument sprucht > davon, dass die beiden genannten PErsonen nachgewiesen > hatten, dass es bis zu e-15 genau sei. Das passt soweit. Ja... vielleicht nochmal kurz zur Erklärung (mich nervt das name dropping in dem Paper von AD etwas): 1. Basis der ganzen Geschichte ist eine stinknormale Polynom-Approximation nach Tschebyscheff. (Vorteil: Maximalfehler wird im GESAMTEN INTERVALL garantiert nicht überschritten -- Taylor-Entwicklung ist im Gegensatz dazu nur im Entwicklungspunkt perfekt und wird immer schlechter, je weiter man zu den Intervallgrenzen geht.) 2. Die Koeffizienten für das Tschebyscheff-Polynom lassen sich mit dem Remez-Algorithmus finden; auf der von foobar verlinkten Seite wird das weiter unten erwähnt. Aus dem AD-Paper lässt sich raten, dass Hart lediglich solche Polynome publiziert hat. 3. Worin die Verbesserung von Cody und Waite besteht, ist weiterhin unklar. In Anbetracht dessen, dass die Formeln auf der von foobar verlinkten Seite schon über 40bit Genauigkeit liefert, wäre mir das aber auch egal. > Grummler schrieb: >> Ja... BINÄR-Stellen. > Wieso binär? Die Werte in den Tabellen sind in Dezimal > und haben teilweise 30 Stellen. Ja klar -- dort werden ja auch Polynome bis zur 33. Ordnung verglichen, und das hat nur mit entsprechend genauen Koeffizienten Sinn. Wenn Du nur ein Polynom 15. Ordnung auf 32Bit genau auswerten willst, brauchst Du maximal vielleicht 36Bit oder so für die Koeffizienten. Cody und White behaupten ja, dass es auch mit 32Bit langen Koeffizienten klappt -- aber deren Werte sind vermutlich (auf eine bisher geheime Art und Weise) handoptimiert. Kann man im Zweifelsfalle einfach ausprobieren. > Grummler schrieb: >> ...und hat den offenkundigen Nachteil, dass man >> dividieren muss. > > Wäre für meinen Fall eventuell noch tolerabel. Ahh, okay. > Wie genau ist diese Funktion? Wie genau müssten die > Koeffizienten sein? Lies mal den Beitrag von W.S. hier im Thread und traktiere dann die Suchfunktion; das sollte Dir weiterhelfen. Das Thema ist vor drei, vier Jahren schonmal diskutiert worden; ich habe aber keine Einzelheiten mehr parat. Ich müsste genauso suchen wie Du.
Grummler schrieb: > Das > Thema ist vor drei, vier Jahren schonmal diskutiert worden; Hallo, Minimax Approximationen mit Polynomen oder rationalen Polynomen, z.B. für die arctan Funktion, wurden u.a. in diesen beiden Diskussionen besprochen: Beitrag "Näherung für ArcusTangens?" Beitrag "64 Bit float Emulator in C, IEEE754 compatibel" Die Bücher "Computer Approximations" von Hart und "Software Manual for the Elementary Functions" von Cody und Waite hätte ich da.
> in Form einer iterativen Schleife bei denen nur X*X verwendet wird
X*X ist schlicht X^2.
Falls einem float reicht, und Mann die Schleife ausrollt:
1 | // |
2 | sin = (((((((( 0.0000027 * x*x ) |
3 | - 0.0001984 ) * x*x ) |
4 | + 0.0083333 ) * x*x ) |
5 | - 0.1666667 ) * x*x ) + 1.0 ) * x; |
6 | // |
Die Herren Taylor und Horner lassen schoen gruessen :). Die Genauigkeit (bis 90 Grad) reicht fuer einen 8 stelligen Milchmaedchentaschenrechner.
Alexander S. schrieb: > Die Bücher "Computer Approximations" von Hart und "Software Manual for > the Elementary Functions" von Cody und Waite hätte ich da. Würde mich auch mal interessieren. ISBN? Was mir zum Thema Genauigkeit noch einfällt: Die iterativen Algos und Näherungen liefern immer eine dedizierte Fehlerfunktion, die man in der Signalstruktur erkennen kann. Der Fehler wächst meistens zum Definitionsbereichsende hin und die Schwingung, die sich beim Durchlauf ergibt, ist relativ niederfrequent und hat teilweise Anteile unterhalb der Nutzfrequenz. Auch beim Pedersen ist das so, dass sich da eine Schwingung ergibt. (M)eine binäre quadratische Näherung v.o. liefert aber einen statistischen Rundungsfehler, dessen Spektrum weitgehend deutlich oberhalb der Nutzfrequenz liegt - also gut gefiltert werden kann, bzw. bei Nutzung der Werte in weiteren Rechenschritten nicht zu deutlichen Mustern führt, wodurch auch die Endwerte einer solchen Rechnung ein gut verteiltes Fehlerspektrum aufweisen. Bei der Bewertung der Genauigkeit schneidet daher ein Algo, der scheinbar nur auf 10 Bit genau ist, erheblich besser ab, als ein anderer, der vielleicht auf 16 Bit genau ist, aber eine eindeutige Fehlerfrequenz hat. Hinzu kommt, dass die Störfrequenzen bei geschickter Wahl der Vektorbreiten bis in hohe Abtastfrequenzen und Nutzfrequenzen hinein ganzzahlige binäre Vielfache sind und damit der musikalisch unproblematisch n-ten Oktave liegen.
Hotte schrieb: > Wie genau ist diese Funktion? Siehe Bild: Der Fehler ist von -PI ... PI und -PI/2 ... +PI/2 aufgetragen. Genau da muss man aufpassen: Ein Kollege hatte mal so einen drin und sich über die peaks gewundert, die im Signal steckten. Die kamen von den Rändern. Man darf den nur für 2 der 4 Viertelbögen nutzen. Da ist er auf 1/100.000 bei 0.5 digit genau. Das Ungünstige ist halt die Division. Die muss auf Ganzzahlmaschinen wie im FPGA sehr hoch aufgelöst in RADIX 2 laufen. Mit CORDIC für die DIV ist nix zu wollen, weil man dann besser den Sinus direkt nimmt.
Jürgen S. schrieb: > Würde mich auch mal interessieren. ISBN? Computer approximations https://www.worldcat.org/title/841853758 Es gibt auch noch einen Nachdruck von 1978, siehe "View all formats and editions". Software manual for the elementary functions https://www.worldcat.org/title/6250863 Die Bücher gibt es aber nur noch im Antiquariat.
Alexander S. schrieb: > Die Bücher gibt es aber nur noch im Antiquariat. Es wird genug andere Bücher geben, wo das auch drin steht: https://epdf.tips/search/Computer+approximations Alles frei herunterladbar!
Hp M. schrieb: > Es wird genug andere Bücher geben, wo das auch drin steht: > https://epdf.tips/search/Computer+approximations > > Alles frei herunterladbar! Das sagt sich leicht. Je spezifischer, und insbesondere älter, die Information ist, die man sucht, desto schwieriger ist es dazu freie Quellen im Internet zu finden. In welchem der pdfs auf https://epdf.tips findet man denn z.B. die Koeffizienten für die rationale Minimax Approximation für den arctan mit einer Genauigkeit von 22 Dezimalstellen? Ich kenne nur Internetquellen mit Programmbeispielen, wo einige wenige der Koeffezienten aus dem Buch verwendet werden.
Jürgen S. schrieb: > Man darf den nur für 2 der 4 Viertelbögen nutzen. Da ist er auf > 1/100.000 bei 0.5 digit genau. Das wäre super! ... schrieb: > Falls einem float reicht, und Mann die Schleife ausrollt: > // > sin = (((((((( 0.0000027 * x*x ) > - 0.0001984 ) * x*x ) > + 0.0083333 ) * x*x ) > - 0.1666667 ) * x*x ) + 1.0 ) * x; > // Das wäre mir auch sehr symphatisch. Wie genau ist der? Ich nehme an, die dort eingesetzten Zahlen können sinnvoll fortgesetzt werden, also die 0.166xxxx um höhere Genauigkeit zu erlangen? Die 0.xxx27 sind genau?
Das Buch ist bei epdf vorhanden. Nach Anklicken von Ampeln oder Hügeln darf man 10,8 MB herunterladen. 279 Seiten ISBN 9780138220648 Hier die Seiten zu sin/cos Mit Beispielprogramm in Fortran, man sieht quasi die einzelnen Lochkarten. Musste ich auch noch lernen 1976.
:
Bearbeitet durch User
> Wie genau ist der? Fuer die 7 dezimalen Nachkommastellen eines einfachen Taschenrechners reicht es. Bei 90 Grad gibt es ein wenig Abweichung. > können sinnvoll fortgesetzt werden > Die Herren Taylor [x] > und Horner lassen schoen gruessen Ich dachte der Hinweis reicht. Es sind die Koeffizienten der Taylorapproximation. (1/(2n+1)! ... 1/3! 1/5! ...) Ja, das ganze laesst sich sicher noch aufbohren. Fuer float lohnt das aber schon nicht mehr. Mir hat es so wie es ist, im allgemeinen gereicht. Damit der Compiler auch wirklich "float" benutzt, muss man gehoerig aufpassen :). Das Beispiel laesst das aus.
... schrieb: >> Wie genau ist der? > > Fuer die 7 dezimalen Nachkommastellen eines einfachen > Taschenrechners reicht es. Bei 90 Grad gibt es ein wenig Abweichung. Das ist eine von denen Funktionen, die die unangenehme Eigenschaft haben, nach "hinten" raus gegen 2*PI immer ungenauer zu werden. Man kann sich helfen, wenn man nur den ersten Viertelbogen nimmt und dort umklappt. Gibt aber trotzdem einen Knick.
À propos 2*PI: Gibt es eigentlich gebräuchliche Sinus-Funktionen, die nicht im Grad- oder Bogenmass sind? (Ich denke an so etwas wie dezimale Perioden.) Bei meinen Anwendungen wird gefühlt immer mit 2*PI skaliert, weil die Periodendauern ja meistens einen rationalen Zeitbezug zum Prozessortakt haben, und der einzige Teil, wo ich verstehe, dass der Bezug auf 2*PI einen Sinn hat, ist die Näherung für kleine Winkel.
:
Bearbeitet durch User
> nur den ersten Viertelbogen nimmt Bei 90 Grad (PI/2) sollte man aufhoeren und dann die Periodiziaet nutzen. Wenn "zufaelligerweise" :) die erste Ableitung des nimerischen Polynoms bei 90 Grad zu Null wird, gibt es logischerweise auch keinen Knick. Eigentlich sollte das so sein. Und wenn nicht, kann man ja nachhelfen. Ich wuesste keinen vitalen Grund, warum man die ganze Periode approximieren sollte oder wollte. Ausser es ist eine immanente Eigenschaft der Approximationsfunktion. Polynome zaehlen wohl mit Sicherheit nicht dazu. > gebräuchliche Sinus-Funktionen Neben Deg und Rad kennen Taschenrechner auch Grad. 360 Deg := 400 Grad. Sicher sehr nuetzlich wenn der einzige vorhandene Winkelmesser diese Teilung hat :).
Walter T. schrieb: > À propos 2*PI: Gibt es eigentlich gebräuchliche Sinus-Funktionen, die > nicht im Grad- oder Bogenmass sind? (Ich denke an so etwas wie dezimale > Perioden.) Na klar: https://de.wikipedia.org/wiki/Strich_(Winkeleinheit)#Der_artilleristische_Strich
Vollwinkel (τ für turn/(Um)Drehung) ist gebräuchlich für Festkomma und herstellerspezifische Erweiterungen wie sinpi(), cospif(), usw. https://de.wikipedia.org/wiki/Vollwinkel
... schrieb: > bei 90 Grad zu Null wird, gibt es logischerweise > auch keinen Knick. Eigentlich sollte das so sein. Bei der ganz oben genannten Approx könnte das so sein, ja - habe die Fehlerfunktion nicht mehr ganz vor Augen, aber die pendelte ja um Null. Bei der zuletzt (von dir ?) genannten Funktion ergibt sich aber eine Fehlerfunktion die kontinuierlich mehr Abweichung liefert, damit gibt es automatisch einen Knick. Und selbst wenn es nicht die erste ABL trifft, taucht es spätestens bei der 2. auf und damit wird es mitunter giftig bei der Lösung von DGLs. ... schrieb: > 360 Deg := 400 Grad. Waren das nicht diese "GON" oder wie die hießen? Ich habe das mal in den 90ern für den Amiga genutzt, weil sich das sehr gut in 100% und binäre Vielfache aufteilen ließ. Aber sonst habe ich die nicht benötigt. Was man in jedem Fall braucht, ist die Skalierung auf 0 ... 2PI und -PI ... +PI sowie von 0 ... 1, damit man sie gut (= bitgenau !) in das lokale INT-System der vorliegenden Rechnung übersetzen kann. Davon ausgehend habe ich mir Sinüsse für 32-Bit Binärphasen mit bitgenauer Skalierung geschrieben - sowie eine, die mit 1.0 = 232792560 funktioniert. Die erste habe ich mal gegen eine identisch formulierte von Mathworks antreten lassen, die sehr interessante Ergebnisse liefert (Simulink Blockset), welches sich ihrerseits von der Implementierung durch Xilinx unterscheidet, was beides für sich etwas verwundert. Die zweite Zahl stelle ich mal zur Diskussion.
... schrieb: > Ich wuesste keinen vitalen Grund, warum man die ganze Periode > approximieren sollte oder wollte. Es gibt auch keinen. Die Symmetrie-Eigenschaften sind bekannt und da man durch schieres Zurückführen auf den ersten Quadranten 2 Bit an Genauigkeit gewinnen kann, ohne dafür nur einen Finger bei der eigentlichen Approximation zu rühren, dann ist das quasi ein Geschenk. W.S.
Wir haben einen Fall wo eine komplette Welle implementiert wurde, nämlich die einer komprimierten Phase als Tchirp. Es wird pro Durchlauf um einen Faktor 2 komprimiert, um die Welle dauerhaft anschließen zu können.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.