imported>Müllt-Renner: /* Literatur */

2026-03-03T06:19:02Z

Literatur

Neue Seite

Der '''CORDIC-Algorithmus''' ({{enS|'''''Co'''ordinate '''R'''otation '''Di'''gital '''C'''omputer''}}) ist ein effizienter iterativer [[Algorithmus]], mit dessen Hilfe sich viele mathematische [[Funktion (Mathematik)|Funktionen]] implementieren lassen, wie [[trigonometrische Funktionen]], [[Exponentialfunktion]] und [[Logarithmus|Logarithmen]] sowie auch die einfache [[Multiplikation]] oder [[Division (Mathematik)|Division]].

== Motivation ==
In der Rechentechnik, vornehmlich in der [[digitale Signalverarbeitung|digitalen Signalverarbeitung]], benötigt man schnelle Verfahren für die Berechnung von bspw. [[Trigonometrische Funktion|trigonometrischen Funktionen]]. Herkömmliche [[Reihenentwicklung]]en wie die [[Taylorreihe]] zeigen oft nur mittelmäßige (d. h. langsame, oder gar von den Argumenten abhängige) [[Grenzwert (Folge)|Konvergenz]] und schlechte [[Stabilität (Numerik)|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. {{lang|en|''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 [[Trägheitsnavigationssystem|Navigationsrechner]] in [[Convair B-58|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 [[HP-9100A|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 [[Logarithmus|Logarithmen]], der [[Exponentialfunktion]] und der [[Quadratwurzel]] in digitalen Schaltungen möglich.

=== Anwendungsbeispiele ===
[[Datei:CORDIC (Bit-Parallel, Unrolled, Circular Rotation).svg|mini|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 [[Multiplizierer (Digitaltechnik)|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 [[FPGA]]s oder [[Anwendungsspezifische integrierte Schaltung|ASICs]].

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

== Funktionsweise ==
[[Datei:CORDIC-illustration.svg|mini|Illustration von CORDIC]]
CORDIC kann man im <math>\mathbb{R}^3</math>, aber auch nur in der zweidimensionalen Ebene betrachten. Im Folgenden umfasst die Beschreibung den einfacheren, zweidimensionalen Fall.

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

Die [[Rotationsmatrix|Rotation]] um den Winkel <math>\Theta</math> entspricht dem [[Matrix-Vektor-Produkt]]:

:<math>
\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}
</math>

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

:<math>
\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}
</math>

Die Drehung um <math>\Theta</math> wird trickreich realisiert als [[Linearkombination]] von Teildrehungen um geschickt gewählte Teilwinkel <math>\alpha_i</math>.

:<math>
\Theta = \sum_{i} \sigma_i\cdot\alpha_i \qquad \sigma_i \in \{-1,1\}
</math>

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

:<math>
z_0 = \Theta \qquad\quad
z_i = z_{i-1}-\sigma_{i-1}\cdot\alpha_{i-1}
</math>

:<math>
\sigma_i = \begin{cases}-1 & \mbox{falls}\quad z_{i-1}\le 0\\ 1 & \mbox{sonst} \end{cases}
</math>

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

:<math>\tan\alpha_i = 2^{-i}</math>.

Man erhält damit den folgenden Algorithmus:

:<math>
\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}
</math>

mit dem Skalierungsfaktor <math> K = \prod_{i=0}^{n-1} \cos\alpha_i \approx </math> 0,60725... für <math> n \to\infty </math>, der während der Initialisierungsphase implizit berechnet wird.

:<math>
x_{i+1} \,:=\, x_i - \sigma_i 2^{-i}y_i
</math>

:<math>
y_{i+1} \,:=\, y_i + \sigma_i 2^{-i}x_i
</math>

:<math>
z_{i+1} \,:=\, z_i - \sigma_i \arctan 2^{-i}
</math>

=== Initialisierung ===
Vorweg wird eine Tabelle <math> T </math> fester Länge <math> L </math> angelegt mit <math> T_1=\pi/4 = \arctan\delta_1</math>, wobei <math> \delta_1=1</math> ist. Die folgenden Werte sind: <math> T_{j} = \arctan\delta_j</math> mit <math>\delta_j=\delta_{j-1}/2</math>. (Die Werte des Arcustangens lassen sich mit der hier gut konvergierenden Potenzreihenentwicklung bestimmen.)

Die Länge <math> L </math> der Tabelle bestimmt die erreichbare Genauigkeit. Führt man alle Drehungen eines Einheitsvektors <math> (0,\;1)^T </math> mit den so berechneten Werten hintereinander in gleichem Drehsinn aus, erzielt man eine Gesamtdrehung von etwas mehr als <math>\pm \pi / 2 </math>. Der Skalenfaktor <math> K </math> wird mit einem Aufruf im Vektormodus (s. u.) berechnet, indem man die Verlängerung des Einheitsvektors <math> (0,1)^T </math> ohne Skalierung berechnet.

=== Rotationsmodus ===
Der Ausgangsvektor <math>(1,0)^T</math> wird in jedem der Schritte so gedreht, dass der Winkel <math>z = \Theta</math> gegen Null geht. Es werden stets alle <math> L </math> Teildrehungen ausgeführt, mit ggf. wechselndem [[Vorzeichen (Zahl)|Vorzeichen]]. Da der Kosinus eine gerade Funktion ist, spielt das Vorzeichen bei der Skalierung keine Rolle. Nach Reskalierung sind die Komponenten des erhaltenen Endvektors <math>\cos\Theta</math> und <math>\sin\Theta</math>. Der [[Konvergenzbereich]] ergibt sich zu <math>-\sum_{i=0}^{n-1}\arctan2^{-i}\le \Theta \le+\sum_{i=0}^{n-1}\arctan2^{-i}</math>, also bei genügend großem <math>n</math> etwa zu <math>-1{,}74\le \Theta \le+1{,}74</math>, 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 <math>y</math>-Komponente verringert. Die Drehwinkel <math>\Theta</math> werden dabei vorzeichenrichtig addiert. Die <math>x</math>-Komponente des Endvektors ist nach Reskalierung der Betrag des Ausgangsvektors. Dieser Modus wird auch benutzt zur Berechnung des Arcustangens aus zwei Argumenten, Start mit <math> c ( \cos \Theta, \sin \Theta)^T</math>. Der Konvergenzbereich ist derselbe wie oben.
Aus <math>\operatorname{arctan2}(y_0,x_0)</math> lassen sich die Funktionen <math>\arcsin y_0</math> und <math>\arccos x_0</math> unter Zuhilfenahme von <math>x_0^2+y_0^2=1</math> leicht ableiten.

=== Bereich außerhalb von ±π/2 ===

Der Startvektor <math> (0,1)^T </math> bzw. <math>(0,-1)^T </math> entspricht einer Vorwegdrehung von <math> \pi / 2 </math> bzw. <math> -\pi/2 </math> (für den Rotationsmodus). Bei einem Startvektor mit negativer <math>x</math>-Komponente im Vektormodus bewirkt man entsprechende Drehungen durch Vertauschen der Komponenten und Änderungen der Vorzeichen.

== Verallgemeinerung ==
Die oben benutzten Iterationsformeln
:<math>
\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}
</math>
sind ein Sonderfall der allgemeineren Vorschrift
:<math>
\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}
</math>
mit <math> m=1</math> und <math> \delta_i=2^{-i}</math> sowie <math> t_i=\arctan\delta_i</math>.

=== Lineare Modi ===
Für <math> m=0</math>, <math>\delta_i=t_i=[1,1/2, 1/4, 1/8, \dotsc]</math> und <math>k=1</math> erhält man
:<math>
\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}
</math>,
womit sich Multiplikation und Division durchführen lassen. Eine Tabelle <math>T</math> erübrigt sich hier.

;Multiplikation:
<math>x_0=a</math>, <math>z_0=b</math> ergibt im Rotationsmodus (<math>z</math> gegen 0) <math>y_n=y_0+a\cdot b</math> für alle <math>-2<b<2</math>.

;Division:
<math>x_0=b</math>, <math>y_0=a</math> ergibt im Vektormodus (<math>y</math> gegen 0) <math>z_n=z_0+a/b</math> für alle <math>-2<a/b<2</math>.

=== Hyperbolische Modi ===
Mit <math>m=-1</math> werden die Hyperbelfunktionen, ihre Umkehrungen ([[Areafunktion]]en), Exponentialfunktion und Logarithmus sowie die Quadratwurzel berechenbar. [[Einheitskreis]] bzw. -hyperbel werden durch <math>\sqrt{x^2+my^2}=1</math> mit <math>m=+1</math> bzw. <math>m=-1</math> beschrieben. Das zu einem Vektor <math>(x,y)^T</math> gehörende Winkel- bzw. Areaargument ist durch <math>\Theta= \arctan (\sqrt{m}\cdot y/x)/\sqrt{m}</math> gegeben, also
:<math>m=1</math>, Winkelfunktionen (s.o): <math>\Theta=\arctan(y/x)</math> und

<math>m=-1</math>, hyperbolische Fkt.:
:<math>\Theta=\arctan(iy/x)/i</math>
, hier <math>i^2=-1</math>; <math>i \Theta= \arctan(i y/x)</math>; und wegen <math>\operatorname{tanh}\alpha=-i \tan(i\alpha)</math> auch <math>\Theta=\operatorname{Atanh}(y/x)</math>.

Das Verfahren ist analog zu dem eingangs gezeigten für die Winkelfunktionen. Erforderlich sind nur eine weitere Tabelle mit <math>t_i=\operatorname{Atanh}\delta_i</math>, <math>\delta_i= [1/2, 1/4, 1/8, \dotsc]</math> und die einmalige Berechnung des Skalenfaktors <math>K</math>.

:<math>
\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}</math>

Die Iterationen <math>i= 4, 13, 40, k, 3k+1</math> müssen immer wiederholt werden, da der [[Areatangens hyperbolicus]] nicht die Bedingung <math>t_{i+1} \le \tfrac{1}{2} t_i</math> erfüllt, das somit für die Reihe <math>\sum\sigma_i t_i</math> nicht konvergieren würde.

Rotation mit <math>[x_0, y_0]=[1, 0]</math> liefert:
_<math>x_n=\operatorname{cosh}z_0,\quad y_n=\operatorname{sinh} z_0</math>,

davon abgeleitet:
:<math>\operatorname{tanh}z=\operatorname{sinh}z/\operatorname{cosh}z</math> und <math>e^z=\operatorname{cosh}z+\operatorname{sinh}z</math>

Vektormodus mit <math>z_0=0</math> berechnet:
: <math>z_n=\operatorname{Atanh}(y_0/x_0)</math>
und den hyperbolischen Betrag
:<math>x_n=\sqrt{x_0^2-y_0^2}</math>

davon abgeleitet:
:<math>\ln w=2\operatorname{Atanh}\frac{w-1}{w+1}</math>
sowie
:<math>\sqrt{w}</math>
aus dem Betrag des Startvektors <math>[w+1/4, w-1/4]</math>

Der Konvergenzbereich ist in beiden Modi beschränkt durch die maximal mögliche Änderung von <math>z</math>. Alle mathematisch erlaubten Argumente können jedoch durch einfache Umstellungen und Shift-Operationen auf ihn abgebildet werden.

== Alternativen ==
Als Alternativen kommen hauptsächlich schnelle [[Lookup-Tabelle|Lookuptable]]-Verfahren in Frage, wie in [[Digitaler Signalprozessor|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.
* [http://baykov.de/cordic1972.htm Vladimir Baykov: ''Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique''. PhD thesis, Leningrad State Univ. of Electrical Eng., 1972.]
* [http://baykov.de/cordic1975.htm V. D. Baykov, V. B. Smolov: ''Hardware implementation of elementary functions in computers''. Leningrad State University, 1975, 96p.]
* V. D. Baykov, S. A. Seljutin: ''Elementary functions evaluation in microcalculators''. Radio & svjaz, Moscow 1982, 64p.
*[http://baykov.de/cordic1985.htm 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.'' 1994.
* Jean-Michel Muller: ''Elementary Functions''. Verlag Birkhäuser, 2006, ISBN 0-8176-4372-9.

== Weblinks ==
* [https://cordic-bibliography.blogspot.de/p/what-is-cordic.html CORDIC Bibliography Site]
* http://www.andraka.com/cordic.php
* [http://www.emesys.com/BS2mathC.htm BASIC Stamp II math note #C]
* [https://opencores.org/project,cordic VHDL-Implementierung des CORDIC-Algorithmus auf Opencores.org]

{{SORTIERUNG:Cordic}}
[[Kategorie:Algorithmus]]
[[Kategorie:Computerarithmetik]]
[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Abkürzung|CORDIC]]

CORDIC - Versionsgeschichte

imported>Müllt-Renner: /* Literatur */