Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten
 
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

Bearbeiten
 
Illustration von CORDIC

CORDIC kann man im  , aber auch nur in der zweidimensionalen Ebene betrachten. Im Folgenden umfasst die Beschreibung den einfacheren, zweidimensionalen Fall.

Dreht man ein Koordinatensystem um den Winkel  , erscheint der Vektor   um den Winkel   gedreht; sein Endpunkt liegt im neuen System bei   und  .

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

 

D. h., um auf den eigentlichen Funktionswert zu kommen, muss der Einheitsvektor   um   gedreht werden. Dies lässt sich leichter bewerkstelligen, wenn innerhalb der Transformationsmatrix nur noch eine Abhängigkeit von einer Winkelfunktion, z. B.   besteht:

 

Die Drehung um   wird trickreich realisiert als Linearkombination von Teildrehungen um geschickt gewählte Teilwinkel  .

 

Eine zu weite Drehung im Schritt   wird kompensiert durch einen Vorzeichenwechsel  . 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   ein, die für den Drehsinn Verantwortung trägt:

 
 

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

 .

Man erhält damit den folgenden Algorithmus:

 

mit dem Skalierungsfaktor   0,60725... für  , der während der Initialisierungsphase implizit berechnet wird.

 
 
 

Initialisierung

Bearbeiten

Vorweg wird eine Tabelle   fester Länge   angelegt mit  , wobei   ist. Die folgenden Werte sind:   mit  . (Die Werte des Arcustangens lassen sich mit der hier gut konvergierenden Potenzreihenentwicklung bestimmen.)

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

Rotationsmodus

Bearbeiten

Der Ausgangsvektor   wird in jedem der Schritte so gedreht, dass der Winkel   gegen Null geht. Es werden stets alle   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   und  . Der Konvergenzbereich ergibt sich zu  , also bei genügend großem   etwa zu  , d. h., er erstreckt sich über mehr als den vierten und ersten Quadranten.

Vektormodus

Bearbeiten

Der vorgegebene Vektor, dessen Polarkoordinaten gesucht werden, wird immer so gedreht, dass sich der Betrag seiner  -Komponente verringert. Die Drehwinkel   werden dabei vorzeichenrichtig addiert. Die  -Komponente des Endvektors ist nach Reskalierung der Betrag des Ausgangsvektors. Dieser Modus wird auch benutzt zur Berechnung des Arcustangens aus zwei Argumenten, Start mit  . Der Konvergenzbereich ist derselbe wie oben. Aus   lassen sich die Funktionen   und   unter Zuhilfenahme von   leicht ableiten.

Bereich außerhalb von ±π/2

Bearbeiten

Der Startvektor   bzw.   entspricht einer Vorwegdrehung von   bzw.   (für den Rotationsmodus). Bei einem Startvektor mit negativer  -Komponente im Vektormodus bewirkt man entsprechende Drehungen durch Vertauschen der Komponenten und Änderungen der Vorzeichen.

Verallgemeinerung

Bearbeiten

Die oben benutzten Iterationsformeln

 

sind ein Sonderfall der allgemeineren Vorschrift

 

mit   und   sowie  .

Lineare Modi

Bearbeiten

Für  ,   und   erhält man

 ,

womit sich Multiplikation und Division durchführen lassen. Eine Tabelle   erübrigt sich hier.

Multiplikation

 ,   ergibt im Rotationsmodus (  gegen 0)   für alle  .

Division

 ,   ergibt im Vektormodus (  gegen 0)   für alle  .

Hyperbolische Modi

Bearbeiten

Mit   werden die Hyperbelfunktionen, ihre Umkehrungen (Areafunktionen), Exponentialfunktion und Logarithmus sowie die Quadratwurzel berechenbar. Einheitskreis bzw. -hyperbel werden durch   mit   bzw.   beschrieben. Das zu einem Vektor   gehörende Winkel- bzw. Areaargument ist durch   gegeben, also

 , Winkelfunktionen (s.o):   und

 , hyperbolische Fkt.:

 

, hier  ;  ; und wegen   auch  .

Das Verfahren ist analog zu dem eingangs gezeigten für die Winkelfunktionen. Erforderlich sind nur eine weitere Tabelle mit  ,   und die einmalige Berechnung des Skalenfaktors  .

 

Die Iterationen   müssen immer wiederholt werden, da der Areatangens hyperbolicus nicht die Bedingung   erfüllt, das somit für die Reihe   nicht konvergieren würde.

Rotation mit   liefert: _ ,

davon abgeleitet:

  und  

Vektormodus mit   berechnet:

 

und den hyperbolischen Betrag

 

davon abgeleitet:

 

sowie

 

aus dem Betrag des Startvektors  

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

Alternativen

Bearbeiten

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

Bearbeiten
Bearbeiten