Mostrar código-fonte de CORDIC

{{Trigonometria}}
'''CORDIC''', acrônimo de '''''CO'''ordinate '''R'''otation '''DI'''gital '''C'''omputer'' (computador digital para rotação de coordenadas), conhecido também como "método dígito-por-dígito" ou "algoritmo de Volder", é um algoritmo simples e eficiente para calcular [[função hiperbólica|funções hiperbólicas]] e [[função trigonométrica|trigonométricas]]. É comum ser usado quando nenhum ''hardware'' multiplicador está disponível (por exemplo, [[microcontrolador]]es e [[FPGA]]s) nas operações que exigem adição, subtração, ''[[lógica binária#Shift|bitshift]]'' e [[LUT|LookUp Table]].

==Origens==

O algoritmo ''CORDIC'' moderno foi primeiramente descrito em [[1959]] pelo Jack E. Volder. Foi desenvolvido no departamento aeroeletrônico de [[Convair]] para substituir o ''[[resolver]]'' [[circuito analógico|analógico]] no computador de navegação do [[Convair B-58 Hustler|bombardeiro 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>. 
Embora o ''CORDIC'' seja similar às técnicas matemáticas publicadas pelo [[Henry Briggs]] em torno de [[1624]], foi otimizado pela baixa complexidade finita do [[CPU]].

John Stephen Walther na [[Hewlett-Packard]] generalizou mais o algoritmo, permitindo ele calcular [[função hiperbólica|funções hiperbólicas]] e [[função exponencial|exponenciais]], [[logaritmo]]s, [[multiplicação|multiplicações]], [[divisão|divisões]], e [[Radiciação|raízes quadradas]]<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>.

Originalmente, o ''CORDIC'' foi implementado usando o [[sistema binário]]. Nos [[década de 1970|anos 1970]], o CORDIC decimal tornou-se amplamente utilizado em calculadoras de bolso, mais para [[codificação binária decimal|codificar binário para decimal (''B-C-D'')]].

''CORDIC'' é particularmente adequado para calculadoras portáteis, na aplicação o qual custo (por exemplo, a entrada do ''chip'' tem que ser minimizado) é muito mais importante que é rápido. Também a [[sub-rotina]] ''CORDIC'' para [[função hiperbólica|funções hiperbólicas]] e [[função trigonométrica|trigonométricas]] poderem compartilhar a maior parte do código.

[[Imagem:CORDIC_Block,_Hyperbolic,_Vectoring.svg|thumb|Vetorização hiperbólica]][[Imagem:CORDIC Block, Linear, Vectoring.svg|thumb|Vetorização linear]][[Imagem:CORDIC Block, Circular, Vectoring.svg|thumb|Vetorização circular]][[Imagem:CORDIC Block, Hyperbolic, Rotation.svg|thumb|Rotação hiperbólica]][[Imagem:CORDIC Block, Linear, Rotation.svg|thumb|Rotação linear]][[Imagem:CORDIC Block, Circular, Rotation.svg|thumb|Rotação circular]]
== Aplicações ==

===[[Hardware]]===
CORDIC é geralmente mais rápido que outros próximos quando um hardware multiplicador está indisponível (por exemplo, no sistema baseado no [[microcontrolador]]), ou quando o número de entradas exigem implementar as funções que ele suporta deve ser minimizadas (por exemplo, no [[FPGA]]).

Em outro lado, quando um hardware multiplicador é disponível (por exemplo, no [[DSP]] [[microprocessador]]), métodos e [[série de potências]] de [[LUT|LookUP Table]] são geralmente mais rápido que o ''CORDIC''. Nos anos recentes, o algoritmo ''CORDIC'' é usado extensivamente em várias aplicações biomédicas, especialmente nas implementações do [[FPGA]].

===[[Software]]===
Muitos sistemas antigos com um só [[CPU]], têm implementado o ''CORDIC'' em extensões diferentes como parte de suas bibliotecas [[IEEE]] de ponto flutuante. Como a maioria dos modernos processadores de uso geral tem registradores de ponto flutuante com operações comuns, tais como [[adição]], [[subtração]], [[multiplicação]], [[divisão]], [[seno]], [[cosseno]], [[radiciação]], [[logaritmo|logaritmo comum]], [[logaritmo natural]], a necessidade de implementar o CORDIC nele é inexistente. Somente o [[microcontrolador]] ou especial segurança e tempo de aplicações de software de restrição terá de considerar o uso de ''CORDIC''.

== Modo de operação ==
''CORDIC'' pode ser usado para calcular um número de diferentes funções. Esta explicação mostra como usar ''CORDIC'' no modo rotação para calcular seno e cosseno de um ângulo, e adquirir o ângulo desejado é dado em [[radianos]] e representado em um formato de [[ponto fixo]]. Para determinar o seno ou cosseno para um ângulo <math> \beta </math>, a coordenada ''y'' ou ''x'' de um ponto no [[círculo unitário]] correspondente ao ângulo desejado. Usando o CORDIC, devemos começar com o vetor <math> v_0 </math>:

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

Na primeira iteração, esse vetor teria rodado 45° [[sentido anti-horário]] para ter o vetor <math> v_1 </math>. Sucessivas iterações rodarão o vetor em uma ou outra direção pelo tamanho dos passos decrescentes, até o ângulo desejado tenha sido alcançado. O tamanho da etapa ''i'' é [[Funções trigonométricas inversas|arctan]](1/(2<sup>''i''&minus;1</sup>)) para ''i''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;….

[[Imagem:CORDIC-illustration.svg|thumb|300px| Ilustração do algoritmo CORDIC em progresso.]]

Mais formalmente, todas as iterações calculam a rotação, que é realizada pela multiplicação do vetor <math>v_{i-1}</math> com a [[matriz de rotação]] <math>R_{i}</math>:

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

A matriz de rotação ''R'' é dada pelo:

: <math> R_{i} = \left( \begin{array}{rr} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{array} \right) </math>

Usando as duas seguintes [[identidade trigonométrica|identidades trigonométricas]]:

: <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>

a matriz de rotação vem a partir desta: 

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

A expressão do vetor rodado <math>v_i = R_i v_{i-1}</math> torna-se assim:

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

Onde <math>x_{i-1}</math> e <math>y_{i-1}</math> são os componentes de <math>v_{i-1}</math>. Restringindo os ângulos <math>\gamma_{i}</math> assim que <math> \tan \gamma_{i} </math> toma os valores <math> \pm 2^{-i} </math> a multiplicação com o tangente pode ser substituído por uma divisão por uma potência de dois, que é feito de forma eficiente em hardware de computador digital usando um ''[[lógica binária#Shift|bit shift]]''. A expressão vem a ser: 

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

onde

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

e <math>\sigma_i</math> pode ter os valores &minus;1 ou 1 e é usado para determinar a direção da rotação: se o ângulo <math>\beta_i</math> é positivo quando <math>\sigma_i</math> é 1, se caso contrário, é &nbsp;&minus;1.

Podemos ignorar <math> K_i </math> no processo iterativo e depois aplicá-lo depois pelo fator de escala:

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

que é calculado com antecedência e armazenado em uma tabela, ou como uma constante singular se o número de iterações for fixado. Essa correção pode see também feita antecipadamente pela escala <math> v_0 </math> e, disso salvando a multiplicação. Adicionadamente, ele pode ser notado deste modo: 

: <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>

para permitir a redução da complexidade do algoritmo.
Depois de um número suficiente de iterações, o ângulo do vetor será fechado para o ângulo desejado <math>\beta</math>. Para muitos propósitos comuns, 40 iterações (''n''&nbsp;=&nbsp;40) é suficiente para obter o resultado certo para o 10º lugar decimal.

A única tarefa que resta é determinar se a rotação deve ser no [[sentido horário]] ou anti-horário a cada iteração (escolhendo o valor da <math>\sigma</math>). Isso é feito acompanhando quantos giramos a cada iteração e subtraindo-se que a partir do ângulo desejado, e então verificar se <math>\beta_{n+1}</math> é positivo e temos de girar no [[sentido horário]] ou se é negativo, devemos girar em [[sentido anti-horário]] para chegar mais perto do ângulo desejado <math>\beta</math>.

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

Os valores de <math>\gamma_n</math> maiores também são pré-computados e armazenados. Mas para ângulos pequenos, <math> \arctan(\gamma_n) = \gamma_n</math> na representação do [[ponto fixo]], reduzindo o tamanho da tabela. 

Como pode ser visto na ilustração cima, o seno do ângulo <math>\beta</math> é a coordenada ''y'' do vetor final <math>v_n</math>, enquanto a coordenada ''x'' é o valor do cosseno.

== Implementação no ''software'' ==
A seguinte é uma implementação de CORDIC da [[MATLAB]]/[[GNU Octave]] que não dependem de quaisquer funções transcendentais, exceto na pré-computação de tabelas. Se o número de iterações ''n'' é determinada, então a segunda tabela podem ser substituídas por uma única constante. A [[produto de matrizes|multiplicação matricial]] de dois-em-dois representa um par de mudanças simples e completas. Com aritmética padrão MATLAB precisa-dupla e "formato longo" de impressão, o aumento de resultados em precisão para ''n'' até cerca de 48.

<syntaxhighlight lang="MATLAB">
function v = cordic(beta,n)
% Essa função computa v = [cos(beta), sin(beta)] (beta em radianos)
% usando n (enésimas) iterações. Crescimento n aumentará a precisão.

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

% Inicialização de tabelas de constantes usado pelo CORDIC
% precisa da tabela de arco-tangentes de potência negativa de dois, em radianos:
% ângulos = 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 ];
% e uma tabela de produtos de graus recíprocos de vetores [1, 2^-j]:
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)));

% Inicializa o loop de variáveis:
v = [1;0]; % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);

% Iterações
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; % multiplicação matricial de dois-em-dois
    beta = beta - sigma * angle; % atualização de outro ângulo
    poweroftwo = poweroftwo / 2;
    % atualização do ângulo da tabela, ou eventualmente apenas pela divisão por dois
    if j+2 > length(angles)
        angle = angle / 2;
    else
        angle = angles(j+2);
    end
end

% Ajuste o comprimento do vetor de saída sendo [cos(beta), sin(beta)]:
v = v * Kn;
return
</syntaxhighlight>

== Implementação no ''hardware'' ==

O uso primário dos algoritmos CORDIC na implementação no ''hardware'' evita a demora dos multiplicadores complexos. A computação da fase de número complexo pode ser facilmente implementado em uma linguagem de descrição de hardware usando apenas os circuitos somador e shifter ignorando o volumoso multiplicadores de números complexos. Técnicas de fabricação têm melhorado, e os números complexos podem ser manipulados diretamente, sem custos demasiado elevados em um tempo, o consumo de energia, portanto, o uso de técnicas CORDIC não é tão crítica em muitas aplicações, como já foram.

== Algoritmos relatados ==

CORDIC faz parte da classe dos algoritmos "''[[:en:multiplication algorithm#Shift and add|shift-and-add]]''", assim como os algoritmos logarítmico e exponencial derivada do trabalho de [[Henry Briggs]]. Outro algoritmo ''shift-and-add'' que pode ser usado para muitas funções de computação básica é o [[algoritmo BKM]], que é uma generalização dos algoritmos logarítmico e exponencial para o plano complexo. Por exemplo, BKM pode ser usado para calcular o seno e cosseno de um ângulo <math> real x </math> (em radianos) pelo cálculo do exponencial <math>0+ix,</math> que é <math>\cos x + i \sin x.</math>  O algoritmo BKM é ligeiramente mais complexa do que CORDIC, mas tem a vantagem de que ele não precisa de um fator de escala (K).

==História==

Volder foi inspirado pela seguinte fórmula na edição [[1946]] do [[:en:CRC Handbook of Chemistry and Physics|CRC - Manual de Química e Física]]:

:<math>\begin{align}
K_n R \sin(\theta\pm\phi) &= R \sin(\theta) \pm 2^{-n} R \cos(\theta)\\
K_n R \cos(\theta\pm\phi) &= R \cos(\theta) \mp 2^{-n} R \sin(\theta)
\end{align}</math>
com <math>K_n = \sqrt{1+2^{-2n}}, \tan(\phi) = 2^{-n}.</math> <ref name="volder00"/>

Algumas das aplicações proeminentes precoce de CORDIC estavam nos computadores de navegação da Convair (CORDIC I a CORDIC III),<ref name="volder00"/> as calculadoras [[HP-9100]] e [[HP-35]],<ref>D. Cochran, "Algorithms and Accuracy in the HP 35", Hewlett Packard J. '''23''', 10 (1972).</ref> co-processador [[Intel 8087]] até [[Intel 80486]] e [[Motorola 68881]].<ref>R. Nave, "Implementation of Transcendental Functions on a Numerics Processor", Microprocessing and Microprogramming '''11''', 221 (1983).</ref>

Decimal CORDIC foi sugerida pela primeira vez por Hermann Schmid e Anthony Bogacki.<ref>H. Schmid and A. Bogacki, "Use Decimal CORDIC for Generation of Many Transcendental Functions", EDN Magazine, February 20, 1973, p. 64.</ref>

{{referências}}

*[http://www.jacques-laporte.org/Volder_CORDIC.pdf Jack E. Volder, ''The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers'', pp330-334, September 1959]
*Daggett, D. H., ''Decimal-Binary conversions in CORDIC'', IRE Transactions on Electronic Computers, Vol. EC-8 #5, pp335–339, IRE, September 1959
*[http://www.jacques-laporte.org/Welther-Unified%20Algorithm.pdf John S. Walther, ''A Unified Algorithm for Elementary Functions'', Proc. of Spring Joint Computer Conference, pp379–385, May 1971]
*[http://www.jacques-laporte.org/Meggitt_62.pdf J. E. Meggitt, ''Pseudo Division and Pseudo Multiplication Processes'', IBM Journal, April 1962]
*[http://baykov.de/cordic1972.htm Vladimir Baykov, ''Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique'', PhD thesis, Leningrad State Univ. of Electrical Eng., 1972]
*Schmid, Hermann, ''Decimal computation.'' New York, Wiley, 1974
*[http://baykov.de/cordic1975.htm V.D.Baykov,V.B.Smolov, ''Hardware implementation of elementary functions in computers'', Leningrad State University, 1975, 96p.]*[http://www.umup.narod.ru/1115.zip Full Text]
*Senzig, Don, ''Calculator Algorithms'', IEEE Compcon Reader Digest, IEEE Catalog No. 75 CH 0920-9C, pp139–141, IEEE, 1975.
*V.D.Baykov,S.A.Seljutin, ''Elementary functions evaluation in microcalculators'', Moscow, Radio & svjaz,1982,64p.''
*[http://baykov.de/cordic1985.htm Vladimir D.Baykov, Vladimir B.Smolov, Special-purpose processors: iterative algorithms and structures, Moscow, 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)
*[http://www.andraka.com/files/crdcsrvy.pdf Andraka, Ray, ''A survey of CORDIC algorithms for FPGA based computers'']
*Henry Briggs, ''Arithmetica Logarithmica.'' London, 1624, folio
*[http://web.archive.org/web/20001017173921/devil.ece.utexas.edu/ ''CORDIC Bibliography Site'']
*[http://www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm ''The secret of the algorithms''], Jacques Laporte, Paris 1981
*[http://www.jacques-laporte.org/digit_by_digit.htm ''Digit by digit methods''], Jacques Laporte, Paris 2006
*Ayan Banerjee, [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0X-4313PR1-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=c85888a82db1f3b515b4a8d2a529624b FPGA realization of a CORDIC based FFT processor for biomedical signal processing], Kharagpur, 2001
*[http://www.hindawi.com/journals/vlsi/2010/794891.html ''CORDIC Architectures: A Survey''], B. Lakshmi and A. S. Dhar,  January 2010

== Ligações externas ==
*[http://www.icmc.usp.br/~legal/arquivos/cordic.pdf ICMC-USP]
*[http://www.jcea.es/artic/cordic.htm El algoritmo CORDIC]
*[http://www.math.ucl.ac.be/~magnus/num1a/cordic.txt Another USENET discussion]
*[http://www.emesystems.com/BS2mathC.htm BASIC Stamp, CORDIC math implementation]
*[http://www.jacques-laporte.org/Trigonometry.htm CORDIC as implemented in the ROM of the HP-35 - Jacques Laporte (step by step analysis, simulator running the real ROM with breakpoints and trace facility.]
*[http://srohit.googlepages.com CORDIC implementation in verilog.]
*[http://www.math.niu.edu/~rusin/known-math/94/cordic CORDIC information]
*[http://portal.acm.org/citation.cfm?id=626526.627179 CORDIC Vectoring with Arbitrary Target Value]
*[http://www.picbasic.co.uk/forum/showthread.php?p=70269#post70269 PicBasic Pro, Pic18 CORDIC math implementation]
*[http://code.activestate.com/recipes/576792 Python CORDIC implementation]
*[http://www.dcs.gla.ac.uk/~jhw/cordic/ Simple C code for fixed-point CORDIC]
*[http://www.andraka.com/cordic.htm The CORDIC Algorithm]
*[http://luminouslogic.com/dsp-simple-phase-estimation-approximation-cordic-matlab.htm Tutorial and MATLAB Implementation - Using CORDIC to Estimate Phase of a Complex Number]
*[http://www.eecg.toronto.edu/~bach/HOME/CORDIC/net.refs USENET discussion]

{{DEFAULTSORT:Cordic}}
[[Categoria:Análise numérica]]
[[Categoria:Matemática computacional]]
[[Categoria:Trigonometria]]