CORDIC算法的相关知识

概 述

CORDIC（Coordinate Rotation Digital Computer）算法即坐标旋转数字计算方法，是J.D.Volder1于1959年首次提出，主要用于三角函数、双曲线、指数、对数的计算。该算法通过基本的加和移位运算代替乘法运算，使得矢量的旋转和定向的计算不再需要三角函数、乘法、开方、反三角、指数等函数。

CORDIC算法是一个“化繁为简”的算法，将许多复杂的运算转化为一种“仅需要移位和加法”的迭代操作。CORDIC算法有旋转和向量两个模式，分别可以在圆坐标系、线性坐标系和双曲线坐标系使用，从而可以演算出8种运算，而结合这8种运算也可以衍生出其他许多运算。

CORDIC算法是天平称重思想在数值运算领域的杰出范例。核心的思想是把非线性的问题变成了线性的迭代问题。由于其结合了天平的砝码原理，可以在固定步内达到设定的精度，因而赢得了广泛的赞誉。

CORDIC实际上用的就是二进制编码，这里的原因更明确，因为计算机的逻辑只有0和1，两种状态，最适合进行二进制运算，如果某一天可以进行N进制编码了，也许黄金分割会被真正应用进来。

基 本 原 理

如图所示，初始向量（X0，Y0）旋转θ角度之后得到向量（X1，Y1），此向量有如下关系：

X1=X0*cos(θ)-Y0*sin(θ)=cos(θ)(X0-Y0*tan(θ))

Y1=Y0*cos(θ)+X0*sin(θ)=cos(θ)(Y0+X0*tan(θ))

注：θ为待求角

假设初始向量经过N次旋转之后得到新向量，且每次旋转角度δ正切值都为2的倍数，则第i次旋转角度为δ=arctan(2^(-i))，即cosδ=（1/（1+2^(-2i)））^0.5。

容易得到角度θ≈∑S(i)●δ(i)，其中S(i)=1或－1，表示旋转角度的方向，

第i步旋转可以表示为：

X(i+1)=(（1/（1+2^(-2i)））^0.5)●(X(i)-S(i)Y(i)2^(-i))

Y(i+1)=(（1/（1+2^(-2i)））^0.5)●(Y(i)+S(i)X(i)2^(-i))

其中（1/（1+2^(-2i)））^0.5)称为校模因子，当旋转次数一定时，趋于一个常数，Π（1/（1+2^(-2i)））^0.5)≈0.6073

而由极限

（被遮住的是根号1加2的负i次方，妈的去不掉水印）

可知，算法每一步就可以简化为：

X(i+1)=X(i)-S(i)Y(i)2^(-i)

Y(i+1)=Y(i)+S(i)X(i)2^(-i)

从而可以看出，对于移动的角度θ，现在只需要硬件加减法器和移位器就可以算出结果。引入Z，表示i次旋转后相位累加的部分和，则：

Z(i+1)=Z(i)-S(i)arctan(2^(-i))

经过n次旋转之后，Z→0，即与目标角重合，即：

X(n)=X1=X0*cos(θ)-Y0*sin(θ)

Y(n)=Y1=Y0*cos(θ)+X0*sin(θ)

现 实 意 义

由于具有频率精度高、转换时间短、频谱纯度高以及频率相位易编程等特点，数控振荡器(NCO)被广泛应用于软件无线电数字上、下变频以及各种频率和相位数字调制解调系统中。NCO传统的实现方法主要有查表法、多项式展开法或近似法，但这些方法在速度、精度、资源方面难以兼顾。而采用CORDIC算法来实现超函数时，则无需使用乘法器，它只需要一个最小的查找表(LUT)，利用简单的移位和相加运算，即可产生高精度的正余弦波形，尤其适合于FPGA的实现。

数字控制振荡器（NCO，numerical controlled oscillator）是软件无线电、直接数据频率合成器（DDS，Direct digital synthesizer）、快速傅立叶变换（FFT，Fast Fourier Transform）等的重要组成部分，同时也是决定其性能的主要因素之一，随着芯片集成度的提高、在信号处理、数字通信领域、调制解调、变频调速、制导控制、电力电子等方面得到越来越广泛的应用。

相 关 图 片