“ Cordic算法是一种特别适合于数字硬件电路实现各种三角函数与反三角函数以及计算直角三角形第三边长的算法。”
01 Cordic算法原理与python代码实现
如上图所示,当点(x1,y1)转过θ角之后,到达点(x2,y2),有如下等式关系(根据三角函数的角度加减运算推导一下就出来了)。
x2 = rcos(θ0+θ) = x1cosθ-y1sinθ = cosθ(x1 - y1tanθ)
y2 = rsin(θ0+θ) = x1sinθ+y1cosθ = cosθ(y1 + x1tanθ)
Codic算法思想就是循环迭代旋转,逐渐向所求结果逼近,每次迭代旋转的角度都减半,旋转之后如果大于所要求的角度值,就顺时钟回转,否则逆时钟转动,如下图动画所示(演示一个向70度角逼近的过程)。
接下来,确定一下每次旋转的角度。在这里我们为了便于硬件额实现,做以下考虑。
旋转n次后得到的值如下:
xn=cosθ0cosθ1cosθ2...cosθn(xn-1 - yn-1tanθn)
yn=cosθ0cosθ1cosθ2...cosθn(yn-1 + xn-1tanθn)
令 k = cosθ0cosθ1cosθ2...cosθn
当旋转次数与每次旋转的角度值确定后,k值就确定了,可以把它当作一个固定的系数。
但是每次运算还要做两个乘法运算:xn - yntanθn
, yn + xntanθn
。
因此考虑将每次旋转的角度值θn都定为使得tanθn = (1/2)^n
,这样乘法运算变成只需要做移位操作就可以了。
首先我们使用python来得到k和每次旋转的角度,方案定为旋转16次。代码如下:
import numpy as np
import math
#get the arctan of 1,1/2,1/4....
arctan_value = np.zeros((16,))
for i in range(0,16) :
arctan_value[i] = (1/2)**i
print(arctan_value)
angle_e = np.degrees(np.arctan(arctan_value))
print(angle_e)
f = open('cordic_arctan.v','w')
f.write( "\n get the arctan of 1,1/2,1/4...." )
for i in range(0,16):
f.write("\n `define angle"+ str(i) +" " + str(angle_e[i]))
f.write( "\n\n get the cos_e of 16 iterations" )
cos_e = np.cos(angle_e*np.pi/180)
k = 1
for i in range(0,16):
k = cos_e[i]*k
f.write( "\n cos_"+ str(i) + ": " + str(cos_e[i]) )
f.write("\n\n get K = cos_0*cos_1*cos_2... = "+str(k))
f.close()
得到(angle为每次旋转的角度):
`define angle0 45.0
`define angle1 26.56505117707799
`define angle2 14.036243467926479
`define angle3 7.125016348901798
`define angle4 3.576334374997351
`define angle5 1.789910608246069
`define angle6 0.895173710211074
`define angle7 0.44761417086055
`define angle8 0.22381050036853
`define angle9 0.11190567706620
`define angle10 0.05595289189380
`define angle11 0.02797645261700
`define angle12 0.01398822714226
`define angle13 0.00699411367535
`define angle14 0.00349705685070
`define angle15 0.00174852842698
get the cos_e of 16 iterations
cos_0: 0.7071067811865476
cos_1: 0.8944271909999159
cos_2: 0.9701425001453319
cos_3: 0.9922778767136676
cos_4: 0.9980525784828885
cos_5: 0.9995120760870788
cos_6: 0.9998779520346953
cos_7: 0.9999694838187878
cos_8: 0.9999923706927791
cos_9: 0.9999980926568242
cos_10: 0.9999995231631829
cos_11: 0.9999998807907318
cos_12: 0.999999970197679
cos_13: 0.9999999925494195
cos_14: 0.9999999981373549
cos_15: 0.9999999995343387
get K = cos_0*cos_1*cos_2... = 0.6072529351031395
其Cordic计算cos,sin值的python代码实现如下(angle_e[i]里面存储了每次旋转的角度值):
x = 1
y = 0
angle = 70 #需要求得角度
x_p = np.zeros((16,2))
y_p = np.zeros((16,2))
for i in range(0,16):
if angle > 0:
x_h = x - y*arctan_value[i]
y_h = y + x*arctan_value[i]
angle = angle - angle_e[i]
else :
x_h = x + y*arctan_value[i]
y_h = y - x*arctan_value[i]
angle = angle + angle_e[i]
x = x_h
y = y_h
cos_angle = x*k #所求角度的cos值
sin_angle = y*k #所求角度的sin值
注意:这里的cordic可以计算的角度角度的范围为
(-angle[0]+angle[1]+…+angle[15] ,+angle[0]+angle[1]+…+angle[15])。
上例求得是角度为70度的角,十六次迭代过程如下视屏所示。
02 verilog实现
为了便于硬件实现少一个乘法器运算,把上面的软件改成:
x = k #初始化为K,因此避免最后需要乘以k
y = 0
angle = 70 #需要求得角度
x_p = np.zeros((16,2))
y_p = np.zeros((16,2))
for i in range(0,16):
if angle > 0:
x_h = x - y*arctan_value[i]
y_h = y + x*arctan_value[i]
angle = angle - angle_e[i]
else :
x_h = x + y*arctan_value[i]
y_h = y - x*arctan_value[i]
angle = angle + angle_e[i]
x = x_h
y = y_h
cos_angle = x #所求角度的cos值
sin_angle = y #所求角度的sin值
硬件电路采用16级流水线设计,(如果对流水线不清楚,可以参考文章 “一个实例彻底拿下流水线设计”),同时为了避免浮点数运算,将数据整体扩大了65535倍,即向左移16位.。所得的cos与sin的真实结果为电路输出值除以65535。下篇文章将会讲述Cordic算法实现 distance=√(x^2+y^2 ),即根据两直角边求斜边长。
有代码,有实例,楼主威武!
这个还是蛮实用的,在电机控制等方面应用还是蛮广的,点一个赞!
Cordic_cos.v
Cordic_tb.v