CORDIC

CORDIC（全稱為coordinate rotation digital computer），也稱為Volder演算法，是一個可以計算三角函數，簡單且有效率的演算法，可以在任意進制下運算，一般會每次計算一位數字。因此CORDIC 是Digit-by-digit方法中的一個例子。

CORDIC演算法還有其他的名稱，像是圓形CORDIC (Jack E. Volder)、線性CORDIC、雙曲線CORDIC(John Stephen Walther)、及泛用雙曲線CORDIC（GH CORDIC, Yuanyong Luo et al.）。用類似的方式也可以計算雙曲函數、平方根、乘法、除法、指數及對數等。

CORDIC和一些名為「偽乘法」（pseudo-multiplication）、「偽除法」（pseudo-division）及factor combining的方法，常用在沒有乘法器的應用（像是簡單的微控制器以及FPGA），其中會用到的運算是加法、減法、位元移位及查找表。這些算法可歸類在「移位和相加」（shift-and-add）演算法中。在計算機科學中，若CPU沒有硬體的乘法器，常會用CORDIC來實現浮点数运算。

歷史

英國數學家亨利·布里格斯早在1624年時就已發現此算法，後來Robert Flower也在1771年時發現，不過後來是因為低複雜度的有限狀態CPU，才針對CORDIC作較進一步的最佳化。

CORDIC是在1956年問世，是由康维尔空氣電子部門的Jack E. Volder發現，一開始是因為要取代B-58轟炸機導航電腦上面的類比式解角器（resolver），更換成更準確而實時的數位方案。因此，有時也會將CORDIC稱為數位解角器（digital resolver）。

Volder的研究，是因為1946年版CRC化学和物理手册中的公式而得到靈感：

${\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}}$

其中$\varphi$是使$\tan(\varphi )=2^{-n}$成立的值，且$K_{n}:={\sqrt {1+2^{-2n}}}$。

他的研究最後產生了一個內部的技術報告，提到用CORDIC演算法來求解正弦及餘弦函數，以及一個實現此功能的原型電腦。報告中也提到用修改版的CORDIC演算法計算雙曲函數、座標旋轉、對數及指數的可能性。用CORDIC來進行乘法和除法運算的想法也是在此時形成。依照CORDIC演算法的原則，Volder的同事Dan H. Daggett發展了在二進位以及二進碼十進數（BCD）之間轉換的演算法。

應用

CORDIC用簡單的移位和相加運算來處理像是三角函數、雙曲函數、對數函數、實數及複數乘法、除法、方根計算、線性系統求解、特徵值估測、奇异值分解、QR分解等。因此，CORDIC可以用在許多的應用中，像是信號處理、影像處理、通訊系統、机器人学及三维计算机图形等。

硬體

若沒有硬體乘法器的話，CORDIC一般會比其他算法要快很多，若是用FPGA或ASIC的話，使用的邏輯閘也會少很多。

CORDIC是FPGA開發應用程式（像是Xilinx的Vivado）中的標準半导体IP核，而不是使用特殊函數的冪級數實現，其原因是CORDIC IP的通用性，CORDIC可以計算許多不同的函數，而為特定函數開發的乘法器只能計算特定的函數。

另一方面，若有硬體乘法器（例如DSP），查表法及冪級數會比CORDIC快很多。近年來，CORDIC演算法常用在生醫應用中，尤其是用FPGA實現的應用。

使用泰勒级数的問題是此方法可以產生小的絕對誤差，但其中沒有良態的相對誤差。其他多項式近似法，例如Minimax近似演算法，可以同時控制這二種的誤差。

軟體

在CPU只有整數運算的古老系統中，會將CORDIC放在其IEEE 754函式庫的一部份。現代的通用CPU已有浮點運算暫存器，也有加法、減法、乘法、除法、三角函數、平方根、一般對數、自然對數等，幾乎沒有用到CORDIC的場合。只有一些有特殊安全性或是時間要求的應用程式才會用到CORDIC。

運作模式

旋轉模式

CORDIC可以用來計算許多不同的函數。以下說明如何在旋轉模式（rotation mode）下的CORDIC計算角度的正弦函數和餘弦函數，假設角度以弧度的定點格式表示。要找到一個角度$\beta$的正弦函數和餘弦函數，可以在單位圓上找到對應角度的y座標和座標。利用CORDIC，會從以下的向量$v_{0}$開始：

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

CORDIC演算法的圖解

在第一次的迭代時，向量逆時針轉45°，得到向量$v_{1}$。接著繼續的迭代，每一次的角度漸漸變小，旋轉方向可能順時針，也可能逆時針，直到得到想要的角度為止。每一次的角度為$\gamma _{i}=\arctan {(2^{-i})}$，其中$i=0,1,2,\dots$。

若以更正式的方式表示，每一次的迭代就是一次旋轉，也就是將向量$v_{i}$乘以旋转矩阵$R_{i}$：

$v_{i+1}=R_{i}v_{i}.$

旋转矩阵為

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

利用以下兩個三角恆等式：

${\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{aligned}}$

旋转矩阵變成

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

旋转向量$v_{i+1}=R_{i}v_{i}$就會變成下式

${\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{bmatrix}},$

其中$x_{i}$和$y_{i}$是$v_{i}$的分量，若將角度$\gamma _{i}$限制在使$\tan(\gamma _{i})=\pm 2^{-i}$的值，和tangent的乘法就以變成乘（或除）2的幂次，在數位電腦硬體中可以快速的用位元右移或左移來計算。因此上法會變成

${\begin{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}},$

其中

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

且$\sigma _{i}$是用來判斷旋轉方向的。若角度$\gamma _{i}$為正，則$\sigma _{i}$為+1，否則則為−1。

所有的$K_{i}$因子可以在迭代過程中忽略，最後再一次乘以$K(n)$因子即可：

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

此數可以事先計算好存在表格中，若迭代次數是固定的，只需計算一個常數且儲存即可，甚至此修正也可以事先進行，將常數先乘以$v_{0}$，可以節省一次乘法。另外，可以注意到

$K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694$

因此可以簡化演算法的複雜度。有些應用會避免修正$K$，因此此演算法本身會帶一個增益$A$：

$A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i}}}\approx 1.64676025812107.$

在夠多次的迭代後，向量的角度會接近想要的角度$\beta$。以一般的應用來說，40次的迭代（n = 40）已可以有小數10位的精度。

唯一未解決的問題是判斷每一次迭代要順時針旋轉或逆時針旋轉（選擇$\sigma$的值）。這可以記錄每一次旋轉的角度，從還需要旋轉的角度中減去此一角度，會得到下一個還需要旋轉的角度$\beta$。若$\beta _{n+1}$為正，需要順時針旋轉，否則，就需要順時針旋轉：

$\beta _{0}=\beta$

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

$\gamma _{n}$的值需要事先計算且記錄下來。不過若是小角度，根據小角度近似，在定點數下可得$\arctan(\gamma _{n})=\gamma _{n}$，因此可以節省儲存用的空間。

如以上所述，角度$\beta$的正弦函數為其y坐標，餘弦函數為其x坐標。

相關條目

• 計算方根的方法
• IEEE 754
• 浮点运算器