CORDIC

CORDIC steht für Coordinate Rotation Digital Computer. Es ist ein iterativer Algorithmus, der trigonometrische Funktionen, hyperbolische Funktionen und Vektorrotationen nur mit Schiebeoperationen und Additionen berechnet, ohne dass Multiplikations- oder Divisionshardware erforderlich ist. Die Kernoperation rotiert einen Vektor in der kartesischen Ebene durch aufeinanderfolgende kleine Winkelapproximationen, wobei jede den restlichen Winkelfehler halbiert.

Der Algorithmus funktioniert, indem der Zielrotationswinkel in eine Summe vorgegebener Arkustangenswerte zerlegt wird: arctan(1), arctan(0,5), arctan(0,25) und so weiter. Bei jeder Iteration wendet der Prozessor den aktuellen Arkustangensschritt entweder an oder überspringt ihn, je nach Vorzeichen des verbleibenden Rotationswinkels. Ein laufendes Koordinatenpaar (x, y) wird durch Schieben und Addieren aktualisiert und konvergiert nach genügend Iterationen gegen Sinus und Kosinus des ursprünglichen Winkels.

CORDIC wird in O(n) Iterationen für n-Bit-Genauigkeit ausgeführt, was es schneller macht als Tabellennachschlag plus Interpolation auf Hardware mit eingeschränkten Befehlssätzen. Frühe Navigationssysteme in der Luftfahrt und Taschenrechner setzten auf CORDIC, weil es in kompakte Schaltkreise passte. Moderne FPGAs und digitale Signalprozessoren nutzen CORDIC weiterhin für Echtzeit-Koordinatentransformationen, Phasenerkennung und Polar-zu-Kartesisch-Umwandlung, da es weniger Chipfläche als Multiplizierarrays verbraucht und in vorhersehbarer Zeit ausgeführt wird.

Der Algorithmus erzeugt Rundungsfehler, die sich über viele Iterationen hinweg akkumulieren, normalerweise auf der Ebene des niedrigstwertigen Bits der Akkumulatorbreite. In Systemen, die sehr hohe Genauigkeit erfordern, kann CORDIC mit einem Newton-Raphson-Verfeinerungsschritt gekoppelt oder nur für schnellere Pfade mit niedrigerer Genauigkeit reserviert werden. Gepipelte Implementierungen können eine Iteration pro Taktzyklus abschließen und erreichen einen Durchsatz von einem Ergebnis pro Zyklus nach einer Pipeline-Füllverzögerung.

Es gibt Varianten für zirkuläre Rotation (Standardfall), hyperbolische Rotation (für Logarithmen und Exponentialfunktionen) und linearen Modus (für Multiplikation und Division). Die Wahl des Modus hängt von der benötigten Funktionsfamilie ab. CORDIC bleibt relevant in eingebetteten Systemen, Motorsteuerung, Radarverarbeitung und jeder numerisch intensiven Anwendung, bei der die Chipfläche oder der Stromverbrauch minimiert werden muss.