# 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. 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.
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 $\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$^{i−1}$)) para i = 1, 2, 3, ….
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$
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

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.

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

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}.$
Algumas das aplicações proeminentes precoce de CORDIC estavam nos computadores de navegação da Convair (CORDIC I a CORDIC III), as calculadoras HP-9100 e HP-35, co-processador Intel 8087 até Intel 80486 e Motorola 68881.
Decimal CORDIC foi sugerida pela primeira vez por Hermann Schmid e Anthony Bogacki.