这里的日志均为读书时转载的,再次澄清说明~~~

CORDIC算法!!

上一篇 / 下一篇  2009-05-01 15:44:50 / 个人分类:FPGA设计

http://hi.baidu.com/shenlang277/blog/item/8497d7ca293a7841f31fe739.html

坐标旋转数字计算机CORDIC(COordinate Rotation DIgital Computer)算法通过移位和加减运算,递归计算常用函数值,如sin, cos, sinh, cosh。

以sin/cos计算为例,可利用正/余弦的和角公式递归进行:

cos(a+b) = cos(a)cos(b) – sin(a)sin(b) = cos(a) [cos(b) – tan(a)sin(b)]

sin(a+b) = sin(a)cos(b) + cos(a)sin(b) = cos(a) [tan(a)cos(b) +sin(b)]

取a=arctan(2^-k), 即tan(a)=2^-k, cos(b) – tan(a)sin(b) 可通过移位和减法来实现。

如果角度z可以表示为z = s0 arctan(2^0) + s1 arctan(2^-1) + ... + sn arctan(2^-n), 其 中s0, s1, ..., sn取+1或-1(+1以理解为逆时针转角即加上一个角; -1则相) ,那么角度z的sin/cos计算可以通过一系列的移位和加减运算来实现。注意到cos(sk arctan(2^-k))=cos(arctan(2^-k)) 与转角方向无关。此外,z应取第一项限角度(收敛域),对於其他项限角度,可由其第一项限对应角度变换得到。

相类似地,sinh/cosh的计算利用以下公式:

cosh(a+b) = cosh(a)cosh(b) + sinh(a)sinh(b) = cosh(a) [cosh(b) + tanh(a)sinh(b)]

sinh(a+b) = sinh(a)cosh(b) + cosh(a)sinh(b) = cosh(a) [tanh(a)cosh(b) + sinh(b)]

a=arctanh(2^-k), tanh(a)=2^-k, 则cosh(b) + tanh(a)sinh(b) 可通移位和减法来实现。如果参数z可以表示为z = s1 arctanh(2^-1) + s2 arctanh(2^-2) + ... + sn arctanh(2^-n), 其 中s1, s2, ..., sn取+1或-1 ,那么z的sinh/cosh计算可以通过一系列的移位和加减运算来实现。

z应取[-ln2, ln2]范围内的值,否则应先预处理 z = z’– pln2, 求得cosh(z’)/sinh(z’)的值,则

cosh(z) = cosh(z’)cosh(pln2) + sinh(z’)sinh(pln2)

              = ½[cosh(z’) + sinh(z’)]2^p + ½[cosh(z’) – sinh(z’)]2^-p

sinh(z) = sinh(z’)cosh(pln2) + cosh(z’)sinh(pln2)

           = ½[cosh(z’) + sinh(z’)]2^p + ½[sinh(z’) – cosh(z’)]2^-p 。

sin/cos和sinh/cosh的计算是CORDIC算法的两个特 例,CORDIC算法可描述如下:

给定初 始值x(0), y(0), z(0),

x(k+1) = x(k) – ms(k)y(k)2^-q(m,k), y(k+1) = y(k) + s(k)x(k) 2^-q(m,k), z(k+1) = z(k) – s(k)d(k),

其中m表示模式,q(m,k) 为移位序列,s(k) 取+1或-1表示旋转方向,d(k) 为递进角度。

以cos(a)/sin(a)计算为例,m = 1, x(0) = 1, y(0) = 0, z(0) = a, s(k) = sign(z(k)),移位序列q(1,k): 0, 1, 2, ..., 递进角度为d(k)=arctan(2^-q(1,k)) 。

下面是实现的Matlab程序:

z = a;

x = 0.6072529350;                              % scaled cos(0)

y = 0;                                                  % sin(0)

for i = 1:K

     signZ = sign(z);                           % s(k) for rotation direction

     xNew = x - signZ*y*2^(-(i-1));

     y = signZ*x*2^(-(i-1)) + y;

    x = xNew;

     z = z - signZ*atan(2^(-(i-1)));    % atan(2^-(i-1)) is included in a look-up table

end

x的初始值为cos(arctan(1)), cos(arctan(2^-1)), ..., cos(arctan(2^-K) 的连积值,收敛为0.6072529350

cosh(a)/sinh(a)算为,m = -1, x(0) = 1, y(0) = 0, z(0) = a, s(k) = sign(z(k)),移位序q(-1,k): 1, 2, 3, 4, 4, 5, ... (3n+1重复两次以保证收敛, 4, 13, 40, ...), 递进角度为d(k)=arctanh(2^-q(-1,k)) 。

通过对初始值和旋转方向s(k) 的选择,模式m=0可以计算乘法和除法; 模式m=1可以计算sin/cos/arcsin/arccos/arctan; 模式m=-1可直接计算sinh/cosh/exp/arctanh/ln/sqrt, 间接计算arcsinh/arccosh,参见http://archives.math.utk.edu/ICTCM/VOL11/C027/paper.pdf

关于CORDIC的FPGA实现可参考 http://www.fpga-guru.com/files/crdcsrvy.pdf


TAG: CORDIC 算法

 

评分:0

我来说两句

显示全部

:loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)

Open Toolbar