CORDIC - CORDIC

CORDIC (a CO ordináta R otation DI gital C omputer), más néven Volder algoritmus , vagy: Digit-by-jegyű módszerrel Circular CORDIC (Jack E. Volder), Lineáris CORDIC , hiperbolikus CORDIC (John Stephen Walther), és a generalizált hiperbolikus A CORDIC ( GH CORDIC ) (Yuanyong Luo et al.) Egy egyszerű és hatékony algoritmus trigonometrikus függvények , hiperbolikus függvények , négyzetgyök , szorzás , osztás , valamint tetszőleges bázisú exponenciálok és logaritmusok kiszámítására , általában egy számjeggyel (vagy bittel) ) iterációnként. A CORDIC tehát példa a számjegyű algoritmusokra is . A CORDIC és a szorosan kapcsolódó módszereket pszeudo-szorzás , pszeudo-osztás vagy tényezőkombináció néven általában akkor használják, ha nincs hardveres szorzó (pl. Egyszerű mikrovezérlőkben és FPGA-kban ), mivel az egyetlen művelet, amelyre szükség van, az összeadás , kivonás , biteltolás és keresési táblázat. . Mint ilyenek, mindegyik a shift-and-add algoritmusok osztályába tartozik . A számítástechnikában a CORDIC-ot gyakran használják lebegőpontos aritmetika megvalósítására, ha a célplatformon nincsenek hardveres szaporodások költség vagy hely miatt.

Történelem

Hasonló matematikai technikákat publikált Henry Briggs már 1624-ben és Robert Flower 1771-ben, de a CORDIC jobban optimalizált az alacsony bonyolultságú véges állapotú CPU-khoz.

CORDIC született 1956-ban Jack E. Volder a aeroelectronics osztályán Convair ki kell váltani a analóg rezolverkábel a B-58 bombázó „s navigációs számítógép pontosabb és gyorsabb a valós idejű digitális megoldás. Ezért a CORDIC -ot néha digitális felbontóként emlegetik .

Kutatásában Voldert a CRC kémiai és fizikai kézikönyve 1946 -os kiadásának egyik formulája ihlette :

{\ displaystyle {\ begin {aligned} K_ {n} R \ sin (\ theta \ pm \ varphi) & = R \ sin (\ theta) \ pm 2^{-n} R \ cos (\ theta), \ \ K_ {n} R \ cos (\ theta \ pm \ varphi) & = R \ cos (\ theta) \ mp 2^{-n} R \ sin (\ theta), \\\ end {aligned}}}

A , . ${\ displaystyle K_ {n} = {\ sqrt {1+2^{-2n}}}}$ ${\ displaystyle \ tan (\ varphi) = 2^{-n}}$

Kutatásai egy belső műszaki jelentéshez vezettek, amely a CORDIC algoritmust javasolta a szinusz- és koszinuszfüggvények megoldására, valamint egy prototípusos számítógépet, amely ezt megvalósította. A jelentés tárgyalta a hiperbolikus koordináta -forgatás , logaritmusok és exponenciális függvények kiszámításának lehetőségét is módosított CORDIC algoritmusokkal. Kihasználva CORDIC a szorzás és osztás is fogant ebben az időben. A CORDIC elve alapján Dan H. Daggett, a Convair Volder munkatársa konverziós algoritmusokat dolgozott ki a bináris és a binárisan kódolt tizedes (BCD) között.

1958-ban, Convair végre kezdett építeni egy demonstrációs rendszert, hogy megoldja radar fix -taking problémákat elemzi CORDIC én , elkészült 1960-ban, anélkül Volder, aki elhagyta a céget már. Az univerzálisabb CORDIC II A (helyhez kötött) és B (légi) modelleket Daggett és Harry Schuss építették és tesztelték 1962 -ben.

Volder CORDIC algoritmusát először 1959-ben írták le a nyilvánosság előtt, ami miatt olyan vállalatok építették be a navigációs számítógépekbe, mint a Martin-Orlando , a Computer Control , a Litton , a Kearfott , a Lear-Siegler , a Sperry , a Raytheon és a Collins Radio .

Volder összefogott Malcolm McMillan-lel, hogy elkészítsék az Athena-t , egy fixpontos asztali számológépet, amely a bináris CORDIC algoritmusát használja. A dizájnt 1965 júniusában mutatták be a Hewlett-Packardnak , de nem fogadták el. Mégis, McMillan be David S. Cochran (HP) a Volder algoritmus és amikor Cochran később találkozott Volder utalt rá, hogy egy hasonló megközelítést John E. MEGGITT (IBM) azt javasolta, mint pszeudo-szorzás és pszeudo-osztály 1961-ben MEGGITT módszere volt szintén a 10 -es bázis használatát javasolja a 2 -es bázis helyett , ahogyan azt Volder CORDIC eddig használta. Ezek a törekvések 1966-ban a Hewlett-Packardon belüli tizedes CORDIC prototípus ROM-os logikai megvalósításához vezettek, amelyet Thomas E. Osborne prototípusos Green Machine , négyfunkciós , lebegőpontos asztali számológépe épített és fogalmilag vezetett le. 1964 decemberében fejeződött be a DTL logika szerint. A projekt eredményeként 1968 márciusában nyilvánosan bemutatták a Hewlett-Packard első tudományos funkciókkal rendelkező asztali számológépét, a hp 9100A- t, és a sorozatgyártás még ebben az évben megkezdődött.

Amikor Wang Laboratories találtuk, hogy a HP 9100A használt hasonló megközelítést a tényező kombinálása eljárás korábbi LOC-1 (szeptember 1964) és LOC-2 (január 1965) logaritmikus Computing eszköz asztali számológépek, akkor sikertelenül azzal vádolta a Hewlett-Packard megsértése An Wang egyik szabadalma 1968 -ban.

John Stephen Walther, a Hewlett-Packard munkatársa 1971-ben általánosította az algoritmust az Unified CORDIC algoritmusba, lehetővé téve a hiperbolikus függvények , természetes exponenciális értékek , természetes logaritmusok , szorzások , osztások és négyzetgyök kiszámítását . A trigonometrikus és hiperbolikus függvények CORDIC alprogramjai megoszthatják kódjuk nagy részét. Ennek eredményeként 1972 - ben született meg az első tudományos kézi számológép , a HP-35 . A hiperbolikus CORDIC alapján Yuanyong Luo és mtsai. javaslatot tett továbbá egy általánosított hiperbolikus CORDIC (GH CORDIC) módszerre a logaritmusok és exponenciálok közvetlen kiszámításához, tetszőlegesen rögzített bázissal 2019 -ben. Elméletileg a Hyperbolic CORDIC a GH CORDIC különleges esete.

Eredetileg a CORDIC-ot csak a bináris számrendszer alkalmazásával valósították meg, és annak ellenére, hogy Meggitt a tizedesrendszer használatát javasolta álszaporítási módszeréhez, a decimális CORDIC még több évig hallatlan maradt, így Hermann Schmid és Anthony Bogacki továbbra is azt javasolta, hogy 1973-ban újdonságnak számított, és csak később derült ki, hogy a Hewlett-Packard már 1966-ban megvalósította.

A decimális CORDIC széles körben elterjedt a zsebszámológépekben , amelyek többsége bináris kódolású decimális (BCD), és nem bináris. Ez a változás a bemeneti és kimeneti formátumban nem változtatta meg a CORDIC alapvető számítási algoritmusait. A CORDIC különösen alkalmas kézi számológépekhez, ahol az alacsony költség-és így az alacsony chipkapu-sokkal fontosabb, mint a sebesség.

A CORDIC-t az ARM-alapú STM32G4 , Intel 8087 , 80287 , 80387 és a 80486-os társprocesszor sorozatok, valamint a Motorola 68881 és 68882 modellekben alkalmazták bizonyos lebegőpontos utasításokra, elsősorban a kapuk számának csökkentése érdekében (és összetettsége) az FPU alrendszerben.

Alkalmazások

A CORDIC egyszerű számítástechnikai feladatokat használ számos számítási feladathoz, például trigonometrikus, hiperbolikus és logaritmikus függvények kiszámításához, valós és összetett szorzásokhoz, osztáshoz, négyzetgyök-számításhoz, lineáris rendszerek megoldásához, sajátérték- becsléshez, szinguláris értékbontáshoz , QR-faktorizáláshoz és sok más. Ennek eredményeképpen a CORDIC -ot az általános tudományos és műszaki számításon kívül számos területen alkalmazták, például jel- és képfeldolgozás , kommunikációs rendszerek , robotika és 3D -s grafika .

Hardver

Az algoritmust használja fel a navigációs rendszer az Apollo-program „s holdjáró a számítási csapágy és a tartomány, illetve távolságra a Lunar modul . A CORDIC -ot az Intel 8087 matematikai társprocesszor megvalósítására használták 1980 -ban, elkerülve a hardveres szorzás megvalósítását.

A CORDIC általában gyorsabb, mint más megközelítések, ha nincs hardver -szorzó (pl. Mikrokontroller), vagy ha minimálisra kell csökkenteni az általa támogatott funkciók megvalósításához szükséges kapuk számát (pl. FPGA vagy ASIC ). Valójában a CORDIC szabványos IP-es csepp IP az olyan FPGA fejlesztési alkalmazásokban, mint a Vivado for Xilinx, míg a hatósoros megvalósítás nem az ilyen IP sajátosságainak köszönhető, azaz a CORDIC számos különböző funkciót tud kiszámítani (általános célú), míg A hatósoros megvalósítások végrehajtására konfigurált hardver -szorzó csak azt a funkciót tudja kiszámítani, amelyre tervezték.

Másrészt, ha rendelkezésre áll egy hardver-szorzó ( pl . DSP mikroprocesszorban), akkor a táblázatkeresési módszerek és a teljesítménysorozatok általában gyorsabbak, mint a CORDIC. Az elmúlt években a CORDIC algoritmust széles körben alkalmazták különböző biomedicinális alkalmazásokhoz, különösen az FPGA megvalósításokban.

Az STM32G4 sorozat és egyes STM32H7 sorozatú MCU -k CORDIC modult valósítanak meg, hogy felgyorsítsák a számításokat különböző vegyes jelű alkalmazásokban, például az emberi gép interfész grafikájában és a motorok terepi irányításában . Bár a CORDIC nem olyan gyors, mint a hatósoros közelítés, a CORDIC valóban gyorsabb, mint a tábla alapú implementációk interpolálása, például az ARM CMSIS és a C szabványos könyvtárak. Bár az eredmények kissé kevésbé pontosak lehetnek, mivel a CORDIC modulok csak 20 bit pontosságot érnek el az eredményben. Például az ARM megvalósításhoz képest a teljesítménykülönbségek nagy része az interpolációs algoritmus általános költségeinek köszönhető, amely teljes lebegőpontos (24 bites) pontosságot ér el, és valószínűleg relatív hibát érhet el ezzel a pontossággal. További előnye, hogy a CORDIC modul társprocesszor, és más CPU -feladatokkal párhuzamosan is futtatható.

A teljesítménysorozat használatával az a probléma, hogy bár kicsi abszolút hibát adnak, nem mutatnak jól viselkedő relatív hibát.

Szoftver

Sok régebbi, csak egész számot tartalmazó CPU-val rendelkező rendszer IEEE lebegőpontos könyvtárai részeként különböző mértékben implementálta a CORDIC -ot . Mivel a legtöbb modern, általános célú CPU lebegőpontos regiszterekkel rendelkezik, amelyek közös műveleteket végeznek, mint például összeadás, kivonás, szorzás, osztás, szinusz, koszinusz, négyzetgyök, napló ₁₀ , természetes napló, a CORDIC szoftverrel való megvalósításának szükségessége szinte nem szükséges -létezik. Csak a mikrokontrollernek vagy speciális biztonsági és időkorlátozott szoftveralkalmazásoknak kell figyelembe venniük a CORDIC használatát.

Működési módok

Forgatási mód

A CORDIC számos különböző funkció kiszámítására használható. Ez a magyarázat azt mutatja, hogyan kell használni CORDIC a forgás módban számítani a szinusz és koszinusz egy szög, feltételezve, hogy a kívánt szöget adják radiánban és képviselt fixpontos formátumban. Annak megállapításához, a szinusz vagy koszinusz egy szöget , az y vagy x koordinátája egy pont a készülék kör megfelel a kívánt szöget kell találni. A CORDIC használatával a vektorral kezdenénk : ${\ displaystyle \ beta}$ ${\ displaystyle v_ {0}}$

{\ displaystyle v_ {0} = {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}}.}

A folyamatban lévő CORDIC algoritmus illusztrációja

Az első iterációban ezt a vektort 45 ° -kal elforgatjuk az óramutató járásával ellentétes irányba, hogy megkapjuk a vektort . Az egymást követő iterációk méretcsökkentő lépésekkel forgatják a vektort egyik vagy másik irányba, amíg el nem érik a kívánt szöget. A lépés mérete erre való . ${\ displaystyle v_ {1}}$ ${\ displaystyle i}$ ${\ displaystyle \ arctan {(2^{-i})}}$ ${\ displaystyle i = 0,1,2, \ dot}$

Formálisabban minden iteráció kiszámítja a forgást, amelyet úgy hajtunk végre, hogy megszorozzuk a vektort a forgási mátrixszal : ${\ displaystyle v_ {i}}$ ${\ displaystyle R_ {i}}$

{\ displaystyle v_ {i+1} = R_ {i} v_ {i}.}

A forgási mátrixot a

{\ displaystyle R_ {i} = {\ begin {bmatrix} \ cos (\ gamma _ {i}) &-\ sin (\ gamma _ {i}) \\\ sin (\ gamma _ {i}) & \ cos (\ gamma _ {i}) \ end {bmatrix}}.}

A következő két trigonometrikus azonosság használatával :

{\ displaystyle {\ begin {aligned} \ cos (\ gamma _ {i}) & = {\ frac {1} {\ sqrt {1+ \ tan ^{2} (\ gamma _ {i})}}} , \\\ sin (\ gamma _ {i}) & = {\ frac {\ tan (\ gamma _ {i})} {\ sqrt {1+ \ tan ^{2} (\ gamma _ {i}) }}}, \ end {igazítva}}}

a forgási mátrix lesz

{\ displaystyle R_ {i} = {\ frac {1} {\ sqrt {1+ \ tan ^{2} (\ gamma _ {i})}}} {\ begin {bmatrix} 1 &-\ tan (\ gamma _ {i}) \\\ tan (\ gamma _ {i}) & 1 \ end {bmatrix}}.}

Ekkor a forgatott vektor kifejezése lesz ${\ displaystyle v_ {i+1} = R_ {i} v_ {i}}$

{\ displaystyle v_ {i+1} = {\ frac {1} {\ sqrt {1+ \ tan ^{2} (\ gamma _ {i})}}} {\ begin {bmatrix} 1 &-\ tan ( \ gamma _ {i}) \\\ tan (\ gamma _ {i}) & 1 \ end {bmatrix}} {\ begin {bmatrix} x_ {i} \\ y_ {i} \ end {bmatrix}},}

hol és hol vannak az összetevői . A szögeket úgy korlátozzuk , hogy az érintővel való szorzás helyettesíthető kettes hatványú osztással, ami hatékonyan végezhető el a digitális számítógépes hardverekben biteltolással . A kifejezés ezután lesz ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {i}}$ ${\ displaystyle v_ {i}}$ ${\ displaystyle \ gamma _ {i}}$ ${\ displaystyle \ tan (\ gamma _ {i}) = \ pm 2^{-i}}$

{\ displaystyle v_ {i+1} = K_ {i} {\ begin {bmatrix} 1 &-\ sigma _ {i} 2^{-i} \\\ sigma _ {i} 2^{-i} & 1 \ end {bmatrix}} {\ begin {bmatrix} x_ {i} \\ y_ {i} \ end {bmatrix}},}

ahol

{\ displaystyle K_ {i} = {\ frac {1} {\ sqrt {1+2^{-2i}}}},}

és a forgás irányának meghatározására szolgál: ha a szög pozitív, akkor +1, különben −1. ${\ displaystyle \ sigma _ {i}}$ ${\ displaystyle \ gamma _ {i}}$ ${\ displaystyle \ sigma _ {i}}$

${\ displaystyle K_ {i}}$ figyelmen kívül hagyható az iteratív folyamatban, majd ezt követően skálázási tényezővel alkalmazható

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

amelyet előre kiszámítanak, és egy táblázatban vagy egyetlen konstansként tárolnak, ha az iterációk száma rögzített. Ezt a korrekciót előre is meg lehet tenni, méretezéssel és ezáltal szorzás mentésével. Ezenkívül megjegyezhető, hogy ${\ displaystyle v_ {0}}$

{\ displaystyle K = \ lim _ {n \ to \ infty} K (n) \ kb 0.6072529350088812561694}

lehetővé teszi az algoritmus összetettségének további csökkentését. Egyes alkalmazások elkerülhetik a javítást , ami feldolgozási nyereséget eredményez : ${\ displaystyle K}$ ${\ displaystyle A}$

{\ displaystyle A = {\ frac {1} {K}} = \ lim _ {n \ to \ infty} \ prod _ {i = 0}^{n-1} {\ sqrt {1+2^{- 2i}}} \ kb 1,64676025812107.}

Megfelelő számú iteráció után a vektor szöge közel lesz a kívánt szöghöz . A legtöbb szokásos célra 40 iteráció ( n = 40) elegendő a helyes eredmény eléréséhez a tizedes tizedesjegyig. ${\ displaystyle \ beta}$

Már csak az a feladat, hogy meghatározza, hogy a forgatást az óramutató járásával megegyező vagy az óramutató járásával ellentétes irányban kell -e végezni minden iterációnál (a érték kiválasztásával ). Ez úgy történik, hogy nyomon követi, hogy mennyit forgatták a szöget minden iteráció során, és kivonják azt a kívánt szögből; majd annak érdekében, hogy közelebb kerüljön a kívánt szöghez , ha pozitív, a forgás az óramutató járásával megegyező irányba történik, ellenkező esetben negatív, és a forgás az óramutató járásával ellentétes: ${\ displaystyle \ sigma}$ ${\ displaystyle \ beta}$ ${\ displaystyle \ beta _ {n+1}}$

{\ displaystyle \ beta _ {0} = \ beta}

{\ displaystyle \ beta _ {i+1} = \ beta _ {i}-\ sigma _ {i} \ gamma _ {i}, \ quad \ gamma _ {i} = \ arctan (2^{-i} ).}

A (z) értékeit szintén előre ki kell számítani és tárolni kell. De kis szögeknél, fixpontos ábrázolásban, csökkentve az asztal méretét. ${\ displaystyle \ gamma _ {n}}$ ${\ displaystyle \ arctan (\ gamma _ {n}) = \ gamma _ {n}}$

Mint látható a fenti illusztráció mutatja, a szinusz a szög a y koordinátája végső vektorban , míg a X koordináta a cosinus érték. ${\ displaystyle \ beta}$ ${\ displaystyle v_ {n},}$

Vektoros mód

A fent leírt forgatási módú algoritmus bármilyen vektort elforgathat (nemcsak az x tengely mentén igazított egységvektorokat ) –90 ° és +90 ° közötti szöggel. A forgás irányával kapcsolatos döntések pozitív vagy negatív döntéstől függenek . ${\ displaystyle \ beta _ {i}}$

A vektoros működési mód az algoritmus enyhe módosítását igényli. Egy vektorral kezdődik, amelynek x koordinátája pozitív, az y koordináta tetszőleges. Az egymást követő forgatások célja, hogy a vektort az x tengelyre forgassák (és ezért az y koordinátát nullára csökkentsék ). Minden lépésben az y értéke határozza meg a forgás irányát. A végső értéke tartalmazza a teljes forgásszöget. Az x végső értéke az eredeti vektor nagysága lesz K -vel skálázva . Tehát a vektoros mód nyilvánvaló használata a téglalap alakú poláris koordinátákká való átalakítás. ${\ displaystyle \ beta _ {i}}$

Végrehajtás

Szoftver példa

Az alábbiakban a CORDIC MATLAB / GNU Octave megvalósítását mutatjuk be, amely nem támaszkodik semmilyen transzcendentális függvényre, kivéve a táblázatok előszámítását . Ha az n iterációk száma előre meghatározott, akkor a második táblázat egyetlen állandóval helyettesíthető. A MATLAB szabványos kettős pontosságú aritmetikai és "formátum hosszú" nyomtatásával az eredmények pontossága n- ig körülbelül 48-ig nő .

function v = cordic(beta,n)
% This function computes v = [cos(beta), sin(beta)] (beta in radians)
% using n iterations. Increasing n will increase the precision.

if beta < -pi/2 || beta > pi/2
    if beta < 0
        v = cordic(beta + pi, n);
    else
        v = cordic(beta - pi, n);
    end
    v = -v; % flip the sign for second or third quadrant
    return
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./abs(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(n, 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:n-1;
    if beta < 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
    beta = beta - 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(beta), sin(beta)]:
v = v * Kn;
return

endfunction

A kétszeres mátrixszorzást pár egyszerű eltolással és összeadással lehet elvégezni.

    x = v[0] - sigma * (v[1] * 2^(-j));
    y = sigma * (v[0] * 2^(-j)) + v[1];
    v = [x; y];

Java -ban a Math osztály rendelkezik egy scalb(double x,int scale)módszerrel az ilyen váltás végrehajtására, a C az ldexp függvénnyel, az x86 osztályú processzorok pedig a fscalelebegőpontos művelettel.

Hardver példa

A CORDIC megvalósításához szükséges logikai kapuk száma nagyjából összehasonlítható a szorzóhoz szükséges számmal, mivel mindkettő műszakok és kiegészítések kombinációját igényli. A szorzó- vagy CORDIC-alapú megvalósítás választása a kontextustól függ. Például két komplex szám szorzata, amelyet valós és képzelt komponenseik képviselnek (téglalap alakú koordináták), 4 szorzást igényel, de megvalósítható egyetlen CORDIC segítségével, amely a poláris koordinátáik által képviselt komplex számokon működik, különösen, ha a számok nagysága nem releváns (ha összetett vektort megszorozunk az egységkörön lévő vektorral, az valójában egy forgást jelent). A CORDIC -okat gyakran használják távközlési áramkörökben, például digitális lefelé konverterekben .

Dupla iterációk CORDIC

A publikációkban: http://baykov.de/CORDIC1972.htm és http://baykov.de/CORDIC1975.htm javasolták a kettős iterációs módszer használatát a funkciók végrehajtásához: arcsinX, arccosX, lnX, expX , valamint a hiperbolikus függvények kiszámításához. A kettős iterációs módszer abban áll, hogy a klasszikus CORDIC módszerrel ellentétben, ahol az iterációs lépés értéke MINDEN alkalommal változik, azaz minden iterációnál, a kettős iterációs módszerben az iterációs lépés értéke kétszer megismétlődik, és csak egy iteráció során változik. Ezért megjelent a kettős iterációk fokjelzőjének megnevezése : i = 1,1,2,2,3,3 ... Míg normál iterációk esetén: i = 1,2,3 ... A kettős iterációs módszer garantálja a konvergenciát metódust az érvváltozások érvényes tartományában.

A http://baykov.de/CORDIC1985.htm Radix R és a CORDIC konvergenciaproblémák általánosítása a http://baykov.de/CORDIC1985.htm segítségével megmutatta, hogy a sin, cos, arctg függvényekhez elegendő az (R-1) iterációk végrehajtása minden i érték (i = 0 vagy 1 -től n -ig, ahol n a számjegyek száma), azaz az eredmény minden számjegye. Az ln, exp, sh, ch, arth, R függvényeknél az i értékek mindegyikét el kell végezni. A függvényeknél az arcsin és az arccos 2 (R-1) iterációkat minden számjegyhez, azaz minden i értékhez el kell végezni. Az arsh, arch függvények esetében az iterációk száma 2R lesz minden i -nél, azaz minden eredmény számjegynél.

Kapcsolódó algoritmusok

A CORDIC a "shift-and-add" algoritmusok osztályának része , csakúgy, mint a Henry Briggs munkájából származó logaritmus és exponenciális algoritmusok. Egy másik shift-and-add algoritmus, amely számos elemi függvény kiszámítására használható, a BKM algoritmus , amely a logaritmus és az exponenciális algoritmusok általánosítása a komplex síkra. Például, BKM lehet kiszámítani az szinusz és koszinusz egy igazi szöget (radiánban), kiszámítva az exponenciális az , ami . A BKM algoritmus valamivel összetettebb, mint a CORDIC, de megvan az az előnye, hogy nincs szüksége skálázási tényezőre ( K ). ${\ displaystyle x}$ ${\ displaystyle 0+ix}$ ${\ displaystyle \ operatornév {cis} (x) = \ cos (x)+i \ sin (x)}$

Lásd még

A négyzetgyök számításának módszerei
IEEE 754
Lebegőpontos egységek
Digitális áramkörök/CORDIC a Wikikönyvekben

Hivatkozások

További irodalom

Parini, Joseph A. (1966-09-05). "A DIVIC választ ad a komplex navigációs kérdésekre". Elektronika : 105–111. ISSN 0013-5070 .(NB. Divić jelentése digitális Variable növekmények Computer . Egyes források tévesen nevezzük, hogy a JM Parini .)
Anderson, Stanley F .; Earle, John G .; Goldschmidt, Robert Elliott; Powers, Don M. (1965-11-01). "Az IBM System/360 91-es modell: lebegőpontos végrehajtó egység" (PDF) . IBM Journal of Research and Development . Riverton, New Jersey, USA (1967. január). 11. (1): 34–53. doi : 10.1147/rd.111.0034 . Letöltve: 2016-01-02 .
Liccardo, Michael A. (1968. szeptember). Interconnect processzor, hangsúlyt fektetve a CORDIC mód működésére (MSc dolgozat). Berkeley, CA, USA: Kaliforniai Egyetem, Berkeley , Villamosmérnöki Tanszék. OCLC 500565168 .
A 3576983A számú amerikai egyesült államokbeli szabadalom , Cochran, David S., "Digitális számológép rendszer négyzetgyök kiszámításához", közzétéve 1971-05-04, kiadva 1971-05-04, a Hewlett-Packard Co.-hoz rendelve ( [14] )
Chen, Tien Chi (1972. július). "Exponenciális értékek, logaritmusok, arányok és négyzetgyök automatikus számítása" (PDF) . IBM Journal of Research and Development . 16 (4): 380–388. doi : 10.1147/rd.164.0380 . ISSN 0018-8646 . Letöltve: 2016-01-02 .
Egbert, William E. (1977. május). "Személyes számológép -algoritmusok I.: Négyzetgyök" (PDF) . Hewlett-Packard Journal . Palo Alto, Kalifornia, USA: Hewlett-Packard . 28 (9): 22–24 . Letöltve: 2016-01-02 .( [15] )
Egbert, William E. (1977. június). "Személyes számológép -algoritmusok II: trigonometrikus függvények" (PDF) . Hewlett-Packard Journal . Palo Alto, Kalifornia, USA: Hewlett-Packard . 28 (10): 17–20 . Letöltve: 2016-01-02 .( [16] )
Egbert, William E. (1977. november). "Személyes számológép -algoritmusok III: fordított trigonometrikus függvények" (PDF) . Hewlett-Packard Journal . Palo Alto, Kalifornia, USA: Hewlett-Packard . 29. (3): 22–23 . Letöltve: 2016-01-02 .( [17] )
Egbert, William E. (1978. április). "Személyes számológép -algoritmusok IV: logaritmikus függvények" (PDF) . Hewlett-Packard Journal . Palo Alto, Kalifornia, USA: Hewlett-Packard . 29. (8): 29–32 . Letöltve: 2016-01-02 .( [18] )
Senzig, Don (1975). "Számológép algoritmusok". IEEE Compcon Reader Digest . IEEE : 139–141. IEEE katalógusszám 75 CH 0920-9C.
Baykov, Vladimir D. (1972), Вопросы исследования вычисления элементарных функций по методу «цифра за цифрой»[ Az elemi funkciók értékelésének problémái számjegyről számjegyre (CORDIC) technika alapján ] (PhD dolgozat) (orosz nyelven), Leningrádi Állami Elektrotechnikai Egyetem
Baykov, Vladimir D .; Smolov, Vladimir B. (1975). Apparaturnaja realizatsija elementarnikh funktsij v CVM Аппаратурная реализация элементарных функций в ЦВМ[ Az elemi funkciók hardver implementációja a számítógépekben ] (oroszul). Leningrádi Állami Egyetem. Archiválva az eredetiből 2019-03-02 . Letöltve: 2019-03-02 .
Baykov, Vladimir D .; Seljutin, SA (1982). Вычисление элементарных функций в ЭКВМ[Az elemi funkciók értékelése mikrokalkulátorokban ] (oroszul). Moszkva: Rádió és svjaz (Радио и связь).
Baykov, Vladimir D .; Smolov, Vladimir B. (1985).Специализированные процессоры: итерационные алгоритмы и структуры[ Speciális célú processzorok: iteratív algoritmusok és struktúrák ] (oroszul). Moszkva: Rádió és svjaz (Радио и связь).
Coppens, Thomas, szerk. (1980. január). "CORDIC állandók a TI 58/59 ROM -ban". Texas Instruments Software Exchange hírlevél . Kapellen, Belgium: TISOFT. 2. (2) bekezdése.
Coppens, Thomas, szerk. (1980. április – június). "Természetes logaritmusszámítási séma / e ^x számítási séma / 1 / x számítási séma". Texas Instruments Software Exchange hírlevél . Kapellen, Belgium: TISOFT. 2. (3) bekezdése.(a CORDIC - ról a TI-58 / TI-59-ben )
TI Graphic Products Team (1995) [1993]. "Transzcendentális függvény algoritmusok" . Dallas, Texas, USA: Texas Instruments , Consumer Products. Archiválva az eredetiből 2016-03-17 . Letöltve: 2019-03-02 .
Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (németül) (1 szerk.). Berlin, Németország: VEB Verlag Technik . 219., 261., 271–296. ISBN 3341005153. EAN 9783341005156 . MPN 5539165. Engedély 201.370/4/89 . Letöltve 2015-12-01 .
M. Zechmeister Kepler egyenletének megoldása CORDIC kettős iterációkkal Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Németország, Előnyomás 2020. augusztus 10., p. 1-10.
Frerking, Marvin E. (1994). Digitális jelfeldolgozás kommunikációs rendszerekben (1 szerk.).
Kantabutra, Vitit (1996). "Az exponenciális és trigonometrikus függvények kiszámítására szolgáló hardverről". IEEE tranzakciók számítógépeken . 45 (3): 328–339. doi : 10.1109/12.485571 .
Johansson, Kenny (2008). "6.5 Szinusz és koszinusz funkciók". Kis teljesítmény és alacsony komplexitás Shift-and-Add alapú számítások (PDF) (értekezés). Linköping Studies in Science and Technology (1 szerk.). Linköping, Svédország: Villamosmérnöki Tanszék, Linköping Egyetem . 244–250. ISBN 978-91-7393-836-5. ISSN 0345-7524 . 1201. sz. Archivált (PDF) az eredetiből 2017-08-13 . Letöltve 2021-08-23 . (x+268 oldal)
Banerjee, Ayan (2001). "A CORDIC alapú FFT processzor FPGA megvalósítása az orvosbiológiai jelfeldolgozáshoz". Mikroprocesszorok és mikroszisztémák . Kharagpur, Nyugat -Bengália, India. 25 (3): 131–142. doi : 10.1016/S0141-9331 (01) 00106-5 .
Kahan, William Morton (2002-05-20). "Ál-osztási algoritmusok lebegőpontos logaritmusokhoz és exponenciálokhoz" (PDF) . Berkeley, CA, USA: Kaliforniai Egyetem . Archiválva az eredetiből (PDF) , 2015-12-25 . Letöltve 2016-01-15 .
Cockrum, Chris K. (2008 ősz). "CORDIC algoritmus megvalósítása digitális lefelé konverterben" (PDF) .
Lakshmi, Boppana; Dhar, Anindya Sundar (2009-10-06). "CORDIC Architecture: A Survey" . VLSI tervezés . Kharagpur, Nyugat-Bengália, India: Indiai Technológiai Intézet Elektronikai és Elektromos Kommunikációs Mérnöki Tanszéke (2010-10-10). 2010 : 1–19. doi : 10.1155/2010/794891 . 794891.
Savard, John JG (2018) [2006]. "Fejlett számtani technikák" . quadibloc . Archiválva az eredetiből 2018-07-03 . Letöltve 2018-07-16 .

Languages

In other projects