三角函式/愛好者/CORDIC 演算法

它是什麼

CORDIC（COordinate Rotation DIgital Computer 的縮寫）是一種簡單高效的演算法，用於計算三角函式。它只需要以下運算：

• 加法，
• 減法，
• 乘以 2 和除以 2，以及
• 查表（一個包含 64 個數字的表格足以用於手持計算器可以計算的所有餘弦和正弦）。

因為計算機內部使用二進位制運算，所以乘以 2 和除以 2 操作非常快且易於執行。因此，CORDIC 演算法允許使用相對簡單的 CPU 高效地計算三角函式。

應用

CORDIC 特別適合手持計算器，對於這種應用，成本（例如晶片門數必須最小化）遠比速度重要。此外，用於三角函式和雙曲函式的 CORDIC 子例程（在三角函式第 2 冊中描述）可以共享大部分程式碼。

操作模式

CORDIC 可以用來計算許多不同的函式。本解釋展示瞭如何使用 CORDIC 的旋轉模式來計算角度的正弦和餘弦，並假設所需的角度以弧度表示，並以定點格式表示。為了確定角度 $\beta$ 的正弦或餘弦，必須找到與所需角度相對應的單位圓上一個點的 y 座標或 x 座標。使用 CORDIC，我們將從向量 $v_{0}$ 

$v_{0}={\begin{pmatrix}1\\0\end{pmatrix}}$

在第一次迭代中，該向量將逆時針旋轉 45 度，得到向量 $v_{1}$。後續的迭代將以逐漸減小的步長，沿一個或另一個方向旋轉該向量，直到達到所需的角度。第 i 步的大小為 Artg(1/(2^(i-1)))，其中 i 為 1、2、3 等。

CORDIC 演算法正在進行的插圖。

更正式地說，每次迭代都會計算一個旋轉，該旋轉透過將向量 $v_{i-1}$ 與旋轉矩陣 $R_{i}$ 相乘來完成。

$v_{i}=R_{i}v_{i-1}$

旋轉矩陣 R 由以下公式給出：

$R_{i}=\left({\begin{array}{rr}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{array}}\right)$

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

${\begin{aligned}\cos(\alpha )&=&{\frac {1}{\sqrt {1+\tan ^{2}(\alpha )}}}\\\sin(\alpha )&=&{\frac {\tan(\alpha )}{\sqrt {1+\tan ^{2}(\alpha )}}}\end{aligned}}$

旋轉矩陣變為

$R_{i}={1 \over {\sqrt {1+\tan ^{2}\gamma _{i}}}}{\begin{pmatrix}1&-\tan \gamma _{i}\\\tan \gamma _{i}&1\end{pmatrix}}$

旋轉後的向量 $v_{i}=R_{i}v_{i-1}$ 的表示式變為

$v_{i}={1 \over {\sqrt {1+\tan ^{2}\gamma _{i}}}}{\begin{pmatrix}x_{i-1}&-&y_{i-1}\tan \gamma _{i}\\x_{i-1}\tan \gamma _{i}&+&y_{i-1}\end{pmatrix}}$

其中，$x_{i-1}$ 和 $y_{i-1}$ 是 $v_{i-1}$ 的分量。限制角度 $\gamma _{i}$ 使得 $\tan \gamma _{i}$ 取值 $\pm 2^{-i}$ ，則與正切的乘法可以替換為除以2的冪，這在使用位移的數字計算機硬體中可以高效地完成。表示式變為

$v_{i}=K_{i}{\begin{pmatrix}x_{i-1}&-&\sigma _{i}2^{-i}y_{i-1}\\\sigma _{i}2^{-i}x_{i-1}&+&y_{i-1}\end{pmatrix}}$

其中

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

並且 $\sigma _{i}$ 可以取值為 -1 或 1，用於確定旋轉方向：如果角度 $\beta _{i}$ 為正，則 $\sigma _{i}$ 為 1，否則為 -1。

我們可以忽略 $K_{i}$ 在迭代過程中，然後透過縮放因子在之後應用它

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

這可以提前計算並存儲在一個表中，或者如果迭代次數是固定的，則儲存為一個常量。這種校正也可以提前進行，透過縮放 $v_{0}$ 並且因此節省了乘法。此外，可以注意到

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

以允許進一步減少演算法的複雜度。在足夠多的迭代之後，向量的角度將接近於想要的角度 $\beta$。對於大多數普通用途，40 次迭代 (n = 40) 足以獲得小數點後第 10 位的正確結果。

剩下的唯一任務是確定每次迭代時旋轉應該是順時針還是逆時針（選擇 $\sigma$ 的值）。這可以透過跟蹤每次迭代我們旋轉了多少並從想要的角度減去它來完成，然後檢查 $\beta _{n+1}$ 是正的，我們需要順時針旋轉，還是如果它是負的，我們必須逆時針旋轉，以便更接近想要的角度 $\beta$。

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

的值 $\gamma _{n}$ 也必須預先計算並存儲。但對於小角度，$\arctan(\gamma _{n})=\gamma _{n}$ 在定點表示中，減少了表的大小。

如上圖所示，角度 $\beta$ 的正弦是最終向量 $v_{n}$ 的 y 座標，而 x 座標是餘弦值。

• 參見 維基百科上的 CORDIC 以獲取更多資訊，包括軟體實現。

硬體實現

在硬體實現中，CORDIC 演算法的主要用途是避免耗時的複雜乘法器。複數相位的計算可以使用硬體描述語言輕鬆實現，僅使用加法器和移位器電路，繞過笨重的複數乘法器。製造技術一直在穩步改進，現在可以以不高的時間、功耗或過大的晶片空間成本直接處理複數，因此在許多應用中，CORDIC 技術的使用不像以前那麼關鍵。

相關演算法

CORDIC 屬於“移位-加”演算法類別，就像從亨利·布里格斯（Henry Briggs）作品中衍生出來的對數和指數演算法一樣。另一種可用於計算許多基本函式的移位-加演算法是 BKM 演算法，它是對數和指數演算法在複平面的推廣。例如，BKM 可用於透過計算$0+ix,$ 的指數來計算實數角度$x$（以弧度為單位）的正弦和餘弦，即$\cos x+i\sin x.$。BKM 演算法比 CORDIC 稍微複雜，但它不需要縮放因子（K）。

起源

現代 CORDIC 演算法由傑克·E·沃爾德（Jack E. Volder）於 1959 年首次描述。它是在康維爾（Convair）的航空電子部門開發的，旨在替代 B-58 轟炸機導航計算機中的模擬解算器。

儘管 CORDIC 與亨利·布里格斯（Henry Briggs）早在 1624 年發表的數學技術類似，但它針對低複雜度有限狀態 CPU 進行了最佳化。

惠普（Hewlett-Packard）的約翰·斯蒂芬·沃爾特（John Stephen Walther）進一步推廣了該演算法，使其能夠計算雙曲函式和指數函式、對數、乘法、除法和平方根。

最初，CORDIC 使用二進位制數值系統實現。在 20 世紀 70 年代，十進位制 CORDIC 在袖珍計算器中得到廣泛使用，這些計算器大多使用二進位制編碼十進位制 (BCD) 而不是二進位制。

硬體

當硬體乘法器不可用（例如，在基於微控制器的系統中）或需要將實現其支援的函式所需的柵極數量降至最低（例如，在 FPGA 中）時，CORDIC 通常比其他方法更快。

另一方面，當硬體乘法器可用（例如，在 DSP 微處理器中）時，查表法和冪級數通常比 CORDIC 快。近年來，CORDIC 演算法被廣泛用於各種生物醫學應用，尤其是在 FPGA 實現中。

軟體

許多具有僅整數 CPU 的舊系統在一定程度上在其 IEEE 浮點庫中實現了 CORDIC。由於大多數現代通用 CPU 都有浮點暫存器，並具有常見的運算（如加、減、乘、除、正弦、餘弦、平方根、log10、自然對數），因此在其中使用軟體實現 CORDIC 的需求幾乎不存在。只有微控制器或特殊的安全和時間約束軟體應用程式需要考慮使用 CORDIC。

歷史

沃爾德（Volder）受到 1946 年版 CRC 化學和物理手冊中以下公式的啟發

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

其中$K_{n}={\sqrt {1+2^{-2n}}},\tan(\phi )=2^{-n}.$。

CORDIC 的一些早期突出應用包括康維爾導航計算機 CORDIC I 到 CORDIC III、惠普（Hewlett-Packard）的 HP-9100 和 HP-35 計算器、英特爾（Intel）的 80x87 協處理器系列（直到英特爾 80486）和摩托羅拉（Motorola）的 68881。

十進位制 CORDIC 最初由赫爾曼·施密特（Hermann Schmid）和安東尼·博加茨基（Anthony Bogacki）提出。

參考文獻

• Jack E. Volder，CORDIC 演算法三角函式計算技術，IRE 電子計算機學報，第 330-334 頁，1959 年 9 月
• Daggett，D. H.，CORDIC 中的十進位制-二進位制轉換，IRE 電子計算機學報，第 EC-8 卷第 5 期，第 335-339 頁，IRE，1959 年 9 月
• John S. Walther，基本函式的統一演算法，春季聯合計算機會議論文集，第 379-385 頁，1971 年 5 月
• J. E. Meggitt，偽除法和偽乘法過程，IBM 雜誌，1962 年 4 月
• Vladimir Baykov，基於逐位（CORDIC）技術的初等函式求值問題，博士論文，列寧格勒國立電氣工程大學，1972 年
• Schmid，Hermann，十進位制計算。紐約，Wiley，1974 年
• V.D.Baykov，V.B.Smolov，計算機中基本函式的硬體實現，列寧格勒國立大學，1975 年，96 頁。*全文
• Senzig，Don，計算器演算法，IEEE Compcon 閱讀摘要，IEEE 目錄號 75 CH 0920-9C，第 139-141 頁，IEEE，1975 年。
• V.D.Baykov，S.A.Seljutin，微型計算器中的基本函式求值，莫斯科，無線電與 связи，1982 年，64 頁。
• Vladimir D.Baykov，Vladimir B.Smolov，專用處理器：迭代演算法與結構，莫斯科，無線電與 связи，1985 年，288 頁
• M. E. Frerking，通訊系統中的數字訊號處理，1994 年
• Vitit Kantabutra，關於計算指數和三角函式的硬體，IEEE 計算機學報 45 (3)，328-339 (1996)
• Andraka，Ray，基於 FPGA 的計算機的 CORDIC 演算法綜述
• Henry Briggs，對數算術。倫敦，1624 年，對開本
• CORDIC 文獻目錄網站
• 演算法的秘密，Jacques Laporte，巴黎 1981 年
• 逐位方法，Jacques Laporte，巴黎 2006 年
• Ayan Banerjee，基於 CORDIC 的生物醫學訊號處理 FFT 處理器的 FPGA 實現，卡拉格布林，2001 年

鳴謝

• 此頁面最初是從CORDIC 演算法在維基百科建立的。