FPGA数字信号处理之CORDIC算法

CORDIC（Coordinate Rotation Digital Computer）算法即坐标旋转数字计算方法。该算法通过基本的加和移位运算代替乘法运算，用于三角函数、双曲线、指数、对数的计算。CORDIC算法的思想是：反复迭代，逐次逼近终值，计算结果达到一定精度即可终止。比如下边图中任意坐标0 [10,20]，计算它的角度值，使用cordic算法就是三角函数不断的旋转坐标系，做法就是：1、将该点0顺时针旋转π/2，得到点1；
2、由于点1位于第四象限，说明转多了，再往逆时针方向转π/4，得到点2；3、点2位置象限，顺时针旋转π/8，得到点3，
4、由于点3位于第四象限，说明转多了，再往逆时针方向转π/16，得到点4；5、点4位置象限，顺时针旋转π/32，得到点5....（根据所需精度，确定旋转次数即可）

终把旋转的角度求和就得到了任意坐标[10,20]的角度值，其中坐标旋转用的三角函数公式为：

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

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

上边的例子能说明cordic算法的思想，在确定旋转次数之后，每次旋转的cos(θ)和tan(θ)值是确定的，这样我们就可以用提前存储的cos(θ)和tan(θ)值去计算任意坐标的角度值。

但是上面角度旋转过程中用到了乘法运算，并没有简化运算量。接下来对cordic进一步优化，将上式中的cos(θ)舍弃，得到如下的结果：

循环过程中Y的正负判断象限，决定旋转方向，但是X/Y坐标会向外无限循环，这时候旋转得到的X/Y坐标会扩展很多倍，如下图，注意下图中的坐标轴刻度是1E17。

上述旋转过程的计算变化成了：

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

Y1=(Y0+X0*tan(θ))每次旋转减少了两个乘法，在需要知道正确坐标值的情景下，比如要知道该信号的幅度，由于cordic算法的旋转测试是确定的，所以cos(θ)确定的，所以cos(θ1)*cos(θ2)*cos(θ3)*...*cos(θn)是一个定值，只需要在旋转之后将的X/Y值与cos(θ1)*cos(θ2)*cos(θ3)*...*cos(θn)这个定值相乘即可。上面的旋转过程还是用到了乘法，乘法依然是FPGA/IC中的紧俏资源，下一篇文章介绍如何不用乘法的在FPGA中实现CORDIC。