CORDIC
A CORDIC („coordinate rotation digital computer”), más néven Volder-algoritmus vagy számjegyenkénti módszer, cirkuláris CORDIC (Jack E. Volder),[1][2] lineáris CORDIC, hiperbolikus CORDIC (John Stephen Walther)[3][4] és általánosított hiperbolikus CORDIC (GH CORDIC) (Yuanyong Luo et al.),[5][6] 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ű mikrokontrollerekben é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[7][8] és Robert Flower 1771-ben,[9] de a CORDIC alacsony komplexitású processzorokra optimalizált.
A CORDIC-ot 1956-ban fogalmazta meg[10][11] 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.[11] Így a CORDIC-ot nvezik néha digitális feloldónak.[12][13]
Volder kutatását a CRC Handbook of Chemistry and Physics 1946-os kiadásában szereplő alábbi képlet inspirálta:[11]
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.[10][11] 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.[10][11] A CORDIC szorzásra és osztásra való használatát is ekkor fogalmazták meg.[11] 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.[11][14]
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.[1][11] 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.[11][15]
Volder CORDIC algoritmusát nyilvánosan 1959-ben írták le,[1][2][11][13][16] 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.[11]
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.[17] A terveket a Hewlett-Packardnak mutatták be 1965 júniusában, de nem fogadták el.[17] 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)[18] javasolt álszorzásnak és álosztásnak nevezve 1961-ben.[18][19] Meggitt módszere a 10-es alap használatát javasolta[18] 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,[20][19] 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[17] 1964 decemberében.[21] 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.[17][21][22][23]
Mikor a Wang Laboratories felfedezte, hogy a HP 9100A hasonló módszert használt, mint a korábbi LOCI–1 (1964. szeptember)[24] és LOCI–2 (1965. január)[25][26] Logarithmic Computing Instrument számológép,[27] sikertelenül vádolták a Hewlett-Packardot An Wang szabadalmának sértéséért 1968-ban.[19][28][29][30]
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.[31][3][4][32] A trigonometriai és hiperbolikus függvények CORDIC-programrészeinek kódja nagyrészt közös lehet.[28] Ezután 1972-ben megjelent az első tudományos hordozható számológép, a HP-35.[28][33][34][35][36][37] 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.[5][6][38][39][40] Elvileg a hiperbolikus CORDIC a GH CORDIC speciális esete.[5]
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á,[16][13][41][42][43] és csak később derült ki, hogy a Hewlett-Packard már 1966-ban létrehozta.[11][13][20][28]
A decimális CORDIC a hordozható számológépekben gyakori,[13] 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,[43][44][45][46][47] a 80287,[47][48] az 80387[47][48] és a 80486[43] koprocesszor-sorozat, továbbá a Motorola 68881[43][44] é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.[49][50]
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.[51][52] A CORDIC az Intel 8087 matematikai koprocesszorban (1980) is használatos volt, így nem kellett hardveres szorzás.[53]
A CORDIC általában gyorsabb más módszereknél hardveres szorzó nélküli rendszerekben (például mikrokontrollerekben) 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.[54] 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.[55] 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.[56] 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ő processzorú 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 mikrokontrollerekben é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:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/89/CORDIC-illustration.png/300px-CORDIC-illustration.png)
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[43]
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:[57]
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)
Alább a CORDIC egy MATLAB/GNU Octave-megvalósítása látható, mely nem függ transzcendens függvényektől, kivéve táblázatok előszámításában. Ha az iterációk száma előre meg van határozva, a második táblázat konstansra cserélhető. A MATLAB dupla pontosságával és a format long kimenetével az eredmények pontossága nagyjából 48 iterációig nő.
function v = cordic(alpha,iteration) % This function computes v = [cos(alpha), sin(alpha)] (alpha in radians) % using iteration increasing iteration value will increase the precision. if alpha < -pi/2 || alpha > pi/2 if alpha < 0 v = cordic(alpha + pi, iteration); else v = cordic(alpha - pi, iteration); end end % Initialization of tables of constants used by CORDIC % need a table of arctangents of negative powers of two, in radians: % angles = atan(2.^-(0:27)); angles = [ ... 0.78539816339745 0.46364760900081 0.24497866312686 0.12435499454676 ... 0.06241880999596 0.03123983343027 0.01562372862048 0.00781234106010 ... 0.00390623013197 0.00195312251648 0.00097656218956 0.00048828121119 ... 0.00024414062015 0.00012207031189 0.00006103515617 0.00003051757812 ... 0.00001525878906 0.00000762939453 0.00000381469727 0.00000190734863 ... 0.00000095367432 0.00000047683716 0.00000023841858 0.00000011920929 ... 0.00000005960464 0.00000002980232 0.00000001490116 0.00000000745058 ]; % and a table of products of reciprocal lengths of vectors [1, 2^-2j]: % Kvalues = cumprod(1./sqrt(1 + 1j*2.^(-(0:23)))) Kvalues = [ ... 0.70710678118655 0.63245553203368 0.61357199107790 0.60883391251775 ... 0.60764825625617 0.60735177014130 0.60727764409353 0.60725911229889 ... 0.60725447933256 0.60725332108988 0.60725303152913 0.60725295913894 ... 0.60725294104140 0.60725293651701 0.60725293538591 0.60725293510314 ... 0.60725293503245 0.60725293501477 0.60725293501035 0.60725293500925 ... 0.60725293500897 0.60725293500890 0.60725293500889 0.60725293500888 ]; Kn = Kvalues(min(iteration, length(Kvalues))); % Initialize loop variables: v = [1;0]; % start with 2-vector cosine and sine of zero poweroftwo = 1; angle = angles(1); % Iterations for j = 0:iteration-1; if alpha < 0 sigma = -1; else sigma = 1; end factor = sigma * poweroftwo; % Note the matrix multiplication can be done using scaling by powers of two and addition subtraction R = [1, -factor; factor, 1]; v = R * v; % 2-by-2 matrix multiply alpha = alpha - sigma * angle; % update the remaining angle poweroftwo = poweroftwo / 2; % update the angle from table, or eventually by just dividing by two if j+2 > length(angles) angle = angle / 2; else angle = angles(j+2); end end % Adjust length of output vector to be [cos(alpha), sin(alpha)]: v = v * Kn; return endfunction
A kétszer kettes mátrixok szorzása egyszerű eltolásokkal és összeadásokkal végezhető el.
x = v[0] - sigma * (v[1] * 2^(-j)); y = sigma * (v[0] * 2^(-j)) + v[1]; v = [x;y];
Javában a Math osztályban van egy ilyen eltolást végző scalb(double x,int scale)
metódus,[58] C-ben van ldexp függvény,[59] az x86 processzorosztályban pedig van fscale
lebegőpontos művelet.[60]
Példa Pythonban
from math import atan2, sqrt, sin, cos, pi, radians ITERS = 16 theta_table = [atan2(1, 2**i) for i in range(ITERS)] def compute_K(n): """ Compute K(n) for n = ITERS. This could also be stored as an explicit constant if ITERS above is fixed. """ k = 1.0 for i in range(n): k *= 1 / sqrt(1 + 2 ** (-2 * i)) return k def CORDIC(alpha, n): K_n = compute_K(n) theta = 0.0 x = 1.0 y = 0.0 P2i = 1 # This will be 2**(-i) in the loop below for arc_tangent in theta_table: sigma = +1 if theta < alpha else -1 theta += sigma * arc_tangent x, y = x - sigma * y * P2i, sigma * P2i * x + y P2i /= 2 return x * K_n, y * K_n if __name__ == "__main__": # Print a table of computed sines and cosines, from -90° to +90°, in steps of 15°, # comparing against the available math routines. print(" x sin(x) diff. sine cos(x) diff. cosine ") for x in range(-90, 91, 15): cos_x, sin_x = CORDIC(radians(x), ITERS) print( f"{x:+05.1f}° {sin_x:+.8f} ({sin_x-sin(radians(x)):+.8f}) {cos_x:+.8f} ({cos_x-cos(radians(x)):+.8f})" )
Kimenet
$ python cordic.py x sin(x) diff. sine cos(x) diff. cosine -90.0° -1.00000000 (+0.00000000) -0.00001759 (-0.00001759) -75.0° -0.96592181 (+0.00000402) +0.25883404 (+0.00001499) -60.0° -0.86601812 (+0.00000729) +0.50001262 (+0.00001262) -45.0° -0.70711776 (-0.00001098) +0.70709580 (-0.00001098) -30.0° -0.50001262 (-0.00001262) +0.86601812 (-0.00000729) -15.0° -0.25883404 (-0.00001499) +0.96592181 (-0.00000402) +00.0° +0.00001759 (+0.00001759) +1.00000000 (-0.00000000) +15.0° +0.25883404 (+0.00001499) +0.96592181 (-0.00000402) +30.0° +0.50001262 (+0.00001262) +0.86601812 (-0.00000729) +45.0° +0.70709580 (-0.00001098) +0.70711776 (+0.00001098) +60.0° +0.86601812 (-0.00000729) +0.50001262 (+0.00001262) +75.0° +0.96592181 (-0.00000402) +0.25883404 (+0.00001499) +90.0° +1.00000000 (-0.00000000) -0.00001759 (-0.00001759)
Hardveres példa
A logikai kapuk száma a CORDIC-hoz nagyjából egy szorzóéhoz hasonló, mivel mindkettőben összeadás és eltolás szükséges. A szorzó- vagy CORDIC-alapú megvalósítás választása kontextusfüggő. Két valós és képzetes rész (Descartes-koordináták) által meghatározott komplex szám szorzása 4 szorzást igényel, de a polárkoordináták által meghatározott komplex számoké elvégezhető CORDIC-kal is, különösen ha a számok nagyságrendje nem számít (egy komplex vektor egységkörön lévő vektorral való szorzása forgatást eredményez). A CORDIC-ot gyakran használják telekommunikációs áramkörökben, például digitális lekonvertálókban.
Dupla iterációs CORDIC
Vlagyimir Bajkov két publikációjában[61][62] javasolta a dupla iterációs módszert az árkusz szinusz, az árkusz koszinusz, a természetes logaritmus, az exponenciális és a hiperbolikus függvények számítására. A dupla iterációs módszer, szemben a klasszikus CORDIC módszerrel, ahol az iterációs lépésszám mindig változik, a dupla iterációs módszerben az iteráció sorszáma kétszer ismétlődik, egyszer változik. Így az iterációk sorszámai: , szemben az egyszerű ismétléssel, ahol . A dupla iterációs módszer biztosítja a módszer konvergenciáját az argumentumok változásának érvényes tartományában.
A CORDIC konvergenciaproblémák tetszőleges alapú helyiértékes számrendszerre való általánosítása megmutatta, hogy a szinusz, koszinusz, árkusz tangens esetén elég iteráció minden i értékre, vagyis az eredmény minden számjegyére. A természetes logaritmus, exponenciális, szinusz, koszinusz és área tangens hiperbolikusz esetén iteráció kell minden i-re, illetve két minden számjegyre, vagyis i minden értékére.[63]
Az área szinusz és koszinusz hiperbolikusz esetén az iterációszám minden i, vagyis minden számjegy esetén.
Kapcsolódó algoritmusok
A CORDIC eltoló-összeadó algoritmus, ahogy a logaritmus- és exponenciálisfüggvény-számító algoritmus, melyek Henry Briggs művében szerepelnek. További, sok elemi függvény számítására használható algoritmus a BKM algoritmus, mely a logaritmust és az exponenciális függvényt általánosítja a komplex síkba. Például a BKM felhasználható valós x radiános szög szinuszának és koszinuszának számításra számításával, mely . A BKM algoritmus kissé összetettebb a CORDIC-nál, de nem kell hozzá a K mérettényező.
Jegyzetek
- ↑ a b c (1959. március 3.) „The CORDIC Computing Technique”. Proceedings of the Western Joint Computer Conference (WJCC), San Francisco, California, USA, 257–261. o, Kiadó: National Joint Computer Committee (NJCC). (Hozzáférés: 2016. január 2.)
- ↑ a b (1959. május 25.) „The CORDIC Trigonometric Computing Technique”. IRE Transactions on Electronic Computers 8 (3), 330–334 (reprint: 226–230). o, Kiadó: The Institute of Radio Engineers, Inc. (IRE). [2021. június 12-i dátummal az eredetiből archiválva]. EC-8(3):330–334. (Hozzáférés: 2023. július 31.)
- ↑ a b (1971. május 1.) „A unified algorithm for elementary functions”. Proceedings of the Spring Joint Computer Conference, Palo Alto, California, USA 38, 379–385. o, Kiadó: Hewlett-Packard Company. [2021. június 12-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.)
- ↑ a b (2000. június 1.) „The Story of Unified CORDIC”. The Journal of VLSI Signal Processing, Hingham, MA, USA 25 (2 (Special issue on CORDIC)), 107–112. o, Kiadó: Kluwer Academic Publishers. DOI:10.1023/A:1008162721424. ISSN 0922-5773.
- ↑ a b c (2019. szeptember 1.) „Generalized Hyperbolic CORDIC and Its Logarithmic and Exponential Computation With Arbitrary Fixed Base”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 27 (9), 2156–2169. o. DOI:10.1109/TVLSI.2019.2919557.
- ↑ a b (2019. szeptember 1.) „Corrections to "Generalized Hyperbolic CORDIC and Its Logarithmic and Exponential Computation With Arbitrary Fixed Base"”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 27 (9), 2222. o. DOI:10.1109/TVLSI.2019.2932174.
- ↑ Arithmetica Logarithmica (1624. augusztus 21.) (angolul: [1] Archiválva 2016. március 4-i dátummal a Wayback Machine-ben.)
- ↑ Henry Briggs and the HP 35, 2014 [2015. március 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 2.) [2] Archiválva 2020. augusztus 10-i dátummal a Wayback Machine-ben
- ↑ The Radix. A new way of making logarithms.. London: J. Beecroft (1771. augusztus 21.)
- ↑ a b c (1956. június 15.) „Binary Computation Algorithms for Coordinate Rotation and Function Generation”, Kiadó: Convair, Aeroelectronics group. IAR-1.148.
- ↑ a b c d e f g h i j k l (2000. június 1.) „The Birth of CORDIC”. Journal of VLSI Signal Processing, Hingham, MA, USA 25 (2 (Special issue on CORDIC)), 101–105. o, Kiadó: Kluwer Academic Publishers. [2016. március 4-i dátummal az eredetiből archiválva]. DOI:10.1023/A:1008110704586. ISSN 0922-5773. (Hozzáférés: 2023. július 31.)
- ↑ (1971. június 1.) „CORDIC Technique Reduces Trigonometric Function Look-Up”. Computer Design, Boston, MA, USA, 72–78. o, Kiadó: Computer Design Publishing Corp.. (Egyes források a szerzőt tévesen P. Z. Perle-nek vagy a lapot Component Designnak nevezik.)
- ↑ a b c d e Decimal Computation, 1 (reprint), Malabar, Florida, USA: Robert E. Krieger Publishing Company, 162, 165–176, 181–193. o. (1983). ISBN 0-89874-318-4 (a reprint egy része hibásan lehetett nyomtatva, ahol a 115–146. oldal hibás.)
- ↑ (1959. szeptember 1.) „Decimal-Binary Conversions in CORDIC”. IRE Transactions on Electronic Computers 8 (3), 335–339. o, Kiadó: The Institute of Radio Engineers, Inc. (IRE). DOI:10.1109/TEC.1959.5222694. ISSN 0367-9950. EC-8(3):335–339. (Hozzáférés: 2016. január 2.)
- ↑ Advanced Systems Group (1962. augusztus 6.). „Technical Description of Fix-taking Tie-in Equipment”, Fort Worth, Texas, USA, Kiadó: General Dynamics. FZE-052.
- ↑ a b Decimal Computation, 1, Binghamton, New York, USA: John Wiley & Sons, Inc., 162, 165–176, 181–193. o. (1974. augusztus 21.). ISBN 0-471-76180-X „So far CORDIC has been known to be implemented only in binary form. But, as will be demonstrated here, the algorithm can be easily modified for a decimal system.* […] *In the meantime it has been learned that Hewlett-Packard and other calculator manufacturers employ the decimal CORDIC techniques in their scientific calculators.”
- ↑ a b c d The HP 9100 Project: An Exothermic Reaction, 2010 (Hozzáférés: 2016. január 2.)
- ↑ a b c (1961. augusztus 29.) „Pseudo Division and Pseudo Multiplication Processes”. IBM Journal of Research and Development, Riverton, New Jersey, USA 6 (2), 210–226, 287. o, Kiadó: IBM Corporation. [2022. február 4-i dátummal az eredetiből archiválva]. DOI:10.1147/rd.62.0210. (Hozzáférés: 2023. július 31.) „John E. Meggitt B.A., 1953; PhD, 1958, Cambridge University. Awarded the First Smith Prize at Cambridge in 1955 and elected a Research Fellowship at Emmanuel College. […] Joined IBM British Laboratory at Hursley, Winchester in 1958. Interests include error-correcting codes and small microprogrammed computers.” ([3], [4])
- ↑ a b c A Quarter Century at HP. Computer History Museum / HP Memories, 2010. november 19. (Hozzáférés: 2016. január 2.) „I even flew down to Southern California to talk with Jack Volder who had implemented the transcendental functions in the Athena machine and talked to him for about an hour. He referred me to the original papers by Meggitt where he'd gotten the pseudo division, pseudo multiplication generalized functions. […] I did quite a bit of literary research leading to some very interesting discoveries. […] I found a treatise from 1624 by Henry Briggs discussing the calculation of common logarithms, interestingly used the same pseudo-division/pseudo-multiplication method that MacMillan and Volder used in Athena. […] We had purchased a LOCI-2 from Wang Labs and recognized that Wang Labs LOCI II used the same algorithm to do square root as well as log and exponential. After the introduction of the 9100 our legal department got a letter from Wang saying that we had infringed on their patent. And I just sent a note back with the Briggs reference in Latin and it said, "It looks like prior art to me." We never heard another word.” ([5])
- ↑ a b (1966. március 14.) „About utilizing CORDIC for computing transcendental functions in BCD”.
- ↑ a b Tom Osborne's Story in His Own Words, 2010 (Hozzáférés: 2016. január 1.)
- ↑ The HP 9100: The Initial Journey, 2010 (Hozzáférés: 2016. január 2.)
- ↑ (1968. szeptember 1.) „Internal Programming of the 9100A Calculator”. Hewlett-Packard Journal, Palo Alto, California, USA, 14–16. o, Kiadó: Hewlett-Packard. (Hozzáférés: 2016. január 2.) ([6])
- ↑ (1964. augusztus 21.) „Extend your Personal Computing Power with the new LOCI-1 Logarithmic Computing Instrument”, 2–3. o, Kiadó: Wang Laboratories, Inc.. (Hozzáférés: 2016. január 3.)
- ↑ Wang LOCI-2. Old Calculator Web Museum, 2013. augusztus 31. (Hozzáférés: 2016. január 3.)
- ↑ Wang LOCI Service Manual. Wang Laboratories, Inc., 1967 (Hozzáférés: 2018. szeptember 14.)
- ↑ Wang Model 360SE Calculator System. Old Calculator Web Museum, 2004. október 23. (Hozzáférés: 2016. január 3.)
- ↑ a b c d The HP-35 Design, A Case Study in Innovation. HP Memory Project, 2010. június 1. (Hozzáférés: 2016. január 2.) „During the development of the desktop HP 9100 calculator I was responsible for developing the algorithms to fit the architecture suggested by Tom Osborne. Although the suggested methodology for the algorithms came from Malcolm McMillan I did considerable amount of reading to understand the core calculations […] Although Wang Laboratories had used similar methods of calculation, my study found prior art dated 1624 that read on their patents. […] This research enabled the adaption of the transcendental functions through the use of the algorithms to match the needs of the customer within the constraints of the hardware. This proved invaluable during the development of the HP-35, […] Power series, polynomial expansions, continued fractions, and Chebyshev polynomials were all considered for the transcendental functions. All were too slow because of the number of multiplications and divisions required. The generalized algorithm that best suited the requirements of speed and programming efficiency for the HP-35 was an iterative pseudo-division and pseudo-multiplication method first described in 1624 by Henry Briggs in 'Arithmetica Logarithmica' and later by Volder and Meggitt. This is the same type of algorithm that was used in previous HP desktop calculators. […] The complexity of the algorithms made multilevel programming a necessity. This meant the calculator had to have subroutine capability, […] To generate a transcendental function such as Arc-Hyperbolic-Tan required several levels of subroutines. […] Chris Clare later documented this as Algorithmic State Machine (ASM) methodology. Even the simple Sine or Cosine used the Tangent routine, and then calculated the Sine from trigonometric identities. These arduous manipulations were necessary to minimize the number of unique programs and program steps […] The arithmetic instruction set was designed specifically for a decimal transcendental-function calculator. The basic arithmetic operations are performed by a 10's complement adder-subtractor which has data paths to three of the registers that are used as working storage.”
- ↑ U.S. Patent {{{1}}}PDF-hivatkozás ([7], [8])
- ↑ Sablon:DE patent ([9])
- ↑ Computer Arithmetic, 2, Los Alamitos: IEEE Computer Society Press. 0818689315 (1990. augusztus 21.). ISBN 9780818689314
- ↑ The Best Computer Papers of 1971. Auerbach Publishers, 71. o. (1972. augusztus 21.). ISBN 0877691274
- ↑ (1972. június 1.) „Algorithms and Accuracy in the HP-35”. Hewlett-Packard Journal 23 (10), 10–11. o. [2013. október 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.)
- ↑ HP35 trigonometric algorithm, 2005. december 6. [2015. március 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 2.) [10] Archiválva 2020. augusztus 10-i dátummal a Wayback Machine-ben
- ↑ (2005. február 1.) „The secret of the algorithms”. L'Ordinateur Individuel, Paris, France (24). [2016. augusztus 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.) [11] Archiválva 2021. június 12-i dátummal a Wayback Machine-ben
- ↑ Digit by digit methods, 2012. február 1. [2016. augusztus 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 2.) [12] Archiválva 2021. június 12-i dátummal a Wayback Machine-ben
- ↑ HP 35 Logarithm Algorithm, 2012. február 1. [2016. augusztus 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 7.) [13] Archiválva 2020. augusztus 10-i dátummal a Wayback Machine-ben
- ↑ (2020. január 1.) „GH CORDIC-Based Architecture for Computing Nth Root of Single-Precision Floating-Point Number”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 28 (4), 864–875. o. DOI:10.1109/TVLSI.2019.2959847.
- ↑ (2019. szeptember 1.) „Low Complexity Generic VLSI Architecture Design Methodology for Nth Root and Nth Power Computations”. IEEE Transactions on Circuits and Systems I: Regular Papers 66 (12), 4673–4686. o. DOI:10.1109/TCSI.2019.2939720.
- ↑ (2019. november 1.) „CORDIC as a Switched Nonlinear System”. Circuits, Systems and Signal Processing 39 (6), 3234–3249. o. DOI:10.1007/s00034-019-01295-8.
- ↑ (1973. február 20.) „Use Decimal CORDIC for Generation of Many Transcendental Functions”. EDN, 64–73. o.
- ↑ An Analysis of Algorithms for Hardware Evaluation of Elementary Functions. Monterey, California, USA: Department of the Navy, Naval Postgraduate School. NPS-53FE73051A (1973. május 8.)
- ↑ a b c d e Elementary Functions: Algorithms and Implementation, 2, Boston: Birkhäuser, 134. o. (2006. augusztus 21.). ISBN 978-0-8176-4372-0
- ↑ The 8087 Primer, 1, John Wiley & Sons Australia, Limited. 9780471875697 (1984. augusztus 21.). ISBN 0471875694
- ↑ (1990. január) „Math Coprocessors: A look at what they do, and how they do it”. Byte 15 (1), 337–348. o. ISSN 0360-5280.
- ↑ a b c (1990. október 1.) „Implementing CORDIC algorithms – A single compact routine for computing transcendental functions”. Dr. Dobb's Journal, 152–156. o. (Hozzáférés: 2016. január 2.)
- ↑ a b (1988. augusztus 21.) „Intel's Floating-Point Processors”. Electro/88 Conference Record, 48/5/1–7. o.
- ↑ (2008. augusztus 22.) „cordic_review.pdf 50 Years of CORDIC: Algorithms, Architectures and Applications”. IEEE Transactions on Circuits and Systems I: Regular Papers 56 (9), 1893–1907. o. DOI:10.1109/TCSI.2009.2025803.
- ↑ (2013. február 1.) „Low Complexity Generic VLSI Architecture Design Methodology for Nth Root and Nth Power Computations”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 21 (2), 217–228. o. DOI:10.1109/TVLSI.2012.2187080.
- ↑ Technical Memorandum 70-2014-8: The Navigation System of the Lunar Roving Vehicle. NASA . Bellcomm, 1970. december 11.
- ↑ Technical Note D-7469: Lunar Roving Vehicle Navigation System Performance Review. NASA . Marshall Space Flight Center, 1973. november 1.
- ↑ Extracting ROM constants from the 8087 math coprocessor's die. righto.com , 2020. május 1. (Hozzáférés: 2020. szeptember 3.) „The ROM contains 16 arctangent values, the arctans of 2−n. It also contains 14 log values, the base-2 logs of (1+2−n). These may seem like unusual values, but they are used in an efficient algorithm called CORDIC, which was invented in 1958.”
- ↑ Getting started with the CORDIC accelerator using STM32CubeG4 MCU Package. STMicroelectronics. (Hozzáférés: 2021. január 1.)
- ↑ CMSIS/CMSIS/DSP_Lib/Source/ControllerFunctions/arm_sin_cos_f32.c. Github . ARM. (Hozzáférés: 2021. január 1.)
- ↑ Error bounds of Taylor Expansion for Sine. Math Stack Exchange . (Hozzáférés: 2021. január 1.)
- ↑ (1998. augusztus 21.) „A survey of CORDIC algorithms for FPGA based computers”. ACM, North Kingstown, RI, USA, Kiadó: Andraka Consulting Group, Inc.. 0-89791-978-5/98/01. (Hozzáférés: 2016. május 8.)
- ↑ Class Math. Java Platform Standard. Oracle Corporation, 2018 [2018. augusztus 6-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. augusztus 6.)
- ↑ ldexp, ldexpf, ldexpl. cppreference.com , 2015. június 11. [2018. augusztus 6-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. augusztus 6.)
- ↑ Intel 64 and IA-32 Architectures Software Developer's Manual Volume 1: Basic Architecture. Intel Corporation, 8–22. o. (2016. szeptember 1.)
- ↑ Baykov, Vladimir: The outline (autoreferat) of my PhD, published in 1972. baykov.de . (Hozzáférés: 2023. május 3.)
- ↑ Vladimir, Baykov: Hardware implementation of elementary functions in computers. baykov.de . (Hozzáférés: 2023. május 3.)
- ↑ Special-purpose processors: iterative algorithms and structures. baykov.de . (Hozzáférés: 2023. május 3.)
Források
- (1966. szeptember 5.) „DIVIC Gives Answer to Complex Navigation Questions”. Electronics, 105–111. o. ISSN 0013-5070. (NB. A DIVIC jelentése DIgital Variable Increments Computer. Egyes források tévesen J. M. Parininek nevezik a szerzőt.)
- (1965. november 1.) „The IBM System/360 Model 91: Floating-Point Execution Unit”. IBM Journal of Research and Development, Riverton, New Jersey, USA 11 (1), 34–53. o. [2016. március 5-i dátummal az eredetiből archiválva]. DOI:10.1147/rd.111.0034. (Hozzáférés: 2023. július 31.)
- An Interconnect Processor with Emphasis on CORDIC Mode Operation. Berkeley, CA, USA: University of California, Berkeley, Department of Electrical Engineering (1968. szeptember 1.). OCLC 500565168
- U.S. Patent 3576983A PDF-hivatkozás ([14])
- (1972. július 1.) „Automatic Computation of Exponentials, Logarithms, Ratios, and Square Roots”. IBM Journal of Research and Development 16 (4), 380–388. o. [2016. augusztus 12-i dátummal az eredetiből archiválva]. DOI:10.1147/rd.164.0380. ISSN 0018-8646. (Hozzáférés: 2023. július 31.)
- (1977. május 1.) „Personal Calculator Algorithms I: Square Roots”. Hewlett-Packard Journal, Palo Alto, California, USA 28 (9), 22–24. o, Kiadó: Hewlett-Packard. [2015. december 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.) ([15])
- (1977. június 1.) „Personal Calculator Algorithms II: Trigonometric Functions”. Hewlett-Packard Journal, Palo Alto, California, USA 28 (10), 17–20. o, Kiadó: Hewlett-Packard. [2016. március 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.) ([16])
- (1977. november 1.) „Personal Calculator Algorithms III: Inverse Trigonometric Functions”. Hewlett-Packard Journal, Palo Alto, California, USA 29 (3), 22–23. o, Kiadó: Hewlett-Packard. [2016. március 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.) ([17])
- (1978. április 1.) „Personal Calculator Algorithms IV: Logarithmic Functions”. Hewlett-Packard Journal, Palo Alto, California, USA 29 (8), 29–32. o, Kiadó: Hewlett-Packard. [2016. március 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. július 31.) ([18])
- (1975. augusztus 21.) „Calculator Algorithms”. IEEE Compcon Reader Digest, 139–141. o, Kiadó: IEEE. IEEE Catalog No. 75 CH 0920-9C.
- {{{title}}} (orosz nyelven). Leningrad State University of Electrical Engineering (1972. augusztus 21.)
- Apparaturnaja realizatsija elementarnikh funktsij v CVM (orosz nyelven). Leningrad State University (1975. augusztus 21.)
- {{{title}}} (orosz nyelven). Moscow: Radio i svjaz (Радио и связь) (1982. augusztus 21.)
- {{{title}}} (orosz nyelven). Moscow: Radio i svjaz (Радио и связь) (1985. augusztus 21.)
- (1980. január 1.) „CORDIC constants in TI 58/59 ROM”. Texas Instruments Software Exchange Newsletter, Kapellen, Belgium 2 (2), Kiadó: TISOFT.
- (April–June 1980) „Natural logarithm computation scheme / ex computing scheme / 1/x computing scheme”. Texas Instruments Software Exchange Newsletter, Kapellen, Belgium 2 (3), Kiadó: TISOFT. (about CORDIC in TI-58/TI-59)
- TI Graphic Products Team. „Transcendental function algorithms”, Texas Instruments, Consumer Products, 1995. augusztus 21.. [2016. március 17-i dátummal az eredetiből archiválva] (Hozzáférés: 2019. március 2.)
- Arithmetische Algorithmen der Mikrorechentechnik, 1 (német nyelven), Berlin, Germany: VEB Verlag Technik, 219, 261, 271–296. o.. Sablon:EAN. MPN 5539165. License 201.370/4/89 (1989. augusztus 21.). ISBN 3341005153
- Solving Kepler's equation with CORDIC double iterations. Göttingen, Germany: Institut für Astrophysik, Georg-August-Universität, 109–117. o.. DOI: 10.1093/mnras/staa2441 (2021)
- Digital Signal Processing in Communication Systems, 1 (1994. augusztus 21.)
- (1996. augusztus 21.) „On hardware for computing exponential and trigonometric functions”. IEEE Transactions on Computers 45 (3), 328–339. o. DOI:10.1109/12.485571.
- 6.5 Sine and Cosine Functions, Low Power and Low Complexity Shift-and-Add Based Computations, 1, Linköping Studies in Science and Technology, Department of Electrical Engineering, Linköping University, 244–250. o.. No. 1201 (2008. augusztus 21.). ISBN 978-91-7393-836-5 (x+268 pages)
- (2001. augusztus 21.) „FPGA realization of a CORDIC based FFT processor for biomedical signal processing”. Microprocessors and Microsystems, Kharagpur, West Bengal, India 25 (3), 131–142. o. DOI:10.1016/S0141-9331(01)00106-5.
- Pseudo-Division Algorithms for Floating-Point Logarithms and Exponentials. University of California, 2002. május 20. [2015. december 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 15.)
- Implementation of a CORDIC Algorithm in a Digital Down-Converter, 2008
- (2009. október 6.) „CORDIC Architectures: A Survey”. VLSI Design, Kharagpur, West Bengal, India 2010, 1–19. o, Kiadó: Department of Electronics and Electrical Communication Engineering, Indian Institute of Technology. DOI:10.1155/2010/794891. 794891.
- Advanced Arithmetic Techniques. quadibloc, 2018 [2018. július 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. július 16.)
További információk
- CORDIC Bibliography Site, 2011. július 1.
- Soft CORDIC IP (verilog HDL code)
- CORDIC Bibliography Site
- BASIC Stamp, CORDIC math implementation
- CORDIC implementation in verilog
- CORDIC Vectoring with Arbitrary Target Value
- PicBasic Pro, Pic18 CORDIC math implementation
- Python CORDIC implementation Archiválva 2017. március 17-i dátummal a Wayback Machine-ben
- Simple C code for fixed-point CORDIC
- Tutorial and MATLAB Implementation – Using CORDIC to Estimate Phase of a Complex Number
- Descriptions of hardware CORDICs in Arx with testbenches in C++ and VHDL
- An Introduction to the CORDIC algorithm
- 50-th Anniversary of the CORDIC Algorithm
- CORDIC-implementációk: fixed point C code for trigonometric and hyperbolic functions, C code for test and performance verification