CORDIC

{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}

CORDIC (sigle de Modèle:Langue, « calcul numérique par rotation de coordonnées ») est un algorithme de calcul des fonctions trigonométriques et hyperboliques, notamment utilisé dans les calculatrices. 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 multiplicateur n'est disponible (sur certains microcontrôleurs 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 décimales du CORDIC (avec des nombres codés en 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 ou le cosinus d'un angle Modèle:Mvar, on recherche la coordonnée x ou y du point du cercle unité lui correspondant. CORDIC commence les calculs avec un vecteur Modèle:Math 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 Modèle:Math. 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.png
Illustration de plusieurs itérations de CORDIC

Plus formellement, à chaque itération Modèle:Mvar, on calcule un nouveau vecteur grâce à la multiplication du vecteur Modèle:Mvar avec la matrice de rotation Modèle:Mvar :

<math> v_{i+1} = R_{i}v_{i}\ </math>

La matrice de rotation Modèle:Mvar 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 Modèle:Mvar prend les valeurs +1 ou -1 et sert à indiquer le sens de la rotation, Modèle:Mvar restant positif.

En factorisant par le terme Modèle:Math, 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 Modèle:Mvar de manière que Modèle:Math soit égal à Modèle:Math 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 bits.

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 Modèle:Mvar peuvent être ignorés pendant les itérations et factorisés en un seul coefficient multiplicatif final (dépendant de Modèle:Mvar) :

<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 Modèle:Mvar tend vers l'infini, ce produit tend vers une constante :

<math> K = \lim_{n \to \infty}K(n) \approx 0,6073 </math> (0,60725294…)

Après suffisamment d'itérations, l'angle du vecteur sera proche de l'angle Modèle: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 Modèle:Mvar). Pour ce faire, on considère la valeur actuelle de l'angle Modèle:Math 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 Modèle:Mvar de façon à s'approcher de l'angle Modèle:Mvar :

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

Les valeurs des Modèle:Mvar sont précalculées dans une table prémémorisée de valeurs. Toutefois, pour des angles petits, on utilise l'approximation Modèle:Math ≈ Modèle:Math 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 Modèle:Mvar est la coordonnée Modèle:Mvar du vecteur final Modèle:Mvar, alors que la coordonnée Modèle:Mvar 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 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 Modèle:Math, Modèle:Mvar des constantes définies à l'avance et Modèle:Math (en fonction de la valeur de Modèle:Mvar).

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 Modèle:Math et Modèle:Math.

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 Modèle:Math en exploitant leurs propriétés les plus connues (voir 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 Modèle:Math et Modèle:Math, ainsi que Modèle:Math.

Cette méthode ne fonctionne que si la valeur absolue de Modèle:Mvar est inférieure à environ 1,05. Des transformations d'expressions grâce à des 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 [1]</ref>,<ref>Modèle:Ouvrage</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>Modèle:Ouvrage</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 Modèle:Mvar et Modèle:Mvar.

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 Modèle:Math. En pratique, elle est peu intéressante car son domaine est restreint : il faut impérativement que Modèle:Math.

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 Modèle:Math. 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

Notes et références

Modèle:Références

Voir aussi

1|2|3|4|5|6|7|8={{#ifeq:6|2|►| }} }}Sigles de 2 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|3|►| }} }}Sigles de 3 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|4|►| }} }}Sigles de 4 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|5|►| }} }}Sigles de 5 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|6|►| }} }}Sigles de 6 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|7|►| }} }}Sigles de 7 caractères
1|2|3|4|5|6|7|8={{#ifeq:6|8|►| }} }}Sigles de 8 caractères

{{#if: 6 

 | {{#ifeq:  | nocat
     | 
     | {{#switch: {{#ifexpr: 6 > 9 | 9 | 6 }}
         |2=
         |3=
         |4=
         |5=
         |6=
         |7=
         |8=
         |9=
         |#default=
       }}
   }}

}}

Articles connexes

Liens externes

Modèle:Portail

Récupérée de « https://wiki.trucsazeb.re:443/index.php?title=CORDIC&oldid=197970 »