CORDIC

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 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 β, on recherche la coordonnée x ou y du point du cercle unité lui correspondant. CORDIC débute les calculs avec un vecteur v₀ 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₁. 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 β_{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 γ_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 β est la coordonnée y du vecteur final v_n, alors que la coordonnée 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 implémentée 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\}$, ε_k des constantes définies à l'avance et $\sigma_k \in \{-1; 1\}$ (en fonction de la valeur de z_k).

Fonctions trigonométriques

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 =\prod_{i=0}^{\infty} \cos(\operatorname{atan}(2^{-i})) \approx 0,60725$

$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 sinus et cosinus peuvent être extrapolées à partir des valeurs $| \theta | < \frac{\pi}{2}$

Fonctions hyperboliques

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

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

Multiplication

$m = 0~$

ε_k = 2 ^{− k}

$\sigma_k = \operatorname{sgn}(z_k)$

x₀ = 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

$m = 0~$

ε_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 toutefois le même défaut que la multiplication puisque la condition sur b doit être remplie : $b \in [-2;2]$.

Exemples de programmation

MATLAB

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

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("%ld",&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;
}

Bibliographie

• Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, septembre 1959
• Daggett, D. H., Decimal-Binary conversions in CORDIC, IRE Transactions on Electronic Computers, Vol. EC-8 n°5, pp335-339, IRE, septembre 1959.
• J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes, IBM Journal, avril 1962.
• 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
• 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, pp139-141, IEEE, 1975.
• V.D.Baykov, S.A.Seljutin, Elementary functions evaluation in microcalculators, Moscou, Radio & svjaz, 1982,64p.
• Vladimir D.Baykov, Vladimir B.Smolov, Special-purpose processors: iterative algorithms and structures, Moscou, Radio & svjaz, 1985, 288 pages
• 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).
• Andraka, Ray, A survey of CORDIC algorithms for FPGA based computers
• 'Le Secret des Algorithmes, Jacques Laporte, Paris 1981
• (en) Jean-Michel Muller, Elementary Functions – Algorithms and Implementation, 2nd Ed., Boston, Birkhäuser, 2006, 2^e éd. (ISBN 978-0-8176-4372-0) (LCCN 2005048094) 
• Lefèvre V., Zimmerman P., janvier 2004, Arithmétique flottante, Rapport de Recherche INRIA n°5105.

Notes

1. ↑ ^{a et b} http://cdeval.free.fr/IMG/pdf/cordic.pdf

Voir aussi

Articles connexes

• Calcul numérique
• Approximation de fonction
• Variation de la Méthode de calcul du cosinus

Liens externes

• (en)Dspguru - Questions sur CORDIC
• (en)Synthèse sonore en FPGA
• (en)Vecteurs arbitraires dans CORDIC
• (en)méthode CORDIC à doubles itérations
• (en)discussions sur USENET
• (en)D'autres discussions sur USENET
• (en)Calculs de Arccos et $\sqrt{1-t^2}$ avec CORDIC
• (en)programmation de CORDIC basée sur des tampons
• (en)http://www.math.niu.edu/~rusin/known-math/94/cordic
• (fr)Implémentation de CORDIC dans la ROM du HP-35 - Jacques Laporte (analyse pas à pas du firmware - simulateur de la ROM du calculateur avec breakpoints et trace.)
• (en)Digit by digit methods, Jacques Laporte, Paris 2006 (la filiation entre CORDIC et les anciennes méthodes notamment celle de Briggs)

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