CORDIC (por CO ordenada R flotación DI gital C omputer), [1] [2] [3]también conocido como el algoritmo de Volder , es un simple y eficiente algoritmo para calcular hiperbólicas y funciones trigonométricas , típicamente converge con un dígito (o bit) por iteración CORDIC es, por lo tanto, también un ejemplo de algoritmos dígito a dígito . CORDIC y los métodos estrechamente relacionados conocidos como pseudo-multiplicación y pseudo-división o combinación de factores se usan comúnmente cuando no hayel multiplicador de hardware está disponible (por ejemplo, en microcontroladores simples y FPGA ), ya que las únicas operaciones que requiere son la suma , la resta , el desplazamiento de bits y la búsqueda de tablas . Como tales, pertenecen a la clase de algoritmos de cambio y adición .
Historia [ editar ]
Henry Briggs publicó técnicas matemáticas similares desde 1624 [4] [5] y Robert Flower en 1771, [6] pero CORDIC está optimizado para CPU de estado finito de baja complejidad.
CORDIC fue concebido en 1956 [7] [8] por Jack E. Volder en el departamento de aeroelectrónica de Convair por necesidad de reemplazar el resolutor analógico en la computadora de navegación del bombardero B-58 con un digital en tiempo real más preciso y eficiente. solución. [8] Por lo tanto, CORDIC se denomina a veces resolución digital . [9] [10]
En su investigación, Volder se inspiró en una fórmula de la edición de 1946 del CRC Handbook of Chemistry and Physics :
Su investigación llevó a un informe técnico interno que propone el algoritmo CORDIC para resolver las funciones de seno y coseno y una computadora prototípica que lo implementa. [7] [8] El informe también discutió la posibilidad de calcular la rotación de coordenadas hiperbólicas , los logaritmos y las funciones exponenciales con los algoritmos CORDIC modificados. [7] [8] La utilización de CORDIC para la multiplicación y la división también se concibió en este momento. [8] Basado en el principio CORDIC, Dan H. Daggett, un colega de Volder en Convair, desarrolló algoritmos de conversión entre binarios ydecimal codificado en binario (BCD). [8] [11]
En 1958, Convair finalmente comenzó a construir un sistema de demostración para resolver problemas delocalización de radar llamado CORDIC I , completado en 1960 sin Volder, quien ya había dejado la compañía. [1] [8] Los modelos A (estacionarios) y B (aerotransportados) de CORDIC II más universales fueron construidos y probados por Daggett y Harry Schuss en 1962. [8] [12]
El algoritmo CORDIC de Volder se describió por primera vez en público en 1959, [1] [2] [8] [10] [13], lo que provocó su incorporación a las computadoras de navegación por parte de compañías como Martin-Orlando , Computer Control , Litton , Kearfott , Lear -Siegler , Sperry , Raytheon , y Collins Radio pronto. [8]
Volder se asoció con Malcolm MacMillan para construir Athena , una calculadora de escritorio de punto fijo queutiliza su algoritmo binario CORDIC. [14] El diseño fue presentado a Hewlett-Packard en junio de 1965, pero no fue aceptado. [14] Sin embargo, MacMillan introdujo a David S. Cochran (HP) al algoritmo de Volder y cuando Cochran se reunió con Volder, él lo refirió a un enfoque similar que John E. Meggitt (IBM [15] ) propuso como pseudo-multiplicación y pseudo división. en 1961. [15] [16] El método de Meggitt también sugería el uso de la base 10 [15]en lugar de la base 2 , como la usó CORDIC de Volder hasta ahora. Estos esfuerzos llevaron a la implementación lógica de ROMable de una máquina prototipo decimal CORDIC dentro de Hewlett-Packard en 1966, [17] [16] construida y derivada conceptualmente de la máquina verde prototípica de Thomas E. Osborne , una máquina flotante de cuatro funciones calculadora de escritorio de punto que había completado en la lógica DTL [14] en diciembre de 1964. [18] Este proyecto resultó en la demostración pública de la primera calculadora de escritorio de Hewlett-Packard con funciones científicas, la hp 9100AEn marzo de 1968, con la producción en serie a partir de ese mismo año. [14] [18] [19] [20]
Cuando los Laboratorios Wang descubrieron que el hp 9100A usaba un enfoque similar al método de combinación de factores en sus LOCI-1 [21] (septiembre de 1964) y LOCI-2 (enero de 1965) [22] [23] Instrumentos de computación logarítmica anteriores . [24] acusaron sin éxito a Hewlett-Packard de infringir una de las patentes de An Wang en 1968. [16] [25] [26] [27]
John Stephen Walther en Hewlett-Packard generalizó el algoritmo en el algoritmo CORDIC Unificado en 1971, permitiéndole calcular funciones hiperbólicas y exponenciales , logaritmos , multiplicaciones , divisiones y raíces cuadradas . [3] [28] [29] [30] Las subrutinas CORDIC para funciones trigonométricas e hiperbólicas podrían compartir la mayor parte de su código. [25] Este desarrollo dio lugar a la primera calculadora de mano científica , la HP-35 en 1972. [25] [31][32] [33] [34] [35]
Originalmente, CORDIC se implementó solo con el sistema de numeración binaria y, a pesar de que Meggitt sugirió el uso del sistema decimal para su enfoque de pseudo-multiplicación, el CORDIC decimal siguió siendo prácticamente desconocido durante varios años más, por lo que Hermann Schmid y Anthony Bogacki aún sugerían fue una novedad hasta 1973 [13] [10] [36] [37] [38] y solo más tarde se descubrió que Hewlett-Packard ya la había implementado en 1966. [8] [10] [17] [25]
El decimal CORDIC llegó a ser ampliamente utilizado en las calculadoras de bolsillo , [10] la mayoría de las cuales operan en decimal codificado en binario (BCD) en lugar de binario. Este cambio en el formato de entrada y salida no alteró los algoritmos de cálculo del núcleo de CORDIC. CORDIC es especialmente adecuado para las calculadoras de mano, en las que el bajo costo, y por lo tanto el bajo número de compuertas de chips, es mucho más importante que la velocidad.
CORDIC se ha implementado en Intel 8087 , [38] [39] [40] [41] [42] 80287 , [42] [43] 80387 [42] [43] hasta la serie de coprocesador 80486 [38] también como en el Motorola 68881 [38] [39] y 68882 para algunos tipos de instrucciones de punto flotante, principalmente como una forma de reducir los conteos de puertas (y la complejidad) del subsistema FPU .
Aplicaciones [ editar ]
CORDIC utiliza operaciones simples de cambio y desplazamiento para varias tareas informáticas, como el cálculo de funciones trigonométricas, hiperbólicas y logarítmicas, multiplicaciones reales y complejas, división, cálculo de raíz cuadrada, solución de sistemas lineales, estimación de valores propios , descomposición de valores singulares , factorización QR y muchos otros. Como consecuencia, CORDIC se ha utilizado para aplicaciones en diversas áreas, como el procesamiento de señales e imágenes , sistemas de comunicación , robótica y gráficos 3D, además de la computación científica y técnica general. [44] [45]
Hardware [ editar ]
CORDIC es generalmente más rápido que otros enfoques cuando no se dispone de un multiplicador de hardware (por ejemplo, un microcontrolador), o cuando el número de compuertas necesarias para implementar las funciones que admite debe minimizarse (por ejemplo, en un FPGA o ASIC ).
Por otro lado, cuando hay un multiplicador de hardware disponible ( por ejemplo , en un microprocesador DSP ), los métodos de búsqueda de tablas y las series de potencias son generalmente más rápidos que CORDIC. En los últimos años, el algoritmo CORDIC se ha utilizado ampliamente para diversas aplicaciones biomédicas, especialmente en implementaciones de FPGA.
Software [ editar ]
Muchos sistemas antiguos con CPU de solo enteros han implementado CORDIC en diferentes extensiones como parte de sus bibliotecas de punto flotante IEEE . Como la mayoría de las CPU modernas de propósito general tienen registros de punto flotante con operaciones comunes como sumar, restar, multiplicar, dividir, seno, coseno, raíz cuadrada, registro 10 , registro natural, la necesidad de implementar CORDIC en ellos con software es casi inexistente. -existente. Solo el microcontrolador o las aplicaciones de software especiales de seguridad y con limitaciones de tiempo deberían considerar el uso de CORDIC.
Modos de operación [ editar ]
Modo de rotación [ editar ]
CORDIC se puede utilizar para calcular varias funciones diferentes. Esta explicación muestra cómo utilizar CORDIC en el modo de rotación para calcular el seno y el coseno de un ángulo, y supone que el ángulo deseado se da en radianes y se representa en un formato de punto fijo. Para determinar el seno o coseno de un ángulo., se debe encontrar la coordenada y o x de un punto en el círculo unitario correspondiente al ángulo deseado. Usando CORDIC, uno comenzaría con el vector:
En la primera iteración, este vector se gira 45 ° en sentido contrario a las agujas del reloj para obtener el vector . Las iteraciones sucesivas giran el vector en una u otra dirección en pasos de disminución de tamaño, hasta que se haya alcanzado el ángulo deseado. Paso el tamaño es para .
Más formalmente, cada iteración calcula una rotación, que se realiza multiplicando el vector con la matriz de rotación :
La matriz de rotación está dada por:
La matriz de rotación se convierte en:
La expresión para el vector girado. entonces se convierte en:
dónde y son los componentes de . Restringiendo los angulos así que eso asume los valores , la multiplicación con la tangente puede reemplazarse por una división por una potencia de dos, que se realiza de manera eficiente en el hardware de una computadora digital utilizando un desplazamiento de bits . La expresión entonces se convierte en:
dónde
y puede tener los valores de −1 o 1, y se utiliza para determinar la dirección de la rotación; si el angulo es positivo entonces es +1, de lo contrario es −1.
puede ignorarse en el proceso iterativo y luego aplicarse después con un factor de escala:
que se calcula de antemano y se almacena en una tabla, o como una constante única si el número de iteraciones es fijo. Esta corrección también se podría hacer por adelantado, escalandoy por lo tanto guardar una multiplicación. Adicionalmente se puede notar que:
para permitir una mayor reducción de la complejidad del algoritmo. Algunas aplicaciones pueden evitar corregiren total, lo que resulta en una ganancia de procesamiento :
Después de un número suficiente de iteraciones, el ángulo del vector estará cerca del ángulo deseado . Para los propósitos más comunes, 40 iteraciones ( n = 40) son suficientes para obtener el resultado correcto al décimo lugar decimal.
La única tarea que queda es determinar si la rotación debe ser hacia la derecha o hacia la izquierda en cada iteración (elegir el valor de ). Esto se hace manteniendo un seguimiento de cuánto se giró el ángulo en cada iteración y restando eso del ángulo deseado; entonces para acercarme al ángulo deseado, Si es positivo, la rotación es hacia la derecha, de lo contrario es negativa y la rotación es hacia la izquierda.
Los valores de También debe ser precomputado y almacenado. Pero para pequeños ángulos, En representación de punto fijo, reduciendo el tamaño de la tabla.
Como se puede ver en la ilustración de arriba, el seno del ángulo es la coordenada y del vector final, mientras que la coordenada x es el valor del coseno.
Modo de vectorización [ editar ]
El algoritmo de modo de rotación descrito anteriormente puede rotar cualquier vector (no solo un vector unitario alineado a lo largo del eje x ) en un ángulo entre –90 ° y + 90 °. Las decisiones sobre la dirección de rotación dependen de ser positivo o negativo
El modo de operación vectorización requiere una ligera modificación del algoritmo. Comienza con un vector cuya coordenada x es positiva y la coordenada y es arbitraria. Las rotaciones sucesivas tienen el objetivo de rotar el vector hacia el eje x (y, por lo tanto, reducir la coordenada y a cero). En cada paso, el valor de y determina la dirección de la rotación. El valor final deContiene el ángulo total de rotación. El coste final de x será la magnitud del vector original escalado por K . Por lo tanto, un uso obvio del modo de vectorización es la transformación de coordenadas rectangulares a polares.
Implementación [ editar ]
Ejemplo de software [ editar ]
La siguiente es una implementación de CORDIC de MATLAB / GNU Octave que no se basa en ninguna función trascendental excepto en la precomputación de tablas. Si el número de iteraciones n está predeterminado, entonces la segunda tabla se puede reemplazar por una constante única. Con la impresión aritmética de doble precisión estándar de MATLAB y el "formato largo", los resultados aumentan en precisión para n hasta aproximadamente 48.
función v = cordic ( beta, n )
% Esta función calcula v = [cos (beta), sin (beta)] (beta en radianes)
% usando n iteraciones. Aumentar n aumentará la precisión.
si beta < - pi / 2 || beta > pi / 2
si beta < 0
v = cordic ( beta + pi , n );
else
v = cordic ( beta - pi , n );
end
v = - v ; % voltear el signo para el segundo o tercer
extremo de retorno de
cuadrante
% De inicialización de tablas de constantes utilizadas por CORDIC
% necesita una tabla de arctangents de potencias negativas de dos, en radianes:
% ángulos = atan (2. ^ - (0:27));
ángulos = [ ...
,78539816339745 ,46364760900081 ,24497866312686 ,12435499454676 ...
,06241880999596 ,03123983343027 ,01562372862048 ,00781234106010 ...
,00390623013197 ,00195312251648 ,00097656218956 ,00048828121119 ...
,00024414062015 ,00012207031189 ,00006103515617 ,00003051757812 ...
,00001525878906 ,00000762939453 ,00000381469727 ,00000190734863 ...
,00000095367432 ,00000047683716 ,00000023841858 ,00000011920929 ...
,00000005960464 ,00000002980232 ,00000001490116 ,00000000745058 ];
% y una tabla de productos de longitudes recíprocas de vectores [1, 2 ^ -2j]:
% Kvalues = cumprod (1./abs (1 + 1j * 2. ^ (- (0:23))))
Kvalues = [ ...
0.70710678118655 0.63245553203368 0.61357199107790 0.60883391251775 ...
0.60764825625617 0.60735177014130 0.60727764409353 0.60725911229889 ...
0.6072544797933256 ,60725332108988 ,60725303152913 ,60725295913894 ...
,60725294104140 ,60725293651701 ,60725293538591 ,60725293510314 ...
,60725293503245 ,60725293501477 ,60725293501035 ,60725293500925 ...
,60725293500897 ,60725293500890 ,60725293500889 ,60725293500888 ];
Kn = Kvalues ( min ( n , longitud ( Kvalues )));
% Inicializar variables de bucle:
v = [ 1 ; 0 ]; % comienza con coseno de 2 vectores y seno de cero
poweroftwo = 1 ;
ángulo = ángulos ( 1 );
% De iteraciones
para j = 0 : n - 1 ;
si beta < 0
sigma = - 1 ;
else
sigma = 1 ;
factor final
= sigma * poweroftwo ; % Tenga en cuenta que la multiplicación de matrices se puede hacer usando la escala por potencias de dos y la resta de suma R = [ 1 , - factor ; factor , 1 ]; v = R * v ;
% 2 por 2 matriz multiplicar
beta = beta - sigma * ángulo ; % de actualización del ángulo restante
poweroftwo = poweroftwo / 2 ;
% actualice el ángulo desde la tabla, o eventualmente simplemente dividiendo por dos
si j + 2 > longitud ( ángulos )
ángulo = ángulo / 2 ;
otro
ángulo = ángulos ( j + 2 );
final
fin
% Ajuste la longitud del vector de salida para que sea [cos (beta), sin (beta)]:
v = v * Kn ;
regreso
disfunción
La multiplicación de matrices de dos por dos se puede llevar a cabo mediante un par de cambios simples y agregados.
x = v [ 0 ] - sigma * ( v [ 1 ] * 2 ^ ( - j ));
y = sigma * ( v [ 0 ] * 2 ^ ( - j )) + v [ 1 ];
v = [ x ; y ];
En Java, la clase de Matemáticas tiene un
scalb(double x,int scale)método para realizar dicho cambio, [47] C tiene la función ldexp , [48] y la clase de procesadores x86 tiene la fscaleoperación de punto flotante. [49]Ejemplo de hardware [ editar ]
El número de compuertas lógicas para la implementación de un CORDIC es aproximadamente comparable al número requerido para un multiplicador, ya que ambos requieren combinaciones de turnos y adiciones. La elección de una implementación basada en multiplicador o basada en CORDIC dependerá del contexto. La multiplicación de dos números complejos representados por sus componentes reales e imaginarios (coordenadas rectangulares), por ejemplo, requiere 4 multiplicaciones, pero podría realizarse mediante un solo CORDIC que opere en números complejos representados por sus coordenadas polares, especialmente si la magnitud de los números no es relevante (multiplicar un vector complejo con un vector en el círculo unitario en realidad equivale a una rotación). Los CORDIC se utilizan a menudo en circuitos para telecomunicaciones tales comoConvertidores de bajada digitales .
Algoritmos relacionados [ editar ]
CORDIC forma parte de la clase de algoritmos de "desplazamiento y adición" , al igual que los algoritmos logarítmicos y exponenciales derivados del trabajo de Henry Briggs. Otro algoritmo de cambio y adición que se puede usar para calcular muchas funciones elementales es el algoritmo BKM , que es una generalización del logaritmo y algoritmos exponenciales al plano complejo. Por ejemplo, BKM se puede usar para calcular el seno y el coseno de un ángulo real (en radianes) calculando el exponencial de , cual es . El algoritmo BKM es un poco más complejo que CORDIC, pero tiene la ventaja de que no necesita un factor de escala ( K ).
No hay comentarios:
Publicar un comentario