CORDIC

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 oktober 2017; kontroller kräver 19 redigeringar .

CORDIC ( CORDIC Method från engelska. Coordinate Rotation DIgital Computer - en digital dator för att rotera koordinatsystemet; metoden "siffra för siffra" , Walders algoritm ) är en iterativ metod för att reducera direkta beräkningar av komplexa funktioner till att utföra enkla additions- och skiftoperationer .

Metodidé

Tanken med metoden är att reducera beräkningen av värdena för komplexa (till exempel hyperboliska ) funktioner till en uppsättning enkla steg - addition och skift.

Detta tillvägagångssätt är särskilt användbart vid beräkning av funktioner på enheter med begränsade beräkningsmöjligheter, såsom mikrokontroller eller programmerbara logiska arrayer ( FPGA ). Dessutom, eftersom stegen är av samma typ, kan hårdvaruimplementeringen av algoritmen utökas till en pipeline eller kollapsa till en loop.

Historik

Metoden beskrevs först i tillämpning för beräkning av trigonometriska funktioner och koordinattransformationsoperationer av Jack Walder 1956 , sedan 1959 . År 1956 lade Akushsky och Yuditsky fram en liknande idé för beräkning av exponentiella och logaritmiska funktioner. Ursprungligen föreslog Henry Briggs en idé nära detta 1624 när han sammanställde tabeller över logaritmer .

Metoden har använts i implementeringen av vissa typer av flyttalsinstruktioner i Intels matematiska samprocessorer , inklusive 8087 [1] [2] [3] [4] [5] , 80287 [5] [6] , 80387 [5 ] [6] och upp till 80486 [1] , samt i samprocessorerna Motorola 68881 [1] [2] och 68882. Detta gjorde det möjligt att minska antalet logiska element (och komplexiteten) hos samprocessorn.

Briggs metod

Den allmänna idén med metoden är följande. Genom successiv multiplikation av argumentet med förvalda konstanter, för argumentet närmare ett med en given noggrannhet för vissa funktioner och till noll för andra funktioner. Men för att värdet på själva funktionen ska förbli oförändrat är det nödvändigt att samtidigt utföra ekvivalenta åtgärder på de valda konstanterna. Genom att välja värdena för konstanterna på ett speciellt sätt är det möjligt att avsevärt förenkla beräkningen av funktionens värden.

Till exempel multiplicerade Briggs värdet av argumentet för decimallogaritmfunktionen med konstanter av formen: antingen . $\log X$ $1+10^{{-i}}$ $1-10^{{-i}}$

I det här fallet utfördes valet av den första multiplikatorn ( ) om det aktuella värdet av kvantiteten visade sig vara mindre än en, och den andra , om det aktuella värdet var större än en. Genom att successivt välja exponentens värden från 1 till , där var det maximala tillåtna beräkningsfelet, reducerade Briggs värdet till ett med den erforderliga noggrannheten, och därmed värdet på funktionen till noll. $1+10^{{-i}}$ $X$ $X$ $N$ $10^{{-N}}$ $X$ $\log X$

För ekvivalensen av dessa transformationer är det emellertid nödvändigt att dividera det angivna värdet med samma värde samtidigt med multiplikationen av det aktuella värdet. Men som ni vet är kvotens logaritm lika med skillnaden mellan täljarens och nämnarens logaritmer. Därför, samtidigt med multiplikationen av strömmen med , är det nödvändigt att subtrahera den tidigare beräknade funktionen av logaritmen av värdet från produkten av argumentet med faktorn . $X$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$

Värdena för alla konstanter i formen och kan beräknas i förväg, eftersom det finns relativt få av dem. Till exempel, med ett acceptabelt fel finns det bara tolv av dem. $1+10^{{-i}}$ $1-10^{{-i}}$ $10^{-6}$

Det återstår att klargöra att multiplikation med konstanter av formen och reduceras till operationer för addition, subtraktion och överföring av ett kommatecken (skift). $1+10^{{-i}}$ $1-10^{{-i}}$

Därför reduceras proceduren för att beräkna Briggs logaritmfunktion till operationerna addition, subtraktion och decimalskifte.

Generaliseringen av idén om Briggs-metoden till komplexa tal utfördes i mitten av slutet av femtiotalet av Jack Walder och nästan samtidigt med honom av Akushsky och Yuditsky. Detta gjorde det möjligt att beräkna trigonometriska funktioner.

Öppettider

CORDIC kan användas för att beräkna ett antal olika funktioner. Den här förklaringen visar hur man använder CORDIC i rotationsläge för att beräkna sinus och cosinus för en vinkel. Det antas att den önskade vinkeln anges i radianer och att resultaten är i fixpunktsformat . För att bestämma sinus eller cosinus för en vinkel måste koordinaterna för en punkt y eller x på enhetscirkeln hittas enligt den önskade vinkeln. Med CORDIC börjar vi med en vektor : $\beta$ $v_{0}$

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

I den första iterationen kommer denna vektor att roteras 45° moturs för att få vektorn . Successiva iterationer kommer att rotera vektorn i den ena eller den andra riktningen i minskande steg tills den önskade vinkeln uppnås. Värdet på det i -te steget är arctg(1/(2 i −1 )), för i = 1, 2, 3, …. $v_{1}$

Mer formellt, vid varje iteration, beräknas rotationen, vilket utförs genom att multiplicera vektorn med rotationsmatrisen : $v_{{i-1}}$ $R_{i}$

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

Rotationsmatriserna R bestäms av formeln:

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

Med hjälp av följande två trigonometriska identiteter

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

vi får rotationsmatrisen:

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

Uttryck för roterad vektor : $v_{i}=R_{i}v_{{i-1}}$

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

var och är komponenterna . Genom att begränsa värdena på vinklarna så att det tar värden kan multiplikation med tangenten ersättas med division med en potens av två, vilket effektivt implementeras i digital datorhårdvara genom bitskiftning . Vi får uttrycket: $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}}

var

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

och kan ha värdena −1 eller 1 och används för att bestämma rotationsriktningen: om vinkeln är positiv är den lika med 1, annars är den lika med −1. $\sigma_i$ ${\displaystyle \gamma _{i))$ $\sigma_i$

Vi kan ignorera det iterativt och sedan tillämpa det efteråt för att få skalningsfaktorn: $K_{i}$

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

som beräknas i förväg och lagras i en tabell, eller som en enda konstant om antalet iterationer är fast. Denna korrigering kan också göras i förväg genom skalning . $v_{0}$

Den enda uppgiften som återstår är att avgöra om rotation medurs eller moturs ska utföras vid varje iteration (välj ett värde på ). Detta görs genom att hålla reda på mängden rotation vid varje iteration och subtrahera från den önskade vinkeln, sedan kontrollera om är positivt så ska vi rotera medurs eller om det är negativt ska vi rotera moturs för att komma närmare vinkeln . $\sigma$ $\beta _{{n+1}}$ $\beta$

\beta _{i}=\beta _{i-1}-\sigma _{i}\gamma _{i}.\quad \gamma _{i}=\operatörsnamn {arctg} 2^{- i},

Värdena måste också beräknas i förväg. Men för små vinklar i fast punkt representation, vilket gör det möjligt att minska storleken på tabellen. $\gamma_n$ ${\displaystyle \operatörsnamn {arctg} (\gamma _{n})=\gamma _{n))$

Som du kan se i illustrationen ovan är vinkelns sinus y -koordinaten för den slutliga vektorn , och x -koordinaten är cosinusvärdet. $\beta$ $v_{n}$

Metoden för "dubbla iterationer"

I arbeten [7] och [8] föreslogs det att använda metoden med "dubbla iterationer" för att beräkna funktionerna arcsinX, arccosX, lnX, expX, såväl som för att beräkna hyperboliska funktioner . Den består i att, till skillnad från den klassiska CORDIC-metoden, där värdet på iterationssteget ändras VARJE gång, d.v.s. vid varje iteration, med metoden med dubbla iterationer, upprepas värdet för iterationssteget två gånger och ändras endast efter en iteration. Därför uppträdde notationen för exponenten för dubbla iterationer: i = 1,1,2,2,3,3... Medan för vanliga iterationer: i =1,2,3... Metoden med dubbla iterationer garanterar konvergensen av metoden i alla tillåtna intervall av argumentändringar.

Generaliseringen av frågorna om konvergens av algoritmer för CORDIC-metoden till ett godtyckligt positionstalssystem med basen R, givet i [9] , visade att för funktionerna sin, cos, arctg räcker det att utföra (R-1) -iterationer för varje värde på i (i från 0 eller 1 till n, där n är antalet siffror), dvs. för varje siffra i resultatet. För funktionerna ln, exp, sh, ch, arth bör R iterationer utföras för varje värde på i. För funktionerna arcsin och arccos bör 2 ⋅ (R-1) iterationer per bit utföras, dvs. för varje värde på i.

För funktionerna arsh, arch kommer antalet iterationer att vara 2R för varje i, dvs. för varje siffra 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, sid 335–339, IRE, september 1959.
JE Meggitt, Pseudo Division and Pseudo Multiplication Processes , IBM Journal, april 1962.
Baikov V. D. Forskningsfrågor för beräkning av elementära funktioner med metoden "siffra för siffra" , sammandrag av avhandlingen för graden av kandidat för tekniska vetenskaper, Leningrad, LETI, 1972
Schmid, Hermann, Decimalberäkning. New York, Wiley, 1974
Baikov V. D., Smolov V. B. Hårdvaruimplementering av elementära funktioner i en digital dator , Leningrad, Leningrad State University, 1975, 96 sidor.
Baikov V. D., Selyutin S. A., Beräkning av elementära funktioner i datorn , Moskva, Radio och kommunikation, 1982, 64 sidor.
Baikov V. D., Smolov V. B. Specialiserade processorer: iterativa algoritmer och strukturer , Moskva, Radio och kommunikation, 1985, 288 s.
Andraka, Ray, En undersökning av CORDIC-algoritmer för FPGA-baserade datorer
Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
M. Zechmeister Löser Keplers ekvation med CORDIC dubbla iterationer Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Tyskland, Preprint 10 augusti 2020, s.1-10.
Tomás Lang & Elisardo Antelo CORDIC-baserad beräkning av ArcCos Journal of VLSI signalbehandlingssystem för signal-, bild- och videoteknik volym 25, sidorna 19–38 (2000)
Vladimir Baykov Dubbla iterationer i CORDIC CORDIC Bibliography
Siffra för siffra metoder , 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), P1 M K 3 (22) deklarerad 12.10.78 (284 283) -24, G 06 F 15/347 med bilaga till ansökan, [1]
Z. S. Kuzin, Processor för beräkning av elementära funktioner , USSR State Committee for Inventions and Discoveries, certifikat nr 888131 (61), deklarerad 11.11.79 (21) 2842574/18-24, [2]
Z. S. Kuzin, En ultrasnabb algoritm för att beräkna Fourier-transformen, Wissenschaftliche Beiträge, Heft 4/81 (1981) s 22–26 (på ryska)
CORDIC Bibliography Site , Shaoyun Wang, juli 2011
CORDIC Bibliografisida

Anteckningar

↑ 1 2 3 Muller Jean-Michel. Elementära funktioner: Algoritmer och implementering . - 2 upplagor. - Boston: Birkhäuser, 2006. - S. 134. - ISBN 978-0-8176-4372-0 . Arkiverad 5 juni 2011 på Wayback Machine
↑ 1 2 Rafi Nave. Implementering av transcendentala funktioner på en numerisk processor // Mikrobehandling och 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 . Arkiverad 30 december 2016 på Wayback Machine
↑ Glas L. Brent. Math Coprocessors: En titt på vad de gör och hur de gör det // Byte Magazine. - 1990. - T. 15 , nr 1 . — S. 337–348 . — ISSN 0360-5280 .
↑ 1 2 3 Pitts Jarvis. Implementering av CORDIC-algoritmer - En enda kompakt rutin för beräkning av transcendentala 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 .
↑ Hårdvaruimplementering av de elementära funktionerna med siffra för siffra (CORDIC) teknik . Hämtad 24 december 2020. Arkiverad från originalet 11 januari 2011. (obestämd)
↑ Baikov V.D., Smolov V.B. Hårdvaruimplementering av elementära funktioner i en digital dator . Hämtad 24 december 2020. Arkiverad från originalet 15 januari 2011. (obestämd)
↑ Baikov V.D., Smolov V.B. Specialiserade processorer: iterativa algoritmer och strukturer . Hämtad 29 december 2020. Arkiverad från originalet 18 juli 2011. (obestämd)