CORDIQUE

CORDIC ( ordinateur numérique à rotation de coordonnées ), algorithme de Volder , méthode chiffre par chiffre , CORDIC circulaire ( Jack E. Volder ), CORDIC linéaire , CORDIC hyperbolique (John Stephen Walther), et CORDIC hyperbolique généralisé ( GH CORDIC ) (Yuanyong Luo et al.), algorithme simple et efficace pour calculer des fonctions trigonométriques , des fonctions hyperboliques , des racines carrées , des multiplications , des divisions , des exponentielles et des logarithmes avec une base arbitraire, convergeant généralement avec un chiffre (ou bit) par itération. CORDIC est donc aussi un exemple d' algorithmes chiffre par chiffre . CORDIC et les méthodes étroitement apparentées connues sous le nom de pseudo-multiplication et pseudo-division ou combinaison de facteurs sont couramment utilisées lorsqu'aucun multiplicateur matériel n'est disponible (par exemple dans les microcontrôleurs simples et les réseaux de portes programmables par l'utilisateur ou FPGA), car les seules opérations qu'elles nécessitent sont des additions , des soustractions , des décalages de bits et des tables de recherche . En tant que tels, ils appartiennent tous à la classe des algorithmes de décalage et d'addition . En informatique, CORDIC est souvent utilisé pour implémenter l'arithmétique à virgule flottante lorsque la plate-forme cible ne dispose pas de multiplicateur matériel pour des raisons de coût ou d'espace.

Des techniques mathématiques similaires ont été publiées par Henry Briggs dès 1624 et Robert Flower en 1771, mais CORDIC est mieux optimisé pour les processeurs à états finis de faible complexité.

CORDIC a été conçu en 1956 par Jack E. Volder au département aéroélectronique de Convair par nécessité de remplacer le résolveur analogique de l' ordinateur de navigation du bombardier B-58 par une solution numérique en temps réel plus précise et plus rapide. Par conséquent, CORDIC est parfois appelé résolveur numérique.

Dans ses recherches, Volder s'est inspiré d'une formule de l'édition 1946 du CRC Handbook of Chemistry and Physics :

où est tel que , et .

Ses recherches ont abouti à un rapport technique interne proposant l'algorithme CORDIC pour résoudre les fonctions sinus et cosinus et un ordinateur prototype le mettant en œuvre. Le rapport a également discuté de la possibilité de calculer la rotation des coordonnées hyperboliques , les logarithmes et les fonctions exponentielles avec des algorithmes CORDIC modifiés. L'utilisation de CORDIC pour la multiplication et la division a également été conçue à cette époque. Sur la base du principe CORDIC, Dan H. Daggett, un collègue de Volder à Convair, a développé des algorithmes de conversion entre le binaire et le décimal codé binaire (BCD).

En 1958, Convair a finalement commencé à construire un système de démonstration pour résoudre les problèmes de fixation radar appelé CORDIC I , achevé en 1960 sans Volder, qui avait déjà quitté l'entreprise. Des modèles CORDIC II plus universels A (stationnaire) et B (aéroporté) ont été construits et testés par Daggett et Harry Schuss en 1962.

L'algorithme CORDIC de Volder a été décrit pour la première fois en public en 1959, ce qui a conduit à son intégration dans les ordinateurs de navigation par des sociétés telles que Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon et Collins Radio .

Volder s'est associé à Malcolm McMillan pour construire Athena , une calculatrice de bureau à virgule fixe utilisant son algorithme binaire CORDIC. La ​​conception a été présentée à Hewlett-Packard en juin 1965, mais n'a pas été acceptée. Pourtant, McMillan a présenté l'algorithme de Volder à David S. Cochran (HP) et lorsque Cochran a rencontré plus tard Volder, il l'a renvoyé à une approche similaire que John E. Meggitt (IBM ) avait proposée comme pseudo-multiplication et pseudo-division en 1961. La méthode de Meggitt suggérait également l'utilisation de la base 10 plutôt que de la base 2 , comme utilisé par le CORDIC de Volder jusqu'à présent. Ces efforts ont conduit à l' implémentation de la logique ROMable d'une machine prototype CORDIC décimale au sein de Hewlett-Packard en 1966, construite par et dérivée conceptuellement de la Green Machine prototypique de Thomas E. Osborne , une calculatrice de bureau à quatre fonctions et à virgule flottante qu'il avait achevée en logique DTL en décembre 1964. Ce projet a abouti à la démonstration publique de la première calculatrice de bureau de Hewlett-Packard avec des fonctions scientifiques, la HP 9100A en mars 1968, avec une production en série commençant plus tard dans l'année.

Lorsque les laboratoires Wang ont découvert que le HP 9100A utilisait une approche similaire à la méthode de combinaison de facteurs dans leurs calculatrices de bureau LOCI-1 (septembre 1964) et LOCI-2 (janvier 1965) Logarithmic Computing Instrument , ils ont accusé sans succès Hewlett-Packard de violation de l'un des brevets d' An Wang en 1968.

Français John Stephen Walther de Hewlett-Packard a généralisé l'algorithme dans l' algorithme CORDIC unifié en 1971, lui permettant de calculer des fonctions hyperboliques , des exponentielles naturelles , des logarithmes naturels , des multiplications , des divisions et des racines carrées . Les sous-routines CORDIC pour les fonctions trigonométriques et hyperboliques pourraient partager la plupart de leur code. Ce développement a donné naissance à la première calculatrice scientifique portable , la HP-35 en 1972. Sur la base du CORDIC hyperbolique, Yuanyong Luo et al. ont également proposé un CORDIC hyperbolique généralisé (GH CORDIC) pour calculer directement les logarithmes et les exponentielles avec une base fixe arbitraire en 2019. Théoriquement, le CORDIC hyperbolique est un cas particulier de GH CORDIC.

À l'origine, CORDIC a été implémenté uniquement en utilisant le système numérique binaire et malgré la suggestion de Meggitt d'utiliser le système décimal pour son approche de pseudo-multiplication, le CORDIC décimal est resté pratiquement inconnu pendant plusieurs années encore, de sorte que Hermann Schmid et Anthony Bogacki l'ont encore suggéré comme une nouveauté jusqu'en 1973 et on a découvert seulement plus tard que Hewlett-Packard l'avait déjà implémenté en 1966.

Le CORDIC décimal a été largement utilisé dans les calculatrices de poche , dont la plupart fonctionnent en décimal codé binaire (BCD) plutôt qu'en binaire. Ce changement dans le format d'entrée et de sortie n'a pas modifié les algorithmes de calcul de base de CORDIC. CORDIC est particulièrement bien adapté aux calculatrices portables, dans lesquelles un faible coût – et donc un faible nombre de portes de puce – est beaucoup plus important que la vitesse.

CORDIC a été implémenté dans les coprocesseurs STM32G4 basés sur ARM , Intel 8087 , 80287 , 80387 jusqu'à la série 80486 ainsi que dans les Motorola 68881 et 68882 pour certains types d'instructions à virgule flottante, principalement comme moyen de réduire le nombre de portes (et la complexité) du sous-système FPU .

CORDIC utilise des opérations simples de décalage-addition pour plusieurs tâches informatiques telles que le calcul de fonctions trigonométriques, hyperboliques et logarithmiques, les multiplications réelles et complexes, la division, le calcul de racines carrées, la résolution de systèmes linéaires, l'estimation de valeurs propres , la décomposition de valeurs singulières , la factorisation QR et bien d'autres. En conséquence, CORDIC a été utilisé pour des applications dans divers domaines tels que le traitement du signal et de l'image , les systèmes de communication , la robotique et les graphiques 3D en plus du calcul scientifique et technique général.

L'algorithme a été utilisé dans le système de navigation du Lunar Roving Vehicle du programme Apollo pour calculer le relèvement et la portée, ou la distance par rapport au module lunaire . CORDIC a été utilisé pour implémenter le coprocesseur mathématique Intel 8087 en 1980, évitant ainsi la nécessité d'implémenter une multiplication matérielle.

CORDIC est généralement plus rapide que les autres approches lorsqu'un multiplicateur matériel n'est pas disponible (par exemple, un microcontrôleur), ou lorsque le nombre de portes nécessaires à la mise en œuvre des fonctions qu'il prend en charge doit être minimisé (par exemple, dans un FPGA ou un ASIC ). En fait, CORDIC est une IP standard dans les applications de développement FPGA telles que Vivado pour Xilinx, alors qu'une implémentation en série de puissance n'est pas due à la spécificité d'une telle IP, c'est-à-dire que CORDIC peut calculer de nombreuses fonctions différentes (à usage général) tandis qu'un multiplicateur matériel configuré pour exécuter des implémentations en série de puissance ne peut calculer que la fonction pour laquelle il a été conçu.

En revanche, lorsqu'un multiplicateur matériel est disponible ( par exemple dans un microprocesseur DSP ), les méthodes de recherche de table et les séries de puissance sont généralement plus rapides que CORDIC. Ces dernières années, l'algorithme CORDIC a été largement utilisé pour diverses applications biomédicales, en particulier dans les implémentations FPGA.

La série STM32G4 et certaines séries STM32H7 de microcontrôleurs implémentent un module CORDIC pour accélérer les calculs dans diverses applications à signaux mixtes telles que les graphiques pour l'interface homme-machine et le contrôle orienté champ des moteurs. Bien qu'il ne soit pas aussi rapide qu'une approximation en série de puissance, CORDIC est en effet plus rapide que les implémentations basées sur des tables d'interpolation telles que celles fournies par les bibliothèques standard ARM CMSIS et C. Bien que les résultats puissent être légèrement moins précis, car les modules CORDIC fournis n'atteignent que 20 bits de précision dans le résultat. Par exemple, la majeure partie de la différence de performances par rapport à l'implémentation ARM est due à la surcharge de l'algorithme d'interpolation, qui atteint une précision en virgule flottante complète (24 bits) et peut probablement atteindre une erreur relative à cette précision. Un autre avantage est que le module CORDIC est un coprocesseur et peut être exécuté en parallèle avec d'autres tâches du processeur.

Le problème avec l'utilisation des séries de Taylor est que même si elles fournissent une petite erreur absolue, elles ne présentent pas d'erreur relative bien comportée. D'autres moyens d'approximation polynomiale, tels que l'optimisation minimax , peuvent être utilisés pour contrôler les deux types d'erreur.

De nombreux systèmes plus anciens avec des processeurs uniquement en nombres entiers ont implémenté CORDIC à des degrés divers dans le cadre de leurs bibliothèques à virgule flottante IEEE . Comme la plupart des processeurs modernes à usage général disposent de registres à virgule flottante avec des opérations courantes telles que l'addition, la soustraction, la multiplication, la division, le sinus, le cosinus, la racine carrée, le logarithme ₁₀ et le logarithme naturel, la nécessité d'implémenter CORDIC dans ces derniers avec un logiciel est presque inexistante. Seuls les microcontrôleurs ou les applications logicielles spéciales soumises à des contraintes de sécurité et de temps devraient envisager d'utiliser CORDIC.

CORDIC peut être utilisé pour calculer un certain nombre de fonctions différentes. Cette explication montre comment utiliser CORDIC en mode rotation pour calculer le sinus et le cosinus d'un angle, en supposant que l'angle souhaité est donné en radians et représenté dans un format à virgule fixe. Pour déterminer le sinus ou le cosinus d'un angle , il faut trouver la coordonnée y ou x d'un point sur le cercle unité correspondant à l'angle souhaité. En utilisant CORDIC, on commencerait par le vecteur :

Dans la première itération, ce vecteur est tourné de 45° dans le sens inverse des aiguilles d'une montre pour obtenir le vecteur . Les itérations successives font tourner le vecteur dans l'une ou l'autre direction par paliers décroissants, jusqu'à ce que l'angle souhaité soit atteint. Chaque angle de palier correspond à .

Plus formellement, chaque itération calcule une rotation, qui est effectuée en multipliant le vecteur par la matrice de rotation :

La matrice de rotation est donnée par

En utilisant l' identité trigonométrique :

le facteur cosinus peut être retiré pour donner :

L'expression du vecteur tourné devient alors :

où et sont les composantes de . En définissant l'angle pour chaque itération de telle sorte que l'on obtienne toujours une série qui converge vers toutes les valeurs de sortie possibles. La multiplication avec la tangente peut donc être remplacée par une division par une puissance de deux, ce qui est fait efficacement dans le matériel informatique numérique en utilisant un décalage de bits . L'expression devient alors :

et est utilisé pour déterminer le sens de rotation : si l'angle est positif, alors il est +1, sinon il est −1.

L'identité trigonométrique suivante peut être utilisée pour remplacer le cosinus :

en donnant ce multiplicateur pour chaque itération :

Les facteurs peuvent ensuite être retirés du processus itératif et appliqués tous en même temps par la suite avec un facteur d'échelle :

qui est calculé à l'avance et stocké dans une table ou comme une constante unique, si le nombre d'itérations est fixe. Cette correction pourrait également être effectuée à l'avance, en mettant à l'échelle et donc en économisant une multiplication. De plus, on peut noter que

pour permettre une réduction supplémentaire de la complexité de l'algorithme. Certaines applications peuvent éviter de corriger complètement, ce qui entraîne un gain de traitement :

Après un nombre suffisant d'itérations, l'angle du vecteur sera proche de l'angle souhaité . Pour la plupart des applications courantes, 40 itérations ( n ​​= 40) suffisent pour obtenir le résultat correct à la 10e décimale.

Il ne reste plus qu'à déterminer si la rotation doit se faire dans le sens des aiguilles d'une montre ou dans le sens inverse à chaque itération (en choisissant la valeur de ). Cela se fait en gardant une trace de la rotation de l'angle à chaque itération et en soustrayant cela de l'angle souhaité ; puis, pour se rapprocher de l'angle souhaité , si est positif, la rotation se fait dans le sens des aiguilles d'une montre, sinon il est négatif et la rotation se fait dans le sens inverse des aiguilles d'une montre :

Les valeurs de doivent également être précalculées et stockées. Pour les petits angles, elles peuvent être approximées avec pour réduire la taille du tableau.

Comme on peut le voir dans l'illustration ci-dessus, le sinus de l'angle est la coordonnée y du vecteur final tandis que la coordonnée x est la valeur du cosinus.

L'algorithme de rotation décrit ci-dessus permet de faire pivoter n'importe quel vecteur (pas seulement un vecteur unitaire aligné sur l' axe x ) d'un angle compris entre −90° et +90°. Les décisions sur le sens de rotation dépendent du fait qu'il soit positif ou négatif.

Le mode de fonctionnement vectorisation nécessite une légère modification de l'algorithme. Il part d'un vecteur dont la coordonnée x est positive tandis que la coordonnée y est arbitraire. Les rotations successives ont pour but de faire tourner le vecteur autour de l' axe x (et donc de réduire la coordonnée y à zéro). A chaque étape, la valeur de y détermine le sens de la rotation. La valeur finale de contient l'angle total de rotation. La valeur finale de x sera la grandeur du vecteur original mis à l'échelle par K . Ainsi, une utilisation évidente du mode vectorisation est la transformation de coordonnées rectangulaires en coordonnées polaires.

En Java, la classe Math dispose d'une scalb(double x,int scale)méthode pour effectuer un tel décalage, C dispose de la fonction ldexp , et la classe x86 des processeurs dispose de l' fscaleopération en virgule flottante.

à partir de 
l'importation mathématique 
atan2 , sqrt , sin , cos , radians
ITERS 
= 
16
theta_table 
= 
[ atan2 ( 1 , 
2 ** i ) 
pour 
i 
dans 
la plage ( ITERS )]
déf.compute_K 
( n ) :
 Calculer K(n) pour n = ITERS. Cela pourrait aussi être
 stocké comme une constante explicite si ITERS ci-dessus est fixe.
k 
= 
1,0
pour 
i 
dans 
la plage ( n ):
k 
*= 
1 
/ 
carré ( 1 
+ 
2 
** 
( - 2 
* 
i ))
retourner 
k
définition 
de CORDIC ( alpha , 
n ):
K_n 
= 
calculer_K ( n )
thêta 
= 
0,0
x 
= 
1,0
y 
= 
0,0
P2i 
= 
1 
# Ce sera 2**(-i) dans la boucle ci-dessous
pour 
arc_tangent 
dans 
theta_table :
sigma 
= 
+ 1 
si 
thêta 
< 
alpha 
sinon 
- 1
thêta 
+= 
sigma 
* 
arc_tangente
x , 
y 
= 
x 
- 
sigma 
* 
y 
* 
P2i , 
sigma 
* 
P2i 
* 
x 
+ 
y
P2i 
/= 
2
renvoie 
x 
* 
K_n , 
y 
* 
K_n
si 
__name__ 
== 
"__main__" :
# Imprimer un tableau des sinus et cosinus calculés, de -90° à +90°, par pas de 15°,
# comparaison avec les routines mathématiques disponibles.
imprimer ( " x sin(x) diff. sinus cos(x) diff. cosinus " )
pour 
x 
dans 
la plage ( - 90 , 
91 , 
15 ) :
cos_x , 
sin_x 
= 
CORDIQUE ( radians ( x ), 
ITERS )
imprimer (
f " { x : +05.1f } ° { sin_x : +.8f } ( { sin_x - sin ( radians ( x )) : +.8f } ) { cos_x : +.8f } ( { cos_x - cos ( radians ( x )) : +.8f } )"
)

$ python cordic.py  x sin(x) diff. sinus cos(x) diff. cosinus 
-90,0° -1,00000000 (+0,00000000) -0,00001759 (-0,00001759) 
-75,0° -0,96592181 (+0,00000402) +0,25883404 (+0,00001499) -60,0° -0,86601812 (+0,00000729 
) +0,50001262 (+0,00001262) 
-45,0° -0,70711776 (-0,00001098) +0,70709580 (-0,00001098) 
-30,0° -0,50001262 (-0,00001262) +0,86601812 (-0,00000729) 
-15,0° -0,25883404 (-0,00001499) +0,96592181 (-0,00000402) 
+00,0° +0,00001759 (+0,00001759) +1,00000000 (-0,00000000) 
+15,0° +0,25883404 (+0,00001499) +0,96592181 (-0,00000402) 
+30,0° +0,50001262 (+0,00001262) +0.86601812 (-0,00000729) 
+45,0° +0,70709580 (-0,00001098) +0,70711776 (+0,00001098) 
+60,0° +0,86601812 (-0,00000729) +0,50001262 (+0,00001262) 
+75,0° +0,96592181 (-0,00000402) +0,25883404 (+0,00001499) 
+90,0° +1,00000000 (-0,00000000) -0,00001759 (-0,00001759)

Le nombre de portes logiques nécessaires à la mise en œuvre d'un CORDIC est à peu près comparable à celui requis pour un multiplicateur, car les deux nécessitent des combinaisons de décalages et d'additions. Le choix d'une mise en œuvre basée sur un multiplicateur ou sur un CORDIC dépendra du contexte. La multiplication de deux nombres complexes représentés par leurs composantes réelle et imaginaire (coordonnées rectangulaires), par exemple, nécessite 4 multiplications, mais pourrait être réalisée par un seul CORDIC opérant sur des nombres complexes représentés par leurs coordonnées polaires, en particulier si la grandeur des nombres n'est pas pertinente (multiplier un vecteur complexe par un vecteur sur le cercle unité équivaut en fait à une rotation). Les CORDIC sont souvent utilisés dans les circuits de télécommunications tels que les convertisseurs descendants numériques .

Français Dans deux des publications de Vladimir Baykov, il a été proposé d'utiliser la méthode des doubles itérations pour la mise en œuvre des fonctions : arcsinus, arccosinus, logarithme naturel, fonction exponentielle, ainsi que pour le calcul des fonctions hyperboliques. La méthode des doubles itérations consiste en ce que contrairement à la méthode CORDIC classique, où la valeur du pas d'itération change à chaque fois, c'est-à-dire à chaque itération, dans la méthode des doubles itérations, la valeur du pas d'itération est répétée deux fois et ne change que sur une seule itération. D'où la désignation de l'indicateur de degré pour les doubles itérations : . Alors qu'avec les itérations ordinaires : . La méthode des doubles itérations garantit la convergence de la méthode sur toute la plage valide de changements d'argument.

La généralisation des problèmes de convergence CORDIC pour le système de nombres positionnels arbitraires à base a montré que pour les fonctions sinus, cosinus, arctangente, il suffit d'effectuer des itérations pour chaque valeur de i (i = 0 ou 1 à n, où n est le nombre de chiffres), c'est-à-dire pour chaque chiffre du résultat. Pour le logarithme naturel, l'exponentiel, le sinus hyperbolique, le cosinus et l'arctangente, il faut effectuer des itérations pour chaque valeur . Pour les fonctions arcsinus et arccosinus, il faut effectuer deux itérations pour chaque chiffre du nombre, c'est-à-dire pour chaque valeur de .

Pour les fonctions sinus et arcosinus hyperboliques inverses, le nombre d'itérations sera pour chaque , c'est-à-dire pour chaque chiffre de résultat.

CORDIC fait partie de la classe des algorithmes de type « shift-and-add » , comme le sont les algorithmes logarithmique et exponentiel dérivés des travaux de Henry Briggs. Un autre algorithme de type « shift-and-add » qui peut être utilisé pour calculer de nombreuses fonctions élémentaires est l' algorithme BKM , qui est une généralisation des algorithmes logarithmique et exponentiel au plan complexe. Par exemple, BKM peut être utilisé pour calculer le sinus et le cosinus d'un angle réel (en radians) en calculant l'exponentielle de , qui est . L'algorithme BKM est légèrement plus complexe que CORDIC, mais a l'avantage de ne pas nécessiter de facteur d'échelle ( K ).