CORDIC

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. oktober 2017; checks kræver 19 redigeringer .

CORDIC ( CORDIC Method fra engelsk. Coordinate Rotation DIgital Computer - en digital computer til at rotere koordinatsystemet; "digit for ciffer" metoden , Walders algoritme ) er en iterativ metode til at reducere direkte beregninger af komplekse funktioner til at udføre simple additions- og forskydningsoperationer .

Metode idé

Ideen med metoden er at reducere beregningen af værdierne af komplekse (for eksempel hyperbolske ) funktioner til et sæt enkle trin - addition og skift.

Denne tilgang er især nyttig, når der beregnes funktioner på enheder med begrænsede computeregenskaber, såsom mikrocontrollere eller programmerbare logiske arrays ( FPGA'er ). Da trinene er af samme type, kan hardwareimplementeringen af algoritmen desuden udvides til en pipeline eller kollapse til en loop.

Historie

Metoden blev først beskrevet i anvendelse til beregning af trigonometriske funktioner og koordinattransformationsoperationer af Jack Walder i 1956 , derefter i 1959 . I 1956 fremsatte Akushsky og Yuditsky en lignende idé til beregning af eksponentielle og logaritmiske funktioner. Oprindeligt blev en idé tæt på dette foreslået af Henry Briggs i 1624 , da han kompilerede tabeller over logaritmer .

Metoden er blevet brugt i implementeringen af nogle former for flydende komma-instruktioner i Intel matematiske coprocessorer , herunder 8087 [1] [2] [3] [4] [5] , 80287 [5] [6] , 80387 [5 ] ] [6] og op til 80486 [1] , samt i Motorola 68881 [1] [2] og 68882. Dette gjorde det muligt at reducere antallet af logiske elementer (og kompleksiteten) af coprocessoren.

Briggs metode

Den generelle idé med metoden er som følger. Ved successiv multiplikation af argumentet med forudvalgte konstanter bringes argumentet tættere på én med en given nøjagtighed for nogle funktioner og til nul for andre funktioner. Men for at værdien af selve funktionen forbliver uændret, er det nødvendigt at udføre ækvivalente handlinger på de valgte konstanter samtidigt. Ved at vælge værdierne af konstanterne på en speciel måde er det muligt at forenkle beregningen af funktionens værdier betydeligt.

For eksempel multiplicerede Briggs værdien af argumentet for decimallogaritmefunktionen med konstanter på formen: enten . $\log X$ $1+10^{{-i}}$ $1-10^{{-i}}$

I dette tilfælde blev valget af den første multiplikator ( ) udført, hvis den aktuelle værdi af mængden viste sig at være mindre end én, og den anden , hvis den aktuelle værdi var større end én. Ved successivt at vælge eksponentens værdier fra 1 til , hvor var den maksimalt tilladte regnefejl, reducerede Briggs værdien til én med den nødvendige nøjagtighed og dermed værdien af funktionen til nul. $1+10^{{-i}}$ $x$ $x$ $N$ $10^{{-N}}$ $x$ $\log X$

Men for ækvivalensen af disse transformationer er det nødvendigt at dividere den angivne værdi med den samme værdi samtidig med multiplikationen af den aktuelle værdi. Men som du ved, er kvotientens logaritme lig med forskellen mellem tællerens og nævnerens logaritmer. Derfor er det samtidig med multiplikationen af strømmen nødvendigt at trække den tidligere beregnede funktion af logaritmen af værdien fra produktet af argumentet med faktoren . $x$ $1+10^{{-i}}$ $x$ $1+10^{{-i}}$ $1+10^{{-i}}$ $x$ $1+10^{{-i}}$

Værdierne af alle formens konstanter og kan beregnes på forhånd, da der er relativt få af dem. For eksempel, med en acceptabel fejl, er der kun tolv af dem. $1+10^{{-i}}$ $1-10^{{-i}}$ $10^{-6}$

Det mangler at blive afklaret, at multiplikation med konstanter af formen og reduceres til operationer med addition, subtraktion og overførsel af et komma (skift). $1+10^{{-i}}$ $1-10^{{-i}}$

Derfor er proceduren for beregning af Briggs logaritmefunktion reduceret til operationerne addition, subtraktion og decimalforskydning.

Generaliseringen af ideen om Briggs-metoden til komplekse tal blev udført i midten af slutningen af halvtredserne af Jack Walder og næsten samtidigt med ham af Akushsky og Yuditsky. Dette gjorde det muligt at beregne trigonometriske funktioner.

Åbningstider

CORDIC kan bruges til at beregne en række forskellige funktioner. Denne forklaring viser, hvordan man bruger CORDIC i rotationstilstand til at beregne sinus og cosinus for en vinkel. Det antages, at den ønskede vinkel er angivet i radianer , og resultaterne er i fikspunktsformat . For at bestemme sinus eller cosinus for en vinkel skal koordinaterne til et punkt y eller x på enhedscirklen findes i henhold til den ønskede vinkel. Ved hjælp af CORDIC starter vi med en vektor : $\beta$ $v_{0}$

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

I den første iteration vil denne vektor blive roteret 45° mod uret for at få vektoren . Successive iterationer vil rotere vektoren i den ene eller den anden retning i faldende trin, indtil den ønskede vinkel er nået. Værdien af det i -te trin er arctg(1/(2 i −1 )), for i = 1, 2, 3, …. $v_{1}$

Mere formelt beregnes rotationen ved hver iteration, som udføres ved at gange vektoren med rotationsmatricen : $v_{{i-1}}$ $R_{i}$

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

Rotationsmatricerne R bestemmes af formlen:

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

Brug af følgende to trigonometriske identiteter

{\begin{aligned}\cos \alpha &=&{1 \over {\sqrt {1+\operatørnavn {tg} ^{2}\alpha }}}\\\sin \alpha &=&{ {\operatørnavn {tg} \alpha } \over {\sqrt {1+\operatørnavn {tg} ^{2}\alpha }}}\end{aligned}}

vi får rotationsmatricen:

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

Udtryk for roteret vektor : $v_{i}=R_{i}v_{{i-1}}$

v_{i}={1 \over {\sqrt {1+\operatørnavn {tg} ^{2}\gamma _{i)))){\begin{pmatrix}x_{i-1}&- &y_{i-1}\operatørnavn {tg} \gamma _{i}\\x_{i-1}\operatørnavn {tg} \gamma _{i}&+&y_{i-1}\end{pmatrix}}

hvor og er komponenterne . Ved at begrænse værdierne af vinklerne , så det tager værdier, kan multiplikation med tangenten erstattes af division med en potens af to, hvilket er effektivt implementeret i digital computerhardware ved bitforskydning . Vi får udtrykket: $x_{{i-1}}$ $y_{{i-1}}$ $v_{{i-1}}$ $\gamma _{{i}}$ $\operatørnavn {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}}

hvor

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

og kan have værdierne −1 eller 1 og bruges til at bestemme rotationsretningen: hvis vinklen er positiv, er den lig med 1, ellers er den lig med −1. $\sigma_i$ ${\displaystyle \gamma _{i))$ $\sigma_i$

Vi kan ignorere det iterativt og derefter anvende det bagefter for at få skaleringsfaktoren: $K_{i}$

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

som er beregnet på forhånd og gemt i en tabel, eller som en enkelt konstant, hvis antallet af iterationer er fast. Denne korrektion kan også foretages på forhånd ved skalering . $v_{0}$

Den eneste opgave, der er tilbage, er at bestemme, om rotation med uret eller mod uret skal udføres ved hver iteration (ved at vælge en værdi på ). Dette gøres ved at holde styr på mængden af rotation ved hver iteration og trække fra den ønskede vinkel, derefter kontrollere, om er positiv, så skal vi rotere med uret, eller hvis den er negativ, skal vi rotere mod uret for at komme tættere på vinklen . $\sigma$ $\beta _{{n+1}}$ $\beta$

\beta _{i}=\beta _{i-1}-\sigma _{i}\gamma _{i}.\quad \gamma _{i}=\operatørnavn {arctg} 2^{- jeg},

Værdierne skal også beregnes på forhånd. Men for små vinkler i fast punkt repræsentation, som gør det muligt at reducere størrelsen af bordet. $\gamma_n$ ${\displaystyle \operatørnavn {arctg} (\gamma _{n})=\gamma _{n))$

Som du kan se i illustrationen ovenfor, er vinklens sinus y -koordinaten for den endelige vektor , og x - koordinaten er cosinusværdien. $\beta$ $v_{n}$

Metoden til "dobbelte iterationer"

I værker [7] og [8] blev det foreslået at bruge metoden med "dobbelte iterationer" til beregning af funktionerne arcsinX, arccosX, lnX, expX, samt til beregning af hyperbolske funktioner . Den består i, at i modsætning til den klassiske CORDIC metode, hvor værdien af iterationstrinnet ændrer sig HVER gang, dvs. ved hver iteration, med metoden med dobbelte iterationer, gentages værdien af iterationstrinnet to gange og ændres kun efter én iteration. Derfor fremkom notationen for eksponenten for dobbelte iterationer: i = 1,1,2,2,3,3... Hvorimod for almindelige iterationer: i =1,2,3... Metoden med dobbelt iterationer garanterer konvergensen af metoden i alle tilladte rækker af argumentændringer.

Generaliseringen af spørgsmålene om konvergens af algoritmer i CORDIC-metoden til et vilkårligt positionstalssystem med basis R, givet i [9] , viste, at for funktionerne sin, cos, arctg er det tilstrækkeligt at udføre (R-1) -iterationer for hver værdi af i (i fra 0 eller 1 til n, hvor n er antallet af cifre), dvs. for hvert ciffer i resultatet. For funktionerne ln, exp, sh, ch, arth skal der udføres R iterationer for hver værdi af i. For arcsin- og arccos-funktionerne skal der udføres 2 ⋅ (R-1) iterationer pr. bit, dvs. for hver værdi af i.

For funktioner arsh, arch vil antallet af iterationer være 2R for hvert i, dvs. for hvert ciffer i resultatet.

Litteratur

Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers , september 1959
Daggett, D.H., Decimal-Binary conversions in CORDIC , IRE Transactions on Electronic Computers, Vol. EC-8 #5, s. 335-339, IRE, september 1959.
JE Meggitt, Pseudo Division and Pseudo Multiplication Processes , IBM Journal, april 1962.
Baikov V. D. Spørgsmål om forskning af beregning af elementære funktioner ved metoden "ciffer for ciffer" , abstrakt af afhandlingen for graden af kandidat for tekniske videnskaber, Leningrad, LETI, 1972
Schmid, Hermann, Decimalberegning. New York, Wiley, 1974
Baikov V. D., Smolov V. B. Hardwareimplementering af elementære funktioner i en digital computer , Leningrad, Leningrad State University, 1975, 96 sider.
Baikov V. D., Selyutin S. A., Beregning af elementære funktioner i computeren , Moskva, Radio og kommunikation, 1982, 64 sider.
Baikov V. D., Smolov V. B. Specialiserede processorer: iterative algoritmer og strukturer , Moskva, Radio og Kommunikation, 1985, 288 s.
Andraka, Ray, En undersøgelse af CORDIC-algoritmer til FPGA-baserede computere
Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
M. Zechmeister Løsning af Keplers ligning med CORDIC dobbeltiterationer Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Tyskland, Preprint 10. august 2020, s.1-10.
Tomás Lang & Elisardo Antelo CORDIC-baseret beregning af ArcCos Journal of VLSI signalbehandlingssystemer til signal-, billed- og videoteknologi bind 25, side 19–38 (2000)
Vladimir Baykov Dobbelt iterationer i CORDIC CORDIC Bibliografi
Digit by digit methods , 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 , USSR State Committee for Inventions and Discoveries, certifikat nr. 849228 (61), Р1 M K 3 (22) erklæret 12.10.79/314 (323) -24, G 06 F 15/347 med bilag til ansøgningen, [1]
Z. S. Kuzin, Processor til beregning af elementære funktioner , USSR State Committee for Opfindelser og Opdagelser, certifikat nr. 888131 (61), erklæret 11.11.79 (21) 2842574/18-24, [2]
Z. S. Kuzin, En ultrahurtig algoritme til beregning af Fourier-transformationen, Wissenschaftliche Beiträge, Heft 4/81 (1981) s. 22-26 (på russisk)
CORDIC Bibliography Site , Shaoyun Wang, juli 2011
CORDIC Bibliografiside

Noter

↑ 1 2 3 Muller Jean-Michel. Elementære funktioner: Algoritmer og implementering . - 2 oplag. - Boston: Birkhäuser, 2006. - S. 134. - ISBN 978-0-8176-4372-0 . Arkiveret 5. juni 2011 på Wayback Machine
↑ 1 2 Rafi Nave. Implementering af transcendentale funktioner på en numerisk processor // Mikrobehandling og mikroprogrammering. - 1983. - T. 11 , nr. 3-4 . — S. 221–225 .
↑ John F. Palmer, Stephen Paul Morse. 8087 Primer . - John Wiley & Sons Australia, Limited, 1984. - ISBN 9780471875697 . Arkiveret 30. december 2016 på Wayback Machine
↑ Glas L. Brent. Math Coprocessors: Et kig på, hvad de gør, og hvordan de gør det // Byte Magazine. - 1990. - T. 15 , nr. 1 . — S. 337–348 . — ISSN 0360-5280 .
↑ 1 2 3 Pitts Jarvis. Implementering af CORDIC-algoritmer - En enkelt kompakt rutine til beregning af transcendentale funktioner // Dr. Dobbs Journal. - 1990. - T. 15 , nr. 10 . — S. 152–156 .
↑ 1 2 A. K. Yuen. Intels Floating-Point-processorer // Electro/88 Conference Record. - 1988. - S. 48 / 5 / 1-7 .
↑ Hardwareimplementering af de elementære funktioner ved hjælp af ciffer-by-digit (CORDIC) teknik . Hentet 24. december 2020. Arkiveret fra originalen 11. januar 2011. (ubestemt)
↑ Baikov V.D., Smolov V.B. Hardwareimplementering af elementære funktioner i en digital computer . Hentet 24. december 2020. Arkiveret fra originalen 15. januar 2011. (ubestemt)
↑ Baikov V.D., Smolov V.B. Specialiserede processorer: iterative algoritmer og strukturer . Hentet 29. december 2020. Arkiveret fra originalen 18. juli 2011. (ubestemt)