CORDIC

Der CORDIC-Algorithmus (englisch Coordinate Rotation Digital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele mathematische Funktionen implementieren lassen, wie z. B. trigonometrische Funktionen, Exponentialfunktion und Logarithmen sowie auch die einfache Multiplikation oder Division.

Motivation

In der Rechentechnik, vornehmlich in der digitalen Signalverarbeitung, benötigt man schnelle Verfahren für die Berechnung von bspw. trigonometrischen Funktionen. Herkömmliche Reihenentwicklungen wie z. B. die Taylorreihe zeigen oft nur mittelmäßige (d. h. langsame, oder gar von den Argumenten abhängige) Konvergenz und schlechte numerische Stabilität. Eine Reihenentwicklung besteht außerdem hauptsächlich aus einer Summe von Produkten, die nur aufwendig zu berechnen sind.

Geschichtliche Entwicklung

Der CORDIC-Algorithmus wurde 1959 von Jack E. Volder präsentiert. In der ursprünglichen Version war es damit möglich, trigonometrische Funktionen wie Sinus, Cosinus und Tangens sowie die Multiplikation und Division von Zahlen allein durch die in digitalen Schaltungen einfach realisierbaren Additionen und Schiebeoperationen (engl.

shift-and-add operations

) zu bilden. Schiebeoperationen zur Zahlenbasis 2 sind in digitalen Schaltungen sehr leicht durch entsprechende Verschaltung realisierbar.

Volders Motivation war der Ersatz der üblichen und fehleranfälligen analogen Navigationsrechner in Convair-B-58-Bombern durch digitale Rechner zur genauen Positionsbestimmung. Die Anforderung war die Positionsberechnung der mit Überschallgeschwindigkeit fliegenden Bomber in Echtzeit über einer vereinfacht als kugelförmig angenommenen Erdoberfläche.

Mitte der 1960er Jahre wurde der CORDIC-Algorithmus auch in zivilen Anwendungen eingesetzt. Vorläufer der heutigen Taschenrechner wie der Tischrechner 9100 von Hewlett-Packard aus dem Jahr 1968 setzten ihn zur Berechnung der trigonometrischen Funktionen ein.

Im Jahr 1971 wurde der CORDIC-Algorithmus von J. S. Walther auf die heute übliche Form erweitert und damit auch die effiziente Berechnung von Logarithmen, der Exponentialfunktion und der Quadratwurzel in digitalen Schaltungen möglich.

Anwendungsbeispiele

Digitalschaltung CORDIC

CORDIC-Algorithmen werden zur Berechnung der wichtigsten Elementarfunktionen in Mikrocontroller-Rechenwerken wie Taschenrechnern eingesetzt. So findet sich auch in arithmetischen x87-Koprozessoren von Intel der CORDIC-Algorithmus zur Berechnung mathematischer Operationen. Weitere Anwendungsbeispiele liegen in der Nachrichtenübertragung. Damit lassen sich beispielsweise effizient Betrag und Phase eines komplexen Signals bestimmen.

Da Multiplizierwerke vor allem in digitalen Schaltungen umfangreich und damit teuer zu realisieren sind, wird CORDIC oft genau da eingesetzt, wo Multiplizierer nicht effizient verfügbar sind. Dies umfasst vor allem den Bereich der digitalen Schaltungstechniken wie FPGAs oder ASICs.

CORDIC ist zwar nicht der schnellste Algorithmus, wird aber wegen seiner Einfachheit und Vielseitigkeit oft eingesetzt.

Funktionsweise

Illustration von CORDIC

CORDIC kann man im $\mathbb {R} ^{3}$, aber auch nur in der zweidimensionalen Ebene betrachten. Im Folgenden umfasst die Beschreibung den einfacheren, zweidimensionalen Fall.

Dreht man ein Koordinatensystem um den Winkel $\Theta$, erscheint der Vektor $(1,\;0)^{T}$ um den Winkel $\Theta$ gedreht; sein Endpunkt liegt im neuen System bei $x=\cos \Theta$ und $y=\sin \Theta$.

Die Rotation um den Winkel $\Theta$ entspricht dem Matrix-Vektor-Produkt:

${\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}}={\begin{pmatrix}\cos \Theta &-\sin \Theta \\\sin \Theta &\cos \Theta \end{pmatrix}}\cdot {\begin{pmatrix}1\\0\end{pmatrix}}$

D. h., um auf den eigentlichen Funktionswert zu kommen, muss der Einheitsvektor $(1,\;0)^{T}$ um $\Theta$ gedreht werden. Dies lässt sich leichter bewerkstelligen, wenn innerhalb der Transformationsmatrix nur noch eine Abhängigkeit von einer Winkelfunktion, z. B. $\tan$ besteht:

${\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}}=\cos \Theta \cdot {\begin{pmatrix}1&-\tan \Theta \\\tan \Theta &1\end{pmatrix}}\cdot {\begin{pmatrix}1\\0\end{pmatrix}}$

Die Drehung um $\Theta$ wird trickreich realisiert als Linearkombination von Teildrehungen um geschickt gewählte Teilwinkel $\alpha _{i}$.

$\Theta =\sum _{i}\sigma _{i}\cdot \alpha _{i}\qquad \sigma _{i}\in \{-1,1\}$

Eine zu weite Drehung im Schritt $i$ wird kompensiert durch einen Vorzeichenwechsel $\sigma _{i+1}:=-\sigma _{i}$. Das gezeigte Verfahren konvergiert und ist numerisch stabil für alle $\Theta$, die sich aus obiger Summe ergeben können. Man führt nun noch eine Hilfsvariable $z$ ein, die für den Drehsinn Verantwortung trägt:

$z_{0}=\Theta \qquad \quad z_{i}=z_{i-1}-\sigma _{i-1}\cdot \alpha _{i-1}$

$\sigma _{i}={\begin{cases}-1&{\mbox{falls}}\quad z_{i}\leq 0\\1&{\mbox{sonst}}\end{cases}}$

Wenn nur einfachste Bauteile verwendet werden sollen und daher keine Multiplizierer vorhanden sind, muss man alles über Schiebe- und Addieroperationen bewerkstelligen. Dieses wird erreicht durch den Ansatz

$\tan \alpha _{i}=2^{-i}$.

Man erhält damit den folgenden Algorithmus:

${\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}}=\prod _{i=0}^{n-1}\cos \alpha _{i}{\begin{pmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{pmatrix}}\cdot {\begin{pmatrix}x_{0}\\y_{0}\end{pmatrix}}=K\cdot \prod _{i=0}^{n-1}{\begin{pmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{pmatrix}}\cdot {\begin{pmatrix}x_{0}\\y_{0}\end{pmatrix}}$

mit dem Skalierungsfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K = \prod_{i=0}^{n-1} \cos\alpha_i \approx } 0,60725... für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \to\infty } , der während der Initialisierungsphase implizit berechnet wird.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{i+1} \,:=\, x_i - \sigma_i 2^{-i}y_i }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_{i+1} \,:=\, y_i + \sigma_i 2^{-i}x_i }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{i+1} \,:=\, z_i - \sigma_i \arctan 2^{-i} }

Initialisierung

Vorweg wird eine Tabelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T } fester Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L } angelegt mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_1=\pi/4 = \arctan\delta_1} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_1=1} ist. Die folgenden Werte sind: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_{j} = \arctan\delta_j} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_j=\delta_{j-1}/2} . (Die Werte des Arcustangens lassen sich mit der hier gut konvergierenden Potenzreihenentwicklung bestimmen.)

Die Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L } der Tabelle bestimmt die erreichbare Genauigkeit. Führt man alle Drehungen eines Einheitsvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (0,\;1)^T } mit den so berechneten Werten hintereinander in gleichem Drehsinn aus, erzielt man eine Gesamtdrehung von etwas mehr als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pm \pi / 2 } . Der Skalenfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K } wird mit einem Aufruf im Vektormodus (s. u.) berechnet, indem man die Verlängerung des Einheitsvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (0,1)^T } ohne Skalierung berechnet.

Rotationsmodus

Der Ausgangsvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1,0)^T} wird in jedem der Schritte so gedreht, dass der Winkel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z = \Theta} gegen Null geht. Es werden stets alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L } Teildrehungen ausgeführt, mit ggf. wechselndem Vorzeichen. Da der Kosinus eine gerade Funktion ist, spielt das Vorzeichen bei der Skalierung keine Rolle. Nach Reskalierung sind die Komponenten des erhaltenen Endvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cos\Theta} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sin\Theta} . Der Konvergenzbereich ergibt sich zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -\sum_{i=0}^{n-1}\arctan2^{-i}\le \Theta \le+\sum_{i=0}^{n-1}\arctan2^{-i}} , also bei genügend großem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} etwa zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -1{,}74\le \Theta \le+1{,}74} , d. h., er erstreckt sich über mehr als den vierten und ersten Quadranten.

Vektormodus

Der vorgegebene Vektor, dessen Polarkoordinaten gesucht werden, wird immer so gedreht, dass sich der Betrag seiner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} -Komponente verringert. Die Drehwinkel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta} werden dabei vorzeichenrichtig addiert. Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} -Komponente des Endvektors ist nach Reskalierung der Betrag des Ausgangsvektors. Dieser Modus wird auch benutzt zur Berechnung des Arcustangens aus zwei Argumenten, Start mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c ( \cos \Theta, \sin \Theta)^T} . Der Konvergenzbereich ist derselbe wie oben. Aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{arctan2}(y_0,x_0)} lassen sich die Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \arcsin y_0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \arccos x_0} unter Zuhilfenahme von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0^2+y_0^2=1} leicht ableiten.

Bereich außerhalb von ±π/2

Der Startvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (0,1)^T } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (0,-1)^T } entspricht einer Vorwegdrehung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi / 2 } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -\pi/2 } (für den Rotationsmodus). Bei einem Startvektor mit negativer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} -Komponente im Vektormodus bewirkt man entsprechende Drehungen durch Vertauschen der Komponenten und Änderungen der Vorzeichen.

Verallgemeinerung

Die oben benutzten Iterationsformeln

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} x_i \\ y_i \end{pmatrix} = \cos \Theta \cdot \begin{pmatrix} 1 & -\tan\Theta \\ \tan\Theta & 1 \end{pmatrix}\cdot \begin{pmatrix} x_{i-1} \\ y_{i-1} \end{pmatrix} }

sind ein Sonderfall der allgemeineren Vorschrift

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} x_i \\ y_i \\ z_i \end{pmatrix} = k_i\cdot \begin{pmatrix} 1 & -m\sigma_i \delta_i& 0 & 0\\ \sigma_i \delta_i& 1 & 0 & 0 \\ 0 & 0 & 1 &-\sigma_i t_i \end{pmatrix}\cdot \begin{pmatrix} x_{i-1}\\ y_{i-1}\\ z_{i-1} \\1 \end{pmatrix} }

mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_i=2^{-i}} sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_i=\arctan\delta_i} .

Lineare Modi

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=0} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_i=t_i=[1,1/2, 1/4, 1/8, \dotsc]} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=1} erhält man

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} x_i \\ y_i \\ z_i \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 &0\\ \sigma_i \delta_i & 1 & 0 &0\\ 0 & 0 & 1 &-\sigma_i \delta_i \end{pmatrix}\cdot \begin{pmatrix} x_{i-1}\\ y_{i-1}\\ z_{i-1}\\1 \end{pmatrix} } ,

womit sich Multiplikation und Division durchführen lassen. Eine Tabelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} erübrigt sich hier.

Multiplikation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0=a} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_0=b} ergibt im Rotationsmodus (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} gegen 0) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_n=y_0+a\cdot b} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -2<b<2} .

Division

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0=b} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_0=a} ergibt im Vektormodus (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} gegen 0) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_n=z_0+a/b} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -2<a/b<2} .

Hyperbolische Modi

Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=-1} werden die Hyperbelfunktionen, ihre Umkehrungen (Areafunktionen), Exponentialfunktion und Logarithmus sowie die Quadratwurzel berechenbar. Einheitskreis bzw. -hyperbel werden durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{x^2+my^2}=1} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=+1} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=-1} beschrieben. Das zu einem Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y)^T} gehörende Winkel- bzw. Areaargument ist durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta= \arctan (\sqrt{m}\cdot y/x)/\sqrt{m}} gegeben, also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=1} , Winkelfunktionen (s.o): Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta=\arctan(y/x)} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=-1} , hyperbolische Fkt.:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta=\arctan(iy/x)/i}

, hier Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i^2=-1} ; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \Theta= \arctan(i y/x)} ; und wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{tanh}\alpha=-i \tan(i\alpha)} auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta=\operatorname{Atanh}(y/x)} .

Das Verfahren ist analog zu dem eingangs gezeigten für die Winkelfunktionen. Erforderlich sind nur eine weitere Tabelle mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_i=\operatorname{Atanh}\delta_i} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_i= [1/2, 1/4, 1/8, \dotsc]} und die einmalige Berechnung des Skalenfaktors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} x_i \\ y_i \\ z_i \end{pmatrix} = k_i\cdot \begin{pmatrix} 1 & \sigma_i \delta_i& 0 & 0\\ \sigma_i \delta_i& 1 & 0 & 0 \\ 0 & 0 & 1 &-\sigma_i t_i \end{pmatrix}\cdot \begin{pmatrix} x_{i-1}\\ y_{i-1}\\ z_{i-1} \\1 \end{pmatrix}}

Die Iterationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i= 4, 13, 40, k, 3k+1} müssen immer wiederholt werden, da der Areatangens hyperbolicus nicht die Bedingung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_{i+1} \le \tfrac{1}{2} t_i} erfüllt, das somit für die Reihe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum\sigma_i t_i} nicht konvergieren würde.

Rotation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [x_0, y_0]=[1, 0]} liefert: _Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_n=\operatorname{cosh}z_0,\quad y_n=\operatorname{sinh} z_0} ,

davon abgeleitet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{tanh}z=\operatorname{sinh}z/\operatorname{cosh}z} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e^z=\operatorname{cosh}z+\operatorname{sinh}z}

Vektormodus mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_0=0} berechnet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_n=\operatorname{Atanh}(y_0/x_0)}

und den hyperbolischen Betrag

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_n=\sqrt{x_0^2-y_0^2}}

davon abgeleitet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ln w=2\operatorname{Atanh}\frac{w-1}{w+1}}

sowie

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{w}}

aus dem Betrag des Startvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [w+1/4, w-1/4]}

Der Konvergenzbereich ist in beiden Modi beschränkt durch die maximal mögliche Änderung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} . Alle mathematisch erlaubten Argumente können jedoch durch einfache Umstellungen und Shift-Operationen auf ihn abgebildet werden.

Alternativen

Als Alternativen kommen hauptsächlich schnelle Tablelookup-Verfahren in Frage, wie z. B. in DSPs, und Bitalgorithmen, die mit einem ähnlichen Ansatz wie CORDIC die Berechnung vornehmen.

Literatur

• Jack E. Volder: The CORDIC Trigonometric Computing Technique. In: IRE Transactions on Electronic Computers. September 1959.
• D. H. Daggett: Decimal-Binary conversions in CORDIC. In: IRE Transactions on Electronic Computers. Vol. EC-8 #5, pp 335–339, IRE, September 1959.
• J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes. In: IBM Journal. April 1962.
• Vladimir Baykov: Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique. PhD thesis, Leningrad State Univ. of Electrical Eng., 1972.
• Hermann Schmid: Decimal computation. Wiley, New York 1974.
• V. D. Baykov, V. B. Smolov: Hardware implementation of elementary functions in computers. Leningrad State University, 1975, 96p.
• Don Senzig, Don: Calculator Algorithms. In: IEEE Compcon Reader Digest. IEEE Catalog No. 75 CH 0920-9C, pp 139-141, IEEE, 1975.
• V. D. Baykov, S. A. Seljutin: Elementary functions evaluation in microcalculators. Radio & svjaz, Moscow 1982, 64p.
• Vladimir D. Baykov, Vladimir B. Smolov: Special-purpose processors: iterative algorithms and structures. Radio & svjaz, Moscow 1985, 288 pages.
• M. E. Frerking: Digital Signal Processing in Communication Systems. 199.
• Vitit Kantabutra: On hardware for computing exponential and trigonometric functions. In: IEEE Trans. Computers. 45 (3), 328–339 (1996).
• Ray Andraka: A survey of CORDIC algorithms for FPGA based computers.
• Jean-Michel Muller: Elementary Functions. Verlag Birkhäuser, 2006, ISBN 0-8176-4372-9.

Weblinks

• CORDIC Bibliography Site
• http://www.andraka.com/cordic.php
• BASIC Stamp II math note #C
• VHDL-Implementierung des CORDIC-Algorithmus auf Opencores.org