CORDIC

CORDIC (COordinate Rotation DIgital Computer), o mètode de dígit per dígit, o algorisme de Volder, és un simple i eficient algorisme per calcular funcions hiperbòliques i trigonomètriques. Típicament és usat quan no hi ha disponible un maquinari per a multiplicacions (per exemple, en microcontroladors i FPGAs simples) perquè les úniques operacions que requereix són suma, resta, desplaçament de bits (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 analògic a l'ordinador de navegació del bombarder B-58. John Stephen Walther, a Hewlett-Packard, va generalitzar més l'algoritme, permetent calcular funcions hiperbòliques, exponencials, logaritmes, multiplicació, divisió, i l'arrel quadrada.

Originalment, CORDIC va ser implementat usant el sistema de numeració binari. En els anys 1970, la implementació en el sistema de numeració decimal del CORDIC va arribar a ser usat extensament en les calculadores de butxaca, la majoria de les quals operava en 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 portes lògiques del 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 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é 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 FPGAs.

Programari

Els sistemes mès àntics que utilitzen CPUs 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, restar, multiplicar, dividir, sinus, cosinus, arrel quadrada, 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 $\beta$, 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 $v_{0}$:

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

A la primera iteració, aquest vector gira 45° cap a l'esquerra per obtenir el vector $v_{1}$. 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ⁱ⁻¹)) per i = 1, 2, 3, ….

Il·lustració de l'algorisme CORDIC en curs.

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

$v_{i}=R_{i}v_{i-1}\$

La matriu de rotació R ve donada per:

$R_{i}={\begin{bmatrix}\cos \gamma _{i}&-\sin \gamma _{i}\\\sin \gamma _{i}&\cos \gamma _{i}\end{bmatrix}}$

Usant les següents identitats trigonomètriques

${\begin{aligned}\cos \alpha &=&{1 \over {\sqrt {1+\tan ^{2}\alpha }}}\\\sin \alpha &=&{{\tan \alpha } \over {\sqrt {1+\tan ^{2}\alpha }}}\end{aligned}}$

la matriu de rotació es converteix en:

$R_{i}={1 \over {\sqrt {1+\tan ^{2}\gamma _{i}}}}{\begin{bmatrix}1&-\tan \gamma _{i}\\\tan \gamma _{i}&1\end{bmatrix}}$

Els vectors de rotació $v_{i}=R_{i}v_{i-1}$ es converteixen en:

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

on $x_{i-1}$ i $y_{i-1}$ són els components de $v_{i-1}$. La restricció els angle que pot prendre $\gamma _{i}$ de manera que $\tan \gamma _{i}$ pren els valors $\pm 2^{-i}$ 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é:

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

on

$K_{i}={1 \over {\sqrt {1+2^{-2i}}}}$

i $\sigma _{i}$ pot tenir els valors de -1 o 1, i s'utilitza per determinar la direcció de la rotació: si l'angle de $\beta _{i}$ és positiu, llavors el $\sigma _{i}$ és 1, en cas contrari, és -1.

En el procés iteratiu podem fer cas omís de $K_{i}$ i aplicar-lo després, ja que tan sols és un factor d'escala:

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

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 $v_{0}$ i per tant l'estalvi d'una multiplicació. Addicionalment es pot observar que

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

Després d'un nombre suficient d'iteracions, l'angle del vector estarà prop a l'angle desitjat, $\beta$. 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 $\sigma$). 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 $\beta _{n+1}$ é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 $\beta$.

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

Els valors de $\gamma _{n}$ també s'ha de calcular i emmagatzemar prèviament. No obstant això, per ángles petits, $\arctan(\gamma _{n})=\gamma _{n}$, 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 $\beta$ és la coordenada y del vector final $v_{n}$, 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.

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

Implementació maquinari

El nombre de 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 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 $x$ (en radiants) calculant l'exponencial de $0+ix,$ que és $\cos x+i\sin x.$.L'algorisme BKM és lleugerament més complex que CORDIC, però té l'avantatge que no necessita un factor d'escala (K).

Enllaços externs

• «CORDIC Bibliography» (en anglès). [Consulta: 19 novembre 2013].
• «The Cordic Algorithm» (en anglès). Andraka Consulting Group. Arxivat de l'original el 30 de setembre 2007. [Consulta: 19 novembre 2013].
• «Polar-to-rectangular conversions using CORDIC (Python recipe)» (en anglès). http://code.activestate.com.+[Consulta: 19 novembre 2013].
• «Simple C source for CORDIC» (en anglès). [Consulta: 19 novembre 2013].
• «Simple Phase Estimator» (en anglès). http://luminouslogic.com.+[Consulta: 19 novembre 2013].