CORDIC

Un article de Wikipédia, l'encyclopédie libre.

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 pipelining (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.

Sommaire

1 Description
2 Algorithme
3 Exemples de programmation
- 3.1 MATLAB
- 3.2 langage C
4 Bibliographie
5 Notes
6 Voir aussi
- 6.1 Articles connexes
- 6.2 Liens externes

[modifier] 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 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} 1/\sqrt{1 + 2^{-2i}}$

qui peut être calculé à l'avance et prémémorisé. On peut également noter qu'à 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.

[modifier] 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\}$ , $\varepsilon_k$ des constantes définies à l'avance et $\sigma_k \in \{-1; 1\}$ (en fonction de la valeur de $z k$ ).

[modifier] 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}$

[modifier] 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 ^[2].

[modifier] Fonctions linéaires

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

[modifier] Multiplication

$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]$ .

[modifier] Division

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

[modifier] Exemples de programmation

[modifier] 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;

[modifier] langage C

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

int iterations; // nombre d'itérations de l'algorithme
float arctanTable[iterations]; // en radians
float K = 0.6073; // K
float v_x,v_y; // Vecteur v; composantes x et y
 
for(int i=0; i < iterations; i++) {
    arctanTable[i] = atan(pow(2,-i));
}
 
float vnew_x;   // mémorise la prochaine valeur de x
for(i = 0; i < iterations; i++) {
     // si beta négatif, rotation dans le sens trigo
     if( beta < 0) {
        vnew_x = v_x + (v_y*pow(2,-i)); 
        v_y -= (v_x*pow(2,-i));  
        beta += arctanTable[i]; 
     }
     // si beta positif, rotation dans le sens horaire
     else {
        vnew_x = v_x - (v_y*pow(2,-i));
        v_y += (v_x*pow(2,-i));
        beta -= arctanTable[i];
     }
     v_x = vnew_x;
}
 
v_x *= K;
v_y *= K;

[modifier] 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