1 Comentário

CORDIC - Introdução

CORDIC
Este post faz parte da série CORDIC - Um processador trigonométrico de ponto fixo. Leia também os outros posts da série:

Olá, caro leitor, como vai? No artigo de hoje vamos iniciar uma série relacionada a um algoritmo bem popular para processamento trignométrico (e funções derivadas), trata - se do CORDIC. Veremos um pouco de sua implementação, o porquê de seu uso e popularidade, além disso implementaremos três das funções mais conhecidas derivadas de um processador CORDIC: Seno, cosseno e arctangente. Abordaremos uma implementação em software para um processador de 8 bits (confirmando que o CORDIC é perfeito em microcontroladores de pouquíssimos recursos), e uma implementação em hardware (sim, vamos fazer um core CORDIC elementar num FPGA) para justificar a sua simplicidade e baixo uso de elementos lógicos. Vamos descobrir nesse primeiro momento o que é e como derivar suas equações a partir de simples rotações matriciais.

O que é um processador CORDIC?

A sigla CORDIC está associada a COordinate Rotation DIgital Computer. Como o nome sugere esse tipo de arranjo trata de um computador de rotações digital. A partir da execução dessas rotações sucessivas podemos obter uma série de operações trigonométricas como seno, cosseno e arctangente. Mais que operações trigonométricas, o uso de um processador CORDIC permite-nos calcular uma série de funções lineares e também hiperbólicas.

Bem, suponho agora que você caro leitor esteja se perguntando qual a vantagem que o CORDIC oferece para calcular essas funções no lugar de métodos tradicionais como tabela de buscas, série de Taylor, ou mesmo uso de métodos numéricos para aproximação do cálculo. Bem, o CORDIC oferece toda essa resolução através de um processo iterativo fixo (ou seja, pode ser usado em aplicações de tempo real) muito simples. Observe a figura abaixo.

Arquitetura-tipica-de-um-processador-CORDIC
Figura 1: Arquitetura típica de um processador CORDIC

A figura 1 representa os elementos combinacionais utilizados para a construção de um processador CORDIC. Veja que o circuito acima contém apenas blocos muito simples, ou seja, multiplexadores, registradores, barrel-shifter e somadores. O bloco em vermelho no canto inferior direito An representa uma pequena tabela de busca auxiliar sendo esse talvez o bloco mais complexo. Resumindo para implementar um CORDIC são necessários basicamente memória, a operação de shift e soma, presentes até no mais simples microcontrolador, consumindo o mínimo de recursos de um FPGA. Seu uso é justificável quando nosso processador não possui recursos matemáticos avançados mas o projeto precisa de algum processamento trigonométrico, iremos em seguida entender como chegar nessas equações de forma elementar. Mas antes, vamos falar um pouco de onde essa ideia veio. 

Breve histórico do processador CORDIC

O processador CORDIC teve sua primeira implementação por volta de 1956, concebida por Jack E. Volder, utilizada como solução para substituição de resolvers analógicos utilizados no computador de bordo do jato supersônico B-58, para uma solução mais precisa e com execução em tempo real. A partir dessa implementação o CORDIC, em algumas publicações, é referenciado também como resolver digital. Volder, na eṕoca do desenvolvimento se inspirou ironicamente em um formulário de cálculo trigonométrico usado em química  de um livro de 1946 chamado: CRC Handbook of Chemistry and Physics. Ao final de sua pesquisa, Volder indicou o uso do CORDIC inicialmente para resolução de operações de seno e cosseno, porém em seu relatório de pesquisa, ele também discutia a utilização da técnica para resolução das mais diversas operações matemáticas, como funções hiperbólicas, logaritmos, funções exponenciais, multiplicação.

Em 1966 com a ajuda de John E. Meggit, propos operações de pseudo - multiplicação e divisão, e além disso algumas modificações foram feitas de modo ao CORDIC usar base 10 em lugar da base 2. Com essas adições a primeira versão em ROM do processador foi embarcada nas calculadoras de desktop da Hewlet-Packard, que foi derivada para uma versão em ponto flutuante com funções cientificas, a HP9100A entrando em produção em março de 1968.

HP9100A
Figura 2: Calculadora desktop HP9100A

Em 1971, John Stephen Walther, ainda na Hewlet-Packard, implementou uma versão generalizada do algoritmo CORDIC, de forma que as funções trigonométricas, hiperbólicas, funções exponenciais, logaritmos, multiplicação e divisão, além de raiz quadrada, fossem igualmente desenvolvidas compartilhando a maioria do código usado na engine CORDIC. Com isso resultou - se na primeira calculadora científica de bolso, a HP-35.

HP35
Figura 3: Calculadora cientifica HP35

Nos anos seguintes o algortimo se popularizou a ponto de ser largamente implementado em calculadoras de bolso, mais que isso, o CORDIC, começou a ser implementado dentro de diversos coprocessadores matemáticos como Intel 8087, 80287, 80387 e 80486, além dos conhecidos Motorola 68881 e 68882, tanto na forma de ponto fixo, quanto em forma de instrução de ponto flutuante.

Nos dias atuais podemos encontrar o uso de CORDIC nas mais diversas aplicações, muitas se concentram no campo de rádios definido por software e controle de motores. Como o CORDIC é uma implementação bem amigável em hardware, podemos encontrar - diversas implementações e IPs com o código aberto. No campo de software este algoritmo é perfeito para rodar em malhas de controle, ou sensoriamento baseados em processadores de poucos recursos, uma vez que sua implementação não necessita do uso de multiplicador.

Mas o que mais chama a atenção no CORDIC é sua implementação, vamos ver de onde partem os cálculos.

Derivando as equações básicas do processador CORDIC

Como já mencionado anteriormente, Volder se inspirou em um formulário trigonométrico de um livro de química para implementação do CORDIC. Essa expressão na verdade tem o aspecto final do algoritmo desenvolvido por ele. Essencialmente sabemos que o CORDIC opera em cima de sucessivas rotações de vetores num plano cartesiano, ou seja, nada melhor que começar a pensar no algoritmo a partir desse ponto. Para tal considerem a expressão para rotacionar um vetor representado num plano de duas dimensões:

CodeCogsEqn(6)
CodeCogsEqn(7)
Equação 1: Rotação de um ponto no plano cartesiano

Observem que podemos modificar o par de equações dividindo ambos os lados e ambas as expressões pelo cosseno do angulo que queremos rotacionar chegaremos em:

CodeCogsEqn(8)
CodeCogsEqn(9)

Porém, nada é simplificado, mas segundo [1][2] e [3], podemos restringir o intervalo do angulo de rotação como sendo a tangente de uma potência de base 2, com expoente negativo. Com isso, obtemos a expressão simplificada abaixo:

CodeCogsEqn(10)
CodeCogsEqn(11)
Equação 2: Par de equações CORDIC

Com:

CodeCogsEqn(3)

E:

CodeCogsEqn(4)

Onde o termo denotado por K refere - se ao chamado ganho Cordic, pois a simplificação não influencia o ângulo de rotação, porém os pontos resultantes são afetados, fazendo com que o módulo calculado pelo produto dos quadrados do ponto não represente o raio da circunferência onde esse par de pontos rotacionou. O ganho de Cordic que converge para o valor aproximado de 0.607, possui função de recuperar esse valores originais, servindo então como uma constante de normalização.

Simples não? com esse par de equações seguidos de alguma lógica, poderemos então ter a implementação mínima de um processador CORDIC, capaz de calcular funções elementares trigonométricas. que veremos abaixo.

Como funciona?

Bom, já vimos um pouco da história do algoritmo CORDIC, bem como derivamos sua principal equação, mas ainda temos uma pergunta a responder, como utilizamos o par de equações? Vejam, que o nosso primeiro interesse é o de rotacionar um par de pontos no plano cartesiano por um ângulo conhecido, obtendo seu valor de seno e cosseno dentro de um circulo unitário. Para isso recorde a equação 2, e perceba a variável d.

Essa, também chamada de variável de decisão tem por função determinar o sentido da próxima rotação com base em algum estado corrente da execução do CORDIC, observemos a figura 4:

CORDIC em execução
Figura 4: Comportamento do CORDIC em execução

Essa figura é perfeita para demonstrar o ocorrido, veja que a variável de decisão é constantemente comparada com um dos valores das coordenadas, essa está relacionada como uma combinação linear entre uma das coordenadas (depende da desejada)  e o ganho de CORDIC, com isso esse valor é constantemente comparado com o ângulo desejado, onde numa primeira iteração as coordenadas são rotacionadas pelo maior ângulo disponível (entre 45 e 90 graus), a variável de decisão determina o sentido da rotação, em seguida o valor é comparado para saber se está maior ou menor que o ângulo desejado, novamente afetando d e o sentido da rotação, e assim sendo executada. Porém por metade do valor do ângulo usado na iteração anterior, com isso a diferença tende a diminuir do angulo atual, para o desejado, e novamente uma nova iteração é realizada, dessa vez com 1/4 do ângulo da primeira rotação (possui uma semelhança caracteristica com o conhecido algoritmo de busca binária). Ao final de "I" iterações o ângulo disponível na saída do processador será o ângulo desejado, bem como seu seno e cosseno, acrescido de um erro que converge para 0 à medida que o número de iterações tende ao infinito, portanto podemos dizer que o processador CORDIC é iterativo, além disso, precisamos também saber por quais ângulos elementares o processo já foi executado, para isso, implementa-se na forma de uma tabela de somente leitura um acumulador de ângulo, introduzindo ao par de equações Cordic, uma terceira variável:

CodeCogsEqn(5)
Equação 3: Acumulador de angulo

Em termos práticos bons valores a respeito do número de iterações de bom compromisso entre velocidade e precisão situa-se entre 16 e 24, no caso da implementação por software podem ser usadas mais rotações e usadas instruções SIMD para paralelização de execução das instruções, além de estratégias bem conhecidas no mundo do processamento digital de sinais que é o loop unrolling. Já para implementação em hardware a otimização fica muito mais acessível pois é possível paralelizar quantos estágios forem necessários, até o limite de células lógicas disponíveis num FPGA por exemplo. Existem arquiteturas CORDIC que entregam os resultados das operações mínimas em um único ciclo de clock (as custas de elevado consumo de corrente, e uso de elementos lógicos).

Conclusão

Acho que o objetivo principal desse primeiro texto sobre CORDIC foi bem atingido, que foi dar uma imersão a essa tecnologia de computação de funções trigonométricas, lineares e hiperbólicas, passamos pelo histórico, rapidamente pela matemática e pelo funcionamento prático de uma engine CORDIC. Os próximos passos vão incluir implementações práticas, passaremos pela implementação em software em um micro com poucos recursos, e implementaremos apenas usando operações de deslocamento e soma afim de demostrar sua viabilidade no uso de projetos onde simplicidade e custo são essenciais, mas que precisem oferecer cálculos trigonométricos com aproximação de boa qualidade. A seguir vamos entrar no mundo da implementação de hardware, construiremos um CORDIC mínimo usando um FPGA de baixo custo. A ideia é validar o uso prático dessa engine sem ser necessário utilizar técnicas de paralelização. Ao final dessa série, vamos utilizar o CORDIC em um caso prático afim de mostrar não somente aquele sinal senoidal na saída do osciloscópio mas, sim o uso do CORDIC na modificação de algum sinal e seu resultado. Espero que tenham gostado, em breve voltaremos com a segunda parte dessa série. Até mais caro leitor.


Referências

[1] - VOLDER, Jack E. - The CORDIC trigonometric computing technique, 1959

[2] - ANDRAKA, Ray - A survey of CORDIC algorithms for FPGA based computers, 1998

[3] - VOLDER, Jack E. - Binary computation algorithms for coordinate rotation and function generation, 1956

Outros artigos da série

CORDIC em Firmware >>
Este post faz da série CORDIC - Um processador trigonométrico de ponto fixo. Leia também os outros posts da série:
Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Software » CORDIC - Introdução
Talvez você goste:
Comentários:

1
Deixe um comentário

avatar
1 Comentários
0 Respostas
0 Seguidores
 
Discussão de maior alcance
Discussão mais quente
1 Autores de comentários
Marcos Comentários recentes
  Notificações  
recentes antigos mais votados
Notificar
Marcos
Visitante
Marcos

Boa tarde. Procurando algo que me ajudasse com um trabalho que devo desenvolver sobre exponencial e logaritmo (série de taylor) em VHDL. Saberias me informar onde posso achar um material com código sobre isso?

Séries



Outros da Série

Menu