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). 

外部链接

编辑