CORDIQUE - CORDIC

Trigonométrie
Contour Histoire Usage Fonctions  ( inverse ) Trigonométrie généralisée
Référence
Identités Constantes exactes les tables Cercle unité
Lois et théorèmes
sinus Cosinus Tangentes Cotangentes théorème de Pythagore
Calcul
Substitution trigonométrique Intégrales  ( fonctions inverses ) Dérivés
v t e

CORDIC (pour CO ordonnée R ottaison DI GITAL C omputer), également connu comme l'algorithme de Volder , ou: Procédé chiffre par chiffre circulaire CORDIC (Jack E. Volder), linéaire CORDIC , hyperbolique CORDIC (John Stephen Walther) et Generalized hyperbolique CORDIC ( GH CORDIC ) (Yuanyong Luo et al.), est un moyen simple et efficace algorithme pour calculer des fonctions trigonométriques , fonctions hyperboliques , racines carrées , multiplications , divisions et exponentielles et logarithmes avec une base arbitraire, généralement convergeant avec un chiffre (ou bit ) par itération. CORDIC est donc aussi un exemple d' algorithmes chiffre par chiffre . CORDIC et les méthodes étroitement liées connues sous le nom de pseudo-multiplication et de pseudo-division ou de combinaison de facteurs sont couramment utilisées lorsqu'aucun multiplicateur matériel n'est disponible (par exemple dans les microcontrôleurs simples et les FPGA ), car les seules opérations qu'il nécessite sont des additions , des soustractions , des décalages de bits et des tables de recherche. . En tant que tels, ils appartiennent tous à la classe des algorithmes de décalage et d'ajout . En informatique, CORDIC est souvent utilisé pour implémenter l' arithmétique à virgule flottante lorsque la plate-forme cible manque de matériel pour des raisons de coût ou d'espace.

Histoire

Des techniques mathématiques similaires ont été publiées par Henry Briggs dès 1624 et Robert Flower en 1771, mais CORDIC est mieux optimisé pour les processeurs à états finis de faible complexité.

CORDIC a été conçu en 1956 par Jack E. Volder au département d' aéroélectronique de Convair par nécessité de remplacer le résolveur analogique de l' ordinateur de navigation du bombardier B-58 par une solution numérique en temps réel plus précise et plus rapide. Par conséquent, CORDIC est parfois appelé résolveur numérique .

Dans ses recherches, Volder s'est inspiré d'une formule de l'édition 1946 du CRC Handbook of Chemistry and Physics :

${\displaystyle {\begin{aligned}K_{n}R\sin(\theta \pm \varphi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta ),\ \K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\end{aligned}}}$

avec , . ${\displaystyle K_{n}={\sqrt {1+2^{-2n}}}}$${\displaystyle \tan(\varphi )=2^{-n}}$

Ses recherches ont abouti à un rapport technique interne proposant l'algorithme CORDIC pour résoudre les fonctions sinus et cosinus et un ordinateur prototype l'implémentant. Le rapport a également discuté de la possibilité de calculer la rotation des coordonnées hyperboliques , les logarithmes et les fonctions exponentielles avec des algorithmes CORDIC modifiés. L'utilisation de CORDIC pour la multiplication et la division a également été conçue à cette époque. Sur la base du principe CORDIC, Dan H. Daggett, un collègue de Volder chez Convair, a développé des algorithmes de conversion entre binaire et décimal codé binaire (BCD).

En 1958, Convair a finalement commencé à construire un système de démonstration pour résoudre les problèmes de prise de position radar nommé CORDIC I , achevé en 1960 sans Volder, qui avait déjà quitté l'entreprise. Des modèles CORDIC II plus universels A (stationnaire) et B (aéroporté) ont été construits et testés par Daggett et Harry Schuss en 1962.

L'algorithme CORDIC de Volder a été décrit pour la première fois en public en 1959, ce qui a entraîné son intégration dans les ordinateurs de navigation par des sociétés telles que Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon et Collins Radio .

Volder s'est associé à Malcolm McMillan pour créer Athena , une calculatrice de bureau à virgule fixe utilisant son algorithme binaire CORDIC. Le design a été présenté à Hewlett-Packard en juin 1965, mais n'a pas été accepté. Pourtant, McMillan a présenté David S. Cochran (HP) à l'algorithme de Volder et lorsque Cochran a rencontré plus tard Volder, il l'a référé à une approche similaire que John E. Meggitt (IBM) avait proposée comme pseudo-multiplication et pseudo-division en 1961. La méthode de Meggitt était suggérant également l'utilisation de la base 10 plutôt que de la base 2 , comme utilisé par CORDIC de Volder jusqu'à présent. Ces efforts ont conduit à la mise en œuvre de la logique ROMable d'un prototype de machine CORDIC décimal à l'intérieur de Hewlett-Packard en 1966, construit par et conceptuellement dérivé de la machine verte prototypique de Thomas E. Osborne , une calculatrice de bureau à virgule flottante à quatre fonctions qu'il avait achevé en logique DTL en décembre 1964. Ce projet a abouti à la démonstration publique de la première calculatrice de bureau de Hewlett-Packard avec des fonctions scientifiques, la hp 9100A en mars 1968, avec une production en série commençant plus tard cette année-là.

Lorsque Wang Laboratories a découvert que le hp 9100A utilisait une approche similaire à la méthode de combinaison de facteurs dans leurs calculatrices de bureau à instruments de calcul logarithmiques LOCI-1 (septembre 1964) et LOCI-2 (janvier 1965) , ils ont accusé en vain Hewlett-Packard de contrefaçon de l'un des brevets d' An Wang en 1968.

John Stephen Walther de Hewlett-Packard a généralisé l'algorithme dans l'algorithme Unified CORDIC en 1971, lui permettant de calculer des fonctions hyperboliques , des exponentielles naturelles , des logarithmes naturels , des multiplications , des divisions et des racines carrées . Les sous-programmes CORDIC pour les fonctions trigonométriques et hyperboliques pourraient partager la plupart de leur code. Ce développement a abouti à la première calculatrice scientifique portable , la HP-35 en 1972. Sur la base de CORDIC hyperbolique, Yuanyong Luo et al. a en outre proposé un CORDIC hyperbolique généralisé (GH CORDIC) pour calculer directement les logarithmes et les exponentielles avec une base fixe arbitraire en 2019. Théoriquement, Hyperbolic CORDIC est un cas particulier de GH CORDIC.

À l'origine, CORDIC n'a été implémenté qu'en utilisant le système de numération binaire et bien que Meggitt ait suggéré l'utilisation du système décimal pour son approche de pseudo-multiplication, CORDIC décimal a continué à rester pratiquement inconnu pendant plusieurs années, de sorte que Hermann Schmid et Anthony Bogacki ont toujours suggéré c'était une nouveauté jusqu'en 1973 et ce n'est que plus tard que Hewlett-Packard l'avait mis en œuvre en 1966 déjà.

Decimal CORDIC est devenu largement utilisé dans les calculatrices de poche , dont la plupart fonctionnent en décimal codé binaire (BCD) plutôt qu'en binaire. Ce changement dans le format d'entrée et de sortie n'a pas modifié les algorithmes de calcul de base de CORDIC. CORDIC est particulièrement bien adapté aux calculatrices portables, dans lesquelles un faible coût - et donc un faible nombre de portes de puces - est beaucoup plus important que la vitesse.

CORDIC a été implémenté dans les séries de coprocesseurs ARM STM32G4 , Intel 8087 , 80287 , 80387 jusqu'à 80486 ainsi que dans les Motorola 68881 et 68882 pour certains types d'instructions à virgule flottante, principalement comme moyen de réduire le nombre de portes (et la complexité) du sous-système FPU .

Applications

CORDIC utilise des opérations simples de décalage-addition pour plusieurs tâches informatiques telles que le calcul de fonctions trigonométriques, hyperboliques et logarithmiques, les multiplications réelles et complexes, la division, le calcul de racine carrée, la solution de systèmes linéaires, l' estimation des valeurs propres , la décomposition en valeurs singulières , la factorisation QR et beaucoup d'autres. En conséquence, CORDIC a été utilisé pour des applications dans divers domaines tels que le traitement du signal et de l' image , les systèmes de communication , la robotique et les graphiques 3D en dehors du calcul scientifique et technique général.

Matériel

L'algorithme a été utilisé dans le système de navigation du programme Apollo de » rover lunaire pour calculer palier et la portée ou la distance du module lunaire . CORDIC a été utilisé pour implémenter le coprocesseur mathématique Intel 8087 en 1980, évitant le besoin d'implémenter la multiplication matérielle.

CORDIC est généralement plus rapide que les autres approches lorsqu'un multiplicateur matériel n'est pas disponible (par exemple, un microcontrôleur), ou lorsque le nombre de portes nécessaires pour implémenter les fonctions qu'il prend en charge doit être minimisé (par exemple, dans un FPGA ou un ASIC ). En fait, CORDIC est une IP standard dans les applications de développement FPGA telles que Vivado pour Xilinx, tandis qu'une implémentation en série puissance n'est pas due à la spécificité d'une telle IP, c'est-à-dire que CORDIC peut calculer de nombreuses fonctions différentes (usage général) tandis qu'un le multiplicateur matériel configuré pour exécuter des implémentations de séries de puissance ne peut calculer que la fonction pour laquelle il a été conçu.

D'un autre côté, lorsqu'un multiplicateur matériel est disponible ( par exemple , dans un microprocesseur DSP ), les méthodes de recherche de table et les séries de puissance sont généralement plus rapides que CORDIC. Ces dernières années, l'algorithme CORDIC a été largement utilisé pour diverses applications biomédicales, en particulier dans les implémentations FPGA.

Les STM32G4 série et certains STM32H7 série d'unités MCU de mettre en œuvre un module CORDIC pour accélérer les calculs dans diverses applications à signaux mixtes tels que des graphiques pour interface homme - machine et de commande orientée de champ de moteurs. Bien qu'il ne soit pas aussi rapide qu'une approximation de séries entières, CORDIC est en effet plus rapide que les implémentations basées sur des tables d'interpolation telles que celles fournies par les bibliothèques standard ARM CMSIS et C. Bien que les résultats puissent être légèrement moins précis car les modules CORDIC fournis n'atteignent que 20 bits de précision dans le résultat. Par exemple, la plupart des différences de performances par rapport à l'implémentation ARM sont dues à la surcharge de l'algorithme d'interpolation, qui atteint une précision totale en virgule flottante (24 bits) et peut probablement générer une erreur relative par rapport à cette précision. Un autre avantage est que le module CORDIC est un coprocesseur et peut être exécuté en parallèle avec d'autres tâches CPU.

Le problème avec l'utilisation des séries entières est que, bien qu'elles fournissent une petite erreur absolue, elles ne présentent pas une erreur relative bien comportée.

Logiciel

De nombreux systèmes plus anciens avec des processeurs à nombre entier uniquement ont implémenté CORDIC à des degrés divers dans le cadre de leurs bibliothèques à virgule flottante IEEE . Comme la plupart des processeurs à usage général modernes ont des registres à virgule flottante avec des opérations courantes telles que l'addition, la soustraction, la multiplication, la division, le sinus, le cosinus, la racine carrée, le log ₁₀ , le log naturel, la nécessité d'y implémenter CORDIC avec un logiciel est presque inexistante. -existant. Seuls les microcontrôleurs ou les applications logicielles spéciales de sécurité et limitées dans le temps devraient envisager d'utiliser CORDIC.

Modes de fonctionnement

Mode de rotation

CORDIC peut être utilisé pour calculer un certain nombre de fonctions différentes. Cette explication montre comment utiliser CORDIC en mode rotation pour calculer le sinus et le cosinus d'un angle, en supposant que l'angle souhaité est donné en radians et représenté dans un format à virgule fixe. Pour déterminer le sinus ou le cosinus d'un angle , il faut trouver la coordonnée y ou x d'un point sur le cercle unité correspondant à l'angle désiré. En utilisant CORDIC, on commencerait par le vecteur : ${\displaystyle \beta }$${\displaystyle v_{0}}$

${\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix}}.}$

Une illustration de l'algorithme CORDIC en cours

Dans la première itération, ce vecteur est tourné de 45° dans le sens inverse des aiguilles d'une montre pour obtenir le vecteur . Des itérations successives font pivoter le vecteur dans l'une ou l'autre direction par pas de taille décroissante, jusqu'à ce que l'angle souhaité soit atteint. La taille du pas est pour . ${\displaystyle v_{1}}$${\style d'affichage i}$${\displaystyle \arctan {(2^{-i})}}$${\displaystyle i=0,1,2,\dots }$

Plus formellement, chaque itération calcule une rotation, qui s'effectue en multipliant le vecteur par la matrice de rotation : ${\displaystyle v_{i}}$ ${\style d'affichage R_{i}}$

${\displaystyle v_{i+1}=R_{i}v_{i}.}$

La matrice de rotation est donnée par

${\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\ cos(\gamma _{i})\end{bmatrice}}.}$

En utilisant les deux identités trigonométriques suivantes :

${\displaystyle {\begin{aligned}\cos(\gamma _{i})&={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}} ,\\\sin(\gamma _{i})&={\frac {\tan(\gamma _{i})}{\sqrt {1+\tan ^{2}(\gamma _{i}) }}},\end{aligné}}}$

la matrice de rotation devient

${\displaystyle R_{i}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}.}$

L'expression du vecteur tourné devient alors ${\displaystyle v_{i+1}=R_{i}v_{i}}$

${\displaystyle v_{i+1}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan( \gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}$

où et sont les composants de . Restreindre les angles tels que , la multiplication avec la tangente peut être remplacée par une division par une puissance de deux, ce qui est efficacement fait dans le matériel informatique numérique en utilisant un décalage de bit . L'expression devient alors ${\style d'affichage x_{i}}$${\style d'affichage y_{i}}$${\displaystyle v_{i}}$${\displaystyle \gamma _{i}}$${\displaystyle \tan(\gamma _{i})=\pm 2^{-i}}$

${\displaystyle v_{i+1}=K_{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\ end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}$

où

${\displaystyle K_{i}={\frac {1}{\sqrt {1+2^{-2i}}}},}$

et permet de déterminer le sens de rotation : si l'angle est positif, alors vaut +1, sinon il vaut -1. ${\displaystyle \sigma _{i}}$${\displaystyle \gamma _{i}}$${\displaystyle \sigma _{i}}$

${\displaystyle K_{i}}$ peut être ignoré dans le processus itératif puis appliqué par la suite avec un facteur d'échelle

${\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i}}}},}$

qui est calculé à l'avance et stocké dans un tableau ou comme une constante unique, si le nombre d'itérations est fixe. Cette correction pourrait aussi être faite à l'avance, en mettant à l'échelle et donc en sauvegardant une multiplication. De plus, on peut noter que ${\displaystyle v_{0}}$

${\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}$

pour permettre une réduction supplémentaire de la complexité de l'algorithme. Certaines applications peuvent éviter de corriger complètement, ce qui entraîne un gain de traitement : ${\style d'affichage K}$${\style d'affichage A}$

${\displaystyle A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{- 2i}}}\environ 1,64676025812107.}$

Après un nombre suffisant d'itérations, l'angle du vecteur sera proche de l'angle voulu . Dans la plupart des cas, 40 itérations ( n  = 40) suffisent pour obtenir le résultat correct à la 10e décimale. ${\displaystyle \beta }$

La seule tâche qui reste est de déterminer si la rotation doit être dans le sens horaire ou antihoraire à chaque itération (en choisissant la valeur de ). Ceci est fait en gardant une trace de combien l'angle a été tourné à chaque itération et en le soustrayant de l'angle souhaité ; alors pour se rapprocher de l'angle voulu , si est positif, la rotation est dans le sens horaire, sinon elle est négative et la rotation est dans le sens antihoraire : ${\style d'affichage \sigma }$${\displaystyle \beta }$${\displaystyle \beta _{n+1}}$

${\displaystyle \beta _{0}=\beta }$

${\displaystyle \beta _{i+1}=\beta _{i}-\sigma _{i}\gamma _{i},\quad \gamma _{i}=\arctan(2^{-i} ).}$

Les valeurs de doivent également être précalculées et stockées. Mais pour les petits angles, en représentation à virgule fixe, la taille du tableau est réduite. ${\displaystyle \gamma _{n}}$${\displaystyle \arctan(\gamma _{n})=\gamma _{n}}$

Comme on peut le voir dans l'illustration ci-dessus, le sinus de l'angle est la coordonnée y du vecteur final tandis que la coordonnée x est la valeur du cosinus. ${\displaystyle \beta }$${\displaystyle v_{n},}$

Mode de vectorisation

L'algorithme de mode de rotation décrit ci-dessus peut faire pivoter n'importe quel vecteur (pas seulement un vecteur unitaire aligné le long de l' axe x ) d'un angle compris entre -90° et +90°. Les décisions sur le sens de la rotation dépendent d' être positif ou négatif. ${\displaystyle \beta _{i}}$

Le mode de fonctionnement vectorisé nécessite une légère modification de l'algorithme. Il part d'un vecteur dont la coordonnée x est positive et la coordonnée y est arbitraire. Les rotations successives ont pour but de faire pivoter le vecteur vers l' axe x (et donc de réduire la coordonnée y à zéro). A chaque pas, la valeur de y détermine le sens de la rotation. La valeur finale de contient l'angle de rotation total. La valeur finale de x sera l'amplitude du vecteur d'origine mis à l'échelle par K . Ainsi, une utilisation évidente du mode de vectorisation est la transformation des coordonnées rectangulaires en coordonnées polaires. ${\displaystyle \beta _{i}}$

Mise en œuvre

Exemple de logiciel

Ce qui suit est une implémentation MATLAB / GNU Octave de CORDIC qui ne repose sur aucune fonction transcendantale, sauf dans le précalcul des tables. Si le nombre d'itérations n est prédéterminé, alors la deuxième table peut être remplacée par une seule constante. Avec l'arithmétique double précision standard de MATLAB et l'impression "format long", les résultats augmentent en précision pour n jusqu'à environ 48.

function v = cordic(beta,n)
% This function computes v = [cos(beta), sin(beta)] (beta in radians)
% using n iterations. Increasing n will increase the precision.

if beta < -pi/2 || beta > pi/2
    if beta < 0
        v = cordic(beta + pi, n);
    else
        v = cordic(beta - pi, n);
    end
    v = -v; % flip the sign for second or third quadrant
    return
end

% Initialization of tables of constants used by CORDIC
% need a table of arctangents of negative powers of two, in radians:
% angles = atan(2.^-(0:27));
angles =  [  ...
    0.78539816339745   0.46364760900081   0.24497866312686   0.12435499454676 ...
    0.06241880999596   0.03123983343027   0.01562372862048   0.00781234106010 ...
    0.00390623013197   0.00195312251648   0.00097656218956   0.00048828121119 ...
    0.00024414062015   0.00012207031189   0.00006103515617   0.00003051757812 ...
    0.00001525878906   0.00000762939453   0.00000381469727   0.00000190734863 ...
    0.00000095367432   0.00000047683716   0.00000023841858   0.00000011920929 ...
    0.00000005960464   0.00000002980232   0.00000001490116   0.00000000745058 ];
% and a table of products of reciprocal lengths of vectors [1, 2^-2j]:
% Kvalues = cumprod(1./abs(1 + 1j*2.^(-(0:23))))
Kvalues = [ ...
    0.70710678118655   0.63245553203368   0.61357199107790   0.60883391251775 ...
    0.60764825625617   0.60735177014130   0.60727764409353   0.60725911229889 ...
    0.60725447933256   0.60725332108988   0.60725303152913   0.60725295913894 ...
    0.60725294104140   0.60725293651701   0.60725293538591   0.60725293510314 ...
    0.60725293503245   0.60725293501477   0.60725293501035   0.60725293500925 ...
    0.60725293500897   0.60725293500890   0.60725293500889   0.60725293500888 ];
Kn = Kvalues(min(n, length(Kvalues)));

% Initialize loop variables:
v = [1;0]; % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);

% Iterations
for j = 0:n-1;
    if beta < 0
        sigma = -1;
    else
        sigma = 1;
    end
    factor = sigma * poweroftwo;
    % Note the matrix multiplication can be done using scaling by powers of two and addition subtraction
    R = [1, -factor; factor, 1];
    v = R * v; % 2-by-2 matrix multiply
    beta = beta - sigma * angle; % update the remaining angle
    poweroftwo = poweroftwo / 2;
    % update the angle from table, or eventually by just dividing by two
    if j+2 > length(angles)
        angle = angle / 2;
    else
        angle = angles(j+2);
    end
end

% Adjust length of output vector to be [cos(beta), sin(beta)]:
v = v * Kn;
return

endfunction

La multiplication matricielle deux par deux peut être effectuée par une paire de simples décalages et additions.

    x = v[0] - sigma * (v[1] * 2^(-j));
    y = sigma * (v[0] * 2^(-j)) + v[1];
    v = [x; y];

En Java, la classe Math a une scalb(double x,int scale)méthode pour effectuer un tel décalage, C a la fonction ldexp et la classe de processeurs x86 a l' fscaleopération en virgule flottante.

Exemple de matériel

Le nombre de portes logiques pour la mise en œuvre d'un CORDIC est à peu près comparable au nombre requis pour un multiplicateur car les deux nécessitent des combinaisons de décalages et d'ajouts. Le choix d'une mise en œuvre basée sur les multiplicateurs ou sur CORDIC dépendra du contexte. La multiplication de deux nombres complexes représentés par leurs composantes réelles et imaginaires (coordonnées rectangulaires), par exemple, nécessite 4 multiplications, mais pourrait être réalisée par un seul CORDIC opérant sur des nombres complexes représentés par leurs coordonnées polaires, surtout si la grandeur des nombres n'est pas pertinent (multiplier un vecteur complexe par un vecteur sur le cercle unité revient en fait à une rotation). Les CORDIC sont souvent utilisés dans les circuits de télécommunications tels que les convertisseurs numériques .

Double itération CORDIC

Dans les publications : http://baykov.de/CORDIC1972.htm et http://baykov.de/CORDIC1975.htm il a été proposé d'utiliser la méthode des doubles itérations pour l'implémentation des fonctions : arcsinX, arccosX, lnX, expX , ainsi que pour le calcul des fonctions hyperboliques. La méthode des doubles itérations consiste dans le fait que contrairement à la méthode CORDIC classique, où la valeur du pas d'itération change à CHAQUE fois, c'est-à-dire à chaque itération, dans la méthode de la double itération, la valeur du pas d'itération est répétée deux fois et ne change qu'au cours d'une itération. D'où la désignation de l'indicateur de degré pour les itérations doubles : i = 1,1,2,2,3,3... Alors qu'avec les itérations ordinaires : i = 1,2,3... La méthode de la double itération garantit la convergence de la méthode dans toute la plage valide de changements d'arguments.

La généralisation des problèmes de convergence CORDIC pour le système de numération positionnelle arbitraire http://baykov.de/CORDIC1985.htm avec Radix R a montré que pour les fonctions sin, cos, arctg, il suffit d'effectuer (R-1) itérations pour chaque valeur de i (i = 0 ou 1 à n, où n est le nombre de chiffres), c'est-à-dire pour chaque chiffre du résultat. Pour les fonctions ln, exp, sh, ch, arth, R des itérations doivent être effectuées pour chaque valeur i. Pour les fonctions arcsin et arccos 2 (R-1) des itérations doivent être effectuées pour chaque chiffre numérique, c'est-à-dire pour chaque valeur de i. Pour les fonctions arch, arch, le nombre d'itérations sera de 2R pour chaque i, c'est-à-dire pour chaque chiffre de résultat.

Algorithmes associés

CORDIC fait partie de la classe des algorithmes "shift-and-add" , tout comme les algorithmes logarithmiques et exponentiels dérivés des travaux d'Henry Briggs. Un autre algorithme de décalage et d'addition qui peut être utilisé pour calculer de nombreuses fonctions élémentaires est l' algorithme BKM , qui est une généralisation des algorithmes logarithmiques et exponentiels au plan complexe. Par exemple, BKM peut être utilisé pour calculer le sinus et le cosinus d'un angle réel (en radians) en calculant l'exponentielle de , qui est . L'algorithme BKM est légèrement plus complexe que CORDIC, mais présente l'avantage de ne pas nécessiter de facteur d'échelle ( K ). ${\style d'affichage x}$${\style d'affichage 0+ix}$${\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)}$

Voir également

• Méthodes de calcul des racines carrées
• IEEE 754
• Unités à virgule flottante
• Circuits numériques/CORDIC dans Wikibooks

Les références

Lectures complémentaires

• Parini, Joseph A. (1966-09-05). "DIVIC donne la réponse aux questions de navigation complexes". Électronique : 105–111. ISSN  0013-5070 .(NB. DIVIC signifie DIgital Variable Increments Computer . Certaines sources se réfèrent à tort à cela comme par JM Parini .)
• Anderson, Stanley F.; Earle, John G.; Goldschmidt, Robert Elliott; Pouvoirs, Don M. (1965-11-01). « L'IBM System/360 Model 91 : Unité d'exécution à virgule flottante » (PDF) . Revue IBM de recherche et développement . Riverton, New Jersey, États-Unis (publié en janvier 1967). 11 (1) : 34-53. doi : 10.1147/rd.111.0034 . Récupéré le 02/01/2016 .
• Liccardo, Michael A. (septembre 1968). Un processeur d'interconnexion mettant l'accent sur le fonctionnement en mode CORDIC (thèse de maîtrise). Berkeley, Californie, États-Unis : Université de Californie, Berkeley , Département de génie électrique. OCLC  500565168 .
• Brevet américain 3576983A , Cochran, David S., "Digital calculator system for computing square roots", publié 1971-05-04, publié 1971-05-04, attribué à Hewlett-Packard Co.  ( [14] )
• Chen, Tien Chi (juillet 1972). "Calcul automatique des exponentielles, des logarithmes, des rapports et des racines carrées" (PDF) . Revue IBM de recherche et développement . 16 (4) : 380-388. doi : 10.1147/rd.164.0380 . ISSN  0018-8646 . Récupéré le 02/01/2016 .
• Egbert, William E. (mai 1977). « Algorithmes de calculatrice personnelle I : Racines carrées » (PDF) . Journal Hewlett Packard . Palo Alto, Californie, États-Unis : Hewlett-Packard . 28 (9) : 22-24 . Récupéré le 02/01/2016 .( [15] )
• Egbert, William E. (juin 1977). « Algorithmes de calculatrice personnelle II : Fonctions trigonométriques » (PDF) . Journal Hewlett Packard . Palo Alto, Californie, États-Unis : Hewlett-Packard . 28 (10) : 17-20 . Récupéré le 02/01/2016 .( [16] )
• Egbert, William E. (novembre 1977). "Algorithmes de calculatrice personnelle III: Fonctions trigonométriques inverses" (PDF) . Journal Hewlett Packard . Palo Alto, Californie, États-Unis : Hewlett-Packard . 29 (3) : 22-23 . Récupéré le 02/01/2016 .( [17] )
• Egbert, William E. (avril 1978). « Algorithmes de calculatrice personnelle IV : fonctions logarithmiques » (PDF) . Journal Hewlett Packard . Palo Alto, Californie, États-Unis : Hewlett-Packard . 29 (8) : 29-32 . Récupéré le 02/01/2016 .( [18] )
• Senzig, Don (1975). "Algorithmes de calculatrice". IEEE Compcon Reader Digest . IEEE : 139-141. Catalogue IEEE n° 75 CH 0920-9C.
• Baykov, Vladimir D. (1972), опросы исследования исления ементарных функций по методу «цифра за цифрой»[ Problèmes d'évaluation des fonctions élémentaires basés sur la technique chiffre par chiffre (CORDIC) ] (Thèse de doctorat) (en russe), Université d'État de génie électrique de Leningrad
• Baykov, Vladimir D.; Smolov, Vladimir B. (1975). Apparaturnaja realizatsija elementarnikh funktsij contre CVM аратурная реализация ементарных нкций в ЦВМ[ Implémentation matérielle des fonctions élémentaires dans les ordinateurs ] (en russe). Université d'État de Léningrad. Archivé de l'original le 2019-03-02 . Récupéré le 02/03/2019 .
• Baykov, Vladimir D.; Seljutin, SA (1982). исление ементарных функций в ЭКВМ[ Évaluation des fonctions élémentaires dans les microcalculateurs ] (en russe). Moscou : Radio i svjaz (Радио и связь).
• Baykov, Vladimir D. ; Smolov, Vladimir B. (1985).ециализированные роцессоры: итерационные алгоритмы и структуры[ Processeurs spécialisés : algorithmes et structures itératifs ] (en russe). Moscou : Radio i svjaz (Радио и связь).
• Coppens, Thomas, éd. (janvier 1980). "Constantes CORDIC dans TI 58/59 ROM". Bulletin d'information sur l'échange de logiciels de Texas Instruments . Kapellen, Belgique : TISOFT. 2 (2).
• Coppens, Thomas, éd. (avril-juin 1980). "Schéma de calcul du logarithme naturel / schéma de calcul e ^x / schéma de calcul 1/x". Bulletin d'information sur l'échange de logiciels de Texas Instruments . Kapellen, Belgique : TISOFT. 2 (3).(à propos de CORDIC dans TI-58 / TI-59 )
• Équipe TI Graphic Products (1995) [1993]. "Algorithmes de fonction transcendantale" . Dallas, Texas, États-Unis : Texas Instruments , produits de consommation. Archivé de l'original le 2016-03-17 . Récupéré le 02/03/2019 .
• Jorke, Gunter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (en allemand) (1 éd.). Berlin, Allemagne : VEB Verlag Technik . p. 219, 261, 271-296. ISBN 3341005153. EAN  9783341005156 . MPN 5539165. Licence 201.370/4/89 . Récupéré le 01/12/2015 .
• M. Zechmeister Solving Kepler's equation with CORDIC double iterations Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Allemagne, Preprint 10 août 2020, p. 1-10.
• Frerking, Marvin E. (1994). Traitement du signal numérique dans les systèmes de communication (1 éd.).
• Kantabutra, Vitit (1996). « Sur le matériel pour le calcul des fonctions exponentielles et trigonométriques ». Transactions IEEE sur les ordinateurs . 45 (3) : 328-339. doi : 10.1109/12.485571 .
• Johansson, Kenny (2008). "6.5 Fonctions sinus et cosinus". Calculs basés sur le décalage et l'ajout de faible puissance et de faible complexité (PDF) (thèse de thèse). Études de Linköping en science et technologie (1 éd.). Linköping, Suède : Département de génie électrique, Université de Linköping . p. 244-250. ISBN 978-91-7393-836-5. ISSN  0345-7524 . N° 1201. Archivé (PDF) de l'original le 2017-08-13 . Récupéré le 2021-08-23 . (x+268 pages)
• Banerjee, Ayan (2001). "Réalisation FPGA d'un processeur FFT basé sur CORDIC pour le traitement du signal biomédical". Microprocesseurs et microsystèmes . Kharagpur, Bengale occidental, Inde. 25 (3) : 131-142. doi : 10.1016/S0141-9331(01)00106-5 .
• Kahan, William Morton (2002-05-20). « Algorithmes de pseudo-division pour les logarithmes à virgule flottante et les exponentielles » (PDF) . Berkeley, Californie, États-Unis : Université de Californie . Archivé de l'original (PDF) le 25-12-2015 . Récupéré le 15/01/2016 .
• Cockrum, Chris K. (Automne 2008). "Implémentation d'un algorithme CORDIC dans un convertisseur numérique vers le bas" (PDF) .
• Lakshmi, Boppana ; Dhar, Anindya Sundar (2009-10-06). "Architectures CORDIC : Une enquête" . Conception VLSI . Kharagpur, West Bengal, India : Department of Electronics and Electrical Communication Engineering, Indian Institute of Technology (publié le 2010-10-10). 2010 : 1-19. doi : 10.1155/2010/794891 . 794891.
• Savard, John JG (2018) [2006]. "Techniques arithmétiques avancées" . quadribloc . Archivé de l'original le 2018-07-03 . Récupéré le 16/07/2018 .

Liens externes

• Wang, Shaoyun (juillet 2011), Site de bibliographie CORDIC
• IP CORDIC souple (code verilog HDL)
• Site de bibliographie CORDIC
• BASIC Stamp, implémentation mathématique CORDIC
• Implémentation de CORDIC dans verilog
• Vectorisation CORDIC avec valeur cible arbitraire
• Implémentation mathématique PicBasic Pro, Pic18 CORDIC
• Implémentation Python CORDIC
• Code C simple pour CORDIC à virgule fixe
• Tutoriel et implémentation MATLAB - Utilisation de CORDIC pour estimer la phase d'un nombre complexe
• Descriptions des CORDIC matériels en Arx avec bancs de test en C++ et VHDL
• Une introduction à l'algorithme CORDIC
• Implémentation de l'algorithme CORDIC dans un down-converter numérique
• 50e anniversaire de l'algorithme CORDIC
• Implémentation de l'algorithme CORDIC : code C à virgule fixe pour les fonctions trigonométriques et hyperboliques , code C pour les tests et la vérification des performances