CORDIC

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. října 2017; kontroly vyžadují 19 úprav .

CORDIC ( CORDIC Method z angl. COordinate Rotation DIgital Computer - digitální počítač pro otáčení souřadnicového systému; metoda "číslice po číslici" , Walderův algoritmus ) je iterativní metoda pro redukci přímých výpočtů složitých funkcí na provádění jednoduchých operací sčítání a posunu . .

Metoda nápad

Myšlenkou metody je zredukovat výpočet hodnot komplexních (například hyperbolických ) funkcí na sadu jednoduchých kroků - sčítání a posun.

Tento přístup je zvláště užitečný při výpočtech funkcí na zařízeních s omezenými výpočetními schopnostmi, jako jsou mikrokontroléry nebo programovatelná logická pole ( FPGA ). Navíc, protože kroky jsou stejného typu, hardwarová implementace algoritmu může být rozšířena do potrubí nebo sbalena do smyčky.

Historie

Tato metoda byla poprvé popsána v aplikaci na výpočet goniometrických funkcí a operací transformace souřadnic Jackem Walderem v roce 1956 a poté v roce 1959 . V roce 1956 předložili Akushsky a Yuditsky podobnou myšlenku pro výpočet exponenciálních a logaritmických funkcí. Zpočátku nápad blízký tomuto navrhl Henry Briggs v roce 1624 , když sestavoval tabulky logaritmů .

Tato metoda byla použita při implementaci některých druhů instrukcí s pohyblivou řádovou čárkou v matematických koprocesorech Intel , včetně 8087 [1] [2] [3] [4] [5] , 80287 [5] [6] , 80387 [5 ] [6] a až 80486 [1] , stejně jako v koprocesorech Motorola 68881 [1] [2] a 68882. To umožnilo snížit počet logických prvků (a složitost) koprocesoru.

Briggsova metoda

Obecná myšlenka metody je následující. Postupným násobením argumentu předem vybranými konstantami přibližte argument s danou přesností pro některé funkce k jedničce a pro jiné funkce k nule. Aby však hodnota samotné funkce zůstala nezměněna, je nutné současně provádět ekvivalentní akce na zvolených konstantách. Speciálním výběrem hodnot konstant je možné výrazně zjednodušit výpočet hodnot funkce.

Například Briggs vynásobil hodnotu argumentu funkce dekadického logaritmu konstantami ve tvaru: buď . $\log X$ $1+10^{{-i}}$ $1-10^{{-i}}$

V tomto případě byla volba prvního násobitele ( ) provedena, pokud se ukázalo, že aktuální hodnota veličiny je menší než jedna, a druhého násobitele, pokud byla aktuální hodnota větší než jedna. Postupným výběrem hodnot exponentu od 1 do , kde byla maximální dovolená chyba výpočtu, Briggs snížil hodnotu na jedničku s požadovanou přesností a tím i hodnotu funkce na nulu. $1+10^{{-i}}$ $X$ $X$ $N$ $10^{{-N}}$ $X$ $\log X$

Pro ekvivalenci těchto transformací je však nutné vydělit indikovanou hodnotu stejnou hodnotou současně s násobením aktuální. Ale jak víte, logaritmus podílu se rovná rozdílu mezi logaritmy čitatele a jmenovatele. Současně s násobením proudu je proto nutné odečíst dříve vypočítanou funkci logaritmu hodnoty od součinu argumentu faktorem . $X$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$ $1+10^{{-i}}$ $X$ $1+10^{{-i}}$

Hodnoty všech konstant formuláře a lze vypočítat předem, protože jich je relativně málo. Například s přijatelnou chybou je jich jen dvanáct. $1+10^{{-i}}$ $1-10^{{-i}}$ $10^{-6}$

Zbývá upřesnit, že násobení konstantami tvaru a je redukováno na operace sčítání, odčítání a přenášení čárky (posun). $1+10^{{-i}}$ $1-10^{{-i}}$

Proto je postup výpočtu Briggsovy logaritmické funkce redukován na operace sčítání, odčítání a desetinného posunu.

Zobecnění myšlenky Briggsovy metody na komplexní čísla provedli v polovině padesátých let Jack Walder a téměř současně s ním Akushsky a Yuditsky. To umožnilo vypočítat goniometrické funkce.

Otevírací doba

CORDIC lze použít k výpočtu řady různých funkcí. Toto vysvětlení ukazuje, jak používat CORDIC v režimu rotace pro výpočet sinusu a kosinu úhlu. Předpokládá se, že požadovaný úhel je dán v radiánech a výsledky jsou ve formátu pevných bodů . Chcete-li určit sinus nebo kosinus úhlu , souřadnice bodu y nebo x na jednotkové kružnici musí být nalezeny podle požadovaného úhlu. Pomocí CORDIC začneme vektorem : $\beta$ $v_{0}$

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

V první iteraci se tento vektor otočí o 45° proti směru hodinových ručiček, aby se získal vektor . Postupné iterace budou otáčet vektor v jednom nebo druhém směru v klesajících krocích, dokud není dosaženo požadovaného úhlu. Hodnota i -tého kroku je arctg(1/(2 i −1 )), pro i = 1, 2, 3, …. $v_{1}$

Formálněji se při každé iteraci vypočítá rotace, která se provede vynásobením vektoru rotační maticí : $v_{{i-1}}$ $R_{i}$

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

Rotační matice R jsou určeny vzorcem:

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

Pomocí následujících dvou goniometrických identit

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

dostaneme rotační matici:

R_{i}={1 \over {\sqrt {1+\operatorname {tg} ^{2}\gamma _{i)))){\begin{pmatrix}1&-\operatorname {tg} \ gamma _{i}\\\jméno operátora {tg} \gamma _{i}&1\end{pmatrix}}

Výraz pro otočený vektor : $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}\jméno operátora {tg} \gamma _{i}\\x_{i-1}\jméno operátora {tg} \gamma _{i}&+&y_{i-1}\end{pmatrix}}

kde a jsou součásti . Omezením hodnot úhlů tak, aby nabývaly hodnot, lze násobení tečnou nahradit dělením mocninou dvou, což je v digitálním počítačovém hardwaru efektivně implementováno bitovým posunem . Dostaneme výraz: $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}}

kde

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

a může mít hodnoty -1 nebo 1 a používá se k určení směru otáčení: pokud je úhel kladný, pak je roven 1, jinak je roven -1. $\sigma_i$ ${\displaystyle \gamma _{i))$ $\sigma_i$

Můžeme jej iterativně ignorovat a poté jej použít, abychom získali faktor měřítka: $K_{i}$

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

která se vypočítá předem a uloží do tabulky, nebo jako jediná konstanta, pokud je počet iterací pevně daný. Tuto korekci lze také provést předem změnou měřítka . $v_{0}$

Jediným úkolem, který zbývá, je určit, zda se má při každé iteraci provést rotace ve směru nebo proti směru hodinových ručiček (zvolte hodnotu ). To se provádí sledováním velikosti rotace při každé iteraci a odečtením od požadovaného úhlu, poté zkontrolujeme, zda je kladná, pak bychom se měli otočit ve směru hodinových ručiček, nebo pokud je záporná, měli bychom se otočit proti směru hodinových ručiček, abychom se přiblížili úhlu . $\sigma$ $\beta _{{n+1}}$ $\beta$

\beta _{i}=\beta _{i-1}-\sigma _{i}\gamma _{i}.\quad \gamma _{i}=\název operátora {arctg} 2^{- i},

Hodnoty je také nutné vypočítat předem. Ale pro malé úhly v reprezentaci pevného bodu, což umožňuje zmenšit velikost stolu. $\gamma_n$ ${\displaystyle \operatorname {arctg} (\gamma _{n})=\gamma _{n))$

Jak můžete vidět na obrázku výše, sinus úhlu je souřadnice y konečného vektoru a souřadnice x je hodnota kosinus. $\beta$ $v_{n}$

Metoda "dvojitých iterací"

V pracích [7] a [8] bylo navrženo použít metodu "dvojitých iterací" pro výpočet funkcí arcsinX, arccosX, lnX, expX a také pro výpočet hyperbolických funkcí . Spočívá v tom, že na rozdíl od klasické metody CORDIC, kde se hodnota iteračního kroku mění POKAŽDÉ, tzn. při každé iteraci se u metody dvojitých iterací hodnota iteračního kroku opakuje dvakrát a mění se pouze po jedné iteraci. Proto se objevil zápis pro exponent pro dvojité iterace: i = 1,1,2,2,3,3... Zatímco pro běžné iterace: i =1,2,3... Metoda dvojitých iterací zaručuje konvergenci metody ve všech povolených rozsahu změn argumentů.

Zobecnění problematiky konvergence algoritmů metody CORDIC k libovolné poziční číselné soustavě se základem R, uvedené v [9] , ukázalo, že pro funkce sin, cos, arctg stačí provést (R-1) -iterace pro každou hodnotu i (i od 0 nebo 1 do n, kde n je počet číslic), tj. pro každou číslici výsledku. U funkcí ln, exp, sh, ch, arth, R by měly být provedeny iterace pro každou hodnotu i. Pro funkce arcsin a arccos by měly být provedeny 2 ⋅ (R-1) iterace na bit, tzn. pro každou hodnotu i.

U funkcí arsh, arch bude počet iterací 2R pro každé i, tzn. pro každou číslici výsledku.

Literatura

Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers , září 1959
Daggett, D.H., Decimal-Binary conversions in CORDIC , IRE Transactions on Electronic Computers, Vol. EC-8 #5, str. 335–339, IRE, září 1959.
JE Meggitt, Pseudo Division and Pseudo Multiplication Processes , IBM Journal, duben 1962.
Baikov V. D. Otázky výzkumu výpočtu elementárních funkcí metodou "číslice po číslici" , abstrakt disertační práce pro stupeň kandidáta technických věd, Leningrad, LETI, 1972
Schmid, Hermann, Dekadický výpočet. New York, Wiley, 1974
Baikov V. D., Smolov V. B. Hardwarová implementace elementárních funkcí v digitálním počítači , Leningrad, Leningradská státní univerzita, 1975, 96 stran.
Baikov V. D., Selyutin S. A., Výpočet elementárních funkcí v počítači , Moskva, Rádio a komunikace, 1982, 64 stran.
Baikov V. D., Smolov V. B. Specializované procesory: iterativní algoritmy a struktury , Moskva, Radio and Communications, 1985, 288 stran.
Andraka, Ray, Přehled CORDIC algoritmů pro FPGA založené počítače
Henry Briggs, Arithmetica Logaritmica. Londýn, 1624, fol
M. Zechmeister Řešení Keplerovy rovnice pomocí dvojitých iterací CORDIC Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Německo, Preprint 10. srpna 2020, s.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 Dvojité iterace v CORDIC CORDIC Bibliography
Metody číslic po číslicích , Jacques Laporte, Paříž 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, vektorový procesor , Státní výbor SSSR pro vynálezy a objevy, osvědčení č. 849228 (61), P1 M K 3 (22) deklarováno 12.10.29/28383 -24, G 06 F 15/347 s přílohou přihlášky, [1]
Z. S. Kuzin, zpracovatel pro výpočet elementárních funkcí , Státní výbor SSSR pro vynálezy a objevy, osvědčení č. 888131 (61), vyhlášeno 11.11.79 (21) 2842574/18-24, [2]
Z. S. Kuzin, Ultrarychlý algoritmus pro výpočet Fourierovy transformace, Wissenschaftliche Beiträge, Heft 4/81 (1981) s. 22–26 (v ruštině)
Stránka bibliografie CORDIC , Shaoyun Wang, červenec 2011
Stránky bibliografie CORDIC

Poznámky

↑ 1 2 3 Muller Jean-Michel. Elementární funkce: Algoritmy a implementace . - 2 vydání. - Boston: Birkhäuser, 2006. - S. 134. - ISBN 978-0-8176-4372-0 . Archivováno 5. června 2011 na Wayback Machine
↑ 1 2 Rafi Nave. Implementace transcendentálních funkcí na numerickém procesoru // Mikrozpracování a mikroprogramování. - 1983. - T. 11 , č. 3-4 . — S. 221–225 .
↑ John F. Palmer, Stephen Paul Morse. Základní nátěr 8087 . - John Wiley & Sons Australia, Limited, 1984. - ISBN 9780471875697 . Archivováno 30. prosince 2016 na Wayback Machine
↑ Sklo L. Brent. Math Coprocessors: Pohled na to, co dělají a jak to dělají // Byte Magazine. - 1990. - T. 15 , č. 1 . — S. 337–348 . — ISSN 0360-5280 .
↑ 1 2 3 Pitts Jarvis. Implementace CORDIC algoritmů – jediná kompaktní rutina pro výpočet transcendentálních funkcí // Dr. Dobbs Journal. - 1990. - T. 15 , č. 10 . — S. 152–156 .
↑ 1 2 A. K. Yuen. Procesory Intel s plovoucí desetinnou čárkou // Electro/88 Conference Record. - 1988. - S. 48/5/1-7 .
↑ Hardwarová implementace elementárních funkcí technikou číslice po číslici (CORDIC) . Staženo 24. prosince 2020. Archivováno z originálu 11. ledna 2011. (neurčitý)
↑ Baikov V.D., Smolov V.B. Hardwarová implementace elementárních funkcí v digitálním počítači . Získáno 24. prosince 2020. Archivováno z originálu 15. ledna 2011. (neurčitý)
↑ Baikov V.D., Smolov V.B. Specializované procesory: iterativní algoritmy a struktury . Získáno 29. prosince 2020. Archivováno z originálu dne 18. července 2011. (neurčitý)