跳转到内容

CORDIC

维基百科,自由的百科全书

CORDIC(英語:Coordinate rotation digital computer),也稱為Volder演算法(英語:Volder's algorithm),是一個可以計算三角函數,簡單且有效率的演算法,可以在任意進制下運算,一般會每次計算一位數字。因此CORDIC屬於逐位計算(Digit-by-digit)方法中的一個例子。

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

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

歷史

[编辑]

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

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

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

其中是使成立的值,且

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

應用

[编辑]

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

硬體

[编辑]

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

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

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

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

軟體

[编辑]

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

運作模式

[编辑]

旋轉模式

[编辑]

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

CORDIC演算法的圖解

在第一次的迭代時,向量逆時針轉45°,得到向量。接著繼續的迭代,每一次的角度漸漸變小,旋轉方向可能順時針,也可能逆時針,直到得到想要的角度為止。每一次的角度為,其中

若以更正式的方式表示,每一次的迭代就是一次旋轉,也就是將向量乘以旋转矩阵

旋转矩阵為

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

旋转矩阵變成

旋转向量就會變成下式

其中的分量,若將角度限制在使的值,和tangent的乘法就以變成乘(或除)2的幂次,在數位電腦硬體中可以快速的用位元右移或左移來計算。因此上法會變成

其中

是用來判斷旋轉方向的。若角度為正,則為 1,否則則為−1。

所有的因子可以在迭代過程中忽略,最後再一次乘以因子即可:

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

因此可以簡化演算法的複雜度。有些應用會避免修正,因此此演算法本身會帶一個增益[19]

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

唯一未解決的問題是判斷每一次迭代要順時針旋轉或逆時針旋轉(選擇的值)。這可以記錄每一次旋轉的角度,從還需要旋轉的角度中減去此一角度,會得到下一個還需要旋轉的角度。若為正,需要順時針旋轉,否則,就需要順時針旋轉:

的值需要事先計算且記錄下來。不過若是小角度,根據小角度近似,在定點數下可得,因此可以節省儲存用的空間。

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

向量模式

[编辑]

上述旋轉模式的演算法,是旋轉原來位在x軸上的單位向量。但此演算法可以用來旋轉角度在−之間的任意向量,旋轉的方向則依的正負號決定。

向量模式下的演算法和旋轉模式略有不同。其啟始向量的x坐標要為正值,y坐標則為任意值。持續轉動的目的是將向量旋轉到x軸(因此y座標為0)。每一步裡的旋轉方向會由y的值決定。的最終值包括了總旋轉角度。x的最終值是原向量的大小,再乘以K。因此,可以看出向量模式可以進行直角坐標到極坐標的轉換。

實現

[编辑]

Java的Math類別中有scalb(double x,int scale)方法可以實現二進位的移位[20],C語言有ldexp函數[21],x86處理器有fscale浮點運算[22]

軟體範例(Python)

[编辑]
from math import atan2, sqrt, sin, cos, 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})"
        )

輸出

[编辑]
$ 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)

硬體範例

[编辑]

實現CORDIC需要的邏輯閘大約和乘法器相當,兩者都是用位元移位和加法所組合的。要選擇乘法器或是CORDIC會隨應用而定。若複數以其實部和虛部表示(直角座標),複數乘法會需要進行四次的乘法。但若複數以極座標表示,只要一個CORDIC即可處理,這更適合用在其乘積的量值不重要的應用(例如將向量和單位圓上的向量相乘的情形)。在數位下轉換器英语digital down converter之類的通訊相關電路中,常會用到CORDIC。

雙重迭代CORDIC

[编辑]

在Vladimir Baykov的二篇文獻中[23][24],曾經提到用「雙重迭代」(double iterations)來實現反正弦函數、反餘弦函數、自然對數、指數函數以及雙曲函數。雙重迭代中的作法和傳統的CORDIC演算法不同,傳統的CORDIC演算法中,迭代變數會在每次迭代時加一。但在雙重迭代中,迭代變數會先重複一次,然後才加一。因此雙重迭代CORDIC演算法的迭代變數會是,而傳統CORDIC演算法的迭代變數是。雙重迭代法保證方法的收斂,不過其引數的有效範圍會變化。

針對進制數字系統中,通用的CORDIC收斂問題,可以證明[25]針對正弦、餘弦及反正切函數,每一個i(i = 0或1到n,其中n是位數)進行次迭代就可以保證收斂。若是自然對數、指數、雙曲正弦、雙曲餘弦及雙曲反正切函數,每一個i需要進行次迭代。若是反正弦函數及反餘弦函數,每一個i需要進行2 次的迭代[25]

若是雙曲反正弦及雙曲反餘弦函數,每一個i需要進行2R次的迭代。

相關演算法

[编辑]

CORDIC屬於「移位及加法」(shift-and-add)的演算法,就像Henry Briggs文獻提到的對數和指數演算法一樣。BKM演算法英语BKM algorithm也是可以計算許多基本函數的移位及加法演算法,是複數平面下對數和指數演算法的推廣。BKM可以計算實數角度(以弧度表示)的正弦和餘弦,其方式是計算的指數,也就是。BKM演算法比CORDIC要複雜一些,但其優點是不需考慮比例因子(K)。

相關條目

[编辑]

參考資料

[编辑]
  1. ^ Volder, Jack E. The CORDIC Computing Technique (PDF). Proceedings of the Western Joint Computer Conference (WJCC) (presentation) (San Francisco, California, USA: National Joint Computer Committee (NJCC)). 1959-03-03: 257–261 [2016-01-02]. (原始内容存档 (PDF)于2018-06-12). 
  2. ^ Volder, Jack E. The CORDIC Trigonometric Computing Technique (PDF). IRE Transactions on Electronic Computers (The Institute of Radio Engineers, Inc. (IRE)). 1959-05-25, 8 (3): 330–334 (reprint: 226–230) (September 1959) [2016-01-01]. EC-8(3):330–334. (原始内容 (PDF)存档于2021-06-12). 
  3. ^ Walther, John Stephen. 写于Palo Alto, California, USA. A unified algorithm for elementary functions (PDF). Proceedings of the Spring Joint Computer Conference (Atlantic City, New Jersey, USA: Hewlett-Packard Company). May 1971, 38: 379–385 [2016-01-01]. (原始内容 (PDF)存档于2021-06-12) –通过American Federation of Information Processing Societies (AFIPS). 
  4. ^ Walther, John Stephen. The Story of Unified CORDIC. The Journal of VLSI Signal Processing (Hingham, MA, USA: Kluwer Academic Publishers). June 2000, 25 (2 (Special issue on CORDIC)): 107–112 [2024-01-28]. ISSN 0922-5773. S2CID 26922158. doi:10.1023/A:1008162721424. (原始内容存档于2018-12-08). 
  5. ^ Luo, Yuanyong; Wang, Yuxuan; Ha, Yajun; Wang, Zhongfeng; Chen, Siyuan; Pan, Hongbing. Generalized Hyperbolic CORDIC and Its Logarithmic and Exponential Computation With Arbitrary Fixed Base. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. September 2019, 27 (9): 2156–2169. S2CID 196171166. doi:10.1109/TVLSI.2019.2919557. 
  6. ^ Luo, Yuanyong; Wang, Yuxuan; Ha, Yajun; Wang, Zhongfeng; Chen, Siyuan; Pan, Hongbing. Corrections to "Generalized Hyperbolic CORDIC and Its Logarithmic and Exponential Computation With Arbitrary Fixed Base". IEEE Transactions on Very Large Scale Integration (VLSI) Systems. September 2019, 27 (9): 2222. S2CID 201711001. doi:10.1109/TVLSI.2019.2932174. 
  7. ^ Briggs, Henry. Arithmetica Logarithmica. London. 1624.  (Translation: [1] 互联网档案馆存檔,存档日期4 March 2016.)
  8. ^ Laporte, Jacques. Henry Briggs and the HP 35. Paris, France. 2014 [2016-01-02]. (原始内容存档于2015-03-09).  [2] 互联网档案馆存檔,存档日期2020-08-10.
  9. ^ Flower, Robert. The Radix. A new way of making logarithms.. London: J. Beecroft. 1771 [2016-01-02]. 
  10. ^ 10.0 10.1 10.2 Volder, Jack E., Binary Computation Algorithms for Coordinate Rotation and Function Generation (internal report), Convair, Aeroelectronics group, 1956-06-15, IAR-1.148 
  11. ^ 11.0 11.1 11.2 11.3 11.4 11.5 11.6 Volder, Jack E. The Birth of CORDIC (PDF). Journal of VLSI Signal Processing (Hingham, MA, USA: Kluwer Academic Publishers). June 2000, 25 (2 (Special issue on CORDIC)): 101–105 [2016-01-02]. ISSN 0922-5773. S2CID 112881. doi:10.1023/A:1008110704586. (原始内容 (PDF)存档于2016-03-04). 
  12. ^ Perle, Michael D., CORDIC Technique Reduces Trigonometric Function Look-Up, Computer Design (Boston, MA, USA: Computer Design Publishing Corp.), June 1971: 72–78  (NB. Some sources erroneously refer to this as by P. Z. Perle or in Component Design.)
  13. ^ Schmid, Hermann. Decimal Computation 1 (reprint). Malabar, Florida, USA: Robert E. Krieger Publishing Company. 1983: 162, 165–176, 181–193 [2016-01-03]. ISBN 0-89874-318-4.  (NB. At least some batches of this reprint edition were misprints with defective pages 115–146.)
  14. ^ Daggett, Dan H. Decimal-Binary Conversions in CORDIC. IRE Transactions on Electronic Computers (The Institute of Radio Engineers, Inc. (IRE)). September 1959, 8 (3): 335–339 [2016-01-02]. ISSN 0367-9950. doi:10.1109/TEC.1959.5222694. EC-8(3):335–339. 
  15. ^ Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik. 50 Years of CORDIC: Algorithms, Architectures and Applications (PDF). IEEE Transactions on Circuits and Systems I: Regular Papers. 2008-08-22, 56 (9): 1893–1907 (2009-09-09) [2024-01-28]. S2CID 5465045. doi:10.1109/TCSI.2009.2025803. (原始内容存档 (PDF)于2024-04-28). 
  16. ^ Meher, Pramod Kumar; Park, Sang Yoon. Low Complexity Generic VLSI Architecture Design Methodology for Nth Root and Nth Power Computations. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. February 2013, 21 (2): 217–228. S2CID 7059383. doi:10.1109/TVLSI.2012.2187080. 
  17. ^ Error bounds of Taylor Expansion for Sine. Math Stack Exchange. [2021-01-01]. 
  18. ^ Muller, Jean-Michel. Elementary Functions: Algorithms and Implementation 2. Boston: Birkhäuser. 2006: 134 [2015-12-01]. ISBN 978-0-8176-4372-0. LCCN 2005048094. (原始内容存档于2011-06-05). 
  19. ^ Andraka, Ray. A survey of CORDIC algorithms for FPGA based computers (PDF). ACM (North Kingstown, RI, USA: Andraka Consulting Group, Inc.). 1998 [2016-05-08]. 0-89791-978-5/98/01. (原始内容存档 (PDF)于2024-04-23). 
  20. ^ Class Math. Java Platform Standard 8. Oracle Corporation. 2018 [2018-08-06]. (原始内容存档于2018-08-06). 
  21. ^ ldexp, ldexpf, ldexpl. cppreference.com. 2015-06-11 [2018-08-06]. (原始内容存档于2018-08-06). 
  22. ^ Section 8.3.9 Logarithmic, Exponential, and Scale. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 1: Basic Architecture (PDF). Intel Corporation. September 2016: 8–22 [2024-01-29]. (原始内容存档 (PDF)于2013-04-02). 
  23. ^ Baykov, Vladimir. The outline (autoreferat) of my PhD, published in 1972. baykov.de. [2023-05-03]. (原始内容存档于2011-01-11). 
  24. ^ Baykov, Vladimir. Hardware implementation of elementary functions in computers. baykov.de. [2023-05-03]. (原始内容存档于2011-01-15). 
  25. ^ 25.0 25.1 Baykov, Vladimir. Special-purpose processors: iterative algorithms and structures. baykov.de. [2023-05-03]. (原始内容存档于2011-07-18). 

外部連結

[编辑]