CORDIC
CORDIC ( betűszó a CO ordináta R otation DI gital C omputer , „numerikus számítási forgása által koordináták”) egy algoritmus kiszámításához trigonometrikus és hiperbolikus függvények , használt különösen számológépek . Először 1959-ben írta le Jack E. Volder . Olyan technikákra hasonlít, amelyeket Henry Briggs írt le 1624-ben.
Ez egy választott algoritmus, ha a szorzó hardveres megvalósítása nem érhető el (bizonyos egyszerű mikrokontrollereken vagy FPGA-kon ). Ezenkívül a CORDIC algoritmus jól alkalmazkodik a láncszámításhoz. Eredetileg a CORDIC programozás bináris rendszeren alapult .
Az 1970-es években a CORDIC decimális verziói (a BCD-be kódolt számokkal ) kezdtek megjelenni, különösen a számológépekben, ahol az anyagköltség-kritériumok fontosabbak, mint a feldolgozási sebesség. A CORDIC további előnye a rugalmassága, mivel lehetővé teszi több függvény kiszámítását szinte azonos kóddal.
Leírás
A CORDIC lehetővé teszi egy adott szög szinuszának vagy koszinuszának meghatározását radiánban, rögzített pont formátumban . A β szög szinuszának vagy koszinuszának megtalálásához megkeressük a hozzá tartozó egységkör pont x vagy y koordinátáját . A CORDIC a v 0 vektorral kezdi a számításokat , például:
v0=(10){\ displaystyle v_ {0} = {\ kezdete {pmatrix} 1 \\ 0 \ end {pmatrix}}}Az első iteráció, a vektor megy keresztül 45 ° forgás az óramutató járásával ellentétes irányban ( az óramutató járásával ellentétes ), hogy egy új vektort v 1 . Az egymást követő iterációknak a vektor helyes irányba történő forogását kell előidézniük. Minden egyes iterációnál a forgatás előre meghatározott szögben történik, és kisebb, mint az előző. Ezt addig, amíg a kívánt szögbe nem konvergál.
Formálisabban, minden i iterációnál új vektort számolunk a v i vektornak az R i rotációs mátrixszal való szorzásának köszönhetően :
vén+1=Rénvén {\ displaystyle v_ {i + 1} = R_ {i} v_ {i} \}Az R i rotációs mátrixot a következő képlet szerint kapjuk meg:
Rén=(kötözősalátaγén-bűnγénbűnγénkötözősalátaγén){\ displaystyle R_ {i} = {\ kezdődik {pmatrix} \ cos \ gamma _ {i} és - \ sin \ gamma _ {i} \\\ sin \ gamma _ {i} és \ cos \ gamma _ {i } \ end {pmatrix}}}A cos ( γ ) kifejezés faktorozásával kapjuk:
vén+1=Rénvén=kötözősalátaγén(1-σénCserγénσénCserγén1)(xényén){\ displaystyle v_ {i + 1} = R_ {i} v_ {i} = \ cos \ gamma _ {i} {\ begin {pmatrix} 1 & - \ sigma _ {i} \ tan \ gamma _ {i} \ \\ sigma _ {i} \ tan \ gamma _ {i} & 1 \ end {pmatrix}} {\ begin {pmatrix} x_ {i} \\ y_ {i} \ end {pmatrix}}}A σ i tényező a +1 vagy -1 értéket veszi fel, és a forgásirány jelzésére szolgál. Ha korlátozzuk a γ szög lehetséges választásait úgy, hogy a tan ( γ ) egyenlő 2 - i-vel, akkor az érintővel történő szorzás 2-es hatvány szorzata lesz. Egy művelet könnyen elvégezhető számítógéppel, mivel binárisan ez egy kis váltás .
A számítás:
vén+1=Rénvén=kötözősaláta(arctan(2-én))(1-σén2-énσén2-én1)(xényén)=Kén(xén-σén2-ényénxénσén2-én+yén){\ displaystyle v_ {i + 1} = R_ {i} v_ {i} = \ cos (\ arctan (2 ^ {- i})) {\ begin {pmatrix} 1 & - \ sigma _ {i} 2 ^ {-i} \\\ sigma _ {i} 2 ^ {- i} & 1 \ end {pmatrix}} {\ begin {pmatrix} x_ {i} \\ y_ {i} \ end {pmatrix}} = K_ {i} {\ begin {pmatrix} x_ {i} - \ sigma _ {i} 2 ^ {- i} y_ {i} \\ x_ {i} \ sigma _ {i} 2 ^ {- i} + y_ {i} \ end {pmatrix}}}val vel
Kén=kötözősaláta(arctan(2-én)) {\ displaystyle K_ {i} = \ cos (\ arctan (2 ^ {- i})) \}Ezeket a K i együtthatókat az iterációk során figyelmen kívül lehet hagyni, és egyetlen végső szorzótényezővé lehet tenni ( n-től függően ):
K(nem)=∏én=0nem-1Kén=∏én=0nem-1kötözősaláta(arctan(2-én))=∏én=0nem-111+2-2én{\ displaystyle K (n) = \ prod _ {i = 0} ^ {n-1} K_ {i} = \ prod _ {i = 0} ^ {n-1} \ cos (\ arctan (2 ^ { -i})) = \ prod _ {i = 0} ^ {n-1} {\ frac {1} {\ sqrt {1 + 2 ^ {- 2i}}}}}amely előre kiszámolható és előre megjegyezhető. Továbbá, ha n végtelenbe hajlik, ez a termék állandóvá válik:
K=limnem→∞K(nem)≈0,6073{\ displaystyle K = \ lim _ {n \ to \ infty} K (n) \ kb. 0,6073} (0.60725294 ...)
Elegendő iteráció után a vektor szöge közel lesz a kívánt β szöghez .
Az utolsó lépés abból áll, hogy minden egyes iterációnál meghatározzuk a forgásirányt, trigonometrikusan vagy az óramutató járásával megegyező irányban (az eredményt áthozzuk az σ i értékére ). Ehhez megnézzük a vektor aktuális β n + 1 szögét, amelyet kivonunk a kívánt szögből. Megvizsgáljuk, hogy ez a különbség pozitív (az óramutató járásával megegyező irányú forgás) vagy negatív (trigonometrikus irány), hogy megközelítsük a β szöget .
βén+1=βén-σénγén.γén=arctan2-én{\ displaystyle \ beta _ {i + 1} = \ beta _ {i} - \ sigma _ {i} \ gamma _ {i}. \ quad \ gamma _ {i} = \ arctan 2 ^ {- i}},
A γ n értékeit előre tároljuk egy előre tárolt értéktáblázatban. Kis szögek esetén azonban az arctan ( γ n ) ≈ γ n közelítést használjuk rögzített pont ábrázolásban, ezáltal lehetővé téve ennek a táblázatnak a méretét.
Amint azt a fenti diagram szemlélteti, a β szög szinusa a v n végső vektor y koordinátája , míg az x koordináta a koszinusznak felel meg.
Algoritmus
A 1971 , John Stephen Walther a Hewlett Packard bemutatta általánosítása az algoritmus amely végre a HP-35 számológép . Ez a módszer lehetővé teszi különösen a hiperbolikus függvények kiszámítását, de más olyan funkciókat is, mint az exponenciális, az osztás vagy a szorzás. Az általánosítás a következő:
{xk+1=xk-mσkyk2-kyk+1=yk+σkxk2-kzk+1=zk-σkεk{\ displaystyle \ left \ {{\ begin {mátrix} x_ {k + 1} = x_ {k} -m \ sigma _ {k} y_ {k} 2 ^ {- k} \\ y_ {k + 1} = y_ {k} + \ sigma _ {k} x_ {k} 2 ^ {- k} \\ z_ {k + 1} = z_ {k} - \ sigma _ {k} \ varepsilon _ {k} \ end {mátrix}} \ jobb.}a m ∈ {-1; 0; 1} , ε k az előre definiált állandók és σ k ∈ {–1; 1} ( z k értékétől függően ).
Trigonometrikus függvények
Az általánosítást a paraméterekkel használjuk:
m=1 {\ displaystyle m = 1 ~}
εk=arctan(2-k){\ displaystyle \ varepsilon _ {k} = \ kezelőnév {arctan} (2 ^ {- k})}
σk=sgn(zk){\ displaystyle \ sigma _ {k} = \ kezelőnév {sgn} (z_ {k})}
x0=K=∏én=0∞kötözősaláta(arctan(2-én))≈0,607252{\ displaystyle x_ {0} = K = \ prod _ {i = 0} ^ {\ infty} \ cos (\ arctan (2 ^ {- i})) \ kb. 0,607252}
y0=0 {\ displaystyle y_ {0} = 0 ~}
z0=θ {\ displaystyle z_ {0} = \ theta ~} (radiánban)
N iteráció végén x n ≈ cos ( θ ) és y n ≈ sin ( θ ) .
Ez a módszer csak akkor működik, ha:
|θ|<∑én=0∞arctan(2-én)≈1,7{\ displaystyle | \ theta | <\ sum _ {i = 0} ^ {\ infty} \ kezelőnév {arctan} (2 ^ {- i}) \ kb 1 {,} 7}A gyakorlatban ez nem jelent problémát, mert a trigonometrikus függvények mindig 0 ≤ θ < esetre redukálhatókπ/2legismertebb tulajdonságaik kihasználásával (lásd: Trigonometrikus azonosság ).
Hiperbolikus funkciók
Az általánosítást a paraméterekkel használjuk:
m=-1 {\ displaystyle m = -1 ~}
εk=artanh(2-k){\ displaystyle \ varepsilon _ {k} = \ kezelőnév {artanh} (2 ^ {- k})}
σk=sgn(zk){\ displaystyle \ sigma _ {k} = \ kezelőnév {sgn} (z_ {k})}
x0=∏én=0∞kényelmes(arctanh(2-én))≈1,20513{\ displaystyle x_ {0} = \ prod _ {i = 0} ^ {\ infty} \ cosh (\ operátornév {arctanh} (2 ^ {- i})) \ kb 1,20513}
y0=0 {\ displaystyle y_ {0} = 0 ~}
z0=θ {\ displaystyle z_ {0} = \ theta ~} (radiánban)
N iteráció végén x n ≈ cosh ( θ ) és y n ≈ sinh ( θ ) , valamint x n + y n ≈ exp ( θ ) .
Ez a módszer csak akkor működik, ha z abszolút értéke kisebb, mint kb. 1,05. A kifejezések trigonometrikus azonosságokat felhasználó transzformációi megkerülhetik ezeket a problémákat, biztosítva, hogy a paraméterek a kívánt tartományban legyenek. Bizonyos iterációk ismétlése megoldja a konvergencia problémákat.
Lineáris függvények
A CORDIC lehetővé teszi az a és b számok szorzatának vagy osztásának kiszámítását is .
Szorzás
m=0 {\ displaystyle m = 0 ~}
εk=2-k{\ displaystyle \ varepsilon _ {k} = 2 ^ {- k}}
σk=sgn(zk){\ displaystyle \ sigma _ {k} = \ kezelőnév {sgn} (z_ {k})}
x0=nál nél{\ displaystyle x_ {0} = a}
y0=0 {\ displaystyle y_ {0} = 0 ~}
z0=b {\ displaystyle z_ {0} = b ~}
Végén n iteráció, mi vagyunk n ≈ egy × b . A gyakorlatban nem túl érdekes, mert tartománya korlátozott: feltétlenül szükséges, hogy b ∈ [–2; 2] .
Osztály
m=0 {\ displaystyle m = 0 ~}
εk=2-k{\ displaystyle \ varepsilon _ {k} = 2 ^ {- k}}
σk=-sgn(yk){\ displaystyle \ sigma _ {k} = - \ kezelőnév {sgn} (y_ {k})}
x0=b {\ displaystyle x_ {0} = b ~}
y0=nál nél {\ displaystyle y_ {0} = a ~}
z0=0 {\ displaystyle z_ {0} = 0 ~}
N iteráció végén van z n ≈ a / b . Korlátozott alkalmazási területe is van, mivel a következő feltételeket be kell tartani:|nál nélb|≤2{\ displaystyle \ left | {\ frac {a} {b}} \ right | \ leq 2}
Bibliográfia
- Jack E. Volder, A CORDIC trigonometrikus számítástechnika, IRE-tranzakciók elektronikus számítógépeken ,1959. szeptember
- Daggett, DH, Tizedes-bináris konverziók a CORDIC-ban , IRE tranzakciók elektronikus számítógépeken, 1. évf. EC-8 n o 5, p. 335-339 , IRE,1959. szeptember.
- JE Meggitt, Pseudo Division és Pseudo Multiplication Processes , IBM Journal,1962. április.
- Vlagyimir Bajkov, Az alapfunkciók kiértékelésének problémái a számjegyenkénti (CORDIC) technika alapján , tézisjelentés , Leningrádi Állami Villamosmérnöki Egyetem, 1972
- Schmid, Hermann, Tizedes számítás. New York, Wiley, 1974
- VDBaykov, VBSmolov, Az alapvető funkciók hardveres megvalósítása a számítógépekben , Leningrádi Állami Egyetem, 1975, 96p.
- Senzig, Don, kalkulátor Algoritmusok , IEEE Compcon Reader Digest, IEEE Katalógus n o 75 CH 0920-9C, p. 139-141 , IEEE, 1975.
- VDBajkov, SASeljutin, Elemi funkciók értékelése mikrokalkulátorokban , Moszkva, Radio & svjaz, 1982, 64p.
- Vladimir D. Baykov, Vladimir B. Smolov, Speciális célú processzorok: iteratív algoritmusok és struktúrák , Moszkva, Radio & svjaz, 1985, 288 oldal
- ME Frerking, Digitális jelfeldolgozás a kommunikációs rendszerekben , 1994
- Vitit Kantabutra, Az exponenciális és trigonometrikus függvények kiszámításához szükséges hardverről , IEEE Trans. Computers 45 (3), 328-339 (1996).
- Andraka, Ray, FORD-alapú számítógépek CORDIC-algoritmusainak felmérése
-
Le Secret des algorithmes , Jacques Laporte, Párizs, 1981. A szerző halála és a házigazda általi megújítás elmaradása után a webhely ma már nem elérhető (még az archive.org oldalon sem), kivéve az NSA-t . Az özvegye által engedélyezett másolat azonban megtalálható a következő címen: http://home.citycable.ch/pierrefleur/Jacques-Laporte/index.html .
- (en) Jean-Michel Muller, Elementary Functions - Algorithms and Implementation, 2. kiadás , Boston, Birkhäuser,2006, 2 nd ed. , 265 p. ( ISBN 978-0-8176-4372-0 , LCCN 2005048094 , online előadás )
-
Lefèvre V., Zimmerman P. ,2004. január, Úszó aritmetikai , INRIA Research Report n o 5105.
Megjegyzések és hivatkozások
-
http://cdeval.free.fr/IMG/pdf/cordic.pdf
Lásd is
Kapcsolódó cikkek
Külső linkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">