CORDIC

CORDIC signifie « coordinate rotation digital computer » (ordinateur numérique de rotation de coordonnées). C'est un algorithme itératif qui calcule des fonctions trigonométriques, des fonctions hyperboliques et des rotations de vecteurs en utilisant uniquement des décalages et des additions, sans nécessiter de matériel de multiplication ou de division. L'opération principale fait pivoter un vecteur dans le plan cartésien par des approximations successives de petits angles, chacune réduisant de moitié l'erreur angulaire résiduelle.

L'algorithme fonctionne en décomposant un angle de rotation cible en une somme de valeurs d'arctangente prédéterminées : arctan(1), arctan(0,5), arctan(0,25), et ainsi de suite. À chaque itération, le processeur applique ou ignore l'étape d'arctangente actuelle en fonction du signe de l'angle restant à faire pivoter. Une paire de coordonnées (x, y) est mise à jour par décalage et addition, convergeant vers le sinus et le cosinus de l'angle original après un nombre suffisant d'itérations.

CORDIC s'exécute en O(n) itérations pour une précision de n bits, ce qui le rend plus rapide que la recherche par table plus interpolation sur du matériel avec des jeux d'instructions restreints. Les premiers ordinateurs de guidage aérospatial et les calculatrices scientifiques ont adopté CORDIC parce qu'il s'intégrait dans des circuits compacts. Les FPGA et les processeurs de signaux numériques modernes utilisent toujours CORDIC pour les transformations de coordonnées en temps réel, la détection de phase et la conversion polaire-rectangulaire, car il consomme moins de surface de silicium que les réseaux de multiplicateurs et s'exécute en un temps prévisible.

L'algorithme produit des erreurs d'arrondi qui s'accumulent sur de nombreuses itérations, généralement au niveau du bit de poids faible de la largeur de l'accumulateur. Dans les systèmes nécessitant une très haute précision, CORDIC peut être associé à une étape de raffinement de Newton-Raphson ou réservé aux chemins rapides de moindre précision. Les implémentations pipelinées peuvent terminer une itération par cycle d'horloge, maintenant un débit d'un résultat par cycle après un délai de remplissage du pipeline.

Des variantes existent pour la rotation circulaire (le cas standard), la rotation hyperbolique (pour les logarithmes et les exponentielles) et le mode linéaire (pour la multiplication et la division). Le choix du mode dépend de la famille de fonctions nécessaires. CORDIC reste pertinent dans les systèmes embarqués, le contrôle moteur, le traitement radar et toute application numériquement intensive où la surface de silicium ou la consommation d'énergie doit être minimisée.