Cordic-Algorithmus erklärt: Mit Addition und Bitschubserei komplexe Berechnungen lösen
Heute startet der bei unserer letzten Leserumfrage oft gewünschte Algorithmus des Monats . Der erste Kandidat steht selten im Rampenlicht, sondern versteckt sich in Hardware oder spezialisierten Softwarebibliotheken. Cordic steht für Coordinate Rotation Digital Computer und kann eine Reihe komplexer Berechnungen ausführen: Der Algorithmus berechnet Winkel-, Exponential-, Hyperbel- und Areafunktionen, multipliziert, dividiert und bestimmt Quadratwurzeln. Das alles ist für Computer deutlich komplexer, als etwa Multiplikation und Division vermuten lassen.
Selbstverständlich ist Cordic nicht der einzige Algorithmus, der sich hierfür eignet. Im Gegensatz zu anderen Algorithmen, etwa dem Newton-Raphson-Verfahren(öffnet im neuen Fenster) zur Bestimmung der Quadratwurzel, ist er aber speziell auf Digitalrechner ausgelegt. Er verwendet ausschließlich Operationen, die sich mit digitaler Logik einfach und günstig realisieren lassen: Additionen und Subtraktionen, bitweises Verschieben sowie einen Speicher.
Eines hat der 1959 von Jack Volder entwickelte Algorithmus mit den teils deutlich älteren Alternativen gemein: Er arbeitet iterativ, nähert sich also in mehreren Schritten dem Ergebnis an. Die Schrittzahl ist immer fest, alle durch Cordic berechenbaren Funktionen werden durch dieselbe Operation abgebildet. Welche Funktion berechnet wird, bestimmen zwei Parameter und die Eingabewerte. Beides ignorieren wir jedoch zunächst.
Winkel addieren durch Drehen
Die Idee hinter Cordic ist ziemlich einfach und lässt sich am besten an der Berechnung von Sinus oder Cosinus eines gegebenen Winkels zeigen. Jeder Winkel lässt sich als Summe einer festen Menge vorgegebener Winkel darstellen. Es liegt nahe, für sie eine Tabelle mit den Ergebnissen der Winkelfunktionen anzulegen und die Einzelwerte zu summieren – so einfach ist es allerdings nicht, da Cosinus und Sinus nichtlineare Funktionen sind. Das bedeutet: cos(67,5°) ≠ cos(45°) + cos(22,5°)
Korrekt funktioniert die Addition der Winkel, wenn wir auf dem Einheitskreis arbeiten. Als Vektor bilden Cosinus (x-Achse) und Sinus (y-Achse) hier einen Punkt ab, der Winkel zwischen positiver x-Achse und dem Vektor ist unser Ausgangswinkel. Soll hierzu ein anderer Winkel γ addiert werden, muss der Punkt auf dem Einheitskreis rotiert werden. Dazu wird der Ausgangsvektor mit der Rotationsmatrix [[cos(γ) -sin(γ)] [sin(γ) cos(γ)]] T multipliziert.
Der Ansatz des Cordic-Algorithmus ist, von einem Winkel mit 0° auszugehen, als Ausgangsvektor also [1 0] T zu verwenden. Dann wird der Winkel, dessen Sinus oder Cosinus bestimmt werden soll, nach und nach angenähert, indem immer kleinere Winkel addiert (oder subtrahiert) werden. Der Vektor wird dabei stets passend rotiert. Am Ende ist der Zielwinkel bis auf einen kleinen Fehler erreicht, der Vektor enthält die gesuchten Werte der Winkelfunktionen.
Geschickte Umformung beseitigt die Multiplikation
Das klingt bislang wenig hilfreich, schließlich soll Cordic doch nur mit Addition und Verschiebung auskommen. Die Verschiebeoperation ist allerdings eine – wenn auch eingeschränkte – Multiplikation: Jede Verschiebung um ein Bit multipliziert oder dividiert im Binärsystem mit 2. Jetzt gilt es also nur noch, passende Winkel zu finden, die immer zu einer Multiplikation mit einer Zweierpotenz führen – und aus denen sich beliebige andere Winkel mit möglichst geringem Fehler summieren lassen, deren Summe also gut konvergiert.
Beides erfüllt die Reihe tan(γ) = 2 -i , die Rotationsmatrix lässt sich leicht umformen, so dass sie nur noch vom Tangens abhängt: 1/sqrt(1 + tan 2 (γ))[[1 -tan(γ)] [tan(γ) 1]] T . Führen wir mehrere Rotationen hintereinander aus, ist das Ergebnis das Produkt aller Einzelrotationen, für jeden Schritt i ( i = 0, 1, 2, ...) ergibt sich folgende Rotationsmatrix: 1/sqrt(1 + 2 -2i )[[1 -2 -i ] [2 -i 1]] T .
Betrachten wir zunächst die Matrix und lassen den Faktor außen vor. x- und y-Komponente des Vektors werden zunächst durch die entsprechende Zweierpotenz geteilt, was einer Schiebeoperation nach rechts entspricht. Diese Werte werden zum vorherigen Wert der jeweils anderen Komponente addiert, also x i+1 = x i ± y i ᐳᐳ i und y i+1 = y i ± x i ᐳᐳ i. Ob addiert oder subtrahiert wird, hängt davon ab, ob der aktuelle Zwischenwert aus der Addition der Einzelwinkel größer oder kleiner ist als der Zielwinkel – ob also im oder gegen den Uhrzeigersinn rotiert werden muss, um sich dem Ziel weiter zu nähern.
Störend ist noch der Faktor, der eine Multiplikation erforderlich macht. Glücklicherweise konvergiert er bereits nach wenigen Schritten gegen einen konstanten Wert (ungefähr 0,60725). Damit ist dann höchstens noch eine Multiplikation erforderlich, in vielen Fällen kann der als Korrekturfaktor bezeichnete Wert allerdings auch als Startwert verwendet werden – damit entfällt die Multiplikation ganz. Anstelle von [1 0] T beginnen wir die Sinus- und Cosinus-Berechnung dann mit [0,60725 0] T . Bei anderen Berechnungen kommen wir hingegen um die Multiplikation nicht herum – die kann Cordic allerdings ebenfalls erledigen. Wie das funktioniert, sehen wir uns jetzt an.
Kleine Erweiterung für viele Funktionen
In der vorgestellten einfachen Variante ist Cordic noch recht eingeschränkt. Eine deutliche Erweiterung entwickelte John Walther 1971 bei Hewlett Packard (HP). Werden Eingabevektor und Matrix auf vier Dimensionen erweitert, können wesentlich mehr Funktionen berechnet werden. Neben x und y kommt noch z als Parameter im Eingabevektor hinzu, der vierte Wert ist eine konstante 1. Z nimmt den Zielwinkel auf, in jedem Schritt wird die aktuelle Winkeländerung subtrahiert. Den Grund dafür sehen wir gleich, die entsprechenden Werte können fest in einem Speicher liegen.
Zusätzlich wird ein Parameter m eingeführt, der, so beschreibt es Walther in einer Veröffentlichung (PDF)(öffnet im neuen Fenster) , das Koordinatensystem auswählt, auf dem Cordic arbeitet. Für m = 1 ist es der Einheitskreis, für m = 0 eine senkrechte Linie durch x und für m = -1 eine Hyperbel. Erreicht wird dies, indem m in die Berechnungsvorschrift für x i eingeht: x i = x i ± m * y i ᐳᐳ i
Daneben hängt der Korrekturfaktor von m ab: Im linearen Modus entfällt er, in den beiden anderen Modi wird 1/sqrt(1 + m * 2 -2i ) verwendet. Während der hyperbolische Modus die entsprechenden Funktionen – sinh und cosh – berechnet, führt der lineare Modus eine Multiplikation durch.
Umkehrfunktionen sind leicht ergänzbar
Neben den drei Koordinatensystemen kennt Cordic noch zwei zusätzliche Varianten: den Rotations- und den Vektormodus. Bislang haben wir nur den Rotationsmodus betrachtet, der Vektormodus ist die Umkehroperation.
Erreicht wird das ganz einfach: Während im Rotationsmodus z die Richtung der nächsten Drehung vorgibt, hängt diese im Vektormodus von y ab. Ziel ist in beiden Fällen, den jeweiligen Parameter auf 0 zu bringen. So kann der Vektormodus etwa verwendet werden, um mit m = 1 einen Vektor vom kartesischen ins Polarkoordinatensystem übertragen.
Eine übersichtliche Aufstellung der verschiedenen Modi findet sich in einem Kapitel des Buchs Digital Signal Processing for Multimedia Systems ( PDF(öffnet im neuen Fenster) ).
Noch mehr Möglichkeiten mit anderen Sequenzen
Für Cordic wurden mehrere Varianten vorgeschlagen, mit denen noch weitere Funktionen berechnet werden können. Sie nutzen andere Durchlaufmuster, die Laufvariable i startet also nicht zwangsläufig bei 0 und wird auch nicht in jedem Schritt um 1 erhöht.
Damit wird eine andere Auswahl an Basiswinkeln verwendet, da der von Entwickler Volder verwendete Satz für einige Funktionen nicht konvergiert. John Walther präsentierte in der oben verlinkten Veröffentlichung eine Sequenz zur Berechnung des Areatangens Hyperbolicus(öffnet im neuen Fenster) .
Grundsätzlich gilt allerdings, dass Cordic nur für einen eingeschränkten Wertebereich konvergiert. Bei Winkeln und einer ausreichend großen Anzahl an Wiederholungen liegt der Wert zwischen -1,74 und 1,74; er umfasst also etwas mehr als den ersten und vierten Quadranten des Einheitskreises. Werte außerhalb des Konvergenzbereichs müssen zunächst angepasst werden.
Heute nur noch selten im Einsatz
Für die meisten Anwendungsfälle ist der Cordic-Algorithmus nicht mehr interessant. Da Hardwaremultiplizierer mittlerweile selbst in Mikrocontrollern integriert sind, lassen sich schnellere Algorithmen nutzen.
Bei der digitalen Signalverarbeitung in FPGAs kann Cordic noch interessant sein, da er allein mit den Logik-Ressourcen umsetzbar ist. Zudem verwendet der Algorithmus keine Gleitkommazahlen, was noch einmal geringeren Schaltungsaufwand bedeutet. Cordic steckt allerdings in einer Reihe alter wissenschaftlicher Taschenrechner wie dem HP 9100A und HP-35 ; auch Intels mathematischer Co-Prozessor x87 implementierte den Algorithmus.
Cordic ist also ein wichtiges Stück Computergeschichte – und ein spannendes Beispiel, wie geschickte Anwendung der Mathematik komplexe Probleme für Computer lösbar macht.
- Anzeige Hier geht es zu den konfigurierbaren Golem-PCs bei Systemtreff Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.