CORDIC

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 2 octombrie 2017; verificările necesită 19 modificări .

CORDIC ( Metoda CORDIC din engleză. Coordinate Rotation DIgital Computer - un computer digital pentru rotirea sistemului de coordonate; metoda „cifră cu cifră” , algoritmul lui Walder ) este o metodă iterativă pentru reducerea calculelor directe ale funcțiilor complexe la efectuarea de operații simple de adăugare și schimbare . .

Ideea metodei

Ideea metodei este de a reduce calculul valorilor funcțiilor complexe (de exemplu, hiperbolice ) la un set de pași simpli - adăugare și schimbare.

Această abordare este utilă în special atunci când se calculează caracteristici pe dispozitive cu capacități de calcul limitate, cum ar fi microcontrolere sau matrice logice programabile ( FPGA ). În plus, deoarece pașii sunt de același tip, implementarea hardware a algoritmului poate fi extinsă într-o conductă sau prăbușită într-o buclă.

Istorie

Metoda a fost descrisă pentru prima dată în aplicarea la calculul funcţiilor trigonometrice şi a operaţiilor de transformare a coordonatelor de către Jack Walder în 1956 , apoi în 1959 . În 1956, Akushsky și Yuditsky au prezentat o idee similară pentru calcularea funcțiilor exponențiale și logaritmice. Inițial, o idee apropiată de aceasta a fost propusă de Henry Briggs în 1624 , când compila tabele de logaritmi .

Metoda a fost folosită în implementarea unor tipuri de instrucțiuni în virgulă mobilă în coprocesoarele matematice Intel , inclusiv 8087 [1] [2] [3] [4] [5] , 80287 [5] [6] , 80387 [5] ] [6] și până la 80486 [1] , precum și în coprocesoarele Motorola 68881 [1] [2] și 68882. Acest lucru a făcut posibilă reducerea numărului de elemente logice (și complexității) coprocesorului.

metoda Briggs

Ideea generală a metodei este următoarea. Prin multiplicarea succesivă a argumentului cu constante preselectate, aduceți argumentul mai aproape de unul cu o precizie dată pentru unele funcții și de zero pentru alte funcții. Cu toate acestea, pentru ca valoarea funcției în sine să rămână neschimbată, este necesar să se efectueze simultan acțiuni echivalente asupra constantelor alese. Prin alegerea valorilor constantelor într-un mod special, este posibilă simplificarea semnificativă a calculului valorilor funcției.

De exemplu, Briggs a înmulțit valoarea argumentului funcției logaritm zecimal cu constante de forma: fie . $\log X$ $1+10^{{-i}}$ $1-10^{{-i}}$

În acest caz, alegerea primului multiplicator ( ) a fost efectuată dacă valoarea curentă a cantității s-a dovedit a fi mai mică de unu, iar al doilea , dacă valoarea curentă a fost mai mare de unu. Alegând succesiv valorile exponentului de la 1 la , unde a fost eroarea maximă admisă de calcul, Briggs a redus valoarea la una cu precizia necesară și, astfel, valoarea funcției la zero. $1+10^{{-i}}$ $X$ $X$ $N$ $10^{{-N}}$ $X$ $\log X$

Totuși, pentru echivalența acestor transformări, este necesară împărțirea valorii indicate la aceeași valoare concomitent cu înmulțirea valorii curente . Dar, după cum știți, logaritmul coeficientului este egal cu diferența dintre logaritmii numărătorului și numitorului. Prin urmare, simultan cu înmulțirea curentului cu este necesar să se scadă funcția calculată anterior a logaritmului valorii din produsul argumentului cu factorul . $X$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$

Valorile tuturor constantelor formularului și pot fi calculate în avans, deoarece sunt relativ puține dintre ele. De exemplu, cu o eroare acceptabilă, există doar douăsprezece dintre ele. $1+10^{{-i}}$ $1-10^{{-i}}$ $10^{-6}$

Rămâne de clarificat faptul că înmulțirea prin constante ale formei și se reduce la operații de adunare, scădere și transfer de virgulă (deplasare). $1+10^{{-i}}$ $1-10^{{-i}}$

Prin urmare, procedura de calcul al funcției logaritmului Briggs se reduce la operațiile de adunare, scădere și deplasare zecimală.

Generalizarea ideii metodei Briggs la numere complexe a fost realizată la mijlocul anilor cincizeci de către Jack Walder și aproape simultan cu el de către Akushsky și Yuditsky. Acest lucru a făcut posibilă calcularea funcțiilor trigonometrice.

Orele de deschidere

CORDIC poate fi folosit pentru a calcula un număr de funcții diferite. Această explicație arată cum să utilizați CORDIC în modul de rotație pentru a calcula sinusul și cosinusul unui unghi. Se presupune că unghiul dorit este dat în radiani , iar rezultatele sunt în format de punct fix . Pentru a determina sinusul sau cosinusul unui unghi , coordonatele unui punct y sau x de pe cercul unitar trebuie găsite în funcție de unghiul dorit. Folosind CORDIC, începem cu un vector : $\beta$ $v_{0}$

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

În prima iterație , acest vector va fi rotit cu 45° în sens invers acelor de ceasornic pentru a obține vectorul . Iterațiile succesive vor roti vectorul într-o direcție sau alta în trepte descrescătoare până când se atinge unghiul dorit. Valoarea pasului i este arctg(1/(2 i −1 )), pentru i = 1, 2, 3, …. $v_{1}$

Mai formal, la fiecare iterație, se calculează rotația, care se realizează prin înmulțirea vectorului cu matricea de rotație : $v_{{i-1}}$ $R_{i}$

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

Matricele de rotație R sunt determinate de formula:

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

Folosind următoarele două identități trigonometrice

{\begin{aliniat}\cos \alpha &=&{1 \over {\sqrt {1+\operatorname {tg} ^{2}\alpha }}}\\\sin \alpha &=&{ {\operatorname {tg} \alpha } \over {\sqrt {1+\operatorname {tg} ^{2}\alpha }}}\end{aligned}}

obținem matricea de rotație:

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

Expresia pentru vector rotit : $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}\operatorname {tg} \gamma _{i}\\x_{i-1}\operatorname {tg} \gamma _{i}&+&y_{i-1}\end{pmatrix}}

unde si sunt componentele . Prin limitarea valorilor unghiurilor astfel încât să ia valori, înmulțirea cu tangentă poate fi înlocuită cu împărțirea cu o putere de doi, care este implementată eficient în hardware-ul computerului digital prin deplasare de biți . Obținem expresia: $x_{{i-1}}$ $y_{{i-1}}$ $v_{{i-1}}$ $\gamma _{{i}}$ $\operatorname {tg} \gamma _{i}$ $\pm 2^{{-i}}$

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{pmatrix}}

Unde

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

și poate avea valorile -1 sau 1 și este folosit pentru a determina direcția de rotație: dacă unghiul este pozitiv atunci este egal cu 1, în caz contrar este egal cu -1. $\sigma_i$ $\gamma _{i)$ $\sigma_i$

Îl putem ignora în mod iterativ și apoi îl putem aplica ulterior pentru a obține factorul de scalare: $K_{i}$

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

care este calculat în avans și stocat într-un tabel, sau ca o singură constantă dacă numărul de iterații este fix. Această corecție se poate face și în prealabil prin scalare . $v_{0}$

Singura sarcină care rămâne este de a determina dacă rotația în sensul acelor de ceasornic sau în sens invers acelor de ceasornic trebuie efectuată la fiecare iterație (alegerea unei valori de ). Acest lucru se face ținând evidența cantității de rotație la fiecare iterație și scăzând din unghiul dorit, apoi verificând dacă este pozitiv, atunci ar trebui să rotim în sensul acelor de ceasornic sau dacă este negativ ar trebui să rotim în sens invers acelor de ceasornic pentru a ne apropia de unghi . $\sigma$ $\beta _{{n+1}}$ $\beta$

\beta _{i}=\beta _{i-1}-\sigma _{i}\gamma _{i}.\quad \gamma _{i}=\operatorname {arctg} 2^{- eu},

De asemenea, valorile trebuie calculate în avans. Dar pentru unghiuri mici în reprezentarea punctului fix, ceea ce permite reducerea dimensiunii mesei. $\gamma_n$ $\operatorname {arctg} (\gamma _{n})=\gamma _{n)$

După cum puteți vedea în ilustrația de mai sus, sinusul unghiului este coordonata y a vectorului final , iar coordonata x este valoarea cosinusului. $\beta$ $v_{n}$

Metoda „iterațiilor duble”

În lucrările [7] și [8] s-a propus utilizarea metodei „iterațiilor duble” pentru calcularea funcțiilor arcsinX, arccosX, lnX, expX, precum și pentru calcularea funcțiilor hiperbolice . Constă în faptul că, spre deosebire de metoda clasică CORDIC, unde valoarea pasului de iterație se modifică de fiecare dată, i.e. la fiecare iterație, cu metoda iterațiilor duble, valoarea pasului de iterație se repetă de două ori și se modifică doar după o iterație. De aici a apărut notația pentru exponent pentru iterațiile duble: i = 1,1,2,2,3,3... În timp ce pentru iterațiile obișnuite: i =1,2,3... Metoda iterațiilor duble garantează convergența a metodei în toată gama permisă de modificări de argument.

Generalizarea problemelor de convergență a algoritmilor metodei CORDIC la un sistem de numere pozițional arbitrar cu baza R, dat în [9] , a arătat că pentru funcțiile sin, cos, arctg, este suficient să se efectueze (R-1) -iterații pentru fiecare valoare a lui i (i de la 0 sau 1 la n, unde n este numărul de cifre), adică. pentru fiecare cifră a rezultatului. Pentru funcțiile ln, exp, sh, ch, arth, R trebuie efectuate iterații pentru fiecare valoare a lui i. Pentru funcțiile arcsin și arccos, ar trebui efectuate 2 ⋅ (R-1) iterații pe bit, adică. pentru fiecare valoare a lui i.

Pentru funcțiile arsh, arch, numărul de iterații va fi 2R pentru fiecare i, i.e. pentru fiecare cifră a rezultatului.

Literatură

Jack E. Volder, Tehnica de calcul trigonometrică CORDIC, IRE Transactions on Electronic Computers , septembrie 1959
Daggett, D.H., Conversii zecimal-binare în CORDIC , IRE Transactions on Electronic Computers, voi. EC-8 #5, pp 335–339, IRE, septembrie 1959.
JE Meggitt, Pseudo Division and Pseudo Multiplication Processes , IBM Journal, aprilie 1962.
Baikov V. D. Întrebări de cercetare a calculului funcțiilor elementare prin metoda „cifră cu cifră” , rezumat al disertației pentru gradul de candidat în științe tehnice, Leningrad, LETI, 1972
Schmid, Hermann, Calcul zecimal. New York, Wiley, 1974
Baikov V. D., Smolov V. B. Implementarea hardware a funcțiilor elementare într-un computer digital , Leningrad, Universitatea de Stat din Leningrad, 1975, 96 de pagini.
Baikov V. D., Selyutin S. A., Calculul funcțiilor elementare în computer , Moscova, Radio și comunicare, 1982, 64 de pagini.
Baikov V. D., Smolov V. B. Procesoare specializate: algoritmi și structuri iterative , Moscova, Radio și Comunicații, 1985, 288 p.
Andraka, Ray, Un studiu al algoritmilor CORDIC pentru calculatoarele bazate pe FPGA
Henry Briggs, Arithmetica Logarithmica. Londra, 1624, folio
M. Zechmeister Rezolvarea ecuației lui Kepler cu iterații duble CORDIC Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Germania, Preprint 10 august 2020, p.1-10.
Tomás Lang & Elisardo Antelo CORDIC-Based Computation of ArcCos Journal of VLSI signal processing systems for signal, image and video technology volume 25, pages19–38 (2000)
Vladimir Baykov Iterații duble în Bibliografia CORDIC CORDIC
Metode digit by digit , Jacques Laporte, Paris 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 , Comitetul de Stat pentru Invenții și Descoperiri al URSS, certificat nr. 849228 (61), P1 M K 3 (22) declarat 12.10.73/281 (283) -24, G 06 F 15/347 cu atașarea cererii, [1]
Z. S. Kuzin, Procesor pentru calcularea funcțiilor elementare , Comitetul de Stat pentru Invenții și Descoperiri al URSS, certificat nr. 888131 (61), declarat 11.11.79 (21) 2842574/18-24, [2]
Z. S. Kuzin, Un algoritm ultrarapid pentru calcularea transformării Fourier, Wissenschaftliche Beiträge, Heft 4/81 (1981) pp. 22–26 (în rusă)
Site de bibliografie CORDIC , Shaoyun Wang, iulie 2011
CORDIC Bibliografie Site

Note

↑ 1 2 3 Muller Jean-Michel. Funcții elementare: algoritmi și implementare . - editia a 2-a. - Boston: Birkhäuser, 2006. - P. 134. - ISBN 978-0-8176-4372-0 . Arhivat pe 5 iunie 2011 la Wayback Machine
↑ 1 2 Nava Rafi. Implementarea funcțiilor transcendentale pe un procesor numeric // Microprocesare și microprogramare. - 1983. - T. 11 , nr. 3-4 . — S. 221–225 .
↑ John F. Palmer, Stephen Paul Morse. Primerul 8087 . - John Wiley & Sons Australia, Limited, 1984. - ISBN 9780471875697 . Arhivat la 30 decembrie 2016 la Wayback Machine
↑ Glass L. Brent. Coprocesoare matematice: o privire asupra a ceea ce fac și cum o fac // Byte Magazine. - 1990. - T. 15 , nr 1 . — S. 337–348 . — ISSN 0360-5280 .
↑ 1 2 3 Pitts Jarvis. Implementarea algoritmilor CORDIC - O singură rutină compactă pentru calcularea funcțiilor transcendentale // Dr. Jurnalul Dobbs. - 1990. - T. 15 , nr 10 . — S. 152–156 .
↑ 1 2 A. K. Yuen. Procesoarele Intel cu virgulă mobilă // Electro/88 Record Conference. - 1988. - S. 48 / 5 / 1-7 .
↑ Implementarea hardware a funcțiilor elementare prin tehnica digit-by-digit (CORDIC) . Preluat la 24 decembrie 2020. Arhivat din original la 11 ianuarie 2011. (nedefinit)
↑ Baikov V.D., Smolov V.B. Implementarea hardware a funcțiilor elementare într-un computer digital . Preluat la 24 decembrie 2020. Arhivat din original la 15 ianuarie 2011. (nedefinit)
↑ Baikov V.D., Smolov V.B. Procesoare specializate: algoritmi și structuri iterative . Preluat la 29 decembrie 2020. Arhivat din original la 18 iulie 2011. (nedefinit)