CORDIC

	Trigonometria
	História ; Funções; Funções inversas ; Aprofundamento ;
	Referência
	Lista de identidades ; CORDIC
	Teoria euclidiana
	Lei dos senos ; Lei dos cossenos ; Lei das tangentes ; Teorema de Pitágoras
	Cálculo
	Integração trigonométrica ; Substituição trigonométrica ; Integrais de funções ; Diferenciação trigonométrica ; ;

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 editar

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.

Vetorização hiperbólica

Vetorização linear

Vetorização circular

Rotação hiperbólica

Rotação linear

Rotação circular

Aplicações editar

Hardware editar

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 editar

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 editar

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

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 $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, ….

Ilustração do algoritmo CORDIC em progresso.

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

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

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

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:

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

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 $v_{i}=R_{i}v_{i-1}$ torna-se assim:

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 $x_{i-1}$ e $y_{i-1}$ são os componentes de $v_{i-1}$ . Restringindo os ângulos $\gamma _{i}$ assim que $\tan \gamma _{i}$ toma os valores $\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:

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

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

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

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

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

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 $\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 $\sigma$ ). Isso é feito acompanhando quantos giramos a cada iteração e subtraindo-se que a partir do ângulo desejado, e então verificar se $\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 $\beta$ .

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

Os valores de $\gamma _{n}$ maiores também são pré-computados e armazenados. Mas para ângulos pequenos, $\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 $\beta$ é a coordenada y do vetor final $v_{n}$ , enquanto a coordenada x é o valor do cosseno.

Implementação no software editar

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 editar

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 editar

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 $realx$ (em radianos) pelo cálculo do exponencial $0+ix,$ que é $\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 editar

Volder foi inspirado pela seguinte fórmula na edição 1946 do CRC - Manual de Química e Física:

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

↑ ^a ^b ^c J. E. Volder, "The Birth of CORDIC", J. VLSI Signal Processing 25, 101 (2000).
↑ J. S. Walther, "The Story of Unified CORDIC", J. VLSI Signal Processing 25, 107 (2000).
↑ J.-M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Edition (Birkhäuser, Boston, 2006), p. 134.
↑ D. Cochran, "Algorithms and Accuracy in the HP 35", Hewlett Packard J. 23, 10 (1972).
↑ R. Nave, "Implementation of Transcendental Functions on a Numerics Processor", Microprocessing and Microprogramming 11, 221 (1983).
↑ H. Schmid and A. Bogacki, "Use Decimal CORDIC for Generation of Many Transcendental Functions", EDN Magazine, February 20, 1973, p. 64.

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 editar

[volder00-1] J. E. Volder, "The Birth of CORDIC", J. VLSI Signal Processing 25, 101 (2000).

[2] J. S. Walther, "The Story of Unified CORDIC", J. VLSI Signal Processing 25, 107 (2000).

[3] J.-M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Edition (Birkhäuser, Boston, 2006), p. 134.

[4] D. Cochran, "Algorithms and Accuracy in the HP 35", Hewlett Packard J. 23, 10 (1972).

[5] R. Nave, "Implementation of Transcendental Functions on a Numerics Processor", Microprocessing and Microprogramming 11, 221 (1983).

[6] H. Schmid and A. Bogacki, "Use Decimal CORDIC for Generation of Many Transcendental Functions", EDN Magazine, February 20, 1973, p. 64.

[1]

[2]

[3]

[4]

[5]

[6]