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.

algorithms reference-request math fixed-point 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 .

2^{x} = 2^{k} \times 2^{x - k}

$2^x = 2^k \times 2^{x-k}$

k \leq x \leq k + 1

$k \le x \le k+1$

\log_{2} ()

$\log_2()$

e

$e$

2^{x}

$2^x$

\log_{2} (x)

$\log_2(x)$

Robert Bristow-Johnson

9

Die allgemeine Polynomform lautet:

\begin{aligned} f (u) & = \sum_{n = 0}^{N} a_{n} u^{n} \\ = a_{0} + (a_{1} + (a_{2} + (a_{3} + . . . (a_{N - 2} + (a_{N - 1} + a_{N} u) u) u . . .) u) u) u \end{aligned}

$\begin{align} f(u) &= \sum\limits_{n=0}^{N} \ a_n \ u^n \\ \\ &= a_{\small{0}} + \Bigg(a_{\small{1}} + \bigg(a_{\small{2}} + \Big(a_{\small{3}} + \,... \big(a_{\small{N-2}} + (a_{\small{N-1}} + a_{\small{N}} \,u \,)u \, \big)u \ ...\Big)u \, \bigg)u \, \Bigg)u\\ \end{align}$

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:

\begin{aligned} f (x - 1) & \approx \sqrt{x} 1 \leq x \leq 2 N = 4 \\ a_{0} & = 1.0 \\ a_{1} & = 0.49959804148061 \\ a_{2} & = - 0.12047308243453 \\ a_{3} & = 0.04585425015501 \\ a_{4} & = - 0.01076564682800 \end{aligned}

$\begin{align} f(x-1) & \approx \sqrt{x} \quad \quad 1 \le x \le 2 \quad \quad N=4\\ a_0 & = 1.0 \\ a_1 & = 0.49959804148061 \\ a_2 & = -0.12047308243453 \\ a_3 & = 0.04585425015501 \\ a_4 & = -0.01076564682800 \\ \end{align}$

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. $2 \le x \le 4$ $\sqrt{\tfrac{x}{2}}$ $\sqrt{2}$ $\sqrt{x}$ $\log_2(x)$ $2$

Logarithmus zur Basis 2:

\begin{aligned} x \cdot f (x - 1) & \approx \log_{2} (x) 1 \leq x \leq 2 N = 5 \\ a_{0} & = 1.44254494359510 \\ a_{1} & = - 0.7181452567504 \\ a_{2} & = 0.45754919692582 \\ a_{3} & = - 0.27790534462866 \\ a_{4} & = 0.121797910687826 \\ a_{5} & = - 0.02584144982967 \end{aligned}

$\begin{align} x\cdot f(x-1) & \approx \log_2(x) \quad \quad 1 \le x \le 2 \quad \quad N=5\\ a_0 & = 1.44254494359510 \\ a_1 & = -0.7181452567504 \\ a_2 & = 0.45754919692582 \\ a_3 & = -0.27790534462866 \\ a_4 & = 0.121797910687826 \\ a_5 & = -0.02584144982967 \\ \end{align}$

Basis 2 exponentiell:

\begin{aligned} f (x) & \approx 2^{x} 0 \leq x \leq 1 N = 4 \\ a_{0} & = 1.0 \\ a_{1} & = 0.69303212081966 \\ a_{2} & = 0.24137976293709 \\ a_{3} & = 0.05203236900844 \\ a_{4} & = 0.01355574723481 \end{aligned}

$\begin{align} f(x) & \approx 2^x \quad \quad 0 \le x \le 1 \quad \quad N=4\\ a_0 & = 1.0 \\ a_1 & = 0.69303212081966 \\ a_2 & = 0.24137976293709 \\ a_3 & = 0.05203236900844 \\ a_4 & = 0.01355574723481 \\ \end{align}$

Sinus:

\begin{aligned} x \cdot f (x^{2}) & \approx \sin (\frac{π}{2} x) - 1 \leq x \leq 1 N = 4 \\ a_{0} & = 1.57079632679490 \\ a_{1} & = - 0.64596406188166 \\ a_{2} & = 0.07969158490912 \\ a_{3} & = - 0.00467687997706 \\ a_{4} & = 0.00015303015470 \end{aligned}

$\begin{align} x\cdot f(x^2) & \approx \sin\left(\tfrac{\pi}{2} x \right) \quad \quad -1 \le x \le 1 \quad \quad N=4 \\ a_0 & = 1.57079632679490 \\ a_1 & = -0.64596406188166 \\ a_2 & = 0.07969158490912 \\ a_3 & = -0.00467687997706 \\ a_4 & = 0.00015303015470 \\ \end{align}$

Cosinus (Sinus verwenden):

\cos (π x) = 1 - 2 \sin^{2} (\frac{π}{2} x)

$\cos(\pi x) = 1 \, - \, 2 \, \sin^2 \left(\tfrac{\pi}{2} x \right)$

Tangente:

\tan (x) = \frac{\sin (x)}{\cos (x)}

$\tan(x) = \frac{\sin(x)}{\cos(x)}$

inverse Tangente:

\begin{aligned} \frac{x}{f (x^{2})} & \approx \arctan (x) - 1 \leq x \leq 1 N = 4 \\ a_{0} & = 1.0 \\ a_{1} & = 0.33288950512027 \\ a_{2} & = - 0.08467922817644 \\ a_{3} & = 0.03252232640125 \\ a_{4} & = - 0.00749305860992 \end{aligned}

$\begin{align} \frac{x}{f(x^2)} & \approx \arctan(x) \quad \quad -1 \le x \le 1 \quad \quad N=4 \\ a_0 & = 1.0 \\ a_1 & = 0.33288950512027 \\ a_2 & = -0.08467922817644 \\ a_3 & = 0.03252232640125 \\ a_4 & = -0.00749305860992 \\ \end{align}$

\arctan (x) = \frac{π}{2} - \arctan (\frac{1}{x}) 1 \leq x

$\arctan(x) = \tfrac{\pi}{2} - \arctan\left( \tfrac{1}{x} \right) \quad \quad 1 \le x$

\arctan (x) = - \frac{π}{2} - \arctan (\frac{1}{x}) x \leq - 1

$\arctan(x) = -\tfrac{\pi}{2} - \arctan\left( \tfrac{1}{x} \right) \quad \quad x \le -1$

inverser Sinus:

\arcsin (x) = \arctan (\frac{x}{\sqrt{1 - x^{2}}})

$\arcsin(x) = \arctan\left( \frac{x}{\sqrt{1-x^2}} \right)$

inverser Kosinus:

\begin{aligned} \arccos (x) & = \frac{π}{2} - \arcsin (x) \\ = \frac{π}{2} - \arctan (\frac{x}{\sqrt{1 - x^{2}}}) \end{aligned}

$\begin{align} \arccos(x) &= \frac{\pi}{2} - \arcsin(x) \\ &= \frac{\pi}{2} - \arctan\left( \frac{x}{\sqrt{1-x^2}} \right)\\ \end{align}$

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.

\log_{2} ()

$\log_2()$

\sqrt{x}

$\sqrt{x}$

2^{x}

$2^x$

\sin ()

$\sin()$

\log (f_{0})

$\log(f_0)$

\arctan ()

$\arctan()$

x

$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 \in [0,20]$ $u = (x\times 0.1) - 1$ $u$ $u$ um 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_{\infty}

$L_\infty$

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

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

Antworten: