Mostra la font per a CORDIC

'''CORDIC''' ('''CO'''ordinate '''R'''otation '''DI'''gital''' C'''omputer), o '''mètode de dígit per dígit''', o '''[[algorisme]] de Volder''', és un simple i eficient algorisme per calcular [[funció (programació)|funcions]] [[funció hiperbòlica|hiperbòliques]] i [[funció trigonomètrica|trigonomètriques]]. Típicament és usat quan no hi ha disponible un maquinari per a multiplicacions (per exemple, en [[microcontrolador]]s i [[FPGA]]s simples) perquè les úniques operacions que requereix són suma, resta, desplaçament de bits ([[Operador_a_nivell_de_bits#Operacions_de_despla.C3.A7ament_i_rotaci.C3.B3|bitshift]]) i recerca en taules ([[lookup table]]). Està optimitzat per CPUs de poca complexitat.

== Orígens ==
L'algorisme CORDIC és similar a les tècniques matemàtiques publicades per [[Henry Briggs]] l'any [[1624]]. El CORDIC modern va ser descrit per primera vegada en [[1959]] per [[Jack E. Volder]]. Va ser desenvolupat en el departament del aeroelectrónica de [[Convair]] per substituir un [[circuit analògic | analògic]] a l'[[ordinador]] de [[navegació]] del bombarder [[B-58]].<ref name="volder00"> [http://dx.doi.org/10.1023/A:1008110704586 J. E. Volder, "The Birth of CORDIC", J. VLSI Signal Processing'' '25'' ', 101 (2000).]</ref> [[John Stephen Walther]], a [[Hewlett-Packard]], va generalitzar més l'algoritme, permetent calcular funcions [[funció hiperbòlica | hiperbòliques]], [[funció exponencial | exponencials]], [[logaritme]]s, [[multiplicació]], [[divisió]], i l'[[arrel quadrada]].<ref>[http://dx.doi.org/10.1023/A:1008162721424 J. S. Walther, "The Story of Unified CORDIC", J. VLSI Signal Processing'' '25'' ', 107 (2000).]</ref>

Originalment, CORDIC va ser implementat usant el [[sistema de numeració]] [[Codi_binari | binari]]. En els [[anys 1970]], la implementació en el sistema de numeració [[sistema de numeració decimal | decimal]] del CORDIC va arribar a ser usat extensament en les [[calculadora|calculadores]] de butxaca, la majoria de les quals operava en [[BCD|binary-coded decimal]] (BCD) en comptes de binari. CORDIC està particularment ben adaptat per a les calculadores de mà, un ús per a les quals el cost és molt més important que la velocitat, és a dir, el nombre de [[porta lògica | portes lògiques]] del [[Circuit integrat|xip]] ha de ser reduït al mínim. També les [[subrutines]] CORDIC per a les funcions trigonomètriques i hiperbòliques poden compartir la major part del seu codi.

== Usos ==
=== Maquinari ===
L'algorisme CORDIC és generalment més ràpid que altres maquinaris en el cas que un sistema no tingui multiplicadors dedicats (per exemple, en un microprocessador), o quan el nombre de [[Portes lògiques|portes]] requerides per implementar s'han de reduir al mínim (per exemple, en una [[FPGA]]).

D'altra banda, quan en un sistema hi han disponibles multiplicadors dedicats (per exemple, en un microprocessador DSP), o bé [[Lookup table|taules de cerca]] o bé mètodes d'avaluació de sèries, aquests mètodes són generalment més ràpids que CORDIC. En els últims anys, l'algorisme CORDIC s'ha utilitzat bastament en el camp de les aplicacions biomèdiques, especialment implementat en [[FPGA]]s.

=== Programari ===
Els sistemes mès àntics que utilitzen [[CPU]]s amb [[nombres enters]] han usat CORDIC en diferents graus d'implementació, com a part de les seves biblioteques de [[coma flotant]]. En CPUs més modernes que tenen registres de coma flotant amb implementacions de les operacions comunes, com ara [[sumar]], [[Resta|restar]], [[Multiplicació|multiplicar]], [[dividir]], [[sinus]], [[cosinus]], [[arrel quadrada]], [[Logaritme|logaritme en base 10]], [[logaritme natural]], no hi ha necessitat d'implementar CORDIC amb el programari. L'ús de CORDIC només es considera en casos especials tals com en aquells on els microcontroladors tinguin requeriments de seguretat especials o bé limitacions en el temps de processat.

== Mode de funcionament: mode de rotació ==
L'algorisme CORDIC es pot utilitzar per calcular un gran nombre de funcions. Aquesta explicació mostra com utilitzar CORDIC des d'un punt de vista de ''rotació'' per a calcular sinus i el cosinus d'un angle. Assumeix l'angle desitjat s'expressa en radiants i és representat en un format de [[coma fixa]]. Per determinar el sinus o el cosinus d'un angle <math> \beta </math>, s'han de trobar les coordenades '' y'' i '' x'' d'un punt en la [[circumferència goniomètrica]] en funcio de l'angle desitjat. L'algorisme CORDIC comença amb el vector <math> v_0 </math>:

: <math> v_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} </math>

A la primera iteració, aquest vector gira 45° cap a l'esquerra per obtenir el vector <math> v_1 </math>. Iteracions successives giraran el vector en una o altra direcció en passos de mida decreixent, fins a aconseguir l'angle desitjat. El pas és arctan(1/(2<sup>''i''−1</sup>)) per ''i'' =&nbsp;1, 2, 3, ….

[[Fitxer:CORDIC-illustration.svg|miniatura|Il·lustració de l'algorisme CORDIC en curs.]]


Més formalment, cada iteració calcula una rotació, que es realitza multiplicant el vector <math>v_{i-1}</math> per la [[matriu de rotació]] <math>R_{i}</math>:

: <math> v_{i} = R_{i}v_{i-1}\ </math>

La matriu de rotació R ve donada per:

: <math> R_{i} = \begin{bmatrix} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{bmatrix} </math>

Usant les següents [[Llista d'identitats trigonomètriques | identitats trigonomètriques]]

: <math>\begin{align} \cos \alpha & = & {1 \over \sqrt{1 + \tan^2 \alpha}} \\ \sin \alpha & = & {{\tan \alpha} \over \sqrt{1 + \tan^2 \alpha}} \end{align} </math>

la matriu de rotació es converteix en:

: <math> R_i = {1 \over \sqrt{1 + \tan^2 \gamma_i}} \begin{bmatrix} 1 & -\tan \gamma_i \\ \tan \gamma_i & 1 \end{bmatrix} </math>

Els vectors de rotació <math>v_i = R_i v_{i-1}</math> es converteixen en:

: <math> v_i = {1 \over \sqrt{1 + \tan^2 \gamma_i}} \begin{bmatrix} 1 & -\tan \gamma_i \\ \tan \gamma_i & 1 \end{bmatrix} \begin{bmatrix} x_{i-1} \\ y_{i-1} \end{bmatrix} </math>

on <math>x_{i-1}</math> i <math>y_{i-1}</math> són els components de <math>v_{i-1}</math>. La restricció els angle que pot prendre <math>\gamma_{i}</math> de manera que <math> \tan \gamma_{i} </math> pren els valors <math> \pm 2^{-i} </math> la multiplicació amb la tangent pot ser reemplaçada per una divisió per una potència de dos, que es realitza eficientment en maquinari digital utilitzant un desplaçament de bits. L'expressió esdevé:

: <math> v_i = K_i \begin{bmatrix} 1 & -\sigma_i 2^{-i} \\ \sigma_i 2^{-i} & 1 \end{bmatrix} \begin{bmatrix} x_{i-1} \\ y_{i-1} \end{bmatrix} </math>

on

: <math> K_i = {1 \over \sqrt{1 + 2^{-2i}}} </math>

i <math>\sigma_i</math> pot tenir els valors de -1 o 1, i s'utilitza per determinar la direcció de la rotació: si l'angle de <math>\beta_i</math> és positiu, llavors el <math>\sigma_i</math> és 1, en cas contrari, és -1.

En el procés iteratiu podem fer cas omís de <math> K_i </math> i aplicar-lo després, ja que tan sols és un factor d'escala:

: <math> K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1} 1/\sqrt{1 + 2^{-2i}} </math>

que es calcula per endavant i s'emmagatzema en una taula, o com una constant si el nombre d'iteracions és fix. Aquesta correcció també pot ser realitzada amb anterioritat, mitjançant l'ampliació del <math> v_0 </math> i, per tant, l'estalvi d'una multiplicació. Addicionalment es pot observar que

: <math> K = \lim_{n \to \infty}K(n) \approx 0.6072529350088812561694 </math><ref>[http://perso.ens-lyon.fr/jean-michel.muller/SecondEdition.html J.-M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Edition (Birkhäuser, Boston, 2006), p. 134.]</ref>

Després d'un nombre suficient d'iteracions, l'angle del vector estarà prop a l'angle desitjat, <math>\beta</math>. Per a la majoria dels usos ordinaris, 40 iteracions ('' n'' = 40) és suficient per obtenir el resultat correcte amb deu xifres de presició decimal.

L'única tasca que queda per fer és determinar si la rotació ha de ser cap a la dreta o cap a l'esquerra en cada iteració (l'elecció del valor de <math>\sigma</math>). Això es fa mitjançant la resta de l'angle girat en cada iteracio respecte a l'angle desitjat, i després s'ha de comprovar si <math>\beta_{n+1}</math> és positiu i s'ha de girar cap a la dreta o si és negatiu, s'ha de girar cap a l'esquerra per tal d'acostar-se successivament a l'angle desitjat <math>\beta</math>.

: <math> \beta_{i} = \beta_{i-1} - \sigma_i \gamma_i. \quad \gamma_i = \arctan 2^{-i},</math>

Els valors de <math>\gamma_n</math> també s'ha de calcular i emmagatzemar prèviament. No obstant això, per ángles petits, <math> \arctan(\gamma_n) = \gamma_n</math>, en representació de punt fix, la reducció de mida de la taula.

Com es pot observar en la il·lustració anterior, el sinus de l'angle <math>\beta</math> és la coordenada ''y'' del vector final <math>v_n</math>, mentre que la coordenada ''x'' és el cosinus.

== Exemple de programació ==
El següent codi és una implementació de CORDIC en [[MATLAB]]/[[GNU Octave]] que no depèn de les funcions transcendents, excepte en el precàlcul de les taules. Si el nombre d'iteracions ''N'' està predeterminat, llavors la segona taula pot ser reemplaçada per una sola constant.

<syntaxhighlight lang="MATLAB">
function v = cordic(beta,n)
% Aquesta funció calcula v = [cos(beta), sin(beta)] (beta en radians)
% usant n iteracions. Incrementant n s'augmenta la precisió del resultat.

if beta < -pi/2 || beta > pi/2
 if beta < 0
 v = cordic(beta + pi, n);
 else
 v = cordic(beta - pi, n);
 end
 v = -v; % Canviem el signe per a calcular valors en el segon o tercer quadrant
 return
end

% Inicialització de les taules de constants usades per CORDIC
% 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 ];
% Taula de productes [1, 2^-2j]:
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)));

% Inicialització de les variables del Bucle:
v = [1;0]; % comença en la posció (1,0)
poweroftwo = 1;
angle = angles(1);

% Iteracions
for j = 0:n-1;
 if beta < 0
 sigma = -1;
 else
 sigma = 1;
 end
 factor = sigma * poweroftwo;
 R = [1, -factor; factor, 1];
 v = R * v; % Multiplicacioó de matrius de 2x2
 beta = beta - sigma * angle; % actualització de l'angle que queda pendent de rotar
 poweroftwo = poweroftwo / 2;
 % actualitzacio de l'angle a partir de la taula, o eventualment dividint per dos
 if j+2 > length(angles)
 angle = angle / 2;
 else
 angle = angles(j+2);
 end
end

% Adjust de les dimensions del vector perquè sigui [cos(beta), sin(beta)]:
v = v * Kn;
return
</syntaxhighlight>

== Implementació maquinari ==
El nombre de [[porta lògica | portes lògiques]] per a l'execució d'un CORDIC és aproximadament comparable a la quantitat requerida per a un multiplicador com ambdós requereixen combinacions de canvis i addicions. L'elecció d'un multiplicador aplicació basada en CORDIC o basats dependrà del context. La multiplicació de dos [[Nombre complex | nombres complexos]] representats pels seus components reals i imaginaris (coordenades rectangulars), per exemple, requereix 4 multiplicacions, però podria ser realitzat per una operació única CORDIC en nombres complexos representats per les seves coordenades polars, especialment si la magnitud dels nombres no és rellevant (multiplicar un vector complex amb un vector en el cercle unitat en realitat equival a una rotació). CORDICs sovint s'utilitzen en els circuits de telecomunicacions, com ara un [[Digital down converter]].

== Algorismes relacionats ==
CORDIC és part de la classe de "shift-and-add" algoritmes, com són els algoritmes de logaritmes i exponencials derivades del treball Henry Briggs. Un altre algoritme de desplaçament i afegida que pot ser utilitzat per al càlcul de moltes funcions elementals és l'[[algorisme BKM]], que és una generalització dels algoritmes de logaritmes i exponencials per al pla complex. Per exemple, BKM es pot utilitzar per calcular el si i el cosinus d'un angle real de <math>x</math> (en radiants) calculant l'exponencial de <math>0+ix,</math> que és <math>\cos x + i \sin x.</math>.L'algorisme BKM és lleugerament més complex que CORDIC, però té l'avantatge que no necessita un factor d'escala (K).

== Referències ==
{{Referències}}

== Enllaços externs ==
* {{ref-web|url=http://cordic-bibliography.blogspot.de/p/what-is-cordic.html|consulta=19 novembre 2013|títol=CORDIC Bibliography|llengua=anglès}}
* {{ref-web|url=http://www.andraka.com/cordic.htm|consulta=19 novembre 2013|títol=The Cordic Algorithm|editor=Andraka Consulting Group|llengua=anglès|arxiuurl=https://web.archive.org/web/20070930090832/http://www.andraka.com/cordic.htm|arxiudata=30 de setembre 2007}}
* {{ref-web|url=http://code.activestate.com/recipes/576792|consulta=19 novembre 2013|títol=Polar-to-rectangular conversions using CORDIC (Python recipe)|editor=http://code.activestate.com|llengua=anglès|arxiuurl=https://web.archive.org/web/20170317235046/http://code.activestate.com/recipes/576792/|arxiudata=17 de març 2017}}
* {{ref-web|url=http://www.dcs.gla.ac.uk/~jhw/cordic/|consulta=19 novembre 2013|títol=Simple C source for CORDIC|llengua=anglès}}
* {{ref-web|url=http://luminouslogic.com/dsp-simple-phase-estimation-approximation-cordic-matlab.htm|consulta=19 novembre 2013|títol=Simple Phase Estimator|editor=http://luminouslogic.com|llengua=anglès}}

{{Trigonometria}}
{{Autoritat}}

[[Categoria:Algorismes]]
[[Categoria:Anàlisi numèrica]]
[[Categoria:Trigonometria]]