A CORDIC („coordinate rotation digital computer”), más néven Volder-algoritmus vagy számjegyenkénti módszer, cirkuláris CORDIC (Jack E. Volder), lineáris CORDIC, hiperbolikus CORDIC (John Stephen Walther) és általánosított hiperbolikus CORDIC (GH CORDIC) (Yuanyong Luo et al.), egyszerű, hatékony módszer trigonometriai, hiperbolikus függvények, négyzetgyökök, szorzások, osztások, valamint tetszőleges alapú exponenciális függvények és logaritmusok számítására, mely jellemzően alkalmanként 1 számjeggyel nagyobb pontosságot ad, így a CORDIC egy számjegyenként haladó algoritmus. A CORDIS és hasonló álszorzás-, álosztás- vagy tényezőkombinációs módszerek általában elérhető hardveres szorzó nélkül (például egyszerű mikrovezérlőkben és FPGA-kban) használatos, mivel hozzá csak összeadás, kivonás, bitenkénti eltolás és keresési táblák kellenek. Így ez egy eltoló-összeadó művelet. A CORDIC-ot gyakran használják lebegőpontos számábrázoláshoz, ha a célplatform korlátozott költség vagy tárhely miatt nem rendelkezik hardveres szorzóval.
Története Hasonló módszereket írt le Henry Briggs 1624-ben (angolul: ) és Robert Flower 1771-ben, de a CORDIC alacsony komplexitású processzorokra optimalizált.
A CORDIC-ot 1956-ban fogalmazta meg Jack E Volder a Convair aeroelektronikai részlegénél a B–58 navigációs számítógépének analóg feloldójának cseréjére egy pontosabb, gyorsabb valós idejű digitális megoldásra. Így a CORDIC-ot nvezik néha digitális feloldónak. (Egyes források a szerzőt tévesen P. Z. Perle-nek vagy a lapot Component Designnak nevezik.) (a reprint egy része hibásan lehetett nyomtatva, ahol a 115–146. oldal hibás.)
Volder kutatását a CRC Handbook of Chemistry and Physics 1946-os kiadásában szereplő alábbi képlet inspirálta:
ahol értéke úgy van megválasztva, hogy , és .
Kutatása egy belső technikai jelentéshez vezetett, melyben a CORDIC algoritmust javasolták szinusz- és koszinuszfüggvények megoldására, valamint egy vele rendelkező kezdeti számítógépet. Itt a hiperbolikus forgatás, logaritmusok és exponenciális függvények számításának módosított CORDIC algoritmusokkal való megoldásáról is szó volt. A CORDIC szorzásra és osztásra való használatát is ekkor fogalmazták meg. A CORDIC elvein alapulva Dan H. Daggett, Volder munkatársa a bináris és a binárisan kódolt decimális (BCD) közti átváltási algoritmusokat javasolt.
1958-ban a Convair elkezdte egy bemutató rendszer építését radarrögzítést igénylő problémák megoldására, melynek neve CORDIC I volt, melyet 1960-ban Volder nélkül fejeztek be, aki elhagyta a társaságot. A több célra használható CORDIC II A (stacionárius) és B (repülő) modelleket Daggett és Harry Schuss készítették el és építették 1962-ben.
Volder CORDIC algoritmusát nyilvánosan 1959-ben írták le, emiatt többek közt a Martin Orlando, a Computer Control, a Litton, a Kearfott, a Lear-Siegler, a Sperry, a Raytheon és a Collins Radio navigációs számítógépeibe is ez került.
Volder Malcolm McMillannel együtt kívánta megépíteni az Athenát, mely egy bináris CORDIC algoritmust használó fixpontos számológép lett volna. A terveket a Hewlett-Packardnak mutatták be 1965 júniusában, de nem fogadták el. Azonban McMillan David S. Cochrannek (HP) bemutatta Volder algoritmusát, és mikor Cochran később Volderrel találkozott, egy hasonló módszert mutatott be, melyet John E. Meggitt (IBM) (, ) javasolt álszorzásnak és álosztásnak nevezve 1961-ben. () Meggitt módszere a 10-es alap használatát javasolta a 2-es helyett, melyet Volder CORDIC-ja használt. Ez egy decimális CORDIC-prototípus 1966-os ROM-olható logikai implementációjának az előzménye volt a Hewlett-Packardnál, mely Thomas Osborne prototipikus Green Machine-jéből származik, mely négyfunkciós, lebegőpontos számológép, melyet DTL logikával alkotott meg 1964 decemberében. Ez a Hewlett Packard első tudományos funkciókkal rendelkező számológépének, az 1968. márciusi HP 9100A-nak az előzménye volt, melynek ugyanez évben kezdődött a sorozatgyártása. ()
Mikor a Wang Laboratories felfedezte, hogy a HP 9100A hasonló módszert használt, mint a korábbi LOCI–1 (1964. szeptember) és LOCI–2 (1965. január) Logarithmic Computing Instrument számológép, sikertelenül vádolták a Hewlett-Packardot An Wang szabadalmának sértéséért 1968-ban. (, ) ()
John Stephen Walther, a Hewlett-Packard dolgozója az algoritmust általánosította egy „egységes CORDIC” algoritmussá 1971-ben, lehetővé téve hiperbolikus és exponenciális függvények, logaritmusok, szorzások, osztások és négyzetgyökök számítását. A trigonometriai és hiperbolikus függvények CORDIC-programrészeinek kódja nagyrészt közös lehet. Ezután 1972-ben megjelent az első tudományos hordozható számológép, a HP-35. A hiperbolikus CORDIC-on alapulva Yuanyong Luo és társai javasolták az általános hiperbolikus CORDIC (GH CORDIC) használatát tetszőleges alapú logaritmusok és exponenciális függvényekhez 2019-ben. Elvileg a hiperbolikus CORDIC a GH CORDIC speciális esete.
Eredetileg a CORDIC-ot csak bináris számrendszerben alkották meg, és bár Meggitt javasolta a decimális rendszer használatát az álszorzáshoz, a decimális CORDIC iránt kevés érdeklődés volt néhány további évig, így Hermann Schmid és Anthony Bogacki még 1973-ban is újdonságként tekintettek rá, és csak később derült ki, hogy a Hewlett-Packard már 1966-ban létrehozta.
A decimális CORDIC a hordozható számológépekben gyakori, melyek nagy része binárisan kódolt decimális számrendszert használ a bináris helyett. E be- és kimeneti változás nem változtatja meg a CORDIC alap számítási algoritmusait. A CORDIC jól használható hordozható számológépekben, ahol az alacsony költség – így a kevés kapu – fontosabb a sebességnél.
A CORDIC-ot használja az ARM-alapú STM32G4, az Intel 8087, a 80287, az 80387 és a 80486 koprocesszor-sorozat, továbbá a Motorola 68881 és a 68882 bizonyos lebegőpontos utasításokhoz, különösképp az FPU alrendszer kapuszámának és összetettségének csökkentésére.
Alkalmazások A CORDIC eltolást és összeadást használ bizonyos számításokhoz, például trigonometriai, hiperbolikus és logaritmikus függvényekhez, valós és komplex szorzásokhoz, osztáshoz, négyzetgyökszámításhoz, lineáris rendszerek megoldásához, sajátértékbecsléshez, szinguláris értékek felbontásához, QR-felbontáshoz stb. Így a CORDIC többek közt jel-, kép-, robotikában és 3D-grafikában is használatos általános tudományos és technikai számításokon kívül.
Hardver Az algoritmust az Apollo-program holdjárójában is alkalmazták az azimut és a holdmodultól való távolság számításához. Alkalmazta az Intel 8087 matematikai koprocesszor (1980) is, így nem kellett hardveres szorzás.
A CORDIC általában gyorsabb más módszereknél hardveres szorzó nélküli rendszerekben (például mikrovezérlőkben) vagy ha a támogatott funkciókhoz szükséges kapuk száma minimalizálandó (például FPGA-ban vagy ASIC-ben). A CORDIC gyakori az FPGA-fejlesztésben, például a Xilinx Vivadójában, míg egy hatványsoros változat nem a specificitása miatt, vagyis a CORDIC számos különböző függvényt képes kiszámítani (általános célú), míg egy hatványsorokat végző hardveres szorzó csak a függvényt tudja számítani, melyre tervezték.
Az STM32G4 sorozat, valamint az STM32H7 MCU-sorozat néhány tagjában CORDIC-modul van, melyek néhány vegyes jeles alkalmazást gyorsítanak, például a felhasználói felület grafikáját és a vektorirányítást. Bár nem oly gyors, mint egy hatványsoros közelítés, a CORDIC gyorsabb a táblázatalapú implementációk, például az ARM CMSIS vagy a C szabványkönyvtárak interpolációjánál. Bár az eredmények kissé pontatlanabbak lehetnek, ugyanis a CORDIC-modulokban csak 20 bit pontosság érhető el az eredményben. Például az ARM-hoz képest lévő teljesítménykülönbség nagy részét a teljes lebegőpontos pontosság (24 bit) interpolációs algoritmus költségei okozzák, melyhez viszonyított relatív hiba érhető el. További előny, hogy a CORDIC modul koprocesszor, így más processzorfeladatokkal párhuzamosan futhat.
A Taylor-sorok hátránya, hogy bár abszolút hibájuk kicsi, a relatív hiba nem viselkedik egyszerűen. Más polinomiális megközelítések, például a minimax közelítőalgoritmus mindkét hiba korlátozására megfelelők.
Szoftver Számos, csak egész számokat kezelő processzoros rendszer a CORDIC-ot használja bizonyos mértékig a lebegőpontos számábrázoláshoz való könyvtárakhoz. Mivel a legtöbb modern, általános célú processzorban van lebegőpontos regiszter gyakori műveletekkel, például összeadással, kivonással, szorzással, osztással, szinusszal, koszinusszal, négyzetgyökkel, 10-es alapú és természetes logaritmussal, a CORDIC implementáció szinte fölösleges. Csak mikrovezérlőkben és speciális biztonsági és időkorlátos szoftverek esetén használatos gyakran a CORDIC.
Módszerek Forgatásos módszer A CORDIC számos különböző függvény számítására használható. E magyarázat megmutatja a CORDIC rotációs módú használatát egy szög szinuszának és koszinuszának számításához, feltéve, hogy a szög radiánban van megadva, és formátumban. Egy szög szinuszának vagy koszinuszának megadásához az adott szögnek megfelelő pont y vagy x koordinátája kell. CORDIC esetén a vektorból indulunk ki:
thumb|300px|Folyamatban lévő CORDIC algoritmus illusztrációja Az első lépés ennek 45°-kal való elfordítása, mely a vektort adja meg. A további iterációk az egyik vagy a másik irányba forgatják a vektort egyre kisebb lépésekkel a kívánt szög eléréséig. A szögek értékei , ahol .
Formálisabban minden iteráció egy fordítást számít ki, mely a forgatási mátrixszal való szorzását jelenti:
A forgatási mátrixot az alábbi képlet adja meg:
Az alábbi két trigonometriai azonosság felhasználásával:
a forgatási mátrix ez lesz:
Az elfordított vektor () képlete:
ahol és koordinátái. A szögek korlátozása értékekre a tangenssel való szorzás cserélhető a kettő hatványával való osztásra, mely egy bitekkel való eltolás. A kifejezés ezzé válik:
ahol
és a határozza meg a forgatás szögét: ha pozitív, +1, ellenkező esetben –1.
Minden tényező elhagyható az iterációs folyamatban, majd mind egyszerre alkalmazható mérettényezővel.
melyet előre kiszámít és táblázatban vagy konstansként tárol fix számú iteráció esetén. Ez a javítás megtehető előre is a méretezésével, mely eggyel csökkenti a szorzások számát. Ezenkívül megjegyezhető, hogy
mely lehetővé teszi az algoritmus összetételének további csökkentését. Egyes esetekben nincs korrekció -ra, így mértékű értéknövekedést okozva:
Elegendően sok iteráció után a vektor szöge közel lesz a kívánt szöghöz. A legtöbb általános célhoz 40 iteráció () elegendő a helyes eredményhez 10 tizedesjegyig.
Ezután az egyetlen megmaradt feladat, hogy a forgatásnak minden iterációban pozitív vagy negatív irányba kell történnie ( értékének választása), mely az egyes iterációkban történő elfordulás számításával és annak a kívánt szögből való kivonásával, majd a szükséges szöghöz való közelítéssel tehető meg: ha pozitív, negatív irányba történik a forgatás, ellenkező esetben pozitívba:
értékeit előre kell számítani és tárolni, azonban kis szögek esetén fixpontos jelölésben, csökkentve a táblázatméretet.
Ahogy a fenti illusztrációban is látható, a végső vektor y koordinátája, míg az x koordináta . Vektormódszer A fent leírt forgatásos algoritmus bármilyen vektort el tud forgatni bármilyen –90 és +90° közti szöggel. A forgatás iránya függ előjelétől.
A vektoros művelet az algoritmus kis módosítását igényli. Egy vektorral kezdődik, melynek x koordinátája pozitív, y koordinátája tetszőleges. Az egymást követő forgatások célja a vektor x tengelyre való forgatása (azaz az y koordináta 0-ra módosítása). Minden lépésben y értéke meghatározza a forgatás irányát. végső értéke a teljes forgásszög, x végső értéke az eredeti vektor nagysága K-val méretezve. A vektormódszer hasznos Descartes-koordinátákról polárkoordinátákra váltáshoz.
Megvalósítások
Szoftveres példa (MATLAB)