CORDIC

CORDIC, acrônimo de COordinate Rotation DIgital Computer (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ções hiperbólicas e trigonométricas. É comum ser usado quando nenhum hardware multiplicador está disponível (por exemplo, microcontroladores e FPGAs) nas operações que exigem adição, subtração, bitshift e 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 analógico no computador de navegação do bombardeiro B-58^[1]. 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ções hiperbólicas e exponenciais, logaritmos, multiplicações, divisões, e raízes quadradas^[2].

Originalmente, o CORDIC foi implementado usando o sistema binário. Nos anos 1970, o CORDIC decimal tornou-se amplamente utilizado em calculadoras de bolso, mais para 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ções hiperbólicas e trigonométricas poderem compartilhar a maior parte do código.

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 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 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 ${\displaystyle \beta }$, 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 ${\displaystyle v_{0}}$:

${\displaystyle v_{0}={\begin{pmatrix}1\\0\end{pmatrix}}}$

Na primeira iteração, esse vetor teria rodado 45° sentido anti-horário para ter o vetor ${\displaystyle v_{1}}$. 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 é arctan(1/(2ⁱ⁻¹)) para i = 1, 2, 3, ….

Mais formalmente, todas as iterações calculam a rotação, que é realizada pela multiplicação do vetor ${\displaystyle v_{i-1}}$ com a matriz de rotação ${\displaystyle R_{i}}$:

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

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

${\displaystyle R_{i}=\left({\begin{array}{rr}\cos \gamma _{i}&-\sin \gamma _{i}\\\sin \gamma _{i}&\cos \gamma _{i}\end{array}}\right)}$

Usando as duas seguintes identidades trigonométricas:

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

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

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

A expressão do vetor rodado ${\displaystyle v_{i}=R_{i}v_{i-1}}$ torna-se assim:

${\displaystyle 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}}}$

Onde ${\displaystyle x_{i-1}}$ e ${\displaystyle y_{i-1}}$ são os componentes de ${\displaystyle v_{i-1}}$. Restringindo os ângulos ${\displaystyle \gamma _{i}}$ assim que ${\displaystyle \tan \gamma _{i}}$ toma os valores ${\displaystyle \pm 2^{-i}}$ 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 bit shift. A expressão vem a ser:

${\displaystyle 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}}}$

onde

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

e ${\displaystyle \sigma _{i}}$ pode ter os valores −1 ou 1 e é usado para determinar a direção da rotação: se o ângulo ${\displaystyle \beta _{i}}$ é positivo quando ${\displaystyle \sigma _{i}}$ é 1, se caso contrário, é  −1.

Podemos ignorar ${\displaystyle K_{i}}$ no processo iterativo e depois aplicá-lo depois pelo fator de escala:

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

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 ${\displaystyle v_{0}}$ e, disso salvando a multiplicação. Adicionadamente, ele pode ser notado deste modo:

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

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 ${\displaystyle \beta }$. Para muitos propósitos comuns, 40 iterações (n = 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 ${\displaystyle \sigma }$). Isso é feito acompanhando quantos giramos a cada iteração e subtraindo-se que a partir do ângulo desejado, e então verificar se ${\displaystyle \beta _{n+1}}$ é 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 ${\displaystyle \beta }$.

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

Os valores de ${\displaystyle \gamma _{n}}$ maiores também são pré-computados e armazenados. Mas para ângulos pequenos, ${\displaystyle \arctan(\gamma _{n})=\gamma _{n}}$ na representação do ponto fixo, reduzindo o tamanho da tabela.

Como pode ser visto na ilustração cima, o seno do ângulo ${\displaystyle \beta }$ é a coordenada y do vetor final ${\displaystyle v_{n}}$, 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 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.

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

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 "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 ${\displaystyle realx}$ (em radianos) pelo cálculo do exponencial ${\displaystyle 0+ix,}$ que é ${\displaystyle \cos x+i\sin x.}$ 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 CRC - Manual de Química e Física:

${\displaystyle {\begin{aligned}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{aligned}}}$

com ${\displaystyle K_{n}={\sqrt {1+2^{-2n}}},\tan(\phi )=2^{-n}.}$ ^[1]

Algumas das aplicações proeminentes precoce de CORDIC estavam nos computadores de navegação da Convair (CORDIC I a CORDIC III),^[1] as calculadoras HP-9100 e HP-35,^[4] co-processador Intel 8087 até Intel 80486 e Motorola 68881.^[5]

Decimal CORDIC foi sugerida pela primeira vez por Hermann Schmid e Anthony Bogacki.^[6]

Referências

• 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
• John S. Walther, A Unified Algorithm for Elementary Functions, Proc. of Spring Joint Computer Conference, pp379–385, May 1971
• J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes, IBM Journal, April 1962
• 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
• V.D.Baykov,V.B.Smolov, Hardware implementation of elementary functions in computers, Leningrad State University, 1975, 96p.*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.
• 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)
• Andraka, Ray, A survey of CORDIC algorithms for FPGA based computers
• Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
• CORDIC Bibliography Site
• The secret of the algorithms, Jacques Laporte, Paris 1981
• Digit by digit methods, Jacques Laporte, Paris 2006
• Ayan Banerjee, FPGA realization of a CORDIC based FFT processor for biomedical signal processing, Kharagpur, 2001
• CORDIC Architectures: A Survey, B. Lakshmi and A. S. Dhar, January 2010

Ligações externas

• ICMC-USP
• El algoritmo CORDIC
• Another USENET discussion
• BASIC Stamp, CORDIC math implementation
• 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.
• CORDIC implementation in verilog.
• CORDIC information
• CORDIC Vectoring with Arbitrary Target Value
• PicBasic Pro, Pic18 CORDIC math implementation
• Python CORDIC implementation
• Simple C code for fixed-point CORDIC
• The CORDIC Algorithm
• Tutorial and MATLAB Implementation - Using CORDIC to Estimate Phase of a Complex Number
• USENET discussion