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.

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

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

$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

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

Voir aussi

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

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article CORDIC de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

CORDIC — (COordinate Rotation DIgital Computer), o el método de dígito por dígito, o el algoritmo de Volder, es un simple y eficiente algoritmo para calcular funciones hiperbólicas y trigonométricas. Típicamente es usado cuando no hay disponible un… … Wikipedia Español
CORDIC — (Метод CORDIC от англ. COordinate Rotation DIgital Computer цифровой вычислитель поворота системы координат; метод «цифра за цифрой», алгоритм Волдера) итерационный метод сведения прямых вычислений сложных функций к выполнению… … Википедия
CORDIC — Trigonometry History Usage Functions Generalized Inverse functions Further reading … Wikipedia
CORDIC — Der CORDIC Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die … Deutsch Wikipedia
Cordic — Der CORDIC Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die… … Deutsch Wikipedia
CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) … Acronyms
CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) … Acronyms von A bis Z
Regis Cordic — Regis John Rege Cordic (May 15, 1926 April 16, 1999) was an American radio personality and actor. His career in entertainment divides roughly in half: from 1948 to 1965, he was the dominant morning drive time radio host in Pittsburgh,… … Wikipedia
KDKA (AM) — KDKA City of license Pittsburgh, Pennsylvania Broadcast area Western Pennsylvania Branding Newsradio 1020 KDKA Slogan The Vo … Wikipedia
Bob Trow — Robert Trow (February 6, 1926 mdash;November 2, 1998) was an American radio celebrity, actor, and craftsman.Raised in the Beltzhoover neighborhood of Pittsburgh, Pennsylvania, USA, Trow began his career in radio. He later became well known for… … Wikipedia

Dictionnaires et Encyclopédies sur 'Academic'

CORDIC

Sommaire

Description