Bücher / Ressourcen zur Implementierung verschiedener mathematischer Funktionen in Festkomma-Arithmetik für DSP-Zwecke

8

Ich suche nach Büchern oder Ressourcen, die Folgendes im Detail behandeln:

  • Implementieren mathematischer Funktionen (z. B. Logarithmus, Exponential, Sinus, Cosinus, Inverse) in Festkomma-Arithmetik für DSP-Zwecke.

  • Techniken wie die Verwendung von Nachschlagetabellen, Taylor-Serien usw.

Ich bin ziemlich vertraut mit der C-Programmierung und interessiere mich mehr für die Algorithmen, wie verschiedene mathematische Funktionen effizient implementiert werden können.

RuD
quelle
1
Dies ist nur ein Trick, aber sehr nützlich. Es geht darum, die atan2-Funktion zu berechnen, dh das Argument einer komplexen Zahl aus ihren Real- und Imaginärteilen zu berechnen.
Matt L.
1
Ich kann Ihnen einige optimierte Potenzreihen endlicher Ordnung geben, die ich vor mehr als einem Jahrzehnt entwickelt habe. Abgesehen vom ursprünglichen Kunden habe ich seitdem kein Geld mehr dafür bekommen, also denke ich, dass ich es genauso gut gemeinfrei machen kann. Ursprünglich wurde es für Gleitkommazahlen in einem Kontext entwickelt, in dem der Client die stdlib nicht in den Build aufnehmen konnte. und die Bewertung ist nicht ein bisschen perfekt. dh es liegt ein Fehler vor, der jedoch sehr klein und für die jeweilige zu bewertende Funktion optimiert ist. Wenn ich diese Datei finde, ziehe ich die Koeffizienten heraus und poste die Serien.
Robert Bristow-Johnson
@ robertbristow-johnson ich freue mich darauf, die serie zu nutzen und zu sehen, wie es geht! Vielen Dank!
RuD
Ruchir, ich habe die Serie unten gepostet. Es gibt vernünftige Dinge, die Sie tun müssen, um die Reichweite zu erweitern. wie wenn . Ähnliches gilt für und die periodischen Sinuskurven. Für exp und log erfordert dies eine arithmetische Bitverschiebung dessen, was herauskommt (für exp) oder was hineingeht (für log). Ich denke, Sie können das herausfinden. und natürlich skalieren Sie für exp und log verschiedener Basen (wie ) einfach mit der entsprechenden Konstante, was in eingeht und was aus . k x k + 1 log 2 ( ) e 2 x log 2 ( x )
2x=2k×2xk
kxk+1log2()e2xlog2(x)
Robert Bristow-Johnson

Antworten:

9

Die allgemeine Polynomform lautet:

f(u)=n=0N an un=a0+(a1+(a2+(a3+...(aN2+(aN1+aNu)u)u ...)u)u)u

Die letztere Form verwendet die Horner-Methode , die sehr zu empfehlen ist, insbesondere wenn Sie dies in Gleitkommazahlen mit einfacher Genauigkeit tun.

dann für ein paar spezifische Funktionen:

Quadratwurzel:

f(x1)x1x2N=4a0=1.0a1=0.49959804148061a2=0.12047308243453a3=0.04585425015501a4=0.01076564682800

Wenn , verwenden Sie die obigen , um auszuwerten und das Ergebnis mit zu multiplizieren, um . wie bei die Skalierungskraft an, um das Argument auf den erforderlichen Bereich zu skalieren.2x4x22 log2(x)2xlog2(x)2

Logarithmus zur Basis 2:

xf(x1)log2(x)1x2N=5a0=1.44254494359510a1=0.7181452567504a2=0.45754919692582a3=0.27790534462866a4=0.121797910687826a5=0.02584144982967

Basis 2 exponentiell:

f(x)2x0x1N=4a0=1.0a1=0.69303212081966a2=0.24137976293709a3=0.05203236900844a4=0.01355574723481

Sinus:

xf(x2)sin(π2x)1x1N=4a0=1.57079632679490a1=0.64596406188166a2=0.07969158490912a3=0.00467687997706a4=0.00015303015470

Cosinus (Sinus verwenden):

cos(πx)=12sin2(π2x)

Tangente:

tan(x)=sin(x)cos(x)

inverse Tangente:

xf(x2)arctan(x)1x1N=4a0=1.0a1=0.33288950512027a2=0.08467922817644a3=0.03252232640125a4=0.00749305860992

arctan(x)=π2arctan(1x)1x

arctan(x)=π2arctan(1x)x1

inverser Sinus:

arcsin(x)=arctan(x1x2)

inverser Kosinus:

arccos(x)=π2arcsin(x)=π2arctan(x1x2)
robert bristow-johnson
quelle
Das scheint ziemlich nützlich zu sein! Vielen Dank für das Teilen. Aber immer noch ist der erste Referenzeintrag in man soxam besten;)
jojek
Keine Ahnung sox. Was sagt das Handbuch dazu?
Robert Bristow-Johnson
2
Einfach [1] R. Bristow-Johnson, Cookbook formulae for audio EQ biquad filter coefficients, http://musicdsp.org/files/Audio-EQ-Cookbook.txt:)
Jojek
Übrigens minimiert die Serie den maximal gewichteten Fehler. Fehler werden so gewichtet, dass sie für die Funktion sinnvoll sind. einheitlicher maximaler Fehler für . proportionaler maximaler Fehler für und . etwas Ähnliches wie proportional für hat mit der Berechnung von Koeffizienten für Resonanzfilter zu tun, so dass der maximale Fehler von minimiert wird. Ich kann mich nicht erinnern, welches Kriterium ich für . und aus irgendeinem Grund kann ich meine Datei nicht finden, die mir sagt, was die maximalen Fehler sind, angesichts des Bereichs von . jemand mit MATLAB kann es herausfinden. log2()x2xsin()log(f0)arctan()x
Robert Bristow-Johnson
1
Sie sollten den Fehler mit Ihrer Python zeichnen, wenn Sie können. auch np.max(np.abs(sqrt_1px(xp)-np.sqrt(1+xp)))könnte stattdessen sein np.max(np.abs((sqrt_1px(xp)-np.sqrt(1+xp))/np.sqrt(1+xp))) und gleiche gilt für 2**x die Fehlergewichtung für die Sünde ist anders und ich muss feststellen , wie ich das tat. Ich habe alte MATLAB-Skripte, die früher in Octave funktionierten, aber jetzt kann ich Octave nicht einmal dazu bringen, auf meinem alten G4 Mac-Laptop zu zeichnen.
Robert Bristow-Johnson
2

Obwohl nicht spezifisch für den Fixpunkt, würde ich das Buch "Math Toolkit for Real-Time Programming" von Jack Crenshaw wärmstens empfehlen. Es wird mit einer CD mit dem Quellcode geliefert.

David
quelle
2

TI verfügt über IQMath-Bibliotheken für alle Festkomma-Mikrocontroller. Ich habe festgestellt, dass sie eine Goldmine von Festkomma-Mathematik- und DSP-Funktionen sind, die nicht unbedingt auf TI-Chips beschränkt sind.

MSP430 C28X

Otto Hunt
quelle
Ich interessiere mich mehr für die Algorithmen als nur für die Implementierung der Funktionen
RuD
1

Die Chebyshev-Näherung kann dabei helfen, Polynomkoeffizienten zu berechnen, die nahezu optimal sind, um eine Funktion über einen endlichen Bereich zu approximieren. Sie führen die Approximationsroutine auf einem PC aus, um einen bestimmten Satz von Polynomkoeffizienten zu erzielen, die Sie dann auf eine beliebige Plattform anwenden können (z. B. Embedded / DSP). Das Kleingedruckte ist mehr oder weniger wie folgt:

  • z=f(x,y)
  • Die Funktion, die Sie approximieren, sollte "polynomartig" sein. Ecken, scharfe Biegungen und viele Wackelbewegungen erfordern Polynome höherer Ordnung, um ein bestimmtes Maß an Genauigkeit zu erreichen.
  • Es ist wichtig, die Polynomreihenfolge niedrig zu halten - über dem 5. oder so können numerische Fehler auftreten.
  • x[0,20]u=(x×0.1)1uuum das gewünschte Ergebnis zu berechnen. Ohne diese Skalierung können numerische Fehler leichter auftreten - oder anders ausgedrückt: Bei gleicher Genauigkeit benötigen Sie möglicherweise höhere Bitlängen, um Zwischenwerte zu berechnen. Dies ist normalerweise unerwünscht.
Jason S.
quelle
L
Remez ist überlegen (wenn auch komplexer) als Chebyshev. Chebyshev nähert sich nur dem Minimax-Zustand an, aber normalerweise ist es gut genug.
Jason S