1、A survey of CORDIC algorithms for FPGA based computers 1. ABSTRACT The 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
2、 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 n
3、umerous 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, an
4、d explore implementation specific to FPGAs. 2. INTRODUCTION The 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 f
5、lexiblility, 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 microp
6、rocessor 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 t
7、ranscendental 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 coord
8、inate 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
9、 each iteration. 3. CORDIC THEORY: AN ALGORITHM FOR VECTOR ROTATION All 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
10、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 of performing vector rotations by arbitrary angles using only shifts and adds. The algorithm is derived from the general (Givens) rotation trans
11、form: cos sinx x y cos siny y x which rotates a vector in a Cartesian plane by the angle These can be rearranged so that: c o s ta n x x y s ta n y y x So far, nothing is simplified. However, if the rotation angles are restricted so that tan 2 i , the multiplication by the tangent term is reduced to
12、 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 cos( )i term becomes a constant.The iterative ro
13、tation can now be expressed as: 1 2 ii i i i ix k x y d ii i i i iy y x Where: 21/ 1 2 iik 1id Removing the scale constant from the iterative equations yields a shift-add algorithm for vector rotation. The product of the Kis can be applied elsewhere in the system or treated as part of a system proce
14、ssing 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. 212in nA The angle of a composite rotation is uniquely defin
15、ed 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 us
16、ing 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)
17、or are hardwired, depending on the implementation. The angle accumulator adds a third difference equation to the CORDIC algorithm: 11 ta n ( 2 )ii i iz z d Obviously, in cases where the angle is useful in the arctangent base, this extra element is not needed. The CORDIC rotator is normally operated
18、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
19、 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 angl
20、e is already expressed in the binary arctangent base, the angle accumulator may be eliminated. For rotation mode, the CORDIC equations are: 1 2 ii i i ix x y d 2 ii i i iy y x d 11 ta n ( 2 )ii i iz z d Where di=-1 if zi0,+1 otherwise Which provides the following result: 0 0 0 0 c o s s i n nnx A x z y z
