CÓRDICO

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de octubre de 2017; las comprobaciones requieren 19 ediciones .

CORDIC ( método CORDIC del inglés. Computadora digital de rotación de coordenadas: una computadora digital para rotar el sistema de coordenadas; el método "dígito por dígito" , algoritmo de Walder ) es un método iterativo para reducir los cálculos directos de funciones complejas a realizar operaciones simples de suma y cambio .

Idea de método

La idea del método es reducir el cálculo de los valores de funciones complejas (por ejemplo, hiperbólicas ) a un conjunto de pasos simples: suma y desplazamiento.

Este enfoque es especialmente útil cuando se calculan funciones en dispositivos con capacidades informáticas limitadas, como microcontroladores o matrices lógicas programables ( FPGA ). Además, dado que los pasos son del mismo tipo, la implementación de hardware del algoritmo se puede expandir en una canalización o colapsar en un bucle.

Historia

El método fue descrito por primera vez en aplicación al cálculo de funciones trigonométricas y operaciones de transformación de coordenadas por Jack Walder en 1956 y luego en 1959 . En 1956, Akushsky y Yuditsky propusieron una idea similar para calcular funciones exponenciales y logarítmicas. Inicialmente, una idea cercana a esta fue propuesta por Henry Briggs en 1624 cuando estaba compilando tablas de logaritmos .

El método se ha utilizado en la implementación de algunos tipos de instrucciones de punto flotante en los coprocesadores matemáticos de Intel , incluido el 8087 [1] [2] [3] [4] [5] , 80287 [5] [6] , 80387 [5 ] [6] y hasta 80486 [1] , así como en los coprocesadores Motorola 68881 [1] [2] y 68882. Esto permitió reducir el número de elementos lógicos (y la complejidad) del coprocesador.

Método de Briggs

La idea general del método es la siguiente. Mediante la multiplicación sucesiva del argumento por constantes preseleccionadas, acerque el argumento a uno con una precisión dada para algunas funciones y a cero para otras funciones. Sin embargo, para que el valor de la función en sí permanezca sin cambios, es necesario realizar simultáneamente acciones equivalentes en las constantes elegidas. Al elegir los valores de las constantes de una manera especial, es posible simplificar significativamente el cálculo de los valores de la función.

Por ejemplo, Briggs multiplicó el valor del argumento de la función de logaritmo decimal por constantes de la forma: o . $\registro X$ $1+10^{{-yo}}$ $1-10^{{-yo}}$

En este caso, la elección del primer multiplicador ( ) se realizaba si el valor actual de la cantidad resultaba menor que uno, y el segundo , si el valor actual era mayor que uno. Al elegir sucesivamente los valores del exponente de 1 a , donde estaba el error de cálculo máximo permitido, Briggs redujo el valor a uno con la precisión requerida y, por lo tanto, el valor de la función a cero. $1+10^{{-yo}}$ $X$ $X$ $norte$ $10^{{-N}}$ $X$ $\registro X$

Sin embargo, para la equivalencia de estas transformaciones, es necesario dividir el valor indicado por el mismo valor simultáneamente con la multiplicación del actual. Pero, como sabes, el logaritmo del cociente es igual a la diferencia entre los logaritmos del numerador y el denominador. Por lo tanto, simultáneamente con la multiplicación de la corriente por es necesario restar la función previamente calculada del logaritmo del valor del producto del argumento por el factor . $X$ $1+10^{{-yo}}$ $X$ $1+10^{{-yo}}$ $1+10^{{-yo}}$ $X$ $1+10^{{-yo}}$

Los valores de todas las constantes de la forma y se pueden calcular de antemano, ya que hay relativamente pocos de ellos. Por ejemplo, con un error aceptable, solo hay doce. $1+10^{{-yo}}$ $1-10^{{-yo}}$ $10^{-6}$

Queda por aclarar que la multiplicación por constantes de la forma e se reduce a operaciones de suma, resta y traslado de una coma (desplazamiento). $1+10^{{-yo}}$ $1-10^{{-yo}}$

Por tanto, el procedimiento para calcular la función logaritmo de Briggs se reduce a las operaciones de suma, resta y desplazamiento decimal.

La generalización de la idea del método de Briggs a números complejos se llevó a cabo a mediados de los años cincuenta por Jack Walder y casi simultáneamente con él por Akushsky y Yuditsky. Esto hizo posible calcular funciones trigonométricas.

Horario de apertura

CORDIC se puede utilizar para calcular una serie de 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. Se supone que el ángulo deseado se da en radianes y los resultados están en formato de punto fijo . Para determinar el seno o el coseno de un ángulo , se deben encontrar las coordenadas de un punto y o x en el círculo unitario de acuerdo con el ángulo deseado. Usando CORDIC, comenzamos con un vector : $\beta$ $v_{0}$

v_{0}={\begin{pmatrix}1\\0\end{pmatrix}}

En la primera iteración , este vector se girará 45° en sentido contrario a las agujas del reloj para obtener el vector . Las iteraciones sucesivas rotarán el vector en una dirección u otra en incrementos decrecientes hasta alcanzar el ángulo deseado. El valor del i -ésimo paso es arctg(1/(2 i −1 )), para i = 1, 2, 3, …. $v_{1}$

Más formalmente, en cada iteración se calcula la rotación, que se realiza multiplicando el vector por la matriz de rotación : $v_{{i-1}}$ $Rhode Island}$

v_{{i}}=R_{{i}}v_{{i-1}}\

Las matrices de rotación R están determinadas por la fórmula:

R_{{i}}=\left({\begin{matriz}{rr}\cos \gamma _{{i}}&-\sin \gamma _{{i}}\\\sin \gamma _{{ i}}&\cos \gamma _{{i}}\end{matriz}}\right)

Usando las siguientes dos identidades trigonométricas

{\begin{alineado}\cos \alpha &=&{1 \over {\sqrt {1+\operatorname {tg} ^{2}\alpha }}}\\\sin \alpha &=&{ {\nombre del operador {tg} \alpha } \over {\sqrt {1+\nombre del operador {tg} ^{2}\alpha }}}\end{alineado}}

obtenemos la matriz de rotación:

R_{i}={1 \over {\sqrt {1+\operatorname {tg} ^{2}\gamma _{i)))){\begin{pmatrix}1&-\operatorname {tg} \ gamma _{i}\\\nombre del operador {tg} \gamma _{i}&1\end{pmatrix}}

Expresión para vector rotado : $v_{i}=R_{i}v_{{i-1}}$

v_{i}={1 \over {\sqrt {1+\operatorname {tg} ^{2}\gamma _{i)))){\begin{pmatrix}x_{i-1}&- &y_{i-1}\nombre del operador {tg} \gamma _{i}\\x_{i-1}\nombre del operador {tg} \gamma _{i}&+&y_{i-1}\end{pmatrix}}

donde y son los componentes . Al limitar los valores de los ángulos para que tome valores, la multiplicación por la tangente se puede reemplazar por la división por una potencia de dos, que se implementa de manera eficiente en el hardware de la computadora digital mediante el cambio de bits . Obtenemos la expresión: $x_{{i-1}}$ $y_{{i-1}}$ $v_{{i-1}}$ $\gamma _{{i}}$ ${\ estilo de visualización \ nombre del operador {tg} \ gamma _ {i}}$ $\pm 2^{{-yo}}$

v_{i}=K_{i}{\begin{pmatrix}x_{{i-1}}&-&\sigma _{i}2^{{-i}}y_{{i-1}}\\ \sigma _{i}2^{{-i}}x_{{i-1}}&+&y_{{i-1}}\end{pmatriz}}

dónde

K_{i}={1 \over {\sqrt {1+2^{{-2i))))}

y puede tener los valores −1 o 1 y se usa para determinar la dirección de rotación: si el ángulo es positivo entonces es igual a 1, de lo contrario es igual a −1. $\sigma_i$ ${\ estilo de visualización \ gamma _ {i}}$ $\sigma_i$

Podemos ignorarlo iterativamente y luego aplicarlo para obtener el factor de escala: $K_{yo}$

K(n)=\prod_{{i=0}}^{{n-1}}K_{i}=\prod_{{i=0}}^{{n-1}}1/{\ sqrt {1+2^{{-2i}}}}

que se calcula de antemano y se almacena en una tabla, o como una sola constante si el número de iteraciones es fijo. Esta corrección también se puede hacer por adelantado escalando . $v_{0}$

La única tarea que queda es determinar si se debe realizar una rotación en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj en cada iteración (eligiendo un valor de ). Esto se hace haciendo un seguimiento de la cantidad de rotación en cada iteración y restando del ángulo deseado, luego verificando si es positivo, entonces debemos rotar en el sentido de las agujas del reloj o si es negativo, debemos rotar en el sentido contrario a las agujas del reloj para acercarnos al ángulo . $\sigma$ $\beta _{{n+1}}$ $\beta$

\beta_{i}=\beta_{i-1}-\sigma_{i}\gamma_{i}.\quad \gamma_{i}=\operatorname {arctg} 2^{- i},

Los valores también deben calcularse por adelantado. Pero para ángulos pequeños en representación de punto fijo, lo que permite reducir el tamaño de la tabla. $\gamma_n$ ${\ estilo de visualización \ nombre del operador {arctg} (\ gamma _ {n}) = \ gamma _ {n}}$

Como puede ver en la ilustración anterior, el seno del ángulo es la coordenada y del vector final y la coordenada x es el valor del coseno. $\beta$ $v_{n}$

El método de las "dobles iteraciones"

En los trabajos [7] y [8] se propuso utilizar el método de las "dobles iteraciones" para el cálculo de las funciones arcsinX, arccosX, lnX, expX, así como para el cálculo de funciones hiperbólicas . Consiste en el hecho de 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, con el método de iteraciones dobles, el valor del paso de iteración se repite dos veces y cambia solo después de una iteración. Así apareció la notación para el exponente para iteraciones dobles: i = 1,1,2,2,3,3... Mientras que para iteraciones ordinarias: i =1,2,3... El método de iteraciones dobles garantiza la convergencia del método en todo el rango permitido de cambios de argumento.

La generalización de los temas de convergencia de algoritmos del método CORDIC a un sistema numérico posicional arbitrario con base R, dada en [9] , mostró que para las funciones sin, cos, arctg, es suficiente realizar (R-1) -iteraciones para cada valor de i (i de 0 o 1 a n, donde n es el número de dígitos), es decir para cada dígito del resultado. Para las funciones ln, exp, sh, ch, arth, R se deben realizar iteraciones para cada valor de i. Para las funciones arcsen y arccos, se deben realizar 2 ⋅ (R-1) iteraciones por bit, es decir para cada valor de i.

Para las funciones arsh, arch, el número de iteraciones será 2R para cada i, es decir para cada dígito del resultado.

Literatura

Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers , septiembre de 1959
Daggett, D.H., Conversiones decimales-binarias en CORDIC , IRE Transactions on Electronic Computers, vol. EC-8 #5, págs. 335–339, IRE, septiembre de 1959.
JE Meggitt, Pseudo Division and Pseudo Multiplication Processes , IBM Journal, abril de 1962.
Baikov V. D. Preguntas de investigación del cálculo de funciones elementales por el método "dígito por dígito" , resumen de la disertación para el grado de candidato de ciencias técnicas, Leningrado, LETI, 1972
Schmid, Hermann, Cálculo decimal. Nueva York, Wiley, 1974
Baikov V. D., Smolov V. B. Implementación de hardware de funciones elementales en una computadora digital , Leningrado, Universidad Estatal de Leningrado, 1975, 96 páginas.
Baikov V. D., Selyutin S. A., Cálculo de funciones elementales en la computadora , Moscú, Radio y comunicación, 1982, 64 páginas.
Baikov V. D., Smolov V. B. Procesadores especializados: estructuras y algoritmos iterativos , Moscú, Radio and Communications, 1985, 288 pp.
Andraka, Ray, Una encuesta de algoritmos CORDIC para computadoras basadas en FPGA
Henry Briggs, Arithmetica Logarithmica. Londres, 1624, folio
M. Zechmeister Resolución de la ecuación de Kepler con iteraciones dobles de CORDIC Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Alemania, Preprint 10 de agosto de 2020, p.1-10.
Tomás Lang y Elisardo Antelo Computación basada en CORDIC de ArcCos Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology volumen 25, páginas 19–38 (2000)
Vladimir Baykov Iteraciones dobles en CORDIC Bibliografía de CORDIC
Métodos dígito a dígito , Jacques Laporte, París 2006 (la filiation entre CORDIC et les anciennes méthodes notamment celle de Briggs)
Z. S. Kuzin, A. E. Sazonov, G. E. Kukharev, L. P. Dyukova, L. K. Novak, Vector Processor , Comité Estatal de Invenciones y Descubrimientos de la URSS, certificado No. 849228 (61), P1 M K 3 (22) declarado el 12.10.79 (23) 2832743/18 -24, G 06 F 15/347 con anexo de la demanda, [1]
Z. S. Kuzin, Procesador para calcular funciones elementales , Comité Estatal de Invenciones y Descubrimientos de la URSS, certificado No. 888131 (61), declarado el 11.11.79 (21) 2842574/18-24, [2]
Z. S. Kuzin, Un algoritmo ultrarrápido para calcular la transformada de Fourier, Wissenschaftliche Beiträge, Heft 4/81 (1981) pp 22–26 (en ruso)
Sitio de bibliografía de CORDIC , Shaoyun Wang, julio de 2011
Sitio de bibliografía de CORDIC

Notas

↑ 1 2 3 Müller Jean-Michel. Funciones elementales: algoritmos e implementación . - 2 edición. - Boston: Birkhäuser, 2006. - Pág. 134. - ISBN 978-0-8176-4372-0 . Archivado el 5 de junio de 2011 en Wayback Machine .
↑ 1 2 Rafi Nave. Implementación de Funciones Trascendentales en un Procesador Numérico // Microprocesamiento y Microprogramación. - 1983. - T. 11 , N° 3-4 . — S. 221–225 .
↑ John F. Palmer, Stephen Paul Morse. La cartilla 8087 . - John Wiley & Sons Australia, Limited, 1984. - ISBN 9780471875697 . Archivado el 30 de diciembre de 2016 en Wayback Machine .
↑ Vidrio L. Brent. Coprocesadores matemáticos: una mirada a lo que hacen y cómo lo hacen // Byte Magazine. - 1990. - T. 15 , N º 1 . — S. 337–348 . — ISSN 0360-5280 .
↑ 1 2 3 Pitts Jarvis. Implementación de algoritmos CORDIC: una sola rutina compacta para calcular funciones trascendentales // Dr. Diario Dobbs. - 1990. - T. 15 , N º 10 . — S. 152–156 .
↑ 1 2 AK Yuen. Procesadores de coma flotante de Intel // Electro/88 Conference Record. - 1988. - S. 48/5/1-7 .
↑ Implementación hardware de las funciones elementales mediante la técnica dígito a dígito (CORDIC) . Consultado el 24 de diciembre de 2020. Archivado desde el original el 11 de enero de 2011. (indefinido)
↑ Baikov V.D., Smolov V.B. Implementación de hardware de funciones elementales en una computadora digital . Consultado el 24 de diciembre de 2020. Archivado desde el original el 15 de enero de 2011. (indefinido)
↑ Baikov V.D., Smolov V.B. Procesadores especializados: estructuras y algoritmos iterativos . Consultado el 29 de diciembre de 2020. Archivado desde el original el 18 de julio de 2011. (indefinido)