数字信号-外文翻译-外文文献-英文文献-基于FPGA的CORDIC算法综述.doc

A survey of CORDIC algorithms for FPGA based computers1. ABSTRACTThe current trend back toward hardware intensive signal processing has uncovered a relative lack of understanding of hardware signal processing architectures. Many hardware efficient algorithms exist, but these are generally not well known due to the dominance of software systems over the past quarter century. Among these algorithms is a set of shift-add algorithms collectively known as CORDIC for computing a wide range of functions including certain trigonometric, hyperbolic, linear and logarithmic functions. While there are numerous articles covering various aspects of CORDIC algorithms, very few survey more than one or two, and even fewer concentrate on implementation in FPGAs. This paper attempts to survey commonly used functions that may be accomplished using a CORDIC architecture, explain how the algorithms work, and explore implementation specific to FPGAs.2. INTRODUCTIONThe digital signal processing landscape has long been dominated by microprocessors with enhancements such as single cycle multiply-accumulate instructions and special addressing modes. While these processors are low cost and offer extreme flexiblility, they are often not fast enough for truly demanding DSP tasks. The advent of reconfigurable logic computers permits the higher speeds of dedicated hardware solutions at costs that are competitive with the traditional software approach. Unfortunately, algorithms optimized for these microprocessor based systems do not usually map well into hardware. While hardware efficient solutions often exist, the dominance of the software systems has kept those solutions out of the spotlight. Among these hardware-efficient algorithms is a class of iterative solutions for trigonometric and other transcendental functions that use only shifts and adds to perform. The trigonometric functions are based on vector rotations, other functions such as square root are implemented using an incremental expression of the desired function. The trigonometric algorithm is called CORDIC, an acronym for coordinate rotation digital computer. The incremental functions are performed with a very simple extension to the hardware architecture, and while not CORDIC in the strict sense, are often included because of the close similarity. The CORDIC algorithms generally produce one additional bit of accuracy for each iteration.3. CORDIC THEORY: AN ALGORITHM FOR VECTOR ROTATIONAll of the trigonometric functions can be computed or derived from functions using vector rotations, as will be discussed in the following sections. Vector rotation can also be used for polar to rectangular and rectangular to polar conversions, for vector magnitude, and as a building block in certain transforms such as the DFT and DCT. The CORDIC algorithm provides an iterative method ofperforming vector rotations by arbitrary angles using only shifts and adds. The algorithm is derived from the general (Givens) rotation transform:which rotates a vector in a Cartesian plane by the angle These can be rearranged so that:So far, nothing is simplified. However, if the rotation angles are restricted so that , the multiplication by the tangent term is reduced to simple shift operation. Arbitrary angles of rotation are obtainable by performing a series of successively smaller elementary rotations. If the decision at each iteration, i, is which direction to rotate rather than whether or not to rotate, then the term becomes a constant.The iterative rotation can now be expressed as:Where:Removing the scale constant from the iterative equations yields a shift-add algorithm for vector rotation. The product of the Ki's can be applied elsewhere in the system or treated as part of a system processing gain. That product approaches 0.6073 as the number of iterations goes to infinity. Therefore, the rotation algorithm has a gain, An , of approximately 1.647. The exact gain depends on the number of iterations, and obeys the relation.The angle of a composite rotation is uniquely defined by the sequence of the directions of the elementary rotations. That sequence can be represented by a decision vector. The set of all possible decision vectors is an angular measurement system based on binary arctangents. Conversions between this angular system and any other can be accomplished using a look-up. A better conversion method uses an additional adder-subtractor that accumulates the elementary rotation angles at each iteration. The elementary angles can be expressed in any convenient angular unit. Those angular values are supplied by a small lookup table (one entry per iteration) or are hardwired, depending on the implementation. The angle accumulator adds a third difference equation to the CORDIC algorithm:Obviously, in cases where the angle is useful in the arctangent base, this extra element is not needed.The CORDIC rotator is normally operated in one of two modes. The first, called rotation by Volder4, rotates the input vector by a specified angle (given as an argument). The second mode, called vectoring, rotates the input vector to the xaxis while recording the angle required to make that rotation.In rotation mode, the angle accumulator is initialized with the desired rotation angle. The rotation decision at each iteration is made to diminish the magnitude of the residual angle in the angle accumulator. The decision at each iteration is therefore based on the sign of the residual angle after each step. Naturally, if the input angle is already expressed in the binary arctangent base, the angle accumulator may be eliminated. For rotation mode, the CORDIC equations are:Wheredi=-1 if zi<0,+1 otherwiseWhich provides the following result:In the vectoring mode, the CORDIC rotator rotates the input vector through whatever angle is necessary to align the result vector with the x axis. The result of the vectoring operation is a rotation angle and the scaled magnitude of the original vector (the x component of the result). The vectoring function works by seeking to minimize the y component of the residual vector at each rotation. The sign of the residual y component is used to determine which direction to rotate next. If the angle accumulator is initialized with zero, it will contain the traversed angle at the end of the iterations. In vectoring mode, the CORDIC equations are:Wheredi=+1 if yi<0,-1 otherwiseThen:The CORDIC rotation and vectoring algorithms as stated are limited to rotation angles between -/2 and /2. This limitation is due to the use of 20 for the tangent in the first iteration. For composite rotation angles larger than /2, an additional rotation is required. Volder4 describes an initial rotation ±/2. This gives the correction iteration:Wheredi=+1 if yi<0,-1 otherwiseThere is no growth for this initial rotation. Alternatively, an initial rotation of either or 0 can be made, avoiding the reassignment of the x and y components to the rotator elements. Again, there is no growth due to the initial rotation:z'=z if d=1,or z- if d=-1d=-1 if x<0,+1 otherwise.Both reduction forms assume a modulo 2 representation of the input angle. The style of first reduction is more consistent with the succeeding rotations, while the second reduction may be more convenient when wiring is restricted, as is often the case with FPGAs.The CORDIC rotator described is usable to compute several trigonometric functions directly and others indirectly. Judicious choice of initial values and modes permits direct computation of sine, cosine, arctangent, vector magnitude and transformations between polar and Cartesian coordinates.4. IMPLEMENTATION IN AN FPGAThere are a number of ways to implement a CORDIC processor. The ideal architecture depends on the speed versus area tradeoffs in the intended application. First we will examine an iterative architecture that is a direct translation from the CORDIC equations. From there, we will look at a minimum hardware solution and a maximum performance solution.5. CONCLUSIONSThe CORDIC algorithms presented in this paper are well known in the research and super-computing circles. It is, however, my experience that the majority of today's hardware DSP designs are being done by engineers with little or no background in hardware efficient DSP algorithms. The new DSP designers must become familiar with these algorithms and the techniques for implementing them in FPGAs in order to remain competitive. The CORDIC algorithm is a powerful tool in the DSP toolbox. This paper shows that tool is available for use in FPGA based computing machines, which are the likely basis for the next generation DSP systems.基于FPGA的CORDIC算法综述1.摘要目前趋向于硬件的信号处理却缺乏对硬件信号处理结构的理解。虽然有许多硬件的高效算法存在，但这些一般没被很好的认识到，这是由于在过去四分之一世纪里软件系统位于统治地位。在这些算法中，是由一系列移位加法算集成的被称为ORDIC算法，它用来计算一系列函数如三角函数，双曲函数，线性函数和对数函数。虽然有许多文章涉及的CORDIC算法的各个方面，但是只有很少的能在FPGAs上实现。本文尝试用CORDIC结构完成一些普通的函数来解释这些算法是如何实现的，并探讨如何用FPGA实现。 2.简介数字信号处理的前景早已被用来做诸如单周期乘法积累器和特殊寻址方式的增强微处理器所主导。虽然这些处理器低消耗以及能提供灵活的使用，但他们的速度往往不能满足实际中DSP任务的要求。可重构逻辑计算机的优点在于能提供更高速的专用硬件解决方案，并与传统的软件方法的消耗差不多。不幸的是，这些基于微处理器的系统通常不能很好地把算法优化映射到硬件中去。虽然硬件能高效的解决问题，但由于软件系统一直处于主导地位是这些解决方案得不到关注。在这些硬件高效的算法中是通过一种迭代的方法解决三角函数和其他抽象函数的，这样就只使用了移位器和加法器来实现。三角函数是基于坐标旋转，而其他功能函数，例如平方方根的实现是通过一种所需函数的增量表述。三角函数算法称为CORDIC算法，它是坐标旋转数字计算机的缩写。增加的函数是通过简单的扩展硬件结构来实现的，而不是严格意义上的CORDIC算法，这是因为它们极为相似。在每次迭代后CORDIC算法通常会产生一个附加位。 3.CORDIC算法理论：矢量旋转算法在三角函数都可以从函数计算所得或使用矢量旋转，这将在下面的章节中讨论。矢量旋转也可用于极坐标和直角坐标的相互转换，矢量大小以及某些诸如的DFT和DCT的变换。CORDIC算法提供了一种实现向量旋转的迭代法，它通过用移位器和加法器来实现任意角度。该算法是从一般的（吉文斯）旋转变换得到的：旋转向量在直角坐标系中为角度重新排列为：到目前为止，还没有得到简化。但是，如果旋转角度受到限制，那么由正切函数的乘法简化为简单移位操作。通过一系列连续的小角度旋转便可得到任意角度的旋转。如果在每次迭代后取值，i是决定旋转的方向，而不是是否旋转，这时变成连续的了。现在迭代旋转可以表述为：其中：去掉从迭代方程不断产生的一个移位加法算就得到旋转向量。Ki的结果可以用到系统中的任何地方或作为系统处理增益的一部分。随着无限次迭代之后这个结果约为0.6073。因此，旋转算法的增益An约为1.647。增益的精度取决于迭代的次数，以及下面的关系。复合旋转的角度是被基本旋转方向序列唯一定义的。该序列被向量所代表。所有可能的向量是一个基于二进制反正切的角测量系统。这个角度系统和任何其它系统之间转换都可以通过查找来完成。一个更好的转换方法是用一个额外的加法器和减法器，它们在每次迭代中积累了基本旋转角度。基本角度可以用角度单元方便的表示出来。这些角的值是通过查表或者硬件来实现的。角度累加器加上三分之一差分方程得到CORDIC算法：显然，在这种情况下，角度对反正切是有用的，这里不需要额外的元素。CORDIC算法通常用到两种操作模式之中的一种。第一种模式，称为旋转模式，通过一个特殊角度（作为参数提供）旋转输入的向量。第二种模式，称为矢量模式，旋转输入向量到x轴，同时记录下作出的旋转角度。在旋转模式下，角度累加器被初始化为所需要的旋转角度。角度是由每次迭代决定的，用这种方法来减少角度累加器中对冗余角度的放大。它是由每次迭代所决定的，因此是基于冗余角的每一阶段。当然，如果输入角度已经表示为二进制的反正切值，角度累加器就可以被去掉了。对于旋转模式，CORDIC算法的方程为：其中如果 zi<0，di=-1 否则di=+1于是得到如下结果：在矢量模式下，CORDIC算法旋转输入向量通过的任何角度都需要使输出向量和x轴对齐。该向量运算的结果是一个旋转角度和初始向量的放大。向量运算是通过找到在每次旋转后y分量的冗余向量的最小值来运算的。冗余的Y分量是用来确定下次向哪个方向旋转的。如果角度累加器被初始化为零，它在迭代完后包含中间角。在矢量模式下，CORDIC算法的方程是：其中如果 yi<0，di=+1 否则di=-1于是：CORDIC旋转和矢量算法都被限制在旋转角度为-/ 2到/ 2之间。这个限制是由于在第一次迭代时用了20的正切值。对于大于/ 2复合旋转角度，就需要附加一个旋转角度。Volder4描述了一种初始旋转角度为±/ 2的情况。这样就给出了正确的迭代方程：其中如果 yi<0，di=+1 否则di=-1这里没初始旋转值的增加。另外，或0的初始旋转值都是可以的，这样避免把x和y分量调换为旋转因子。接着，这里没有增长是由于初始旋转：如果 d=1,z'=z 或者如果d=-1,z'=z-如果 x<0, d=-1 否则 d=+1这两种缩减形式都可以仿真一个2的输入角度。第一种更蒹容旋转角的连续性，而第二种是当接线受到限制时更为方便，它往往用于FPGA中。CORDIC算法适用于直接计算很多三角函数和间接计算其他函数。恰当的选择初始值和模式可以直接计算正弦，余弦，反正切，矢量幅度以及极坐标和直角坐标之间的转换。4.FPGA的实现现在有许多方法都可以实现CORDIC算法。理想的结构通过速度与在预定的应用领域之间的权衡。首先，我们测试一种迭代结构，它直接通过CORDIC算法方程得到的。然后，我们用最简单和最复杂的硬件来实现要求。5.结论本文提出的CORDIC算法现在已经被广泛的用于研究和无限循环计算中。然而，现在绝大多数的硬件DSP设计很少被工程师用到或者被没有学过硬件的工程师有效地实现DSP算法。新的DSP设计者必须熟悉在FPGA上实现他们的这些算法和技术以便保持竞争力。CORDIC算法是在DSP家族中的强大工具。本文说明了这个工具在基于计算机的FPGA上是可以实现的，它很可能是下一代DSP系统的前身。