A survey of CORDIC algorithms for FPGA based computersRay AndrakaAndraka Consulting Group, Inc16 Arcadia DriveNorth Kingstown, RI 02852401/884-7930 FAX 401/884-7950email:[email protected]. ABSTRACTThe current trend back toward hardwareintensive signal processing has uncovered arelative lack of understanding of hardwaresignal processing architectures. Manyhardware efficient algorithms exist, but theseare generally not well known due to thedominance of software systems over the pastquarter century. Among these algorithms is aset of shift-add algorithms collectively knownas CORDIC for computing a wide range offunctions including certain trigonometric,hyperbolic, linear and logarithmic functions.While there are numerous articles coveringvarious aspects of CORDIC algorithms, veryfew survey more than one or two, and evenfewer concentrate on implementation inFPGAs. This paper attempts to surveycommonly used functions that may beaccomplished using a CORDIC architecture,explain how the algorithms work, and exploreimplementation specific to FPGAs.1.1 KeywordsCORDIC, sine, cosine, vector magnitude, polar conversion2. INTRODUCTIONThe digital signal processing landscape has long beendominated by microprocessors with enhancements such assingle cycle multiply-accumulate instructions and specialaddressing modes. While these processors are low costand offer extreme flexiblility, they are often not fast enoughfor truly demanding DSP tasks. The advent ofreconfigurable logic computers permits the higher speeds ofdedicated hardware solutions at costs that are competitivewith the traditional software approach. Unfortunately,algorithms optimized for these microprocessor basedsystems do not usually map well into hardware. Whilehardware-efficient solutions often exist, the dominance ofthe software systems has kept those solutions out of thespotlight. Among these hardware-efficient algorithms is aclass of iterative solutions for trigonometric and othertranscendental functions that use only shifts and adds toperform. The trigonometric functions are based on vectorrotations, while other functions such as square root areimplemented using an incremental expression of the desiredfunction. The trigonometric algorithm is called CORDIC,an acronym for COordinate Rotation DIgital Computer.The incremental functions are performed with a very simpleextension to the hardware architecture, and while notCORDIC in the strict sense, are often included because ofthe close similarity. The CORDIC algorithms generallyproduce one additional bit of accuracy for each iteration.The trigonometric CORDIC algorithms were originallydeveloped as a digital solution for real-time navigationproblems. The original work is credited to Jack Volder[4,9]. Extensions to the CORDIC theory based on work byJohn Walther[1] and others provide solutions to a broaderclass of functions. The CORDIC algorithm has found itsway into diverse applications including the 8087 mathcoprocessor[7], the HP-35 calculator, radar signalprocessors[3] and robotics. CORDIC rotation has also beenproposed for computing Discrete Fourier[4], DiscreteCosine[4], Discrete Hartley[10] and Chirp-Z [9] transforms,filtering[4], Singular Value Decomposition[14], and solvinglinear systems[1].This paper attempts to survey the existing CORDIC andCORDIC-like algorithms with an eye towardimplementation in Field Programmable Gate Arrays(FPGAs). First a brief description of the theory behind thealgorithm and the derivation of several functions ispresented. Then the theory is extended to the so-calledunified CORDIC algorithms, after which implementation ofFPGA CORDIC processors is discussed.Permission to make digital or hard copies of part or all of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and thatcopies bear this notice and the full citation on the first page. Copyrightsfor components of this work owned by others than ACM must behonored. Abstracting with credit is permitted. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires priorspecific permission and/or a fee. Request permissions from PublicationsDept, ACM Inc., fax +1 (212) 869-0481, or [email protected] 98 Monterey CA USACopyright 1998 ACM 0-89791-978-5/98/01..$5.003. CORDIC THEORY: AN ALGORITHMFOR VECTOR ROTATIONAll of the trigonometric functions can be computed orderived from functions using vector rotations, as will bediscussed in the following sections. Vector rotation canalso be used for polar to rectangular and rectangular topolar conversions, for vector magnitude, and as a buildingblock in certain transforms such as the DFT and DCT. TheCORDIC algorithm provides an iterative method ofperforming vector rotations by arbitrary angles using onlyshifts and adds. The algorithm, credited to Volder[4], isderived from the general (Givens) rotation transform:xx yyy x’cos sin’ cos sin=−=+φφφφwhich rotates a vector in a Cartesian plane by the angle φ.These can be rearranged so that:[][]xxyyyx’cos tan’cos tan=⋅−=⋅+φφφφSo far, nothing is simplified. However, if the rotationangles are restricted so that tan(φ)=±2-i, the multiplicationby the tangent term is reduced to simple shift operation.Arbitrary angles of rotation are obtainable by performing aseries of successively smaller elementary rotations. If thedecision at each iteration, i, is which direction to rotaterather than whether or not to rotate, then the cos(δi) termbecomes a constant (because cos(δi) = cos(-δi)). Theiterative rotation can now be expressed as:[][]xKxydyKyxdiiiiiiiiiiii+−+−=−⋅⋅=+⋅⋅1122 where:()Kdiiii==+=±−− −cos tan1221121Removing the scale constant from the iterative equationsyields a shift-add algorithm for vector rotation. Theproduct of the Ki’s can be applied elsewhere in the systemor treated as part of a system processing gain. That productapproaches 0.6073 as the number of iterations goes toinfinity. Therefore, the rotation algorithm has a gain, An,of approximately 1.647. The exact gain depends on thenumber of iterations, and obeys the relationAnin=+−∏122The angle of a composite rotation is uniquely defined by thesequence of the directions of the elementary rotations. Thatsequence can be represented by a decision vector. The setof all possible decision vectors is an angular measurementsystem based on binary