Hispanopedia Wiki
Articulo de referencia

CORDIC

CORDIC , acrónimo de ordenador digital de rotación de coordenadas , es un algoritmo sencillo y eficiente para calcular funciones trigonométricas , hiperbólicas , raíces cuadrada...

Hispanopedia WikiContenido en espanolLectura gratuita

CORDIC , acrónimo de ordenador digital de rotación de coordenadas , es un algoritmo sencillo y eficiente para calcular funciones trigonométricas , hiperbólicas , raíces cuadradas , multiplicaciones , divisiones , exponenciales y logaritmos con base arbitraria, convergiendo típicamente con un dígito (o bit) por iteración. Por lo tanto, CORDIC es un ejemplo de algoritmo de cálculo dígito a dígito . El sistema original a veces se denomina algoritmo de Volder .

CORDIC y métodos estrechamente relacionados, conocidos como pseudomultiplicación y pseudodivisión o combinación de factores, se utilizan comúnmente cuando no se dispone de un multiplicador de hardware (por ejemplo, en microcontroladores simples y matrices de puertas programables en campo o FPGA), ya que las únicas operaciones que requieren son suma , resta , desplazamiento de bits y tablas de búsqueda . Por lo tanto, todos pertenecen a la clase de algoritmos de desplazamiento y suma . En ciencias de la computación, CORDIC se usa a menudo para implementar aritmética de punto flotante cuando la plataforma de destino carece del hardware para multiplicar por razones de costo o espacio. Este fue el caso de la mayoría de las primeras microcomputadoras basadas en procesadores como el MOS 6502 y el Zilog Z80 .

A lo largo de los años, surgieron varias variaciones del concepto, incluyendo CORDIC circular ( Jack E. Volder ), [ 1 ] [ 2 ] CORDIC lineal , CORDIC hiperbólico (John Stephen Walther), [ 3 ] [ 4 ] y CORDIC hiperbólico generalizado ( GH CORDIC ) (Yuanyong Luo et al.), [ 5 ] [ 6 ]

Concepto

A grandes rasgos, el algoritmo básico de CORDIC consiste en aplicar una secuencia de rotaciones escaladas a un vector. Los factores de escala y los ángulos de rotación se conocen de antemano; solo la dirección de cada rotación depende de la entrada. En el modo de rotación, se toma como entrada un ángulo de rotación objetivo y se eligen las direcciones de rotación de manera que el ángulo de rotación acumulado se aproxime a dicho objetivo. La salida es el vector final. En el modo de vectorización, se toma como entrada un vector y se eligen las direcciones de rotación de manera que la coordenada y del vector se aproxime a 0. La salida es el ángulo de rotación total. Consulte los modos de operación para obtener más detalles.

Los factores de escala y los ángulos de rotación se eligen de manera que las rotaciones escaladas se puedan calcular utilizando únicamente suma, resta y desplazamiento de bits. Los ángulos se consultan en una tabla que se ha calculado previamente.

Historia

Técnicas matemáticas similares fueron publicadas ya en 1624 [ 7 ] [ 8 ] y Robert  Flower en 1771, [ 9 ] pero CORDIC está mejor optimizado para CPU de estados finitos de baja complejidad.

CORDIC fue concebido en 1956 [ 10 ] [ 11 ] por Jack E. Volder en el departamento de aeroelectrónica de Convair por la necesidad de reemplazar el resolutor analógico en la computadora de navegación del bombardero B-58 con una solución digital en tiempo real más precisa y rápida. [ 11 ] Por lo tanto, a CORDIC a veces se le denomina resolutor digital . [ 12 ] [ 13 ]

En su investigación, Volder se inspiró en una fórmula de la edición de 1946 del Manual CRC de Química y Física : [ 11 ]

KnorteRpecado⁡(θ±φ)=Rpecado⁡(θ)±2−norteRporque⁡(θ),KnorteRporque⁡(θ±φ)=Rporque⁡(θ)∓2−norteRpecado⁡(θ),{\displaystyle {\begin{aligned}K_{n}R\sin(\theta \pm \varphi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta ),\\K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\end{alineado}}}

dóndeφ{\displaystyle \varphi }es tal quebroncearse⁡(φ)=2−norte{\displaystyle \tan(\varphi)=2^{-n}}, yKnorte:=1+2−2norte{\displaystyle K_{n}:={\sqrt {1+2^{-2n}}}}.

Su investigación dio lugar a un informe técnico interno que proponía el algoritmo CORDIC para resolver funciones seno y coseno , así como un prototipo de computadora que lo implementaba. [ 10 ] [ 11 ] El informe también analizaba la posibilidad de calcular la rotación de coordenadas hiperbólicas , logaritmos y funciones exponenciales con algoritmos CORDIC modificados. [ 10 ] [ 11 ] En ese momento también se concibió la utilización de CORDIC para la multiplicación y la división . [ 11 ] Basándose en el principio CORDIC, Dan  H.  Daggett, colega de Volder en Convair, desarrolló algoritmos de conversión entre binario y decimal codificado en binario (BCD). [ 11 ] [ 14 ]

En 1958, Convair finalmente comenzó a construir un sistema de demostración para resolver problemas de toma de posición por radar llamado CORDIC I , completado en 1960 sin Volder, quien ya había dejado la compañía. [ 1 ] [ 11 ] Los modelos más universales CORDIC II A (estacionario) y B (aéreo) fueron construidos y probados por Daggett y Harry Schuss en 1962. [ 11 ] [ 15 ]

El algoritmo CORDIC de Volder se describió públicamente por primera vez en 1959, [ 1 ] [ 2 ] [ 11 ] [ 13 ] [ 16 ] lo que provocó que fuera incorporado a las computadoras de navegación por compañías como Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon y Collins Radio . [ 11 ]

Volder se asoció con Malcolm McMillan para construir Athena , una calculadora de escritorio de punto fijo que utilizaba su algoritmo binario CORDIC. [ 17 ] El diseño se presentó a Hewlett-Packard en junio de 1965, pero no fue aceptado. [ 17 ] Aun así, McMillan le presentó a David S. Cochran (HP) el algoritmo de Volder y cuando Cochran conoció más tarde a Volder, le remitió a un enfoque similar que John E. Meggitt (IBM [ 18 ] ) había propuesto como pseudomultiplicación y pseudodivisión en 1961. [ 18 ] [ 19 ] El método de Meggitt también sugería el uso de la base 10 [ 18 ] en lugar de la base 2 , como la que utilizaba el CORDIC de Volder hasta entonces. Estos esfuerzos llevaron a la implementación lógica ROMable de una máquina prototipo CORDIC decimal dentro de Hewlett-Packard en 1966, [ 20 ] [ 19 ] construida y derivada conceptualmente de la Green Machine prototípica de Thomas E. Osborne , una calculadora de escritorio de punto flotante de cuatro funciones que había completado en lógica DTL [ 17 ] en diciembre de 1964. [ 21 ] Este proyecto resultó en la demostración pública de la primera calculadora de escritorio de Hewlett-Packard con funciones científicas, la HP 9100A en marzo de 1968, con la producción en serie comenzando más tarde ese año. [ 17 ] [ 21 ] [ 22 ] [ 23 ]

Cuando Wang Laboratories descubrió que la HP  9100A utilizaba un enfoque similar al método de combinación de factores de sus calculadoras de escritorio LOCI-1 [ 24 ] (septiembre de 1964) y LOCI-2 (enero de 1965) [ 25 ] [ 26 ] Logarithmic Computing Instrument [ 27 ] anteriores, acusaron sin éxito a Hewlett-Packard de infringir una de las patentes de An Wang en 1968. [ 19 ] [ 28 ] [ 29 ] [ 30 ]

John Stephen Walther en Hewlett-Packard generalizó el algoritmo en el algoritmo CORDIC unificado en 1971, lo que le permitió calcular funciones hiperbólicas , exponenciales naturales , logaritmos naturales , multiplicaciones , divisiones y raíces cuadradas . [ 31 ] [ 3 ] [ 4 ] [ 32 ] Las subrutinas CORDIC para funciones trigonométricas e hiperbólicas podían compartir la mayor parte de su código. [ 28 ] Este desarrollo dio como resultado la primera calculadora científica portátil , la HP-35 en 1972. [ 28 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] Basándose en CORDIC hiperbólico, Yuanyong Luo et al. Además, en 2019 se propuso un CORDIC hiperbólico generalizado (GH CORDIC) para calcular directamente logaritmos y exponenciales con una base fija arbitraria. [ 5 ] [ 6 ] [ 38 ] [ 39 ] [ 40 ] Teóricamente, el CORDIC hiperbólico es un caso especial del GH CORDIC. [ 5 ]

Originalmente, CORDIC se implementó solo utilizando el sistema numérico binario y, a pesar de que Meggitt sugirió el uso del sistema decimal para su enfoque de pseudomultiplicación, CORDIC decimal siguió siendo prácticamente desconocido durante varios años más, de modo que Hermann Schmid y Anthony Bogacki todavía lo sugirieron como una novedad tan tarde como en 1973 [ 16 ] [ 13 ] [ 41 ] [ 42 ] [ 43 ] y solo más tarde se descubrió que Hewlett-Packard ya lo había implementado en 1966. [ 11 ] [ 13 ] [ 20 ] [ 28 ]

El CORDIC decimal se popularizó en las calculadoras de bolsillo , [ 13 ] la mayoría de las cuales operan en código binario decimal (BCD) en lugar de binario. Este cambio en el formato de entrada y salida no alteró los algoritmos de cálculo principales del CORDIC. El CORDIC es especialmente adecuado para calculadoras de mano, donde el bajo costo —y, por lo tanto, el bajo número de compuertas del chip— es mucho más importante que la velocidad.

CORDIC se ha implementado en el STM32G4 basado en ARM , Intel 8087 , [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] 80287 , [ 47 ] [ 48 ] 80387 [ 47 ] [ 48 ] hasta la serie de coprocesadores 80486 [ 43 ] así como en el Motorola 68881 [ 43 ] [ 44 ] y 68882 para algunos tipos de instrucciones de punto flotante, principalmente como una forma de reducir el número de compuertas (y la complejidad) del subsistema FPU .

Aplicaciones

CORDIC utiliza operaciones simples de suma y desplazamiento para diversas tareas de cálculo, como el cálculo de funciones trigonométricas, hiperbólicas y logarítmicas, la multiplicación y división de números reales y complejos, el cálculo de raíces cuadradas, la resolución de sistemas lineales, la estimación de valores propios , la descomposición en valores singulares , la factorización QR y muchas otras. En consecuencia, CORDIC se ha utilizado en aplicaciones de diversas áreas, como el procesamiento de señales e imágenes , los sistemas de comunicación , la robótica y los gráficos 3D, además de la computación científica y técnica general. [ 49 ] [ 50 ]

Hardware

El algoritmo se utilizó en el sistema de navegación del vehículo lunar del programa Apolo para calcular el rumbo y el alcance, o distancia desde el módulo lunar . [ 51 ] [ 52 ] CORDIC se utilizó para implementar el coprocesador matemático Intel 8087 en 1980, evitando la necesidad de implementar la multiplicación por hardware. [ 53 ]

CORDIC suele ser más rápido que otros métodos cuando no se dispone de un multiplicador de hardware (por ejemplo, en un microcontrolador) o cuando se debe minimizar el número de compuertas necesarias para implementar las funciones que admite (por ejemplo, en una FPGA o ASIC ). De hecho, CORDIC es una IP estándar que se integra fácilmente en aplicaciones de desarrollo de FPGA como Vivado para Xilinx, mientras que una implementación de series de potencias no lo es debido a la especificidad de dicha IP; es decir, CORDIC puede calcular muchas funciones diferentes (de propósito general), mientras que un multiplicador de hardware configurado para ejecutar implementaciones de series de potencias solo puede calcular la función para la que fue diseñado.

Por otro lado, cuando se dispone de un multiplicador de hardware ( por ejemplo , en un microprocesador DSP ), los métodos de búsqueda en tablas y las series de potencias suelen ser más rápidos que CORDIC. En los últimos años, el algoritmo CORDIC se ha utilizado ampliamente en diversas aplicaciones biomédicas, especialmente en implementaciones FPGA.

Las series STM32G4 , STM32U5 y STM32H5 , así como ciertas series STM32H7 de MCU, implementan un módulo CORDIC para acelerar los cálculos en diversas aplicaciones de señales mixtas, como gráficos para interfaces hombre-máquina y control orientado al campo de motores. Si bien no es tan rápido como una aproximación de series de potencias, CORDIC es de hecho más rápido que las implementaciones basadas en tablas de interpolación, como las proporcionadas por las bibliotecas estándar ARM CMSIS y C. [ 54 ] Aunque los resultados pueden ser ligeramente menos precisos, ya que los módulos CORDIC proporcionados solo alcanzan 20 bits de precisión en el resultado. Por ejemplo, la mayor parte de la diferencia de rendimiento en comparación con la implementación de ARM se debe a la sobrecarga del algoritmo de interpolación, que alcanza la precisión de punto flotante completa (24 bits) y probablemente puede alcanzar un error relativo a esa precisión. [ 55 ] Otra ventaja es que el módulo CORDIC es un coprocesador y puede ejecutarse en paralelo con otras tareas de la CPU.

El problema con el uso de series de Taylor es que, si bien proporcionan un pequeño error absoluto, no presentan un error relativo bien comportado. [ 56 ] Se pueden utilizar otros métodos de aproximación polinómica, como la optimización minimax , para controlar ambos tipos de error.

Software

Muchos sistemas antiguos con CPU que solo manejan números enteros han implementado CORDIC en diversos grados como parte de sus bibliotecas de punto flotante IEEE . Dado que la mayoría de las CPU modernas de propósito general cuentan con registros de punto flotante para operaciones comunes como suma, resta, multiplicación, división, seno, coseno, raíz cuadrada, logaritmo en base 10 y logaritmo natural, la necesidad de implementar CORDIC mediante software es prácticamente inexistente. Solo los microcontroladores o las aplicaciones de software especiales con restricciones de seguridad y tiempo requerirían considerar el uso de CORDIC.

Modos de funcionamiento

Modo de rotación

CORDIC se puede utilizar para calcular varias funciones diferentes. Esta explicación muestra cómo usar CORDIC en modo de rotación para calcular el seno y el coseno de un ángulo, suponiendo que el ángulo deseado se da en radianes y se representa en un formato de punto fijo. Para determinar el seno o el coseno de un ánguloβ{\displaystyle \beta }Se debe encontrar la coordenada y o x de un punto en el círculo unitario correspondiente al ángulo deseado. Usando CORDIC, se comenzaría con el vectorv0{\displaystyle v_{0}}:

v0=[10].{\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix}}.}
Ilustración del algoritmo CORDIC en desarrollo.

En la primera iteración, este vector se rota 45° en sentido contrario a las agujas del reloj para obtener el vectorv1{\displaystyle v_{1}}Las iteraciones sucesivas rotan el vector en una u otra dirección mediante pasos de tamaño decreciente, hasta que se alcanza el ángulo deseado. Cada ángulo de paso esγi=arctan⁡(2−i){\displaystyle \gamma _{i}=\arctan {(2^{-i})}}parai=0,1,2,…{\displaystyle i=0,1,2,\dots }.

De forma más formal, cada iteración calcula una rotación, que se realiza multiplicando el vector.vi{\displaystyle v_{i}}con la matriz de rotaciónRi{\displaystyle R_{i}}:

vi+1=Rivi.{\displaystyle v_{i+1}=R_{i}v_{i}.}

La matriz de rotación viene dada por

Ri=[porque⁡(γi)−pecado⁡(γi)pecado⁡(γi)porque⁡(γi)].{\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{bmatrix}}.}

Utilizando la identidad trigonométrica :

broncearse⁡(γi)≡pecado⁡(γi)porque⁡(γi),{\displaystyle {\begin{aligned}\tan(\gamma _{i})&\equiv {\frac {\sin(\gamma _{i})}{\cos(\gamma _{i})}},\end{aligned}}}

El factor coseno se puede extraer para obtener:

Ri=porque⁡(γi)[1−broncearse⁡(γi)broncearse⁡(γi)1].{\displaystyle R_{i}=\cos(\gamma _{i}){\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}.}

La expresión para el vector rotadovi+1=Rivi{\displaystyle v_{i+1}=R_{i}v_{i}}entonces se convierte en:

[incógnitai+1yi+1]=porque⁡(γi)[1−broncearse⁡(γi)broncearse⁡(γi)1][incógnitaiyi],{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}=\cos(\gamma _{i}){\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}

dóndeincógnitai{\displaystyle x_{i}}yyi{\displaystyle y_{i}}son los componentes devi{\displaystyle v_{i}}. Ajustando el ánguloγi{\displaystyle \gamma _{i}}para cada iteración tal quebroncearse⁡(γi)=±2−i{\displaystyle \tan(\gamma _{i})=\pm 2^{-i}}sigue produciendo una serie que converge a cada posible valor de salida. Por lo tanto, la multiplicación por la tangente puede reemplazarse por una división por una potencia de dos, lo cual se realiza de manera eficiente en el hardware de las computadoras digitales mediante un desplazamiento de bits . La expresión queda entonces como:

[incógnitai+1yi+1]=porque⁡(arctan⁡(2−i))[1−σi2−iσi2−i1][incógnitaiyi],{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}=\cos(\arctan(2^{-i})){\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}

en el cualσi{\displaystyle \sigma _{i}}determina la dirección de la rotación. Si el ángulo de rotaciónγi{\displaystyle \gamma _{i}}es ser positivo,σi{\displaystyle \sigma _{i}}es +1, de lo contrario es −1.

La siguiente identidad trigonométrica puede utilizarse para reemplazar el coseno:

porque⁡(γi)≡11+broncearse2⁡γi{\displaystyle \cos(\gamma _{i})\equiv {\frac {1}{\sqrt {1+\tan ^{2}{\gamma _{i}}}}}},

asignando este multiplicador para cada iteración:

Ki=porque⁡(arctan⁡(2−i))=11+2−2i.{\displaystyle K_{i}=\cos(\arctan(2^{-i}))={\frac {1}{\sqrt {1+2^{-2i}}}}.}

ElKi{\displaystyle K_{i}}Los factores pueden entonces eliminarse del proceso iterativo y aplicarse todos a la vez posteriormente con un factor de escala.K(norte){\displaystyle K(n)}:

K(norte)=∏i=0norte−1Ki=∏i=0norte−111+2−2i,{\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i}}}},}

que se calcula de antemano y se almacena en una tabla o como una única constante, si el número de iteraciones es fijo. Esta corrección también podría hacerse de antemano, mediante escalado.v0{\displaystyle v_{0}}y por lo tanto, ahorrando una multiplicación. Además, se puede observar que [ 43 ]

K=límitenorte→∞K(norte)≈0,6072529350088812561694{\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}

para permitir una mayor reducción de la complejidad del algoritmo. Algunas aplicaciones pueden evitar corregirK{\displaystyle K}en conjunto, lo que resulta en una ganancia de procesamientoA{\displaystyle A}: [ 57 ]

A=1K=límitenorte→∞∏i=0norte−11+2−2i≈1.64676025812107.{\displaystyle A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i}}}\approx 1.64676025812107.}

Después de un número suficiente de iteraciones, el ángulo del vector estará cerca del ángulo deseado.β{\displaystyle \beta }Para la mayoría de los propósitos comunes, 40 iteraciones ( n  =  40) son suficientes para obtener el resultado correcto hasta la décima cifra decimal.

La única tarea restante es determinar si la rotación debe ser en sentido horario o antihorario en cada iteración (eligiendo el valor deσ{\displaystyle \sigma }). Esto se hace registrando cuánto se giró el ángulo en cada iteración y restándolo del ángulo deseado; luego, para acercarse al ángulo deseadoβ{\displaystyle \beta }, siβnorte+1{\displaystyle \beta _{n+1}}Si el valor es positivo, la rotación es en el sentido de las agujas del reloj; de lo contrario, si es negativo, la rotación es en sentido contrario a las agujas del reloj.

β0=β{\displaystyle \beta _{0}=\beta }
βi+1=βi−σiγi,γi=arctan⁡(2−i).{\displaystyle \beta _{i+1}=\beta _{i}-\sigma _{i}\gamma _{i},\quad \gamma _{i}=\arctan(2^{-i}).}

Los valores deγnorte{\displaystyle \gamma _{n}}También debe precalcularse y almacenarse. Para ángulos pequeños se puede aproximar conarctan⁡(γnorte)≈γnorte{\displaystyle \arctan(\gamma _{n})\approx \gamma _{n}}para reducir el tamaño de la tabla.

Como se puede ver en la ilustración anterior, el seno del ánguloβ{\displaystyle \beta }es la coordenada y del vector finalvnorte,{\displaystyle v_{n},}mientras que la coordenada x es el valor del coseno.

Modo vectorial

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 la rotación dependen deβi{\displaystyle \beta _{i}}ser positivo o negativo.

El modo de operación vectorial requiere una ligera modificación del algoritmo. Comienza con un vector cuya coordenada x es positiva, mientras que la coordenada y es arbitraria. Las rotaciones sucesivas tienen como objetivo rotar el vector al 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 deβi{\displaystyle \beta _{i}}Contiene el ángulo total de rotación. El valor final de x será la magnitud del vector original escalada por K. Por lo tanto, un uso obvio del modo de vectorización es la transformación de coordenadas rectangulares a polares.

Implementación

En Java, la clase Math tiene un scalb(double x, int scale)método para realizar dicho desplazamiento, [ 58 ] C tiene la función ldexp , [ 59 ] y la clase de procesadores x86 tiene la fscaleoperación de punto flotante. [ 60 ]

Ejemplo de software (Python)

from math import atan2 , sqrt , sin , cos , radiansITERS = 16theta_table = [ atan2 ( 1 , 2 ** i ) para i en range ( ITERS )]def compute_K ( n ):""" Calcula K(n) para n = ITERS. Esto también podría ser Se almacena como una constante explícita si ITERS arriba está fijo. """k = 1.0para i en rango ( n ):k *= 1 / raíz cuadrada ( 1 + 2 ** ( - 2 * i ))devolver kdef cordic ( alpha : float , n : int ) -> tuple [ float , float ]:afirmar n <= ITERSK_n = compute_K ( n )theta = 0.0x = 1.0y = 0.0P2i = 1 # Esto será 2**(-i) en el bucle siguientepara arc_tangent en theta_table [: n ]:sigma = + 1 si theta < alfa, de lo contrario - 1theta += sigma * arc_tangentex , y = x - sigma * y * P2i , sigma * P2i * x + yP2i /= 2devolver x * K_n , y * K_nSi __name__ == "__main__" :# Imprime una tabla de senos y cosenos calculados, desde -90° hasta +90°, en pasos de 15°,# comparando con las rutinas matemáticas disponibles.imprimir ( " x sin(x) diff. seno cos(x) diff. coseno " )para x en rango ( - 90 , 91 , 15 ):cos_x , sin_x = cordic ( radianes ( x ), ITERS )imprimir (f " { x : +05.1f } ° { sin_x : +.8f } ( { sin_x - sin ( radians ( x )) : +.8f } ) { cos_x : +.8f } ( { cos_x - cos ( radians ( x )) : +.8f } )")

Producción

$ python cordic.py  x sin(x) diff. seno cos(x) diff. coseno -90.0° -1.00000000 (+0.00000000) -0.00001759 (-0.00001759) -75.0° -0.96592181 (+0.00000402) +0.25883404 (+0.00001499) -60.0° -0.86601812 (+0.00000729) +0.50001262 (+0.00001262) -45.0° -0.70711776 (-0.00001098) +0.70709580 (-0.00001098) -30.0° -0.50001262 (-0.00001262) +0,86601812 (-0,00000729) -15,0° -0,25883404 (-0,00001499) +0,96592181 (-0,00000402) +00,0° +0,00001759 (+0,00001759) +1,00000000 (-0,00000000) +15,0° +0,25883404 (+0,00001499) +0,96592181 (-0,00000402) +30,0° +0,50001262 (+0,00001262) +0,86601812 (-0,00000729) +45,0° +0,70709580 (-0,00001098) +0,70711776 (+0,00001098) +60,0° +0,86601812 (-0,00000729) +0,50001262 (+0,00001262) +75,0° +0,96592181 (-0,00000402) +0,25883404 (+0,00001499) +90,0° +1,00000000 (-0,00000000) -0,00001759 (-0,00001759)

Ejemplo de hardware

El número de puertas 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 desplazamientos y sumas. La elección entre una implementación basada en multiplicadores o en CORDIC dependerá del contexto. La multiplicación de dos números complejos representados por sus componentes real e imaginaria (coordenadas rectangulares), por ejemplo, requiere 4 multiplicaciones, pero podría realizarse con un solo CORDIC que opere sobre números complejos representados por sus coordenadas polares, especialmente si la magnitud de los números no es relevante (multiplicar un vector complejo por un vector en el círculo unitario equivale en realidad a una rotación). Los CORDIC se utilizan a menudo en circuitos de telecomunicaciones, como los convertidores descendentes digitales .

Iteraciones dobles CORDIC

En dos publicaciones de Vladimir Baykov, [ 61 ] [ 62 ] se propuso utilizar el método de iteraciones dobles para la implementación de las funciones: arcoseno, arcocoseno, logaritmo natural, función exponencial, así como para el cálculo de funciones hiperbólicas. El método de iteraciones dobles consiste en que, a diferencia del método CORDIC clásico, donde el valor del paso de iteración cambia cada vez, es decir, en cada iteración, en el método de iteraciones dobles, el valor del paso de iteración se repite dos veces y cambia solo a través de una iteración. Al mismo tiempo, cuando el valor de i no cambia, el signo (dirección) de la iteración, es decir, + o - (en sentido horario o antihorario) depende del signo de la variable que se reduce a cero. De ahí surgió la designación para el indicador de grado para iteraciones dobles:i=0,0,1,1,2,2…{\displaystyle i=0,0,1,1,2,2\dots }. Mientras que con las iteraciones ordinarias:i=0,1,2…{\displaystyle i=0,1,2\dots }El método de doble iteración garantiza la convergencia del método en todo el rango válido de cambios de argumentos.

La generalización de los problemas de convergencia CORDIC para el sistema de numeración posicional arbitrario con baseR{\displaystyle R}demostró [ 63 ] que para las funciones seno, coseno, arcotangente, es suficiente realizarR−1{\displaystyle R-1}iteraciones para cada valor de i (i = 0 o 1 a n, donde n es el número de dígitos), es decir, para cada dígito del resultado. Para el logaritmo natural, exponencial, seno hiperbólico, coseno y arcotangente,R{\displaystyle R}Se deben realizar iteraciones para cada valor.i{\displaystyle i}. Para las funciones arcoseno y arcocoseno, dosR−1{\displaystyle R-1}Se deben realizar iteraciones para cada dígito del número, es decir, para cada valor dei{\displaystyle i}. [ 63 ]

Para las funciones de seno hiperbólico inverso y arcoseno, el número de iteraciones será2R{\displaystyle 2R}para cadai{\displaystyle i}, es decir, para cada dígito del resultado.

CORDIC pertenece a la clase de algoritmos de "desplazamiento y suma" , al igual que los algoritmos logarítmico y exponencial derivados del trabajo de Henry Briggs. Otro algoritmo de desplazamiento y suma que puede utilizarse para calcular muchas funciones elementales es el algoritmo BKM , que es una generalización de los algoritmos logarítmico y exponencial al plano complejo. Por ejemplo, BKM puede utilizarse para calcular el seno y el coseno de un ángulo real.incógnita{\displaystyle x}(en radianes) calculando la exponencial de0+iincógnita{\displaystyle 0+ix}, que escis⁡(incógnita)=porque⁡(incógnita)+ipecado⁡(incógnita){\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)}El algoritmo BKM es un poco más complejo que CORDIC, pero tiene la ventaja de que no necesita un factor de escala ( K ).

Véase también

Referencias

  1. 1 2 3 Volder, Jack E. (1959-03-03). "La técnica de computación CORDIC" (PDF) . Actas de la Conferencia Conjunta de Computación del Oeste (presentación). San Francisco, California, EE. UU.: Comité Nacional Conjunto de Computación : 257–261 . Recuperado el 2 de enero de 2016 .
  2. 1 2 Volder, Jack E. (1959-05-25). "The CORDIC Trigonometric Computing Technique" (PDF) . IRE Transactions on Electronic Computers . 8 (3). The Institute of Radio Engineers, Inc. (IRE) (publicado en septiembre de 1959): 330–334 (reimpresión: 226–230). Bibcode : 1959IRTEC...8..330V . doi : 10.1109/TEC.1959.5222693 . EC-8(3):330–334. Archivado del original (PDF) el 12 de junio de 2021. Recuperado el 1 de enero de 2016 .
  3. 1 2 Walther, John Stephen (mayo de 1971). Escrito en Palo Alto, California, EE. UU. "Un algoritmo unificado para funciones elementales" (PDF) . Actas de la Conferencia Conjunta de Computación de Primavera . 38. Atlantic City, Nueva Jersey, EE. UU.: Hewlett-Packard Company : 379–385 . Archivado del original (PDF) el 12 de junio de 2021. Recuperado el 1 de enero de 2016 a través de la Federación Estadounidense de Sociedades de Procesamiento de la Información (AFIPS).
  4. 1 2 Walther, John Stephen (junio de 2000). "La historia de CORDIC unificado" . The Journal of VLSI Signal Processing . 25 (2 (número especial sobre CORDIC)). Hingham, MA, EE. UU.: Kluwer Academic Publishers : 107–112 . Bibcode : 2000JSPSy..25..107W . doi : 10.1023/A:1008162721424 . ISSN 0922-5773 . S2CID 26922158 .  
  5. 1 2 3 Luo, Yuanyong; Wang, Yuxuan; Ha, Yajun; Wang, Zhongfeng; Chen, Siyuan; Pan, Hongbing (septiembre de 2019). "CORDIC hiperbólico generalizado y su cálculo logarítmico y exponencial con base fija arbitraria". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 27 (9): 2156– 2169. Bibcode : 2019ITVL...27.2156L . doi : 10.1109/TVLSI.2019.2919557 . S2CID 196171166 . 
  6. 1 2 Luo, Yuanyong; Wang, Yuxuan; Ha, Yajun; Wang, Zhongfeng; Chen, Siyuan; Pan, Hongbing (septiembre de 2019). "Correcciones a "CORDIC hiperbólico generalizado y su cálculo logarítmico y exponencial con base fija arbitraria"". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 27 (9): 2222. Bibcode : 2019ITVL...27.2222L . doi : 10.1109/TVLSI.2019.2932174 . S2CID 201711001 . 
  7. ↑ Briggs, Henry (1624). Arithmetica Logarithmica . Londres.(Traducción:Archivado el 4 de marzo de 2016 en Wayback Machine .
  8. ↑ Laporte, Jacques (2014) [2005]. "Henry Briggs y el HP 35" . París, Francia. Archivado del original el 9 de marzo de 2015. Recuperado el 2 de enero de 2016 .Archivado el 10 de agosto de 2020 en Wayback Machine .
  9. ↑ Flower, Robert (1771). The Radix. Una nueva forma de hacer logaritmos . Londres: J. Beecroft . Consultado el 2 de enero de 2016 .
  10. 1 2 3 Volder, Jack E. (1956-06-15), Algoritmos de computación binaria para la rotación de coordenadas y la generación de funciones (informe interno), Convair , grupo de aeroelectrónica, IAR-1.148
  11. 1 2 3 4 5 6 7 8 9 10 11 12 Volder, Jack E. (junio de 2000). "El nacimiento de CORDIC" (PDF) . Journal of VLSI Signal Processing . 25 (2 (número especial sobre CORDIC)). Hingham, MA, EE. UU.: Kluwer Academic Publishers : 101–105 . Bibcode : 2000JSPSy..25..101V . doi : 10.1023/A:1008110704586 . ISSN 0922-5773 . S2CID 112881. Archivado del original (PDF) el 4 de marzo de 2016. Recuperado el 2 de enero de 2016 .  
  12. ↑ Perle, Michael D. (junio de 1971), "La técnica CORDIC reduce la búsqueda de funciones trigonométricas", Computer Design , Boston, MA, EE. UU.: Computer Design Publishing Corp.: 72–78(Nota: Algunas fuentes se refieren erróneamente a esto como obra de PZ Perle o en Component Design ).
  13. 1 2 3 4 5 Schmid, Hermann (1983) [1974]. Cálculo decimal (1.ª ed. (reimpresión)). Malabar, Florida, EE. UU.: Robert E. Krieger Publishing Company. págs. 162, 165–176 , 181–193 . ISBN   0-89874-318-4. Consultado el 3 de enero de 2016 .(Nota: Al menos algunos lotes de esta edición reimpresa presentaban errores de impresión, con las páginas 115 a 146 defectuosas ) .
  14. ↑ Daggett, Dan H. (septiembre de 1959). "Conversiones decimales-binarias en CORDIC" . IRE Transactions on Electronic Computers . 8 (3). The Institute of Radio Engineers, Inc. (IRE): 335–339 . Bibcode : 1959IRTEC...8..335D . doi : 10.1109/TEC.1959.5222694 . ISSN 0367-9950 . EC-8(3):335–339 . Consultado el 2 de enero de 2016 . 
  15. ↑ Advanced Systems Group (6 de agosto de 1962), Descripción técnica del equipo de conexión para la toma de posiciones (informe), Fort Worth, Texas, EE. UU.: General Dynamics , FZE-052
  16. 1 2 Schmid, Hermann (1974). Cálculo decimal (1.ª ed.). Binghamton, Nueva York, EE. UU.: John Wiley & Sons, Inc. págs. 162 , 165–176 , 181–193 . ISBN   0-471-76180-XRecuperado el 3 de enero de 2016. Hasta ahora , se sabía que CORDIC solo se implementaba en formato binario. Pero, como se demostrará aquí, el algoritmo se puede modificar fácilmente para un sistema decimal.* […] *Mientras tanto, se ha sabido que Hewlett-Packard y otros fabricantes de calculadoras emplean las técnicas decimales de CORDIC en sus calculadoras científicas.
  17. 1 2 3 4 Leibson, Steven (2010). "El proyecto HP 9100: una reacción exotérmica" . Recuperado el 2 de enero de 2016 .
  18. 1 2 3 Meggitt, John E. (1961-08-29). "Procesos de pseudodivisión y pseudomultiplicación" (PDF) . IBM Journal of Research and Development . 6 (2). Riverton, Nueva Jersey, EE. UU.: IBM Corporation (publicado en abril de 1962): 210–226 , 287. doi : 10.1147/rd.62.0210 . Archivado del original (PDF) el 4 de febrero de 2022. Recuperado el 9 de enero de 2016. John E. Meggitt BA, 1953; PhD, 1958, Universidad de Cambridge . Galardonado con el Primer Premio Smith en Cambridge en 1955 y elegido becario de investigación en Emmanuel College . […] Se incorporó al Laboratorio Británico de IBM en Hursley, Winchester, en 1958. Sus intereses incluyen los códigos de corrección de errores y las pequeñas computadoras microprogramadas.(,)
  19. 1 2 3 Cochran, David S. (19-11-2010). "Un cuarto de siglo en HP" (manuscrito de entrevista). Museo de Historia de la Computación / HP Memories. 7: Calculadoras científicas, circa 1966. CHM X5992.2011 . Recuperado el 02-01-2016 . Incluso volé al sur de California para hablar con Jack Volder, quien había implementado las funciones trascendentales en la máquina Athena , y hablé con él durante aproximadamente una hora. Me remitió a los artículos originales de Meggitt, donde había obtenido las funciones generalizadas de pseudodivisión y pseudomultiplicación. […] Hice bastante investigación literaria que condujo a algunos descubrimientos muy interesantes. […] Encontré un tratado de 1624 de Henry Briggs que analizaba el cálculo de logaritmos comunes, y curiosamente utilizaba el mismo método de pseudodivisión/pseudomultiplicación que MacMillan y Volder utilizaron en Athena . […] Habíamos comprado un LOCI-2 a Wang Labs y nos dimos cuenta de que el Wang Labs LOCI II utilizaba el mismo algoritmo para calcular la raíz cuadrada, así como el logaritmo y la exponencial. Tras la presentación del 9100, nuestro departamento legal recibió una carta de Wang alegando que habíamos infringido su patente. Les respondí con una nota que incluía la referencia de Briggs en latín y decía: «Me parece que se trata de una técnica anterior ». No volvimos a saber nada de ellos. ()
  20. 1 2 Cochran, David S. (1966-03-14), Acerca de la utilización de CORDIC para el cálculo de funciones trascendentales en BCD (comunicación privada con Jack E. Volder)
  21. 1 2 Osborne, Thomas E. (2010) [1994]. "La historia de Tom Osborne en sus propias palabras" . Recuperado el 1 de enero de 2016 .
  22. ↑ Leibson, Steven (2010). "La HP 9100: El viaje inicial" . Recuperado el 2 de enero de 2016 .
  23. ↑ Cochran, David S. (septiembre de 1968). "Programación interna de la calculadora 9100A" . Hewlett-Packard Journal . Palo Alto, California, EE. UU.: Hewlett-Packard : 14–16 . Consultado el 2 de enero de 2016 .()
  24. ↑ Amplíe su capacidad de computación personal con el nuevo instrumento de computación logarítmica LOCI-1 , Wang Laboratories, Inc. , 1964, págs. 2–3 , consultado el 3 de enero de 2016. 
  25. ↑ Bensene, Rick (31-08-2013) [1997]. "Wang LOCI-2" . Museo Web de Calculadoras Antiguas . Beavercreek, Oregon City, Oregon, EE. UU . Recuperado el 03-01-2016 .
  26. ↑ "Manual de servicio de Wang LOCI" (PDF) . Wang Laboratories, Inc. 1967. L55-67 . Consultado el 14 de septiembre de 2018 .
  27. ↑ Bensene, Rick (23-10-2004) [1997]. "Sistema de calculadora Wang Modelo 360SE" . Museo Web de Calculadoras Antiguas . Beavercreek, Oregon City, Oregon, EE. UU . Recuperado el 3-01-2016 .
  28. 1 2 3 4 Cochran, David S. (junio de 2010). "El diseño de la HP-35, un estudio de caso en innovación" . Proyecto de memoria HP . Recuperado el 2 de enero de 2016. Durante el desarrollo de la calculadora de escritorio HP 9100, fui responsable de desarrollar los algoritmos para que se ajustaran a la arquitectura sugerida por Tom Osborne. Aunque la metodología sugerida para los algoritmos provino de Malcolm McMillan, leí una cantidad considerable para comprender los cálculos centrales […] Aunque Wang Laboratories había utilizado métodos de cálculo similares, mi estudio encontró arte previo que data de 1624 que se basaba en sus patentes. […] Esta investigación permitió la adaptación de las funciones trascendentales a través del uso de los algoritmos para satisfacer las necesidades del cliente dentro de las limitaciones del hardware. Esto resultó invaluable durante el desarrollo de la HP-35 , […] Se consideraron series de potencias , expansiones polinómicas , fracciones continuas y polinomios de Chebyshev para las funciones trascendentales. Todos eran demasiado lentos debido a la cantidad de multiplicaciones y divisiones requeridas. El algoritmo generalizado que mejor se ajustaba a los requisitos de velocidad y eficiencia de programación para la HP-35 era un método iterativo de pseudo-división y pseudo-multiplicación descrito por primera vez en 1624 por Henry Briggs en ' Aritmética Logarítmica ' y posteriormente por Volder y Meggitt. Este es el mismo tipo de algoritmo que se utilizó en las calculadoras de escritorio HP anteriores. […] La complejidad de los algoritmos hizo que la programación multinivel fuera necesaria. Esto significaba que la calculadora debía tener capacidad de subrutinas, […] Para generar una función trascendental como Arco-Hiperbólico-Tan se requerían varios niveles de subrutinas. […] Chris Clare documentó posteriormente esto como metodología de Máquina de Estados Algorítmica (ASM). Incluso el simple Seno o Coseno utilizaba la rutina Tangente y luego calculaba el Seno a partir de identidades trigonométricas. Estas arduas manipulaciones eran necesarias para minimizar la cantidad de programas únicos y pasos de programa […] El conjunto de instrucciones aritméticas fue diseñado específicamente para una calculadora de funciones trascendentales decimales. Las operaciones aritméticas básicas las realiza un sumador-restador de complemento a diez que tiene rutas de datos a tres de los registros que se utilizan como almacenamiento de trabajo.
  29. ↑ Patente estadounidense 3402285A , Wang, An , "Aparato de cálculo", publicada el 17 de septiembre de 1968, emitida el 17 de septiembre de 1968, asignada a Wang Laboratories  (,)
  30. ^ Patente DE 1499281B1 , Wang, An , "Rechenmaschine fuer logarithmische Rechnungen", publicado el 6 de mayo de 1970, emitido el 6 de mayo de 1970, asignado a Wang Laboratories ( )
  31. ↑ Swartzlander, Jr., Earl E. (1990). Aritmética computacional . Vol. 1 (2.ª ed.). Los Alamitos: IEEE Computer Society Press . ISBN   9780818689314. 0818689315 . Consultado el 2 de enero de 2016 .
  32. ↑ Petrocelli, Orlando R., ed. (1972), Los mejores artículos sobre informática de 1971 , Auerbach Publishers , pág. 71, ISBN  0877691274, recuperado el 2 de enero de 2016
  33. ↑ Cochran, David S. (junio de 1972). "Algoritmos y precisión en la HP-35" (PDF) . Hewlett-Packard Journal . 23 (10): 10– 11. Archivado del original (PDF) el 4 de octubre de 2013. Consultado el 2 de enero de 2016 .
  34. ↑ Laporte, Jacques (2005-12-06). "HP35 trigonometric algorithm" . París, Francia. Archivado del original el 2015-03-09 . Recuperado el 2016-01-02 .Archivado el 10 de agosto de 2020 en Wayback Machine .
  35. ↑ Laporte, Jacques (febrero de 2005) [1981]. "El secreto de los algoritmos" . L'Ordinateur Individuel (24). París, Francia. Archivado del original el 18 de agosto de 2016. Consultado el 2 de enero de 2016 .Archivado el 12 de junio de 2021 en Wayback Machine.
  36. ↑ Laporte, Jacques (febrero de 2012) [2006]. "Métodos dígito por dígito" . París, Francia. Archivado del original el 18 de agosto de 2016. Consultado el 2 de enero de 2016 .Archivado el 12 de junio de 2021 en Wayback Machine.
  37. ↑ Laporte, Jacques (febrero de 2012) [2007]. "HP 35 Logarithm Algorithm" . París, Francia. Archivado del original el 18 de agosto de 2016. Consultado el 7 de enero de 2016 .Archivado el 10 de agosto de 2020 en Wayback Machine .
  38. ↑ Wang, Yuxuan; Luo, Yuanyong; Wang, Zhongfeng; Shen, Qinghong; Pan, Hongbing (enero de 2020). "Arquitectura basada en GH CORDIC para el cálculo de la raíz enésima de un número de punto flotante de precisión simple". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 28 (4): 864– 875. doi : 10.1109/TVLSI.2019.2959847 . S2CID 212975618 . 
  39. ↑ Mopuri, Suresh; Acharyya, Amit (septiembre de 2019). "Metodología de diseño de arquitectura VLSI genérica de baja complejidad para cálculos de raíz enésima y potencia enésima". IEEE Transactions on Circuits and Systems I: Regular Papers . 66 (12): 4673– 4686. doi : 10.1109/TCSI.2019.2939720 . S2CID 203992880 . 
  40. ↑ Vachhani, Leena (noviembre de 2019). "CORDIC como un sistema no lineal conmutado". Circuitos, sistemas y procesamiento de señales . 39 (6): 3234– 3249. doi : 10.1007/s00034-019-01295-8 . S2CID 209904108 . 
  41. ↑ Schmid, Hermann ; Bogacki, Anthony (20 de febrero de 1973). "Use Decimal CORDIC for Generation of Many Transcendental Functions". EDN : 64–73 .
  42. ↑ Franke, Richard (8 de mayo de 1973). Un análisis de algoritmos para la evaluación de hardware de funciones elementales (PDF) . Monterey, California, EE. UU.: Departamento de la Marina , Escuela Naval de Posgrado . NPS-53FE73051A . Recuperado el 3 de enero de 2016 .
  43. 1 2 3 4 5 Muller, Jean-Michel (2006). Funciones elementales: algoritmos e implementación (2.ª ed.). Boston: Birkhäuser . pág. 134. ISBN   978-0-8176-4372-0LCCN 2005048094. Consultado el 1 de diciembre de 2015 . 
  44. 1 2 Nave, Rafi (marzo de 1983). "Implementación de funciones trascendentales en un procesador numérico". Microprocesamiento y microprogramación . 11 ( 3–4 ): 221–225 . doi : 10.1016/0165-6074(83)90151-5 .
  45. ↑ Palmer, John F.; Morse, Stephen Paul (1984). The 8087 Primer (1.ª ed.). John Wiley & Sons Australia, Limited . ISBN  0471875694. 9780471875697 . Consultado el 2 de enero de 2016 .
  46. ↑ Glass, L. Brent (enero de 1990). "Coprocesadores matemáticos: una mirada a lo que hacen y cómo lo hacen". Byte . 15 (1): 337– 348. ISSN 0360-5280 . 
  47. 1 2 3 Jarvis, Pitts (1990-10-01). "Implementación de algoritmos CORDIC: una única rutina compacta para el cálculo de funciones trascendentales" . Dr. Dobb's Journal : 152–156 . Archivado del original el 4 de marzo de 2016. Recuperado el 2 de enero de 2016 .
  48. 1 2 Yuen, AK (1988). "Procesadores de punto flotante de Intel". Electro/88 Conference Record : 48/5/1–7.
  49. ↑ Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (22 de agosto de 2008). "50 años de CORDIC: algoritmos, arquitecturas y aplicaciones" (PDF) . IEEE Transactions on Circuits and Systems I: Regular Papers . 56 (9) (publicado el 9 de septiembre de 2009): 1893–1907 . doi : 10.1109/TCSI.2009.2025803 . S2CID 5465045 . 
  50. ↑ Meher, Pramod Kumar; Park, Sang Yoon (febrero de 2013). "Metodología de diseño de arquitectura VLSI genérica de baja complejidad para cálculos de raíz enésima y potencia enésima". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 21 (2): 217– 228. doi : 10.1109/TVLSI.2012.2187080 . S2CID 7059383 . 
  51. ↑ Heffron, WG; LaPiana, F. (1970-12-11). "Memorando técnico 70-2014-8: El sistema de navegación del vehículo lunar" (PDF) . NASA . Washington, DC, EE. UU.: Bellcomm . pág. 14. 
  52. ↑ Smith, Earnest C.; Mastin, William C. (noviembre de 1973). "Nota técnica D-7469: Revisión del rendimiento del sistema de navegación del vehículo lunar" (PDF) . NASA . Huntsville, Alabama, EE. UU.: Centro de Vuelos Espaciales Marshall . pág. 17. 
  53. ↑ Shirriff, Ken (mayo de 2020). "Extracción de constantes ROM del chip del coprocesador matemático 8087" . righto.com . Consultado el 3 de septiembre de 2020. La ROM contiene 16 valores de arcotangente, las arctangentes de 2 −n . También contiene 14 valores de logaritmo, los logaritmos en base 2 de (1+2 −n ). Estos valores pueden parecer inusuales, pero se utilizan en un algoritmo eficiente llamado CORDIC, inventado en 1958.
  54. ↑ "Primeros pasos con el acelerador CORDIC usando el paquete de microcontrolador STM32CubeG4" (PDF) . STMicroelectronics . Consultado el 1 de enero de 2021 .
  55. ↑ "CMSIS/CMSIS/DSP_Lib/Source/ControllerFunctions/arm_sin_cos_f32.c" . Github . ARM . Consultado el 1 de enero de 2021 .
  56. ↑ "Límites de error de la expansión de Taylor para el seno" . Math Stack Exchange . Consultado el 1 de enero de 2021 .
  57. ↑ Andraka, Ray (1998). "Un estudio de los algoritmos CORDIC para computadoras basadas en FPGA". Actas del sexto simposio internacional ACM/SIGDA de 1998 sobre matrices de puertas programables en campo - FPGA '98 . págs. 191–200 . doi : 10.1145/275107.275139 . ISBN  0-89791-978-5.
  58. ↑ "Matemáticas de clase" . Estándar de la plataforma Java (8.ª ed.). Oracle Corporation . 2018 [1993]. Archivado del original el 6 de agosto de 2018. Recuperado el 6 de agosto de 2018 . 
  59. ↑ "ldexp, ldexpf, ldexpl" . cppreference.com . 11 de junio de 2015. Archivado del original el 6 de agosto de 2018. Consultado el 6 de agosto de 2018 .
  60. ↑ "Sección 8.3.9 Logarítmica, exponencial y escala". Manual del desarrollador de software de las arquitecturas Intel 64 e IA-32, Volumen 1: Arquitectura básica (PDF) . Intel Corporation . Septiembre de 2016. págs. 8–22 . 
  61. ↑ Baykov, Vladimir. "El esquema (autorefrat) de mi tesis doctoral, publicada en 1972" . baykov.de . Consultado el 3 de mayo de 2023 .
  62. ↑ Baykov, Vladimir. "Implementación de hardware de funciones elementales en computadoras" . baykov.de . Consultado el 3 de mayo de 2023 .
  63. 1 2 Baykov, Vladimir. "Procesadores de propósito especial: algoritmos y estructuras iterativas" . baykov.de . Consultado el 3 de mayo de 2023 .

Lecturas adicionales

  • Parini, Joseph A. (5 de septiembre de 1966). "DIVIC da respuesta a preguntas complejas de navegación". Electronics : 105–111 . ISSN 0013-5070 . (Nota: DIVIC significa Computadora Digital de Incrementos Variables . Algunas fuentes se refieren erróneamente a ella como obra de JM Parini ).
  • Anderson, Stanley F.; Earle, John G.; Goldschmidt, Robert Elliott; Powers, Don M. (1965-11-01). "The IBM System/360 Model 91: Floating-Point Execution Unit" (PDF) . IBM Journal of Research and Development . 11 (1). Riverton, Nueva Jersey, EE. UU. (publicado en enero de 1967): 34–53 . doi : 10.1147/rd.111.0034 . Archivado del original (PDF) el 5 de marzo de 2016. Recuperado el 2 de enero de 2016 .
  • Liccardo, Michael A. (septiembre de 1968). Un procesador de interconexión con énfasis en el funcionamiento en modo CORDIC (tesis de maestría). Berkeley, CA, EE. UU.: Universidad de California, Berkeley , Departamento de Ingeniería Eléctrica. OCLC 500565168 . 
  • Patente estadounidense 3576983A , Cochran, David S., "Sistema de calculadora digital para calcular raíces cuadradas", publicada el 4 de mayo de 1971, emitida el 4 de mayo de 1971, asignada a Hewlett-Packard Co.  ()
  • Chen, Tien Chi (julio de 1972). "Cálculo automático de exponenciales, logaritmos, razones y raíces cuadradas" (PDF) . IBM Journal of Research and Development . 16 (4): 380–388 . doi : 10.1147/rd.164.0380 . ISSN 0018-8646 . Archivado del original (PDF) el 12 de agosto de 2016. Consultado el 2 de enero de 2016 . 
  • Egbert, William E. (mayo de 1977). "Algoritmos de calculadora personal I: raíces cuadradas" (PDF) . Hewlett-Packard Journal . 28 (9). Palo Alto, California, EE. UU.: Hewlett-Packard : 22–24 . Archivado del original (PDF) el 18 de diciembre de 2015. Consultado el 2 de enero de 2016 .()
  • Egbert, William E. (junio de 1977). "Algoritmos de calculadora personal II: funciones trigonométricas" (PDF) . Hewlett-Packard Journal . 28 (10). Palo Alto, California, EE. UU.: Hewlett-Packard : 17–20 . Archivado del original (PDF) el 4 de marzo de 2016. Consultado el 2 de enero de 2016 .()
  • Egbert, William E. (November 1977). "Personal Calculator Algorithms III: Inverse Trigonometric Functions"(PDF). Hewlett-Packard Journal. 29 (3). Palo Alto, California, USA: Hewlett-Packard: 22–23. Archived from the original(PDF) on 2016-03-04. Retrieved 2016-01-02. ()
  • Egbert, William E. (April 1978). "Personal Calculator Algorithms IV: Logarithmic Functions"(PDF). Hewlett-Packard Journal. 29 (8). Palo Alto, California, USA: Hewlett-Packard: 29–32. Archived from the original(PDF) on 2016-03-04. Retrieved 2016-01-02. ()
  • Senzig, Don (1975). "Calculator Algorithms". IEEE Compcon Reader Digest. IEEE: 139–141. IEEE Catalog No. 75 CH 0920-9C.
  • Baykov, Vladimir D. (1972), Вопросы исследования вычисления элементарных функций по методу «цифра за цифрой»[Problems of elementary functions evaluation based on digit by digit (CORDIC) technique] (PhD thesis) (in Russian), Leningrad State University of Electrical Engineering
  • Baykov, Vladimir D.; Smolov, Vladimir B. (1975). Apparaturnaja realizatsija elementarnikh funktsij v CVMАппаратурная реализация элементарных функций в ЦВМ[Hardware implementation of elementary functions in computers] (in Russian). Leningrad State University. Archived from the original on 2019-03-02. Retrieved 2019-03-02.
  • Baykov, Vladimir D.; Seljutin, S. A. (1982). Вычисление элементарных функций в ЭКВМ[Elementary functions evaluation in microcalculators] (in Russian). Moscow: Radio i svjaz (Радио и связь).
  • Baykov, Vladimir D.; Smolov, Vladimir B. (1985). Специализированные процессоры: итерационные алгоритмы и структуры[Special-purpose processors: iterative algorithms and structures] (in Russian). Moscow: Radio i svjaz (Радио и связь).
  • Coppens, Thomas, ed. (January 1980). "CORDIC constants in TI 58/59 ROM". Texas Instruments Software Exchange Newsletter. 2 (2). Kapellen, Belgium: TISOFT.
  • Coppens, Thomas, ed. (April–June 1980). "Natural logarithm computation scheme / ex computing scheme / 1/x computing scheme". Texas Instruments Software Exchange Newsletter. 2 (3). Kapellen, Belgium: TISOFT.(sobre CORDIC en TI-58 / TI-59 )
  • Equipo de Productos Gráficos de TI (1995) [1993]. "Algoritmos de funciones trascendentales" . Dallas, Texas, EE. UU.: Texas Instruments , Productos de Consumo. Archivado del original el 17 de marzo de 2016. Consultado el 2 de marzo de 2019 .
  • Jorke, Günter; Lampe, Bernhard; Wengel, Norberto (1989). Arithmetische Algorithmen der Mikrorechentechnik (en alemán) (1  ed.). Berlín, Alemania: VEB Verlag Technik . págs.  219, 261, 271-296 . ISBN 3341005153EAN 9783341005156. MPN 5539165. Licencia 201.370/4/89 . Consultado el 1 de diciembre de 2015 . 
  • Zechmeister, M. (2021). "Resolver la ecuación de Kepler con dobles iteraciones CORDIC" . Avisos mensuales de la Real Sociedad Astronómica . 500 (1). Göttingen, Alemania: Institut für Astrophysik, Georg-August-Universität: 109– 117. arXiv : 2008.02894 . doi : 10.1093/mnras/staa2441 .
  • Frerking, Marvin E. (1994). Procesamiento digital de señales en sistemas de comunicación (1.ª  ed.).
  • Kantabutra, Vitit (1996). "Sobre hardware para el cálculo de funciones exponenciales y trigonométricas". IEEE Transactions on Computers . 45 (3): 328– 339. Bibcode : 1996ITCmp..45..328K . doi : 10.1109/12.485571 .
  • Johansson, Kenny (2008). "6.5 Funciones de seno y coseno". Cálculos basados ​​en desplazamiento y suma de baja potencia y baja complejidad (PDF) (tesis doctoral). Estudios de Linköping en ciencia y tecnología (1.ª  ed.). Linköping, Suecia: Departamento de Ingeniería Eléctrica, Universidad de Linköping . pp. 244–250 . ISBN  978-91-7393-836-5ISSN 0345-7524 . N.° 1201. Archivado (PDF) del original el 13 de agosto de 2017. Consultado el 23 de agosto de 2021 . (x+268 páginas)
  • Banerjee, Ayan (2001). "Realización en FPGA de un procesador FFT basado en CORDIC para el procesamiento de señales biomédicas". Microprocessors and Microsystems . 25 (3). Kharagpur, Bengala Occidental, India: 131– 142. doi : 10.1016/S0141-9331(01)00106-5 .
  • Kahan, William Morton (2002-05-20). "Algoritmos de pseudodivisión para logaritmos y exponenciales de punto flotante" (PDF) . Berkeley, CA, EE. UU.: Universidad de California . Archivado del original (PDF) el 25-12-2015 . Recuperado el 15-01-2016 .
  • Cockrum, Chris K. (Otoño de 2008). "Implementación de un algoritmo CORDIC en un convertidor descendente digital" (PDF) .
  • Lakshmi, Boppana; Dhar, Anindya Sundar (06-10-2009). "Arquitecturas CORDIC: una revisión" . Diseño VLSI . 2010. Kharagpur, Bengala Occidental, India: Departamento de Ingeniería Electrónica y de Comunicaciones Eléctricas, Instituto Indio de Tecnología (publicado el 10-10-2010): 1–19 . doi : 10.1155/2010/794891 . 794891.
  • Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .
  • Wang, Shaoyun (julio de 2011), Sitio de bibliografía de CORDIC , archivado del original el 17 de octubre de 2000 – vía Chandra, Departamento de Ingeniería Eléctrica e Informática, Escuela de Ingeniería Cockrell, Universidad de Texas en Austin
  • IP CORDIC flexible (código HDL Verilog)
  • Sitio web de la bibliografía de CORDIC
  • Implementación matemática de BASIC Stamp y CORDIC.
  • Implementación de CORDIC en Verilog
  • Vectorización CORDIC con valor objetivo arbitrario
  • Implementación de CORDIC en Python. Archivada el 17 de marzo de 2017 en Wayback Machine.
  • Código C simple para CORDIC de punto fijo
  • Tutorial e implementación en MATLAB: uso de CORDIC para estimar la fase de un número complejo (archive.org)
  • Descripciones de los circuitos integrados de hardware CORDIC en Arx con bancos de pruebas en C++ y VHDL.
  • Introducción al algoritmo CORDIC
  • Implementación del algoritmo CORDIC en un convertidor descendente digital.
  • Implementación del algoritmo CORDIC: código C de punto fijo para funciones trigonométricas e hiperbólicas , código C para pruebas y verificación del rendimiento.
Obtenido de " https://en.wikipedia.org/w/index.php?title=CORDIC&oldid=1362284203 "
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Funciones trigonométricasBase de la trigonometría: si dos triángulos rectángulos tienen ángulos agudos iguales , son semejantes , por lo que las longitudes de sus lados cor...Funciones hiperbólicasFunciones hiperbólicasEn matemáticas , las funciones hiperbólicas son análogas a las funciones trigonométricas ordinarias , pero definidas utilizando la hipérbola en lug...Raíz cuadradaRaíz cuadradaEn matemáticas , una raíz cuadrada de un número x es un número y tal que ; en otras palabras, un número y cuyo cuadrado (el resultado de multiplica...MultiplicaciónMultiplicaciónCuatro bolsas con tres canicas por bolsa dan doce canicas (4 × 3 = 12). La multiplicación también puede considerarse como una operación de escalado...División (matemáticas)División (matemáticas)La división es una de las cuatro operaciones básicas de la aritmética . Las otras operaciones son la suma , la resta y la multiplicación . Lo que s...