Voir la source de CORDIC

'''CORDIC''' ([[sigle]] de ''{{langue|en|'''CO'''ordinate '''R'''otation '''DI'''gital '''C'''omputer}}'', « calcul numérique par rotation de coordonnées ») est un [[Algorithmique|algorithme]] de calcul des [[fonction trigonométrique|fonctions trigonométriques]] et [[fonction hyperbolique|hyperboliques]], notamment utilisé dans les [[calculatrice]]s. Il a été décrit pour la première fois en 1959 par [[Jack E. Volder]]. Il ressemble à des techniques qui avaient été décrites par [[Henry Briggs]] en 1624.

Il s'agit d'un algorithme de choix lorsque aucune implantation matérielle d'un [[Unité de calcul en virgule flottante|multiplicateur]] n'est disponible (sur certains [[microcontrôleur]]s simples ou des [[FPGA]]). De plus, l'algorithme du CORDIC s'adapte bien au calcul à la chaîne. À l'origine, la programmation du CORDIC reposait sur un [[système binaire]].

Durant les années 1970, les versions [[Nombre décimal|décimales]] du CORDIC (avec des nombres codés en [[Binary coded decimal|BCD]]) commencèrent à apparaître, notamment dans les calculatrices où les critères de coût du matériel sont plus importants que la vitesse de traitement. Un autre avantage du CORDIC est sa flexibilité puisqu'il permet de calculer plusieurs fonctions avec quasiment le même code.
== Description ==
CORDIC permet de déterminer le sinus ou le cosinus d'un angle donné en radians sous un format à [[virgule fixe]]. Pour trouver le [[Sinus (mathématiques)|sinus]] ou le [[cosinus]] d'un angle {{mvar|β}}, on recherche la coordonnée x ou y du point du [[cercle unité]] lui correspondant. CORDIC commence les calculs avec un [[vecteur]] {{math|''v''{{ind|0}}}} tel que :
: <math> v_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix} </math>

Durant la première itération, le vecteur subit une rotation de 45° dans le sens anti-horaire ([[sens trigonométrique]]) afin d'obtenir un nouveau vecteur {{math|''v''{{ind|1}}}}. Des itérations successives doivent engendrer une rotation du vecteur dans la bonne direction. À chaque itération, la rotation est faite d'un angle prédéterminé et moindre que le précédent. Ceci jusqu'à converger vers l'angle voulu.

[[Fichier:CORDIC-illustration.svg|thumb|300px|Illustration de plusieurs itérations de CORDIC]]

Plus formellement, à chaque itération {{mvar|i}}, on calcule un nouveau vecteur grâce à la multiplication du vecteur {{mvar|v{{ind|i}}}} avec la [[Rotation plane|matrice de rotation]] {{mvar|R{{ind|i}}}} :
: <math> v_{i+1} = R_{i}v_{i}\ </math>

La matrice de rotation {{mvar|R{{ind|i}}}} s'obtient selon la formule suivante :
: <math> R_{i} = \begin{pmatrix} \cos \gamma_{i} & -\sigma_{i}\sin \gamma_{i} \\ \sigma_{i}\sin \gamma_{i} & \cos \gamma _{i}\end{pmatrix} </math>
Le facteur {{mvar|σ{{ind|i}}}} prend les valeurs +1 ou -1 et sert à indiquer le sens de la rotation, {{mvar|γ{{ind|i}}}} restant positif.

En factorisant par le terme {{math|cos(γ{{ind|i}})}}, on obtient :
: <math> v_{i+1} = R_{i}v_{i} = \cos \gamma_{i} \begin{pmatrix} 1 & -\sigma_{i} \tan \gamma_{i} \\ \sigma_{i} \tan \gamma_{i} & 1 \end{pmatrix}\begin{pmatrix} x_{i} \\ y_{i} \end{pmatrix} </math>

Si l'on restreint les choix possibles pour l'angle {{mvar|γ{{ind|i}}}} de manière que {{math|tan(γ{{ind|i}})}} soit égal à {{math|2{{exp|–''i''}}}} alors la multiplication par la tangente devient une multiplication par une puissance de 2. Une opération aisée à réaliser informatiquement puisqu'en binaire il s'agit d'un décalage de [[bit]]s.

Le calcul devient :
: <math> v_{i+1} = R_{i}v_{i} = \cos(\arctan(2^{-i}))\begin{pmatrix} 1 & -\sigma_{i} 2^{-i} \\ \sigma_{i} 2^{-i} & 1 \end{pmatrix}\begin{pmatrix} x_{i} \\ y_{i} \end{pmatrix} = K_{i}\begin{pmatrix} x_{i} -\sigma_{i} 2^{-i}y_{i} \\ x_{i}\sigma_{i} 2^{-i}+y_{i} \end{pmatrix} </math>

avec
: <math> K_i = \cos(\arctan(2^{-i}))\ </math>

Ces coefficients {{mvar|K{{ind|i}}}} peuvent être ignorés pendant les itérations et factorisés en un seul coefficient multiplicatif final (dépendant de {{mvar|n}}) :
: <math> K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1} \cos(\arctan(2^{-i})) = \prod_{i=0}^{n-1} \frac{1}{\sqrt{1 + 2^{-2i}}} </math>

qui peut être calculé à l'avance et prémémorisé. Également, lorsque {{mvar|n}} tend vers l'infini, ce produit tend vers une constante :
: <math> K = \lim_{n \to \infty}K(n) \approx 0,6073 </math> <small>(0,60725294…)</small>

Après suffisamment d'itérations, l'angle du vecteur sera proche de l'angle {{mvar|β}} voulu.

La dernière étape consiste à déterminer à chaque itération le sens de rotation, trigonométrique ou horaire (un résultat reporté sur la valeur de {{mvar|σ{{ind|i}}}}). Pour ce faire, on considère la valeur actuelle de l'angle {{math|''β''{{ind|''i''}}}} du vecteur, que l'on soustrait à l'angle désiré. On teste si cette différence est positive (rotation dans le sens horaire) ou négative (sens trigonométrique), ce qui détermine la valeur de {{mvar|σ{{ind|i}}}} de façon à s'approcher de l'angle {{mvar|β}} :

: <math> \beta_{i+1} = \beta_i - \sigma_i \gamma_i. \quad \gamma_i = \arctan 2^{-i}</math>,

Les valeurs des {{mvar|γ{{ind|i}}}} sont précalculées dans une table prémémorisée de valeurs. Toutefois, pour des angles petits, on utilise l'approximation {{math|arctan(2{{exp|-{{mvar|i}}}})}} ≈ {{math|2{{exp|-{{mvar|i}}}}}} dans une représentation en virgule fixe, permettant ainsi de réduire la taille de cette table.

Comme illustré dans le schéma ci-dessus, le sinus de l'angle {{mvar|β}} est la coordonnée {{mvar|y}} du vecteur final {{mvar|v{{ind|n}}}}, alors que la coordonnée {{mvar|x}} correspond au cosinus.

== Algorithme ==
En [[1971]], John Stephen Walther de [[Hewlett Packard]], a présenté une généralisation de l'algorithme qui fut mise en œuvre dans la calculatrice [[HP-35]]. Cette méthode permet de calculer notamment les [[Fonction hyperbolique|fonctions hyperboliques]] mais également d'autres fonctions comme l'exponentielle, la division ou la multiplication. La généralisation se présente comme suit<ref name="autogenerated1">http://cdeval.free.fr/IMG/pdf/cordic.pdf</ref> :
:<math>\left\{\begin{matrix} x_{k+1} = x_k - m\sigma_k y_k 2^{-k} \\ y_{k+1} = y_k + \sigma_k x_k 2^{-k} \\ z_{k+1} = z_k - \sigma_k \varepsilon_k \end{matrix}\right.</math>

avec {{math|''m'' ∈ {–1 ; 0 ; 1} }}, {{mvar|ε{{ind|k}}}} des constantes définies à l'avance et {{math|''σ{{ind|k}}'' ∈ {–1 ; 1} }} (en fonction de la valeur de {{mvar|z{{ind|k}}}}).

=== Fonctions trigonométriques ===
On utilise la généralisation avec les paramètres :

: <math>m = 1~</math>
: <math>\varepsilon_k = \operatorname{arctan}(2^{-k})</math>
: <math>\sigma_k = \operatorname{sgn}(z_k)</math>
:<math>x_0 =K = \prod_{i=0}^{\infty} \cos(\arctan(2^{-i})) \approx 0.607252</math>
: <math>y_0 = 0~</math>
: <math>z_0 = \theta~</math> (en radians)

À la fin de ''n'' itérations, on a {{math|''x{{ind|n}}'' ≈ cos(''θ'')}} et {{math|''y{{ind|n}}'' ≈ sin(''θ'')}}.

Cette méthode ne fonctionne que si :
: <math>| \theta | < \sum_{i=0}^{\infty} \operatorname{arctan}(2^{-i}) \approx 1{,}7</math>

En pratique cela ne pose pas de problème car les fonctions trigonométriques peuvent toujours être ramenées au cas {{math|0 ≤ ''θ'' < {{sfrac|π|2}}}} en exploitant leurs propriétés les plus connues (voir [[Identité trigonométrique#Propriétés liées au cercle trigonométrique|Identité trigonométrique]]).

=== Fonctions hyperboliques ===
On utilise la généralisation avec les paramètres :

: <math>m = -1~</math>
: <math>\varepsilon_k = \operatorname{artanh}(2^{-k})</math>
: <math>\sigma_k = \operatorname{sgn}(z_k)</math>
:<math>x_0 =\prod_{i=0}^{\infty} \cosh(\operatorname{arctanh}(2^{-i})) \approx 1,20513</math>
: <math>y_0 = 0~</math>
: <math>z_0 = \theta~</math> (en radians)

À la fin de ''n'' itérations, on a {{math|''x{{ind|n}}'' ≈ cosh(''θ'')}} et {{math|''y{{ind|n}}'' ≈ sinh(''θ'')}}, ainsi que {{math|''x{{ind|n}}'' + ''y{{ind|n}}'' ≈ exp(''θ'')}}.

Cette méthode ne fonctionne que si la valeur absolue de {{mvar|z}} est inférieure à environ 1,05. Des transformations d'expressions grâce à des [[Fonction hyperbolique|identités trigonométriques]] permettent de contourner ces problèmes en faisant en sorte que les paramètres soient dans l'intervalle requis. La répétition de certaines itérations résout les problèmes de convergence<ref name="autogenerated1" />.

=== Double itération CORDIC ===

Dans les publications de Baykov<ref>''Hardware implementation of the elementary functions by digit-by-digit (CORDIC) technique'', thèse de Vladimir Baykov, disponible sur [http://baykov.de/CORDIC1972.htm]</ref>{{,}}<ref>{{ouvrage|lang=en|auteur1=V.D.Baykov|auteur2=V.B.Smolov|titre=Hardware implementation of elementary functions in computers|lieu=Leningrad State University|année=1975|pages=96|lire en ligne=http://baykov.de/CORDIC1975.htm}}</ref>, celui-ci a proposé d'utiliser la méthode des doubles itérations pour l'implémentation des fonctions : arcsinX, arccosX, lnX, expX, ainsi que pour le calcul des fonctions hyperboliques. La méthode des doubles itérations consiste dans le fait 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 de la double itération, la valeur du pas d'itération est répétée deux fois et ne change qu'au cours d'une itération. D'où la désignation de l'indicateur de degré pour les itérations doubles : i = 1,1,2,2,3,3... Alors qu'avec les itérations ordinaires : i = 1,2,3... La méthode de la double itération garantit la convergence de la méthode dans toute la plage valide de changements d'arguments.

La généralisation des problèmes de convergence CORDIC pour le système de numération positionnelle arbitraire<ref>{{ouvrage|lang=en|titre=Special-purpose processors: iterative algorithms and structures|lieu=Moscow|année=1985|pages=288|auteur1=Vladimir Baykov|auteur2=Vladimir Smolov|lire en ligne=http://baykov.de/CORDIC1985.htm}}</ref>, avec Radix R a montré que pour les fonctions sin, cos, arctg, il suffit d'effectuer (R-1) 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 les fonctions ln, exp, sh, ch, arth, des itérations R doivent être effectuées pour chaque valeur i. Pour les fonctions arcsin et arccos 2 (R-1) des itérations doivent être effectuées pour chaque chiffre numérique, c'est-à-dire pour chaque valeur de i. Pour les fonctions arch, arch, le nombre d'itérations sera de 2R pour chaque i, c'est-à-dire pour chaque chiffre de résultat.

=== Fonctions linéaires ===
CORDIC permet également de calculer la multiplication ou la division entre des nombres {{mvar|a}} et {{mvar|b}}.

==== Multiplication ====

: <math>m = 0~</math>
: <math>\varepsilon_k = 2^{-k}</math>
: <math>\sigma_k = \operatorname{sgn}(z_k)</math>
: <math>x_0 = a</math>
: <math>y_0 = 0~</math>
: <math>z_0 = b~</math>

À la fin de ''n'' itérations, on a {{math|''y{{ind|n}}'' ≈ ''a'' × ''b''}}. En pratique, elle est peu intéressante car son domaine est restreint : il faut impérativement que {{math|''b'' ∈ [–2 ; 2]}}.

==== Division ====

: <math>m = 0~</math>
: <math>\varepsilon_k = 2^{-k}</math>
: <math>\sigma_k = -\operatorname{sgn}(y_k)</math>
: <math>x_0 = b~</math>
: <math>y_0 = a~</math>
: <math>z_0 = 0~</math>

À la fin de ''n'' itérations, on a {{math|''z{{ind|n}}'' ≈ ''a'' / ''b''}}. Elle a aussi un domaine d'application restreint puisque la condition suivante doit être respectée : <math>\left|\frac{a}{b}\right| \leq 2</math>

== Bibliographie ==
* [[Jack E. Volder]], ''The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers'', {{date-|septembre 1959}}
* Daggett, D. H., ''Decimal-Binary conversions in CORDIC'', IRE Transactions on Electronic Computers, Vol. EC-8 {{n°|5}}, {{p.|335-339}}, IRE, {{date-|septembre 1959}}.
* J. E. Meggitt, ''Pseudo Division and Pseudo Multiplication Processes'', IBM Journal, {{date-|avril 1962}}.
* [http://baykov.de/cordic1972.htm Vladimir Baykov, ''Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique'', rapport de thèse, Université d'État de Leningrad d'ingénierie électrique, 1972]
* Schmid, Hermann, ''Decimal computation''. New York, Wiley, 1974
* [http://baykov.de/cordic1975.htm V.D.Baykov, V.B.Smolov, ''Hardware implementation of elementary functions in computers'', Université d'État de Leningrad, 1975, 96p.]
* Senzig, Don, ''Calculator Algorithms'', IEEE Compcon Reader Digest, Catalogue IEEE {{n°|75}} CH 0920-9C, {{p.|139-141}}, IEEE, 1975.
* V.D.Baykov, S.A.Seljutin, ''Elementary functions evaluation in microcalculators'', Moscou, Radio & svjaz, 1982,64p.
* [http://baykov.de/cordic1985.htm Vladimir D.Baykov, Vladimir B.Smolov, ''Special-purpose processors: iterative algorithms and structures'', Moscou, Radio & svjaz, 1985, 288 pages]
* [http://arxiv.org/pdf/2008.02894.pdf M. Zechmeister '' Solving Kepler’s equation with CORDIC double iterations '' Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany, Preprint 10 August 2020, p.1-10.]
* M. E. Frerking, ''Digital Signal Processing in Communication Systems'', 1994
* Vitit Kantabutra, ''On hardware for computing exponential and trigonometric functions'', IEEE Trans. Computers 45 (3), 328-339 (1996).
* [https://link.springer.com/article/10.1023/A:1008121502359 Tomás Lang & Elisardo Antelo ''CORDIC-Based Computation of ArcCos '' Journal of VLSI signal processing systems for signal, image and video technology volume 25, pages19–38 (2000)]
* [http://cordic-bibliography.blogspot.com/p/double-iterations-in-cordic.html?m=1 Vladimir Baykov ''Double iterations in CORDIC '' CORDIC Bibliography]
* [http://www.andraka.com/cordic.htm Andraka, Ray, ''A survey of CORDIC algorithms for FPGA based computers'']
* [http://www.jacques-laporte.org/LeSecretDesAlgorithmes.htm ''Le Secret des algorithmes''], Jacques Laporte, Paris 1981. À la suite du décès de son auteur et non-renouvellement auprès de l'hébergeur, le site est désormais inaccessible (même chez archive.org), sauf auprès de la [[NSA]]. Néanmoins, une copie, autorisée par sa veuve, se trouve à l'adresse : [http://home.citycable.ch/pierrefleur/Jacques-Laporte/index.html http://home.citycable.ch/pierrefleur/Jacques-Laporte/index.html].
* {{Ouvrage | langue=en | auteur1=Jean-Michel Muller | titre=Elementary Functions – Algorithms and Implementation, 2nd Ed. | éditeur=Birkhäuser | lieu=Boston | année=2006 | numéro d'édition=2 | pages totales=265 | isbn=978-0-8176-4372-0 | lccn=2005048094 | présentation en ligne=https://books.google.com/books?id=g3AlWip4R38C&printsec=frontcover}}
* [http://hal.archives-ouvertes.fr/docs/00/07/14/77/PDF/RR-5105.pdf Lefèvre V., Zimmerman P.], {{date-|janvier 2004}}, ''Arithmétique flottante'', Rapport de Recherche INRIA {{n°|5105}}.

== Notes et références ==
{{Références}}

== Voir aussi ==
{{Sigle|6}}
=== Articles connexes ===
* [[Calcul numérique]]
* [[Approximation de fonction]]
* [[v:Very High Speed Integrated Circuit Hardware Description Language/Réalisation d'un coprocesseur CORDIC|Réalisation d'un coprocesseur CORDIC]] dans la WIKIversité

=== Liens externes ===
* {{en}} [http://www.dspguru.com/dsp/faqs/cordic Dspguru - Questions sur CORDIC]
* {{en}} [http://www.cnmat.berkeley.edu/~norbert/cordic/ Synthèse sonore en FPGA]
* {{en}} [http://portal.acm.org/citation.cfm?id=626526.627179 Vecteurs arbitraires dans CORDIC]
* {{en}} [http://cordic-bibliography.blogspot.com/p/double-iterations-in-cordic.html méthode CORDIC à doubles itérations]
* {{en}} [http://www.eecg.toronto.edu/~bach/HOME/CORDIC/net.refs discussions sur USENET]
* {{en}} [http://www.math.ucl.ac.be/~magnus/num1a/cordic.txt D'autres discussions sur USENET]
* {{en}} [http://citeseer.ist.psu.edu/lang00cordicbased.html Calculs de Arccos et <math>\sqrt{1-t^2}</math> avec CORDIC]
* {{en}} [http://www.emesystems.com/BS2mathC.htm programmation de CORDIC basée sur des tampons]
* {{en}}http://www.math.niu.edu/~rusin/known-math/94/cordic
* {{en}} [http://www.jacques-laporte.org/Trigonometry.htm Implémentation de CORDIC dans la ROM du HP-35 - Jacques Laporte (analyse pas à pas du firmware)]
* {{en}} [http://www.jacques-laporte.org/digit_by_digit.htm ''Digit by digit methods''], Jacques Laporte, Paris 2006 (la filiation entre CORDIC et les anciennes méthodes notamment celle de Briggs)

{{Portail|mathématiques|informatique}}

[[Catégorie:Algorithme numérique]]
[[Catégorie:Trigonométrie]]