Cordic-Algorithmus erklärt: Mit Addition und Bitschubserei komplexe Berechnungen lösen

Algorithmus des Monats Wie berechnen Computer eigentlich Winkel- und Exponentialfunktionen? Wir stellen einen Algorithmus mit geringem Schaltungsaufwand vor.

Artikel von Johannes Hiltscher veröffentlicht am 9. Juni 2023, 9:13 Uhr

Cordic lässt sich, wie hier schon zu erkennen, kompakt als Matrix schreiben. (Bild: Johannes Hiltscher, Golem.de)

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 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°)

• 

Die Idee hinter Cordic: Ausgehend von einem Startvektor V0 wird um vorgegebene Winkel rotiert, bis der gestrichelte Zielvektor annähernd erreicht ist. Hier sind nur drei Iterationsschritte dargestellt. (Bild: Johannes Hiltscher, Golem.de)

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²(γ))[[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.