CORDIC

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

CORDIC (sigle de COordinate Rotation DIgital Computer : « 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 lorsqu'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[modifier | modifier le code]

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  \beta , on recherche la coordonnée x ou y du point du cercle unité lui correspondant. CORDIC commence les calculs avec un vecteur  v_0 tel que :

 v_o = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

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  v_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.

Illustration de plusieurs itérations de CORDIC

Plus formellement, à chaque itération i, on calcule un nouveau vecteur grâce à la multiplication du vecteur v_i avec la matrice de rotation R_{i} :

 v_{i+1} = R_{i}v_{i}\

La matrice de rotation R_{i}~ s'obtient selon la formule suivante :

 R_{i} = \begin{pmatrix} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{pmatrix}

En factorisant le terme \cos(\gamma)~ on obtient :

 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}

Le facteur \sigma_{i}~ prend les valeurs +1 ou -1 et sert à indiquer le sens de la rotation. Si l'on restreint les choix possibles pour l'angle \gamma~ de manière à ce que \tan(\gamma)~ soit égal à  2^{-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 bits.

Le calcul devient :

 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}

avec

 K_i = \cos(\arctan(2^{-i}))\

Ces coefficients K_i peuvent être ignorés pendant les itérations et factorisés en un seul coefficient multiplicatif final (dépendant de n) :

 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}}}

qui peut être calculé à l'avance et prémémorisé. Également, lorsque n tend vers l'infini, ce produit tend vers une constante :

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

Après suffisamment d'itérations, l'angle du vecteur sera proche de l'angle \beta ~ 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 \sigma_{i}~). Pour ce faire, on regarde l'angle \beta_{n+1} actuel 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), de façon à s'approcher de l'angle \beta ~.

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

Les valeurs de \gamma_n sont précalculées dans une table prémémorisée de valeurs. Toutefois, pour des angles petits, on utilise l'approximation  arctan(\gamma_n) \approx \gamma_n 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 \beta est la coordonnée y du vecteur final v_{n}, alors que la coordonnée x correspond au cosinus.

Algorithme[modifier | modifier le code]

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[1] :

\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.

avec m \in \{-1; 0; 1\}, \varepsilon_k des constantes définies à l'avance et \sigma_k \in \{-1; 1\} (en fonction de la valeur de z_k).

Fonctions trigonométriques[modifier | modifier le code]

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

m = 1~
\varepsilon_k = \operatorname{atan}(2^{-k})
\sigma_k = \operatorname{sgn}(z_k)
x_0 = 1
y_0 = 0~
z_0 = \theta~ (en radians)

À la fin de n itérations, on a x_n \approx \cos(\theta) et y_n \approx \sin(\theta).

Cette méthode ne fonctionne que si :

| \theta | < \sum_{i=0}^{\infty} \operatorname{atan}(2^{-i}) \approx 1,7

En pratique cela ne pose pas de problème car les fonctions trigonométriques peuvent toujours être ramenées au cas 0 \leq \theta < \frac{\pi}{2} en exploitant leurs propriétés les plus connues (voir Identité trigonométrique).

Fonctions hyperboliques[modifier | modifier le code]

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

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

À la fin de n itérations, on a x_n \approx \cosh(\theta) et y_n \approx \sinh(\theta), ainsi que x_n + y_n \approx e^\theta.

Cette méthode ne fonctionne que si la valeur absolue de z 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[1].

Fonctions linéaires[modifier | modifier le code]

CORDIC permet également de calculer la multiplication ou la division entre des nombres a et b.

Multiplication[modifier | modifier le code]

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

À la fin de n itérations, on a y_n \approx a \cdot b. En pratique, elle est peu intéressante car son domaine est restreint. Il faut impérativement que b \in [-2;2].

Division[modifier | modifier le code]

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

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

Exemples de programmation[modifier | modifier le code]

MATLAB[modifier | modifier le code]

function v=cordic(beta,n)
 % Calcul de 'cos' et 'sin' d'un angle 'beta' (en radians) 
 % par l'algorithme CORDIC. Résultat dans le vecteur 'v'. 
 % 'n' est le nombre d'itérations (la précision augmente avec lui).
 
%%Initialisation
v=[1;0];
sigma=1; 
Kn=prod(1./sqrt(1+2.^(-2*(0:(n-1)))));
 
%%Itérations
for i=0:n-1;
    R=[1 -sigma*2^-i;sigma*2^-i 1];
    v=R*v;
    beta=beta-sigma*atan(2^-i);
    sigma=sign(beta);
end
 
%% Calcul final
v=v*Kn;

Langage C[modifier | modifier le code]

Le code suivant utilise les flottants étendus (double). Beta est l'angle voulu en radians. On démarre par le vecteur v = (1;0), prémultiplié par K.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main()
{
    int nb_iter; // Nombre d'itérations
    double K = 0.6073; // Valeur de K
    double x = K, y = 0; // Valeur approchante de cos(beta) et sin(beta)
    double x_Nouveau; // Variable temporaire
    double beta = 0; // Angle à chercher
    double Pow2; // Valeur de la puissance de deux
 
    printf("Calcul par la methode CORDIC de sinus : \n\n\n Veuillez entrer beta\n");
    scanf("%lf",&beta); // entrer la valeur de beta
 
    printf("Veuillez entrer le nombre d'iterations voulues\n");
    scanf("%d",&nb_iter); // Entrer le nombre d'itération
 
    int i = 0; // declaration de l'indice d'iteration
    for(i = 0; i < nb_iter; i++) {
         Pow2 = pow(2,-i);
         // Si beta<0 rotation dans le sens trigo
         if(beta < 0) {
            x_Nouveau = x + y*Pow2;
            y -= x*Pow2;
            beta += atan(Pow2);
         }
         // sinon dans l'autre sens
         else {
            x_Nouveau = x - y*Pow2;
            y += x*Pow2;
            beta -= atan(Pow2);
         }
         x = x_Nouveau;
    }
 
    printf("cos(beta) = %lf , sin(beta) = %lf \n", x,y); // Affichage du résultat
    return 0;
}

Ce programme est donné à titre d'exemple pour en montrer le principe. Si vous le compilez pour un Microcontrôleur il vous prendra autour de 8 ko si ce dernier est sur 8 bits ce qui est la taille mémoire programme disponible pour les microcontrôleurs bas de gamme. Une version beaucoup moins consommatrice de ressource est présentée ICI dans la remarque (WIKIversité).

Cette adaptation est aussi discutée ICI (dans un livre sur VHDL) où l'on a ajouté une réalisation matérielle.

Bibliographie[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

  Sigles d’une seule lettre
  Sigles de deux lettres
  Sigles de trois lettres
  Sigles de quatre lettres
  Sigles de cinq lettres
> Sigles de six lettres
  Sigles de sept lettres
  Sigles de huit lettres

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]