Cordic


Cordic

Der CORDIC-Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die einfache Multiplikation oder Division.

Inhaltsverzeichnis

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 welche 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 möglich, damit trigonometrische Funktionen wie Sinus, Cosinus und Tangens und die Multiplikation und Division von Zahlen nur durch die in digitalen Schaltungen einfach realisierbare Additionen und Schiebeoperationen (engl. shift-and-add operations) zu bilden. Schiebeoperationen zur Zahlenbasis 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 als vereinfacht 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 den CORDIC-Algorithmus zur Berechnung der trigonometrischen Funktionen ein.

Erst 1971 wurde von J. S. Walther der CORDIC-Algorithmus 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

CORDIC-Algorithmen werden zur Berechnung der wichtigsten Elementarfunktionen in Mikrocontroller-Rechenwerken wie Taschenrechnern eingesetzt. So findet sich auch im arithmetischen Koprozessor 8087 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 zur 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 seiner Einfachheit und Vielseitigkeit wegen oft eingesetzt.

Funktionsweise (Zweidimensional)

CORDIC kann man im \mathbb ~^{R^3}, aber auch nur in der zweidimensionalen Ebene betrachten.

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

Die Rotation um den Winkel Θ 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 Θ 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 Θ wird trickreich realisiert als Linearkombination von Teildrehungen um geschickt gewählte Teilwinkel α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 σi + 1: = − σi. Das gezeigte Verfahren konvergiert und ist numerisch stabil für alle Θ, 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-1}\le 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  K = \prod_{i=0}^{n-1} \cos\alpha_i , der während der Initialisierungsphase implizit berechnet wird.


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


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


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

Initialisierung

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

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

Rotationsmodus

Der Ausgangsvektor (1,\;0)^T wird in jedem der Schritte so gedreht, dass der Winkel z = Θ gegen Null geht. Es werden stets alle 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 \cos\,\Theta und \sin \, \Theta . Der Konvergenzbereich ergibt sich zu -\sum_{i=0}^{n-1}\;\arctan\,2^{-i}\;\le \Theta \le\;+\sum_{i=0}^{n-1}\;\arctan\,2^{-i}, also bei genügend großem n etwa zu -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 y-Komponente verringert. Der Drehwinkel Θ wird dabei vorzeichenrichtig aufaddiert. Die x-Komponente des Endvektors ist nach Reskalierung der Betrag des Ausgangsvektors. Dieser Modus wird auch benutzt zu Berechnung des Arcustangens aus zwei Argumenten, Start mit  c \,( \cos \, \Theta, \quad \sin \, \Theta)^T. Der Konvergenzbereich ist derselbe wie oben. Aus \operatorname{arctan2}\,(y_0,\,x_0) lassen sich die Funktionen \arcsin\,y_0 und \arccos\,x_0 unter Zuhilfenahme von x_0^2+y_0^2=1 leicht ableiten.

Bereich außerhalb von \mpπ / 2

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

Verallgemeinerung

Die oben benutzten Iterationsformeln 
  \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


  \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 m = 1 und δi = 2 i sowie  t_i=\arctan\,\delta_i.

Lineare Modi

Für m = 0, \delta_i=t_i=[1,\;1/2,\; 1/4,\; 1/8\; ...] und k = 1 erhält man


  \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 T erübrigt sich hier.

Multiplikation: x0 = a, z0 = b, ergibt im Rotationsmodus (z gegen 0) y_n=y_0+a\cdot b für alle − 2 < b < 2.

Division: x0 = b, y0 = a, ergibt im Vektormodus (y gegen 0) zn = z0 + a / b für alle − 2 < b < 2.

Hyperbolische Modi

Mit m = − 1 werden die Hyperbelfunktionen, ihre Umkehrungen (Areafunktionen), Exponentialfunktion und Logarithmus sowie die Quadratwurzel berechenbar. Einheitskreis bzw. -hyperbel werden durch \sqrt{x^2+my^2}=1 mit m = + 1 bzw. m = − 1 beschrieben. Das zu einem Vektor (x,\;y)^T gehörende Winkel- bzw. Areaargument ist durch \Theta= \arctan (\sqrt{m}\cdot y/x)/\sqrt{m} gegeben, also

m = 1, Winkelfunktionen (s.o): \Theta=\arctan\,(y/x) und

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

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


  \begin{pmatrix} 
    x_i \\ y_i \\ z_i
  \end{pmatrix} = k_i\cdot
  \begin{pmatrix} 
    1 &amp;amp; \sigma_i \delta_i&amp;amp; 0 &amp;amp; 0\\ 
    \sigma_i \delta_i&amp;amp; 1 &amp;amp; 0 &amp;amp; 0 \\
    0 &amp;amp; 0 &amp;amp; 1 &amp;amp;-\sigma_i t_i
  \end{pmatrix}\cdot
  \begin{pmatrix} 
    x_{i-1}\\  y_{i-1}\\ z_{i-1} \\1
  \end{pmatrix}

Die Iterationen i = 4,13,40,k,3k + 1 müssen immer wiederholt werden, da der Areatangens Hyperbolicus nicht die Bedingung t_{i+1} \le \frac{1}{2} t_i erfüllt, dass somit für die Reihe \sum\sigma_i t_i nicht konvergieren würde.

Rotation mit [x_0,\; y_0]=[1,\; 0] liefert: x_n=\operatorname{cosh}\,z_0,\quad y_n=\operatorname{sinh}\, z_0,

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

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

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

Der Konvergenzbereich ist in beiden Modi beschränkt durch die maximal mögliche Änderung von 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, wie in z.B. DSPs, und Bitalgorithmen, die mit einem ähnlichen Ansatz wie CORDIC die Berechnung vornehmen, in Frage.

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • CORDIC — (sigle de COordinate Rotation DIgital Computer : « calcul numérique par rotation de coordonnées ») est un algorithme de calcul des fonctions trigonométriques et hyperboliques, notamment utilisé dans les calculatrices. Il a été… …   Wikipédia en Français

  • CORDIC — (COordinate Rotation DIgital Computer), o el método de dígito por dígito, o el algoritmo de Volder, es un simple y eficiente algoritmo para calcular funciones hiperbólicas y trigonométricas. Típicamente es usado cuando no hay disponible un… …   Wikipedia Español

  • CORDIC — (Метод CORDIC от англ. COordinate Rotation DIgital Computer  цифровой вычислитель поворота системы координат; метод «цифра за цифрой», алгоритм Волдера)  итерационный метод сведения прямых вычислений сложных функций к выполнению… …   Википедия

  • CORDIC — Trigonometry History Usage Functions Generalized Inverse functions Further reading …   Wikipedia

  • CORDIC — Der CORDIC Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die …   Deutsch Wikipedia

  • CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) …   Acronyms

  • CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) …   Acronyms von A bis Z

  • Regis Cordic — Regis John Rege Cordic (May 15, 1926 April 16, 1999) was an American radio personality and actor. His career in entertainment divides roughly in half: from 1948 to 1965, he was the dominant morning drive time radio host in Pittsburgh,… …   Wikipedia

  • KDKA (AM) — KDKA City of license Pittsburgh, Pennsylvania Broadcast area Western Pennsylvania Branding Newsradio 1020 KDKA Slogan The Vo …   Wikipedia

  • Bob Trow — Robert Trow (February 6, 1926 mdash;November 2, 1998) was an American radio celebrity, actor, and craftsman.Raised in the Beltzhoover neighborhood of Pittsburgh, Pennsylvania, USA, Trow began his career in radio. He later became well known for… …   Wikipedia