KORDIC

CORDIC (od „komputer cyfrowy z rotacją współrzędnych”), znany również jako algorytm Voldera lub: metoda cyfra po cyfrze Circular CORDIC (Jack E. Volder), Linear CORDIC , Hyperbolic CORDIC (John Stephen Walther) i Generalized Hyperbolic CORDIC ( GH CORDIC ) (Yuanyong Luo et al.), to prosty i wydajny algorytm do obliczania funkcji trygonometrycznych , funkcji hiperbolicznych , pierwiastków kwadratowych , mnożenia , dzielenia oraz wykładniczych i logarytmów o dowolnej podstawie, zwykle zbieżnych z jedną cyfrą (lub bitem) na iteracja. CORDIC jest zatem również przykładem algorytmów cyfra po cyfrze . CORDIC i blisko spokrewnione metody znane jako pseudo-mnożenie i pseudo- dzielenie lub łączenie czynników są powszechnie stosowane, gdy nie jest dostępny sprzętowy mnożnik (np. w prostych mikrokontrolerach i układach FPGA ), ponieważ jedynymi operacjami, których wymaga, są dodawanie , odejmowanie , przesunięcie bitów i tablice wyszukiwania . Jako takie, wszystkie należą do klasy algorytmów typu shift-and-add . W informatyce CORDIC jest często używany do implementacji arytmetyki zmiennoprzecinkowej , gdy platforma docelowa nie jest zwielokrotniona sprzętowo ze względu na koszty lub miejsce.

Historia

Podobne techniki matematyczne zostały opublikowane przez Henry'ego Briggsa już w 1624 r. I Roberta Flower'a w 1771 r., Ale CORDIC jest lepiej zoptymalizowany pod kątem procesorów o niskiej złożoności o skończonych stanach.

CORDIC został wymyślony w 1956 roku przez Jacka E. Voldera w dziale aeroelektroniki Convair z konieczności zastąpienia analogowego resolwera w komputerze nawigacyjnym bombowca B-58 dokładniejszym i szybszym rozwiązaniem cyfrowym czasu rzeczywistego. Dlatego CORDIC jest czasami określany jako cyfrowy resolwer.

W swoich badaniach Volder inspirował się formułą z wydania CRC Handbook of Chemistry and Physics z 1946 roku :

{\ Displaystyle {\ rozpocząć {wyrównane} K_ {n} R \ sin (\ teta \ pm \ varphi) & = R \ sin (\ teta) \ pm 2 ^ {- n} R \ cos (\theta ),\\K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\ koniec {wyrównany}}}

z ${\ Displaystyle K_ {n} = {\ sqrt {1 + 2 ^ {- 2n}}}}$ dębnik $\ Displaystyle \ tan (\ varphi )=2^{-n}}$ .

Jego badania doprowadziły do wewnętrznego raportu technicznego, w którym zaproponowano algorytm CORDIC do rozwiązywania funkcji sinus i cosinus oraz prototypowy komputer, który go implementuje. W raporcie omówiono również możliwość obliczania rotacji współrzędnych hiperbolicznych , logarytmów i funkcji wykładniczych za pomocą zmodyfikowanych algorytmów CORDIC. W tym czasie wymyślono również wykorzystanie CORDIC do mnożenia i dzielenia . Opierając się na zasadzie CORDIC, Dan H. Daggett, współpracownik Voldera w Convair, opracował algorytmy konwersji między binarnym i binarnym kodowaniem dziesiętnym (BCD).

W 1958 roku Convair w końcu zaczął budować system demonstracyjny do rozwiązywania problemów z naprawą radarów o nazwie CORDIC I , ukończony w 1960 roku bez Voldera, który już opuścił firmę. Bardziej uniwersalne modele CORDIC II A (stacjonarne) i B (powietrzne) zostały zbudowane i przetestowane przez Daggetta i Harry'ego Schussa w 1962 roku.

Algorytm CORDIC Voldera został po raz pierwszy opisany publicznie w 1959 roku, co spowodowało, że został włączony do komputerów nawigacyjnych przez firmy takie jak Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon i Collins Radio .

Volder połączył siły z Malcolmem McMillanem, aby zbudować Athena , stacjonarny kalkulator stacjonarny wykorzystujący jego binarny algorytm CORDIC. Projekt został przedstawiony firmie Hewlett-Packard w czerwcu 1965 roku, ale nie został zaakceptowany. Mimo to McMillan zapoznał Davida S. Cochrana (HP) z algorytmem Voldera, a kiedy Cochran później spotkał Voldera, skierował go do podobnego podejścia, które John E. Meggitt (IBM) zaproponował jako pseudo-mnożenie i pseudo-dzielenie w 1961 roku . zasugerował użycie bazy 10 zamiast bazy 2 , jak do tej pory stosował CORDIC Voldera. Wysiłki te doprowadziły do ROMable dziesiętnej prototypowej maszyny CORDIC wewnątrz firmy Hewlett-Packard w 1966 r., zbudowanej i koncepcyjnie wywodzącej się z prototypowej Green Machine Thomasa E. Osborne'a , czterofunkcyjnego, zmiennoprzecinkowego kalkulatora biurkowego, który ukończył w Logika DTL w grudniu 1964 r. Projekt ten zaowocował publiczną demonstracją pierwszego kalkulatora biurkowego firmy Hewlett-Packard z funkcjami naukowymi, hp 9100A, w marcu 1968 r., A produkcja seryjna rozpoczęła się jeszcze w tym samym roku.

Kiedy Wang Laboratories odkryło, że hp 9100A stosowało podejście podobne do metody łączenia czynników we wcześniejszych kalkulatorach stacjonarnych LOCI-1 (wrzesień 1964) i LOCI-2 (styczeń 1965) Logarithmic Computing Instrument , bezskutecznie oskarżyli firmę Hewlett-Packard o naruszenie jeden z patentów An Wanga w 1968 roku.

John Stephen Walther z firmy Hewlett-Packard uogólnił algorytm na algorytm Unified CORDIC w 1971 roku, umożliwiając obliczanie funkcji hiperbolicznych , wykładników naturalnych , logarytmów naturalnych , mnożenia , dzielenia i pierwiastków kwadratowych . Podprogramy CORDIC dla funkcji trygonometrycznych i hiperbolicznych mogą współdzielić większość swojego kodu. Ten rozwój zaowocował pierwszym naukowym kalkulatorem podręcznym HP -35 w 1972 roku. Opierając się na hiperbolicznym CORDIC, Yuanyong Luo i in. ponadto zaproponował uogólniony hiperboliczny CORDIC (GH CORDIC) do bezpośredniego obliczania logarytmów i wykładników z dowolną stałą podstawą w 2019 r. Teoretycznie hiperboliczny CORDIC jest szczególnym przypadkiem GH CORDIC.

Pierwotnie CORDIC został zaimplementowany tylko przy użyciu binarnego systemu liczbowego i pomimo tego, że Meggitt sugerował użycie systemu dziesiętnego w swoim podejściu do pseudomnożenia, dziesiętny CORDIC nadal pozostawał w większości niespotykany przez kilka kolejnych lat, więc Hermann Schmid i Anthony Bogacki nadal sugerowali jako nowość dopiero w 1973 roku, a dopiero później okazało się, że Hewlett-Packard wdrożył ją już w 1966 roku.

Dziesiętny CORDIC stał się szeroko stosowany w kalkulatorach kieszonkowych , z których większość działa w systemie dziesiętnym kodowanym binarnie (BCD), a nie binarnym. Ta zmiana formatu danych wejściowych i wyjściowych nie zmieniła podstawowych algorytmów obliczeniowych CORDIC. CORDIC szczególnie dobrze nadaje się do kalkulatorów podręcznych, w których niski koszt – a tym samym mała liczba bramek chipowych – jest znacznie ważniejszy niż szybkość.

CORDIC został zaimplementowany w opartych na ARM STM32G4 , Intel 8087 , 80287 , 80387 aż do serii koprocesorów 80486 , a także w Motoroli 68881 i 68882 dla niektórych rodzajów instrukcji zmiennoprzecinkowych, głównie jako sposób na zmniejszenie liczby bramek (i złożoność) podsystemu FPU .

Aplikacje

CORDIC wykorzystuje proste operacje shift-add do kilku zadań obliczeniowych, takich jak obliczanie funkcji trygonometrycznych, hiperbolicznych i logarytmicznych, mnożenie rzeczywiste i zespolone, dzielenie, obliczanie pierwiastka kwadratowego, rozwiązywanie układów liniowych, szacowanie wartości własnych, dekompozycja wartości osobliwych , faktoryzacja QR i wiele innych. W rezultacie CORDIC był używany do zastosowań w różnych obszarach, takich jak sygnałów i obrazów , systemy komunikacyjne , robotyka i grafika 3D , oprócz ogólnych obliczeń naukowych i technicznych.

Sprzęt komputerowy

Algorytm został wykorzystany w systemie nawigacyjnym Lunar Roving Vehicle programu Apollo do obliczenia namiaru i zasięgu, czyli odległości od modułu księżycowego . CORDIC został użyty do zaimplementowania Intel 8087 w 1980 roku, unikając konieczności implementacji mnożenia sprzętowego.

CORDIC jest generalnie szybszy niż inne podejścia, gdy nie jest dostępny mnożnik sprzętowy (np. mikrokontroler) lub gdy liczba bramek wymaganych do realizacji obsługiwanych funkcji powinna być zminimalizowana (np. w FPGA lub ASIC ) . W rzeczywistości CORDIC jest standardowym drop-in IP w aplikacjach rozwojowych FPGA, takich jak Vivado dla Xilinx, podczas gdy implementacja szeregów potęgowych nie wynika ze specyfiki takiego IP, tj. CORDIC może obliczać wiele różnych funkcji (ogólnego przeznaczenia), podczas gdy mnożnik sprzętowy skonfigurowany do wykonywania implementacji szeregów mocy może obliczyć tylko funkcję, dla której został zaprojektowany.

Z drugiej strony, gdy dostępny jest mnożnik sprzętowy ( np . w mikroprocesorze DSP ), metody przeszukiwania tabeli i szeregi potęgowe są na ogół szybsze niż CORDIC. W ostatnich latach algorytm CORDIC był szeroko stosowany w różnych zastosowaniach biomedycznych, zwłaszcza w implementacjach FPGA ^{[ potrzebne źródło ]} .

Seria STM32G4 i niektóre serie MCU STM32H7 implementują moduł CORDIC do przyspieszania obliczeń w różnych aplikacjach z mieszanymi sygnałami, takimi jak grafika dla interfejsu człowiek-maszyna i zorientowane na pole sterowanie silnikami. Chociaż CORDIC nie jest tak szybki jak aproksymacja szeregów potęgowych, jest faktycznie szybszy niż implementacje oparte na interpolacji tabel, takie jak te dostarczane przez standardowe biblioteki ARM CMSIS i C. Chociaż wyniki mogą być nieco mniej dokładne, ponieważ dostarczone moduły CORDIC osiągają tylko 20-bitową precyzję w wyniku. Na przykład większość różnic w wydajności w porównaniu z implementacją ARM wynika z narzutu algorytmu interpolacji, który osiąga pełną precyzję zmiennoprzecinkową (24 bity) i prawdopodobnie może osiągnąć względny błąd w stosunku do tej precyzji. Kolejną korzyścią jest to, że moduł CORDIC jest koprocesorem i może być uruchamiany równolegle z innymi zadaniami procesora.

Problem z użyciem szeregów Taylora polega na tym, że chociaż zapewniają one mały błąd bezwzględny, nie wykazują dobrze zachowanego błędu względnego. Inne sposoby aproksymacji wielomianów, takie jak minimax , mogą być użyte do kontrolowania obu rodzajów błędów.

Oprogramowanie

Wiele starszych systemów z procesorami obsługującymi tylko liczby całkowite zaimplementowało CORDIC w różnym stopniu jako część swoich bibliotek zmiennoprzecinkowych IEEE . Ponieważ większość nowoczesnych procesorów ogólnego przeznaczenia ma rejestry zmiennoprzecinkowe z typowymi operacjami, takimi jak dodawanie, odejmowanie, mnożenie, dzielenie, sinus, cosinus, pierwiastek kwadratowy, log 10 , log naturalny, potrzeba zaimplementowania w nich CORDIC z oprogramowaniem prawie _nie istnieje -istniejący. Tylko mikrokontroler lub specjalne aplikacje bezpieczeństwa i ograniczone czasowo musiałyby rozważyć użycie CORDIC.

Tryby działania

Tryb rotacji

CORDIC może być używany do obliczania wielu różnych funkcji. To wyjaśnienie pokazuje, jak używać CORDIC w trybie rotacji do obliczania sinusa i cosinusa kąta, zakładając, że żądany kąt jest podany w radianach i przedstawiony w formacie stałoprzecinkowym. Aby określić $lub$ lub cosinus kąta , należy znaleźć współrzędną y x punktu na okręgu jednostkowym odpowiadającego żądanemu kątowi. Używając CORDIC, można by zacząć od wektora : ${\ displaystyle v_ {0}}$

{\ Displaystyle v_ {0} = {\ początek {bmatrix} 1 \\ 0 \ koniec {bmatrix}}.}

Ilustracja algorytmu CORDIC w toku

W pierwszej iteracji ten wektor jest obracany o 45 ° w kierunku przeciwnym do ruchu wskazówek zegara, aby uzyskać wektor ${\ displaystyle v_ {1}}$ . Kolejne iteracje obracają wektor w jednym lub drugim kierunku krokami zmniejszającymi rozmiar, aż do osiągnięcia pożądanego kąta. γ ${\ Displaystyle \ gamma _ {i} = \ arctan {(2 ^ {-i})}}$ ja $\ Displaystyle i =0,1,2,\kropki }$ .

$ja$ obrót, który jest wykonywany przez pomnożenie wektora przez rotacji : R $Displaystyle R_ {i}}$

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

Macierz rotacji jest dana przez

{\ Displaystyle R_ {i} = {\ rozpocząć {bmatrix} \ cos (\ gamma _ {i}) & - \ sin (\ gamma _ {i}) \\\ sin (\ gamma _ {i}) & \ cos(\gamma _{i})\end{bmacierz}}.}

Korzystając z dwóch tożsamości trygonometrycznych :

{\ Displaystyle {\ rozpocząć {wyrównane} \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{wyrównane} }}

staje się macierzą rotacji

{\ Displaystyle R_ {i} = {\ Frac {1} {\ sqrt {1+ \ tan ^ {2} (\ gamma _ {i})}}} {\ rozpocząć {bmatrix} 1 & - \ tan (\ gamma _{i})\\\tan(\gamma _{i})&1\end{bmacierz}}.}

Wyrażenie dla obróconego wektora staje się wtedy ${\ Displaystyle v_ {i + 1} = R_ {i} v_ {i}}$

{\ Displaystyle {\ begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}={\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{bmacierz}},}

gdzie $v_$ są składnikami $\ displaystyle y_ {i}}$ ${i}}$ . ${\ Displaystyle \ gamma _ {i}}$ tak, że ${-i} }$ ^ , mnożenie ze styczną można zastąpić dzieleniem przez potęgę dwójki, co jest skutecznie wykonywane w cyfrowym sprzęcie komputerowym przy użyciu przesunięcia bitowego . Wyrażenie staje się wtedy

{\ Displaystyle {\ rozpocząć {bmatrix} x_ {i + 1} \\y_{i+1}\end{bmatrix}}=K_{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{ -i}&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}

Gdzie

{\ Displaystyle K_ {i} = {\ Frac {1} {\ sqrt {1 + 2 ^ {- 2i}}}}}

a ${\ Displaystyle \ sigma _ {i}}$ służy do określenia kierunku obrotu: jeśli kąt $jest$ , to $Displaystyle \ sigma _ {i}}$ to +1, w przeciwnym razie -1.

Wszystkie czynniki można zignorować w procesie iteracyjnym, a następnie zastosować je wszystkie naraz ze współczynnikiem skalowania $}}$ $\$

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

która jest obliczana z góry i przechowywana w tabeli lub jako pojedyncza stała, jeśli liczba iteracji jest stała. Korekty tej można również dokonać z wyprzedzeniem, skalując $a$ tym samym zapisując mnożenie. Dodatkowo można zauważyć, że

{\ Displaystyle K = \ lim _ {n \ do \ infty} K (n) \ około 0,6072529350088812561694}

aby umożliwić dalszą redukcję złożoności algorytmu. Niektóre aplikacje mogą całkowicie uniknąć korygowania , co skutkuje wzmocnieniem przetwarzania : $K.$ $displaystyle A$ }

{\ Displaystyle A = {\ Frac {1} {K}} = \ lim _ {n \ do \ infty} \ prod _ {i = 0} ^ {n-1} {\ sqrt {1 + 2 ^ {- 2i}}}\około 1,64676025812107.}

Po wystarczającej liczbie iteracji kąt wektora będzie zbliżony do $kąta$ . W większości zwykłych zastosowań 40 iteracji ( n = 40) wystarcza do uzyskania poprawnego wyniku z dokładnością do 10 miejsca po przecinku.

$ruchu wskazówek zegara$ każdej iteracji (wybierając wartość ). Odbywa się to poprzez śledzenie, o ile kąt został obrócony w każdej iteracji i odjęcie tego od pożądanego kąta; następnie, aby zbliżyć się do pożądanego kąta $}$ jeśli jest dodatni, jest zgodny z ruchem wskazówek zegara, w przeciwnym razie jest ujemny, a obrót jest β { $\$ jest przeciwnie do ruchu wskazówek zegara:

{\ Displaystyle \ beta _ {0} = \ beta }

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

Wartości muszą być również $wstępnie$ zapisane. Ale dla małych kątów ${\ Displaystyle \ arctan (\ gamma _ {n}) = \ gamma _ {n}}$ w reprezentacji stałoprzecinkowej, zmniejszając rozmiar tabeli.

$x$ ilustracji, sinus kąta $współrzędna$ współrzędną y wektora końcowego gdy jest wartością cosinus.

Tryb wektorowania

Algorytm trybu obracania opisany powyżej może obracać dowolny wektor (nie tylko wektor jednostkowy wyrównany wzdłuż osi x ) o kąt między -90° a +90°. Decyzje dotyczące kierunku obrotu zależą od tego, czy $dodatni$ czy ujemny.

Praca w trybie wektorowym wymaga niewielkiej modyfikacji algorytmu. Zaczyna się od wektora , którego współrzędna x jest dodatnia, a współrzędna y jest dowolna. Kolejne obroty mają na celu obrócenie wektora do x (a tym samym zmniejszenie współrzędnej y do zera). Na każdym kroku wartość y określa kierunek obrotu. Ostateczna wartość $całkowity$ obrotu. Ostateczna wartość x będzie wielkością oryginalnego wektora przeskalowanego przez K . Tak więc oczywistym zastosowaniem trybu wektorowania jest transformacja ze współrzędnych prostokątnych na biegunowe.

Realizacja

Przykład oprogramowania

Poniżej znajduje się implementacja CORDIC w MATLAB / GNU Octave , która nie opiera się na żadnych funkcjach transcendentalnych, z wyjątkiem wstępnego obliczania tabel. Jeśli liczba iteracji n jest z góry określona, to drugą tablicę można zastąpić pojedynczą stałą. Dzięki standardowej arytmetyce podwójnej precyzji MATLAB i wydrukowi „formatu długiego” wyniki zwiększają dokładność dla n do około 48.

   



       
       0
             
    
             
    
       
    





     
              
              
              
              
              
              
              


   
              
              
              
              
              
              
   


  0 
  
  


   0
       0
          
    
          
    
        
    
         
         
           
        
    
       
            
    
          
    



    


 funkcja  v  =  cordic  (  beta,n  )  % Ta funkcja oblicza v = [cos(beta), sin(beta)] (beta w radianach)  % przy użyciu n iteracji. Zwiększenie n zwiększy precyzję.   jeśli  beta  <  -  pi  /  2  ||  beta  >  pi  /  2  jeśli  beta  <  v  =  korowe  (  beta  +  pi  ,  n  );  else  v  =  kordowy  (  beta  -  pi  ,  n  );  koniec  v  =  -  v  ;  % odwróć znak dla drugiej lub trzeciej ćwiartki  powrót  koniec  % Inicjalizacja tablic stałych używanych przez CORDIC  % potrzebna tablica arcus tangensów ujemnych potęg dwójki, w radianach:  % kąty = 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  ];  % oraz tablica iloczynów odwrotnych długości wektorów [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  =  wartości K  (  min  (  n  ,  długość  (  wartości K  )));  % Inicjalizacja zmiennych pętli:  v  =  [  1  ;  ];  % zaczyna się od 2-wektorowego cosinusa i sinusa zerowej  potęgi dwóch  =  1  ;  kąt  =  kąty  (  1  );  % iteracji  dla  j  =  :  n  -  1  ;  jeśli  beta  <  sigma  =  -  1  ;  inaczej  sigma  =  1  ;  czynnik  końcowy  =  sigma  *  potęga dwóch  ; % Zauważ   ,  że mnożenie macierzy można wykonać używając skalowania przez potęgi dwójki i dodawania odejmowania  R  =  [  1  ,  -czynnik  ;  współczynnik  ,  1  ];  v  =  R  *  v  ;  % macierz 2 na 2 pomnóż  beta  =  beta  -  sigma  *  kąt  ;  % aktualizacja pozostałego kąta  poweroftwo  =  poweroftwo  /  2  ;  % zaktualizuj kąt z tabeli lub ewentualnie po prostu podziel przez dwa,  jeśli  j  +  2  >  długość  (  kąty  )  kąt  =  kąt  /  2  ;  inaczej  kąt  =  kąty  (  j  +  2  );  end  end  % Dopasuj długość wektora wyjściowego do [cos(beta), sin(beta)]:  v  =  v  *  Kn  ;  zwróć  funkcję końcową

Mnożenie macierzy dwa na dwa można wykonać za pomocą pary prostych przesunięć i dodań.

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

W Javie klasa Math ma metodę scalb(double x,int scale) do wykonywania takiego przesunięcia, C ma funkcję ldexp , a klasa procesorów x86 ma operację zmiennoprzecinkową fscale .

Przykład sprzętu

Liczba bramek logicznych do wdrożenia CORDIC jest z grubsza porównywalna z liczbą wymaganą dla mnożnika, ponieważ obie wymagają kombinacji przesunięć i dodatków. Wybór wdrożenia opartego na mnożnikach lub na CORDIC będzie zależał od kontekstu. mnożenie dwóch liczb zespolonych reprezentowanych przez ich składowe rzeczywiste i urojone (współrzędne prostokątne) wymaga 4 mnożeń, ale może być zrealizowane przez pojedynczy CORDIC operujący na liczbach zespolonych reprezentowanych przez ich współrzędne biegunowe, zwłaszcza jeśli wielkość liczb nie ma znaczenia (mnożenie wektora zespolonego przez wektor na okręgu jednostkowym w rzeczywistości jest równoznaczne z obrotem). Przewody CORDIC są często używane w obwodach telekomunikacyjnych, takich jak cyfrowe konwertery w dół .

Podwójne iteracje CORDIC

W publikacjach: http://baykov.de/CORDIC1972.htm oraz http://baykov.de/CORDIC1975.htm zaproponowano wykorzystanie metody podwójnych iteracji do realizacji funkcji: arcsinX, arccosX, lnX, expX , a także do obliczania funkcji hiperbolicznych. Metoda podwójnych iteracji polega na tym, że w przeciwieństwie do klasycznej metody CORDIC, gdzie wartość kroku iteracji zmienia się KAŻDEGO czasu, tj. na każdej iteracji, w metodzie podwójnej iteracji wartość kroku iteracji jest powtarzana dwukrotnie i zmienia się tylko podczas jednej iteracji. Stąd pojawiło się oznaczenie wskaźnika stopnia dla podwójnych iteracji: i = 1,1,2,2,3,3... Natomiast dla zwykłych iteracji: i = 1,2,3... Metoda podwójnej iteracji gwarantuje zbieżność metody w całym prawidłowym zakresie zmian argumentów.

Uogólnienie problemów konwergencji CORDIC dla dowolnego systemu liczb pozycyjnych http://baykov.de/CORDIC1985.htm z Radix R wykazało, że dla funkcji sin, cos, arctg wystarczy wykonać (R-1) iteracje dla każdą wartość i (i = 0 lub 1 do n, gdzie n jest liczbą cyfr), tj. dla każdej cyfry wyniku. Dla funkcji ln, exp, sh, ch, arth, dla każdej wartości i należy wykonać iteracje. Dla funkcji arcsin i arccos 2 (R-1) należy wykonać iteracje dla każdej cyfry liczby, czyli dla każdej wartości i. Dla arsh, funkcji łukowych, liczba iteracji będzie wynosić 2R dla każdego i, czyli dla każdej cyfry wyniku.

Powiązane algorytmy

CORDIC należy do klasy algorytmów „przesuń i dodaj” , podobnie jak algorytmy logarytmiczne i wykładnicze wywodzące się z pracy Henry'ego Briggsa. Innym algorytmem typu „przesuń i dodaj”, który można wykorzystać do obliczania wielu funkcji elementarnych, jest algorytm BKM , który jest uogólnieniem algorytmów logarytmicznych i wykładniczych na płaszczyznę zespoloną. Na $x$ BKM można wykorzystać do obliczenia sinusa i cosinusa kąta rzeczywistego ${\ Displaystyle \ operatorname {cis} (x) = \ cos (x) + i \ sin (x)}$ $radianach )$ wykładniczego , czyli . Algorytm BKM jest nieco bardziej złożony niż CORDIC, ale ma tę zaletę, że nie potrzebuje współczynnika skalowania ( K ).

Zobacz też

Metody obliczania pierwiastków kwadratowych
IEEE 754
Jednostki zmiennoprzecinkowe
Obwody cyfrowe/CORDIC w Wikibooks

Dalsza lektura

Parini, Joseph A. (1966-09-05). „DIVIC daje odpowiedź na złożone pytania nawigacyjne” . Elektronika : 105–111. ISSN 0013-5070 . (Uwaga. DIVIC oznacza DIgital Variable Increments Computer . Niektóre źródła błędnie określają to jako JM Parini .)
Anderson, Stanley F.; Earle, John G.; Goldschmidt, Robert Elliott; Uprawnienia, Don M. (1965-11-01). „System IBM System / 360 Model 91: jednostka wykonawcza zmiennoprzecinkowa” (PDF) . IBM Journal of Research and Development . Riverton, New Jersey, USA (opublikowane w styczniu 1967). 11 (1): 34–53. doi : 10.1147/rd.111.0034 . Źródło 2016-01-02 .
Liccardo, Michael A. (wrzesień 1968). Procesor interkonektowy z naciskiem na pracę w trybie CORDIC (praca magisterska). Berkeley, Kalifornia, USA: Uniwersytet Kalifornijski, Berkeley , Wydział Elektrotechniki. OCLC 500565168 .
Patent USA 3576983A , Cochran, David S., „Cyfrowy system kalkulatora do obliczania pierwiastków kwadratowych”, opublikowany 1971-05-04, wydany 1971-05-04, przeniesiony na Hewlett-Packard Co. ( [14] )
Chen, Tien Chi (lipiec 1972). „Automatyczne obliczanie wykładników, logarytmów, współczynników i pierwiastków kwadratowych” (PDF) . IBM Journal of Research and Development . 16 (4): 380–388. doi : 10.1147/rd.164.0380 . ISSN 0018-8646 . Źródło 2016-01-02 .
Egbert, William E. (maj 1977). „Algorytmy kalkulatora osobistego I: pierwiastki kwadratowe” (PDF) . Dziennik Hewlett-Packard . Palo Alto, Kalifornia, USA: Hewlett-Packard . 28 (9): 22–24 . Źródło 2016-01-02 . ( [15] )
Egbert, William E. (czerwiec 1977). „Algorytmy kalkulatora osobistego II: funkcje trygonometryczne” (PDF) . Dziennik Hewlett-Packard . Palo Alto, Kalifornia, USA: Hewlett-Packard . 28 (10): 17–20 . Źródło 2016-01-02 . ( [16] )
Egbert, William E. (listopad 1977). „Algorytmy kalkulatora osobistego III: odwrotne funkcje trygonometryczne” (PDF) . Dziennik Hewlett-Packard . Palo Alto, Kalifornia, USA: Hewlett-Packard . 29 (3): 22–23 . Źródło 2016-01-02 . ( [17] )
Egbert, William E. (kwiecień 1978). „Algorytmy kalkulatora osobistego IV: funkcje logarytmiczne” (PDF) . Dziennik Hewlett-Packard . Palo Alto, Kalifornia, USA: Hewlett-Packard . 29 (8): 29–32 . Źródło 2016-01-02 . ( [18] )
Senzig, Don (1975). „Algorytmy kalkulatora” . Przegląd czytnika IEEE Compcon . IEEE : 139–141. Numer katalogowy IEEE 75 CH 0920-9C.
Baykov, Vladimir D. (1972), Вопросы исследования вычисления элементарных функций по методу «цифра за цифрой» (CORDIC) technika ] (praca doktorska) (w języku rosyjskim), Leningradzki Uniwersytet Państwowy im Inżynieria elektryczna
Bajkow, Władimir D.; Smołow, Władimir B. (1975). Apparaturnaja realizatsija elementarnikh funktsij v CVM Аппаратурная реализация элементарных функций в ЦВМ [ Sprzętowa implementacja podstawowych funkcji w komputerach ] (w języku rosyjskim). Leningradzki Uniwersytet Państwowy. Zarchiwizowane od oryginału w dniu 2019-03-02 . Źródło 2019-03-02 .
Bajkow, Władimir D.; Seljutin SA (1982). Вычисление элементарных функций в ЭКВМ [ Ocena funkcji elementarnych w mikrokalkulatorach ] (po rosyjsku). Moskwa: Radio i svjaz (Радио и связь).
Bajkow, Władimir D.; Smołow, Władimir B. (1985). Специализированные процессоры: итерационные алгоритмы и структуры [ Procesory specjalnego przeznaczenia: iteracyjne algorytmy i struktury ] (w języku rosyjskim). Moskwa: Radio i svjaz (Радио и связь).
Coppens, Thomas, wyd. (styczeń 1980). „Stałe CORDIC w TI 58/59 ROM” . Biuletyn wymiany oprogramowania firmy Texas Instruments . Kapellen, Belgia: TISOFT. 2 (2).
Coppens, Thomas, wyd. (kwiecień – czerwiec 1980). „Schemat obliczeń logarytmu naturalnego / ^ex / schemat obliczeń 1/x” . Biuletyn wymiany oprogramowania firmy Texas Instruments . Kapellen, Belgia: TISOFT. 2 (3). (o CORDIC w TI-58 / TI-59 )
Zespół produktów graficznych TI (1995) [1993]. „Algorytmy funkcji transcendentalnych” . Dallas, Teksas, USA: Texas Instruments , produkty konsumenckie. Zarchiwizowane od oryginału w dniu 17.03.2016 . Źródło 2019-03-02 .
Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (w języku niemieckim) (1 wyd.). Berlin, Niemcy: VEB Verlag Technik . s. 219, 261, 271–296. ISBN 3341005153 . EAN 9783341005156 . MPN 5539165. Licencja 201.370/4/89 . Źródło 2015-12-01 .
Zachmeister, M. (2021). Rozwiązywanie równania Keplera za pomocą podwójnych iteracji CORDIC . Miesięczne ogłoszenia Królewskiego Towarzystwa Astronomicznego . Tom. 500. Getynga, Niemcy: Institut für Astrophysik, Georg-August-Universität. s. 109–117. arXiv : 2008.02894 . doi : 10.1093/mnras/staa2441 .
Frerking, Marvin E. (1994). Cyfrowe przetwarzanie sygnału w systemach komunikacyjnych (1 wyd.).
Kantabutra, Vitit (1996). „O sprzęcie do obliczania funkcji wykładniczych i trygonometrycznych”. Transakcje IEEE na komputerach . 45 (3): 328–339. doi : 10.1109/12.485571 .
Johansson, Kenny (2008). „6.5 Funkcje sinusoidalne i cosinusowe”. Obliczenia oparte na przesunięciu i dodaniu małej mocy i małej złożoności (PDF) (praca doktorska). Linköping Studies in Science and Technology (1 wyd.). Linköping, Szwecja: Wydział Elektrotechniki Uniwersytetu w Linköping . s. 244–250. ISBN 978-91-7393-836-5 . ISSN 0345-7524 . Nr 1201. Zarchiwizowane (PDF) od oryginału w dniu 13.08.2017 r . Źródło 2021-08-23 . (x+268 stron)
Banerjee, Ayan (2001). „Realizacja FPGA procesora FFT opartego na CORDIC do przetwarzania sygnałów biomedycznych”. Mikroprocesory i mikrosystemy . Kharagpur, Zachodni Bengal, Indie. 25 (3): 131–142. doi : 10.1016/S0141-9331(01)00106-5 .
Kahan, William Morton (2002-05-20). „Algorytmy pseudodzielenia dla logarytmów zmiennoprzecinkowych i wykładniczych” (PDF) . Berkeley, Kalifornia, USA: Uniwersytet Kalifornijski . Zarchiwizowane od oryginału (PDF) w dniu 2015-12-25 . Źródło 2016-01-15 .
Cockrum, Chris K. (jesień 2008). „Implementacja algorytmu CORDIC w cyfrowym konwerterze w dół” (PDF) .
Lakszmi, Boppana; Dhar, Anindya Sundar (2009-10-06). „Architektury CORDIC: ankieta” . Projekt VLSI . Kharagpur, Bengal Zachodni, Indie: Wydział Elektroniki i Inżynierii Komunikacji Elektrycznej, Indyjski Instytut Technologii (opublikowane 10.10.2010). 2010 : 1–19. doi : 10.1155/2010/794891 . 794891.
Savard, John JG (2018) [2006]. „Zaawansowane techniki arytmetyczne” . czworokąt . Zarchiwizowane od oryginału w dniu 2018-07-03 . Źródło 2018-07-16 .

Linki zewnętrzne