CORDIC算法

Version3.10/30/07ForAcademicUseOnlyinAccordancewithLicence-to-Use,seereadme.pdfFPGAsforDSP4CORDIC算法DSPNotesMenuDSPediaHomeReturnReturnTHISSLIDEISBLANKAugust2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop简介4.1•目前的FPGA具有许多乘法器和加法器。然而各种各样的通信技术和矩阵算法则需要三角函数、平方根等的运算。如何在FPGA上执行这些运算?可以使用查找表,或是迭代法•本节介绍了CORDIC算法;这是一个“移位相加”算法,允许计算不同的三角函数,例如:•••包括除法和对数函数在内的其它函数。x2y2+θcosθtanθsin,,Notes:Developedby:Top关于CORDIC算法的细节问题，可参见下面的材料:[1]R.Andraka.AsurveyofCORDICalgorithmsforFPGAbasedcomputers.[2]TheCORDICAlgorithms.[3]CORDICTutorial.~geezer/embed/cordic.htm[4]M.J.Irwin.ComputerArithmetic.~cg575/lectures/cse575-cordic.pdfCORIDC技术并不是什么新鲜的东西。事实上它可以追溯到1957年由J.Volder发表的一篇文章。在上个世纪五十年代，在大型实际的计算机中的实行移位相加受到了当时技术上的限制，所以使用CORDIC变得非常必要。到了七十年代，HewlettPackard和其他公司出产了手持计算器,许多计算器使用一个内部CORDIC单元来计算所有的三角函数(了解这件事的人们一定还记得，那时求一个角度的正切值需要延迟大约1秒中)。二十世纪八十年代，随着高速度乘法器与带有大存储量的通用处理器的出现，CORDIC算法变得无关紧要了。然而在二十一世纪的今天，对于FPGA来说，CORDIC一定是在DSP应用中(诸如多输入多输出（MIMO）,波束形成以及其他自适应系统)计算三角函数的备选技术。August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop笛卡尔坐标平面旋转4.2•在xy坐标平面上将点(旋转角度到点的标准方法如下所示:•这被称为是平面旋转、向量旋转或者线性(矩阵)代数中的Givens旋转。x1y1,()θx2y2,()x2x1θy1θsin–cos=y2x1θy1θcos+sin=y2y1x1x2θNotes:Developedby:Top上面的方程组同样可写成矩阵向量形式:例如一个90o相移为:x2y2θcosθsin–θsinθcosx1y1=x2y201–10x1y1y1–x1==x1y1x1x2-y1August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop伪旋转4.3•通过提出因数，方程可写成下面的形式:•如果去除项，我们得到伪旋转方程式:即旋转的角度是正确的，但是x与y的值增加倍(由于1，所以模值变大。•注意我们并不能通过适当的数学方法去除项,然而随后我们发现去除项可以简化坐标平面旋转的计算操作。θcosx2x1θy1θsin–cosθx1y1θtan–()cos==y2x1θy1θcos+sinθy1x1θtan+()cos==θcosxˆ2θx1y1θtan–()cosx1y1θtan–==yˆ2θy1x1θtan+()cosy1x1θtan+==θcos1–θcos1–θcosθcosNotes:Developedby:Top在xy坐标平面中:因此经过伪旋转之后，向量R的模值将增加倍。向量旋转了正确的角度,但模值出现错误。θ(x2,y2)(x1,y1)xˆ1xˆ2,()RotationRˆRx12y12+x22y22+==Pseudo-RotationRRˆRθcos-------------x12y12+θcos----------------------==1θcos⁄August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTopCORDIC方法4.4•CORDIC方法的核心是(伪)旋转角度，其中tan=2-i。故方程为:•下面的表格指出用于CORDIC算法中每个迭代(i)的旋转角度(精确到9位小数):i(Degrees)045.01126.555051177...0.5214.036243467...0.2537.125016348...0.12543.576334374...0.0625θθixˆ2x1y1θtan–x1y12i––==yˆ2y1x1θtan+y1x12i–+==θiθitan2i–=Notes:Developedby:Top在这里，我们把变换改成了迭代算法。我们将各种可能的旋转角度加以限制，使得对任意角度的旋转能够通过一系列连续小角度的旋转迭代i来完成。旋转角度遵循法则:，遵循这样的法则，乘以正切项变成了移位操作。前几次迭代的形式为:第1次迭代:旋转45o;第2次迭代:旋转26.6o,第3次迭代:旋转14o等。很显然，每次旋转的方向都影响到昀终要旋转的累积角度。在的范围内的任意角度都可以旋转。满足法则的所有角度的总和为99.7。对于该范围之外的角度，可使用三角恒等式转化成该范围内的角度。当然，角分辨率的数据位数与昀终的精度有关。。因此，在13次旋转以后，为了标定伪旋转的幅度，要求乘以一个系数1.64676024187。角分辨率的数据位数对昀终的旋转精度非常关键。θθi()tan2i–=99.7θ99.7≤≤–θitan2i–=itanθAngle,θcosθ1145.00000000000.70710678120.526.56505117710.89442719130.2514.03624346790.970142540.1257.12501634890.99227787750.06253.57633437500.99805257860.031251.78991060820.99951207670.0156250.89517371020.99987795280.00781250.44761417090.99996948490.003906250.22381050040.999992371100.0019531250.11190567710.999998093110.0009765630.05595289190.999999523120.0004882810.02797645260.999999881130.0002441410.01398822710.99999997cos45xcos26.5xcos14.03xcos7.125...xcos0.0139=0.60725294110607252941⁄1.6467602=August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop角度累加器4.5•·前面所示的伪旋转现在可以表示为（对每次迭代）:•在这里我们引入第三个方程，被称为角度累加器，用来在每次迭代过程中追踪累加的旋转角度:•符号di是一个判决算子，用于确定旋转的方向。xi1+()xi()di2i–yi()()–=yi1+()yi()di2i–xi()()+=zi1+()zi()diθi()(AngleAccumulator)–=wheredi=+/-1Notes:Developedby:Top在这里，我们把每次迭代的方程表示为:其中判决算子di决定旋转的方向是顺时针还是逆时针。di的值取决于下面将要讨论的操作模式。这里我们引入了名为角度累加器的第三个等式，用于追踪每次迭代中旋转的角度的叠加:上述三个方程式为圆周坐标系中用于角度旋转的CORDIC算法的表达式。在本章的后续部分中我们还将看到CORDIC算法被用于其它的坐标系，通过使用这些坐标系可以执行更大范围的函数计算。xi1+()xi()di2i–yi()()–=yi1+()yi()di2i–xi()()+=zi1+()zi()diθi()–=August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop移位-加法算法4.6•因此,原始的算法现在已经被减化为使用向量的伪旋转来表示的迭代移位-相加算法:•因此每个迭代需要:•2次移位•1次查找表(值)•3次加法xi1+()xi()di2i–yi()()–()=yi1+()yi()di2i–xi()()+()=zi1+()zi()diθi()–=θi()Notes:Developedby:Top前面提到的去除cos项的原因是显而易见的。当将该项去除时，转换公式已经被简化为伪旋转的迭代移位相加计算。CORDIC硬件:θShiftShiftLookupTable+-+-+-xRegisteryRegisterzRegisterIterationCounterInitialxInitialyInitialzdiControlMuxControlAugust2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop伸缩因子4.7•伸缩因子是伪旋转的副产物。•当简化算法以允许伪旋转时，cos项被忽略。•这样，输出x(n),y(n)被伸缩Kn倍，其中:•然而如果迭代次数可知，则我们可以预先计算伸缩因子Kn。•同样,1/Kn也可被预先计算以得到x(n)和y(n)的真值。θKn1θi()cos()⁄n∏122i–()+()n∏==Notes:Developedby:Top为了简化Givens旋转，我们去除了cos项以执行伪旋转。然而，该简化引发了负面效应。输出值x(n)和y(n)被乘以一个因子Kn，该因子被称为伸缩因子，这里:然而，如果我们已知了将被执行的迭代次数，我们便可以预先计算出1/Kn的值，并通过将1/Kn与x(n)和y(n)相乘来校正x(n)和y(n)的昀终值。θKn1θi()cos()⁄n∏1tan2θi()+⎝⎠⎛⎞n∏122i–()+⎝⎠⎛⎞n∏===Kn1.6476asn∞→→1Kn⁄0.6073asn∞→→nnumberofiterations=August2007,Version3.8/21/07ForAcademicUseOnly.AllRightsReservedTop旋转模式4.8•CORDIC方法有两种操作模式;•工作模式决定了控制算子di的条件;•在旋转模式中选择:di=sign(z(i))z(i)0;•n次迭代后我们得到:•通过设置x(0)=1/Kn和y(0)=0可以计算cosz(0)和sinz(0)。⇒→xn()Knx0()z0()y0()z0()sin–cos()=yn()Kny0()z0()x0()z0()sin+cos()=zn()0=Notes:Developedby:Top旋转模式中，判决算子di满足下面条件:因此，我们输入x(0)和z(0)(y(0)=0)，然后通过迭代使z(0)取值趋近于0。例如:当z(0)=30o时，计算sinz(0),cosz(0)disignzi()()=idiθ(i)z(i)y(i)x(i)0+145+3000.60731-126.6-150.60730.60732+11