|
坐标旋转数字计算机CORDIC<br />[编辑本段]<br />坐标旋转数字计算机CORDIC(COordinate Rotation DIgital Computer)算法，通过移位和加减运算，能递归计算常用函数值，如Sin， Cos，Sinh，Cosh等函数，由J. Volder于1959年提出 ，首先用于导航系统，使得矢量的旋转和定向运算不需要做查三角函数表、乘法、开方及反三角函数等复杂运算。J. Walther在1974年用它研究了一种能计算出多种超越函数的统一算法 。<br /><br /><br />CORDIC原理<br />[编辑本段]<br />如图所示，初始向量（X(0)，Y(0)）旋转θ角度之后得到向量（X(1)，Y(1)），此向量有如下关系：<br />X(1)=X(0)cos(θ)-Y(0)sin(θ)=cos(θ)(X(0)-Y(0)tan(θ))<br />Y(1)=Y(0)cos(θ)-X(0)sin(θ)=cos(θ)(Y(0)-X(0)tan(θ))<br />假设初始向量经过N次旋转之后得到新向量，且每次旋转角度δ都是正切值为2的倍数，则第i次旋转角度为δ－arctan(2^(-i))，即cosδ＝（1/（1+2^(-2i)））^0.5。<br />容易得到角度θ≈∑S(i)●δ(i)，其中S(i)=1或－1，表示旋转角度的方向，<br />第i步旋转可以表示为：<br />X(i+1)=(（1/（1+2^(-2i)））^0.5)●(X(i)-S(i)Y(i)2^(-i))<br />Y(i+1)=(（1/（1+2^(-2i)））^0.5)●(Y(i)-S(i)X(i)2^(-i))<br />其中（1/（1+2^(-2i)））^0.5)称为校模因子，当旋转次数一定时，趋于一个常数，Π（1/（1+2^(-2i)））^0.5)≈0.6073<br />这样，算法每一步就可以简化为：<br />X(i+1)=(X(i)-S(i)Y(i)2^(-i))<br />Y(i+1)=(Y(i)-S(i)X(i)2^(-i))<br />从而可以看出，对于移动的角度θ，现在只需要硬件加减法器和移位器就可以算出结果。引入Z，表示i次旋转后与目标角度之差，则：<br />Z(i+1)=Z(i)-S(i)arctan(2^(-i))<br />经过n次旋转之后，Z→0，即与目标角重合，即：<br />X(n)=X(1)=X(0)cos(θ)-Y(0)sin(θ)<br />Y(n)=Y(1)=Y(0)cos(θ)-X(0)sin(θ)<br /><br /><br />三角函数的计算<br />[编辑本段]<br />以sin/cos计算为例，可利用正/余弦的和角公式递归进行：<br />cos(a+b) = cos(a)cos(b) – sin(a)sin(b) = cos(a) [cos(b) – tan(a)sin(b)] <br />sin(a+b) = sin(a)cos(b) + cos(a)sin(b) = cos(a) [tan(a)cos(b) +sin(b)] <br />取a=arctan(2^-k), 即tan(a)=2^-k, 则cos(b) – tan(a)sin(b) 可通过移位和减法来实现。<br />如果角度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应取第一项限角度(收敛域)，对於其他项限角度，可由其第一项限对应角度变换得到。<br /><br />相类似地，sinh/cosh的计算利用以下公式：<br />cosh(a+b) = cosh(a)cosh(b) + sinh(a)sinh(b) = cosh(a) [cosh(b) + tanh(a)sinh(b)]<br />sinh(a+b) = sinh(a)cosh(b) + cosh(a)sinh(b) = cosh(a) [tanh(a)cosh(b) + sinh(b)] <br />取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计算可以通过一系列的移位和加减运算来实现。<br />z应取[-ln2, ln2]范围内的值，否则应先预处理 z = z’– pln2, 求得cosh(z’)/sinh(z’)的值，则 <br />cosh(z) = cosh(z’)cosh(pln2) + sinh(z’)sinh(pln2) = ½[cosh(z’) + sinh(z’)]2^p + ½[cosh(z’) – sinh(z’)]2^-p <br />sinh(z) = sinh(z’)cosh(pln2) + cosh(z’)sinh(pln2) = ½[cosh(z’) + sinh(z’)]2^p + ½[sinh(z’) – cosh(z’)]2^-p 。<br /><br />sin/cos和sinh/cosh的计算是CORDIC算法的两个特例，CORDIC算法可描述如下:<br />给定初始值x(0), y(0), z(0), <br />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), <br />其中m表示模式，q(m,k) 为移位序列，s(k) 取+1或-1表示旋转方向，d(k) 为递进角度。<br /><br /><br />CORDIC的MATLAB运算<br />[编辑本段]<br />以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)) 。<br />下面是实现的Matlab程序: <br />z = a; <br />x = 0.6072529350; % scaled cos(0) <br />y = 0; % sin(0) <br />for i = 1:K<br />signZ = sign(z); % s(k) for rotation direction <br />xNew = x - signZ*y*2^(-(i-1)); <br />y = signZ*x*2^(-(i-1)) + y; <br /><br />x = xNew; <br />z = z - signZ*atan(2^(-(i-1))); % atan(2^-(i-1)) is included in a look-up table <br />end<br />x的初始值为cos(arctan(1)), cos(arctan(2^-1)), ..., cos(arctan(2^-K) 的连积值，收敛为0.6072529350。<br /><br />以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)) 。<br /><br />通过对初始值和旋转方向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。<br /><br /><br />CORDIC的FPGA实现<br />[编辑本段]<br />参考 http://www.fpga-guru.com/files/crdcsrvy.pdf<br /><br /><br /><a href="http://baike.baidu.com/view/1800964.htm" target=_blank>http://baike.baidu.com/view/1800964.htm</a> |
|
楼主
