CORDIC

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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 | editar código-fonte]

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 | editar código-fonte]

Hardware[editar | editar código-fonte]

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 | editar código-fonte]

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, radiaçã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 | editar código-fonte]

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

Na primeira iteração, esse vetor teria rodado 45° sentido anti-horário para ter o vetor . 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/(2i−1)) 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 com a matriz de rotação :

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

Usando as duas seguintes identidades trigonométricas:

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

A expressão do vetor rodado torna-se assim:

Onde e são os componentes de . Restringindo os ângulos assim que toma os valores 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:

onde

e pode ter os valores −1 ou 1 e é usado para determinar a direção da rotação: se o ângulo é positivo quando é 1, se caso contrário, é  −1.

Podemos ignorar no processo iterativo e depois aplicá-lo depois pelo fator de escala:

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

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

Os valores de maiores também são pré-computados e armazenados. Mas para ângulos pequenos, na representação do ponto fixo, reduzindo o tamanho da tabela.

Como pode ser visto na ilustração cima, o seno do ângulo é a coordenada y do vetor final , enquanto a coordenada x é o valor do cosseno.

Implementação no software[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 (em radianos) pelo cálculo do exponencial que é 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 | editar código-fonte]

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

com [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

  1. a b c 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.

Ligações externas[editar | editar código-fonte]