CORDIC

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

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} = (10)

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 :

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

R_{i} = (cos γ_{i} - sin γ_{i} sin γ_{i} cos γ_{i})

En factorisant le terme $cos (γ)$ on obtient :

v_{i + 1} = R_{i} v_{i} = cos γ_{i} (1 - σ_{i} tan γ_{i} σ_{i} tan γ_{i} 1) (x_{i} y_{i})

Le facteur $σ_{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 $γ$ de manière à ce que $tan (γ)$ 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 :

avec

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) :

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

K = n \to \infty lim K (n) \approx 0, 6073

Après suffisamment d'itérations, l'angle du vecteur sera proche de l'angle $β$ 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 $σ_{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 $β$ .

$β_{i + 1} = β_{i} - σ_{i} γ_{i} . γ_{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 $a r c t an (γ_{n}) \approx γ_{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 :

{x_{k + 1} = x_{k} - m σ_{k} y_{k} 2^{- k} y_{k + 1} = y_{k} + σ_{k} x_{k} 2^{- k} z_{k + 1} = z_{k} - σ_{k} ε_{k}

avec $m \in {- 1; 0; 1}$ , $ε_{k}$ des constantes définies à l'avance et $σ_{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

ε_{k} = atan (2^{- k})

σ_{k} = sgn (z_{k})

x_{0} = i = 0 \prod \infty cos (atan (2^{- i})) \approx 0, 60725

y_{0} = 0

$z_{0} = θ$ (en radians)

À la fin de n itérations, on a $x_{n} \approx cos (θ)$ et $y_{n} \approx sin (θ)$ .

Cette méthode ne fonctionne que si :

∣ θ ∣ < i = 0 \sum \infty 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 $∣ θ ∣ < \frac{π}{2}$

Fonctions hyperboliques

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

m = - 1

ε_{k} = atanh (2^{- k})

σ_{k} = sgn (z_{k})

x_{0} = i = 0 \prod \infty cosh (atanh (2^{- i})) \approx 1, 20513

y_{0} = 0

$z_{0} = θ$ (en radians)

À la fin de n itérations, on a $x_{n} \approx cosh (θ)$ et $y_{n} \approx sinh (θ)$ , ainsi que $x_{n} + y_{n} \approx e^{θ}$ .

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 .

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}

σ_{k} = 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}

σ_{k} = - 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 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 for(int 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
Jean-Michel Muller, Elementary Functions – Algorithms and Implementation, 2nd Ed., Birkhäuser, Boston, 2006