CORDIC（Coordinate RotaTIon Digital Computer）算法即坐标旋转数字核算办法，是J.D.Volder1于1959年初次提出，首要用于三角函数、双曲线、指数、对数的核算。该算法经过根本的加和移位运算替代乘法运算，使得矢量的旋转和定向的核算不再需求三角函数、乘法、开方、反三角、指数等函数。
本文是依据FPGA完成Cordic算法的规划与验证，运用Verilog HDL规划，开始可完成正弦、余弦、横竖切函数的完成。将杂乱的运算转化成FPGA拿手的加减法和乘法，而乘法运算能够用移位运算替代。Cordic算法有两种形式，旋转形式和向量形式。能够在圆坐标系、线性坐标系、双曲线坐标系运用。本文线开始完成在圆坐标系下的两种形式的算法完成。
Cordic算法简化
旋转形式，迭代位移算法。假设有一点P0（x0，y0），经过逆时针旋转视点θ，抵达点Pm（xm，ym），咱们依据数学运算能够得到公式如下：
xm = x0cosθ – y0sinθ = cosθ（x0 – y0tanθ）
ym = y0cosθ + x0sinθ = cosθ（y0 – x0tanθ）
假如不考虑旋转后的向量模值，只考虑旋转视点，即去掉cosθ，得到如下方程式。这儿旋转的视点的正确的，但x和y的值增加。cosθ值是小于等于1的，值大于等于1，所以模值应该增大。咱们不能经过恰当的数学核算去掉cosθ，可是去掉cosθ项能够便利咱们后边的坐标平面旋转的核算。这儿称为伪旋转。
xm = x0 – y0tanθ
ym = y0 – x0tanθ
Cordic的办法中心便是伪旋转，将旋转角θ细化成若干个巨细固定的视点θi，规则θi满意tanθi = 2^-i，经过一系列的迭代旋转，每次旋转θi，i为迭代次数，规则∑θi的规模即旋转视点θ的规模为［-99.7， 99.7］。假如θ的大于这个规模则可经过三角运算操作转化到该规模的视点。
咱们经过事先将一切每次旋转的视点核算出来，因为每次旋转的视点是固定的，所以经过i次旋转的∑θi可能会超越θ，所以就必须设置一个方向值di，假如旋转视点之和现已小于θ，则di为1，下次旋转持续为顺时针旋转，假如旋转视点之和大于θ，则di为-1，下次旋转为逆时针。设置zi+1为旋转剩下视点，zi+1 = z0 – dizi，z0 = θ，跟着i值得增大，zi+1会趋向于0时，即旋转完毕。di与zi的符号位相同。
选用伪旋转的办法，每次提出一个cosθi，旋转完毕后会发生一个∏cosθi的累乘，一旦咱们确认了迭代次数，∏cosθi便是一个常数，迭代公式可写为。这是将cosθi提出、tanθi 替换成 2^-i后的成果。di与zi的符号位相同。
xi+1 = xi – di * yi * 2^-i
yi+1 = yi + di * xi * 2^-i
zi+1 = z0 – di * θi
设迭代i = n – 1，那么旋转n次后得到Pm的坐标应该为（xn * ∏cosθi， yn * ∏cosθi）。应为每次迭代都会提出一个cosθi，旋转n次后的xn和yn就会少乘一个∏cosθi，所以实践上终究的Pm坐标视点近似于（xn * ∏cosθi， yn * ∏cosθi）。
xn * ∏cosθi = x0cosθ – y0sinθ
yn * ∏cosθi = y0cosθ + x0sinθ
xn = 1/∏cosθi （x0cosθ – y0sinθ）
yn = 1/∏cosθi （y0cosθ – x0sinθ）
弹性因子，KN = 1 / ∏cosθi，已知迭代次数，咱们能够预先核算KN的值。如下这是博主运用MATLAB核算出的迭代成果数值。
xn =KN （x0cosθ – y0sinθ）
yn = KN （y0cosθ – x0sinθ）
从上表能够得出，咱们预先核算出KN的值，然后令x0 = ∏cosθi，y0 = 0，则上述公式可化简为
xn = cosθ
yn = sinθ
即可完成正弦、余弦操作了。
旋转形式
总结一下，Cordic算法旋转形式运用Verilog HDL的完成流程
（1） 确认迭代次数，将每次迭代的视点核算出来，预先界说为参数，为了防止浮点运算，将视点值向左移位16位，取整数部分。
（2） 依据迭代公式进行迭代核算，本规划取16次迭代，从上表能够看出，当迭代次数越大时，1/∏cosθi会趋向于一个确认值。假如对成果精度要求更高，能够设置更高的迭代次数，依据迭代次数，能够将弹性因子KN = 1/∏cosθi核算出来。相同将其左移16位。
xi+1 = xi – di * yi * 2^-i
yi+1 = yi + di * xi * 2^-i
zi+1 = z0 – di * θi
（3） 设置x0 = ∏cosθi，y0 = 0，则求出x16 = cosθ，y16 = sinθ。
这儿需求留意的是，咱们在进行迭代运算的时分，将2^-i变成移位运算，关于正余弦来说是有正负的，所以在一开始界说的时分，就应该界说成有符号数，Verilog中也能够界说有符号数，最高位表明符号位，界说如下
迭代寄存器界说为有符号数，那么咱们移位运算就不能用》》逻辑右移《《逻辑左移或来移位了，而是用》》》算术右移和《《《算术左移。逻辑左移也就相当于管用左移，右边统一添0 ，逻辑右移，左面统一添0 ，管用右移，左面增加的数和符号有关。
例如1010_1010， ［］是增加的位
逻辑左移一位：0101_010［0］
管用左移一位：0101_010［0］
逻辑右移一位：［0］101_0101
管用右移一位：［1］101_0101
迭代运算选用16级流水线，进行运算，终究需求判别输出的正余弦值在哪个象限，前面讲旋转视点θ的规模为［-99.7，99.7］，不在这个规模咱们要进行三角运算使其满意这个规模，当输入的视点小于90度即可进行核算，当输入视点大于90度小于180度，将输入视点减去90度并设定其时视点处于第二象限，然后进行核算，当输入视点大于180度小于270度，将输入的视点减去180度设置其时视点处于第三象限，进行核算，当输入的视点大于270度，减去270设置其时视点处于第四象限，进行核算。象限的设定经过quarant寄存器完成。
假如视点在榜首象限，sin（x） = sin（a），cos（x） = sin（a）终究的成果x16 = cosθ， y16 = sinθ，这儿我想起了那句口诀，一全正，二正弦，三正切，四余弦
假如视点在第二象限，sin（x） = sin（a+90） = cos（a），cos（x） = cos（a+90） = -sin（a）
假如视点在第三象限，sin（x） = sin（a+180） = -sin（a），cos（x） = cos（a+180） = -cos（a）
假如视点在第四象限，sin（x） = sin（a+270） = cos（a），cos（x） = cos（a+270） = -sin（a）
关于正数，咱们直接赋值输出，负数，这儿运用有符号数表明，将其取反加1即可。终究运用modelsim对算法进行仿真，从波形图上看现已开始完成了sin，cos函数。
向量形式
Cordic算法在向量形式下的核算办法和旋转形式根本上是相似的，设有一点P0（x0， y0），经过顺时针旋转视点到与轴重合，得到点Pm（xm， ym），即ym = 0。
xm = x0cosθ – y0sinθ = cosθ（x0 – y0tanθ）
ym = y0cosθ + x0sinθ = cosθ（y0 – x0tanθ） = 0
咱们设置x0 = x， y0 = y， z0 = 0，迭代次数为16，经过16次迭代后得到zn = θ = arctan（y/x）和坐标所代表的向量的模值d = xm = xn * ∏cosθi，di与yi方向相反，即其时完毕运算。完成办法为判别yi的符号位，符号位为1，di为1，符号位为0，di为-1。
xi+1 = xi – di * yi * 2^-i
yi+1 = yi + di * xi * 2^-i
zi+1 = z0 – di * θi
关于横竖切函数，因为在［-99.7°，99.7°］规模内，所以咱们输入向量P0（x0， y0）时，需求保证其在榜首、四象限。
下面是运用MATLAB核算出来的数据和FPGA核算出来的数据进行比较。
从FPGA核算出的成果与MATLAB来比较，和实践成果之间的差错仍是挺小的，毕竟是硬件核算出来的数据，向量的差错就比较大了，假如关于精度比较高的核算，咱们能够经过进步迭代次数来进步精度。至此依据FPGA的Cordic算法就完成完毕了。
