1

Cordic算法FPGA实现cos,sin (含python和verilog代码)

“ 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度角逼近的过程)。

cordic算法过程演示动画

接下来,确定一下每次旋转的角度。在这里我们为了便于硬件额实现,做以下考虑。
旋转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θnyn + 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度的角,十六次迭代过程如下视屏所示。

cordic算法十六次迭代过程演示动画

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 ),即根据两直角边求斜边长。
verilog完整代码见下面第一个回答:

编辑 重设标签(回车键确认) 标为违禁 关闭 合并 删除

提问于 2019-05-05 13:25:45 +0800

这个帖子被标记为一个社区wiki

这个帖子是一个wiki(维基). 任何一个积分 >500的人都可以完善它

想向站长提问,微信扫码立刻加入! shawn的FPGA圈.png
0
  答案登陆可见 做站不容易,小伙伴支持一下我们吧!
编辑 标为违禁 删除 链接 更多选项...
shawn 头像
0

这个还是蛮实用的,在电机控制等方面应用还是蛮广的,点一个赞!

编辑 标为违禁 删除 链接 更多选项...
ipqsn 头像
0

有代码,有实例,楼主威武!

编辑 标为违禁 删除 链接 更多选项...
BertramChen 头像
登录/注册后进行回答