Cordic算法初探

 

最近开始研究cordic算法。Cordic算法是坐标旋转数字计算方法,之前是用来进行坐标变换的算法。之后经过发展可以进行很多其他的数学运算。

看了很多的资料,才对这个算法有了个大致的了解。按照我理解是:这个算法是利用迭代的运算,来得到数学运算的数值解。当然这个数值解和精确解之间有误差,不过这误差会随着迭代的次数增多而减小。到最后,误差小到可以忽略掉。

 这算法比较麻烦,不过对于我们,不用太了解,只需要会用就行了我一直都是这样认为的,先会用,然后再去了解原理,毕竟有些原理太麻烦了,有时难以理解,但是不影响我们使用。

 Cordic算法,有三个参数,一个x,一个y,一个z。三个输入不同的值,并令不同的值趋向于0。会得到不同的结果。

 首先,研究z趋向于0的情况:

  clip_image001

从上图看出,当z趋向于0.x的输入为0.60725的时候,输出x的值为cosz),和sinz)的值。这样就计算出来正弦和余弦的值了。

 下面是对应的伪代码:

for n=0 to [inf]
    if (Z(n) >= 0) then
        X(n + 1) := X(n) – (Yn/2^n);
        Y(n + 1) := Y(n) + (Xn/2^n);
        Z(n + 1) := Z(n) – atan(1/2^n);
    else
        X(n + 1) := X(n) + (Yn/2^n);
        Y(n + 1) := Y(n) – (Xn/2^n);
        Z(n + 1) := Z(n) + atan(1/2^n);
    end if;
end for;

其中的inf可以自己设置为一个值,理论上越大越好。但是越大的话,处理就会越慢。因此需要在精确度和速度间折衷。

matlab仿真看看:

其代码如下:

clear all;
p = 1.646768
k = 1/p;
x0 = k;
y0 = 0;
z0 = 45;
 
for i = 0:1:10000
   if z0 > 0
       x = x0 - y0*2^(-i);
       y = y0 + x0*2^(-i);
       z = z0 - atan(1/2^i)*180/pi;
   else
       x = x0 + y0*2^(-i);
       y = y0 - x0*2^(-i);
       z = z0 + atan(1/2^i)*180/pi;
   end
       x0 = x;
       y0 = y;
       z0 = z;
end

  以上程序是计算sin45,和cos45的值。 理论上,这两个值为1/sqrt(2).

  运行,看结果。

      x =  0.707103456896123  y = 0.707103456896123

而理论值1/sqrt(2)= 0.707106781186547

可看出,是有误差的。不过误差比较小,大致为0.000003。。这误差,在实际中,可忽略了。

接下来让y趋向于0,可得另外一些运算。

clip_image002

 

可看出,初始让z=0。然后迭代过程中,让y趋向于0.这样得出输出x的值为输入x和输入y的值的平方和在开根号。而z的值为反正切的值。

其对应的伪代码如下:

for n=0 to [inf]
    if (y(n) <= 0) then
        X(n + 1) := X(n) – (Yn/2^n);
        Y(n + 1) := Y(n) + (Xn/2^n);
        Z(n + 1) := Z(n) – atan(1/2^n);
    else
        X(n + 1) := X(n) + (Yn/2^n);
        Y(n + 1) := Y(n) – (Xn/2^n);
        Z(n + 1) := Z(n) + atan(1/2^n);
    end if;
end for;

其中的inf为迭代次数的值。理论上为无穷大,但是在实际中,应为有限值。这值越大,结果的误差越小。

从以上的式子中可看出,输出x的值为所求值的p倍。因此在最后的结果的中,x的值要除以p,这样的值才正确。

其对应的matlab代码为:

clear all;
p = 1.646768;
k = 1/p;
x0 = 6;
y0 = 8;
z0 = 0;
for i = 0:1:10000
   if y0 < 0
       x = x0 - y0*2^(-i);
       y = y0 + x0*2^(-i);
       z = z0 - atan(1/2^i)*180/pi;
   else
       x = x0 + y0*2^(-i);
       y = y0 - x0*2^(-i);
       z = z0 + atan(1/2^i)*180/pi;
   end
       x0 = x;
       y0 = y;
       z0 = z;
end
x = x0/p;

理论上,68的平方和在开根号的值为10*atan8/6)的值为53.130102354155980

运行程序,看结果:

x = 9.999952987433964     z =  53.130102354156008

对比理论值,可看出还是有一定误差,不过误差非常的小,在实际中,不要求特别精确的情况下,是可以忽略的。

Cordic的可以用迭代计算很多数学运算。但是真正cordic比较牛的地方,是可以用硬件来实现。从以上的伪代码,可看出,xy的运算有个乘以2^-i)的这个因子。而这个因子,在硬件中,只要是乘以2,或者除以2,都是通过简单的右移和左移来实现的。这样,迭代就简单的用移位,加法实现了。而atan(1/2^i),这个因子,因为i的值是固定从整数0到我们需要迭代次数的值。因此,对于确定的每个迭代i,这个atan(1/2^i)是个确定的值。因此,我们可以将这些预先知道的值存进一个rom里面,然后再调用的时候在用就行了。这样的话,就发现,cordic算法,用硬件来实现就很简单了。只需要移位,加法,查表,然后再迭代,就可以得出我们想要的结果了。

对于上面的伪代码,z = z0 + atan(1/2^i)*180/pi; 中的180/pi这个是为了将弧度转化为我们平常说的角度数,方便我们查看。在硬件实现中,这个可去掉。这样就变成了,

z = z0 + atan(1/2^i)atan(1/2^i)的值是存在rom里面的值,因此z的计算也很简单。就简单的加法就行了。

 以上,就是我分析的cordic算法。想详细了解这个算法的,需要去查找资料看看。这里原理讲的比较简单,就讲怎么使用了。

之后,会研究,用verilog实现cordic算法。

     

此条目发表在其他分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。