數(shù)字信號 外文翻譯 -- 基于fpga的cordic算法綜述

1、<p>　　A survey of CORDIC algorithms for FPGA based computers</p><p>　　1. ABSTRACT</p><p>　　The current trend back toward hardware intensive signal processing has uncovered a relative lack o

2、f 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. Amon

3、g 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 loga</p><p>　　2. INTRODUCTION

4、</p><p>　　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

5、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

6、 at costs that are competitive with the traditional software approach. Unfortunatel</p><p>　　3. CORDIC THEORY: AN ALGORITHM FOR VECTOR ROTATION</p><p>　　All of the trigonometric functions can be

7、 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 magni

8、tude, and as a building block in certain transforms such as the DFT and DCT. The CORDIC algorithm provides an iterative method of</p><p>　　performing vector rotations by arbitrary angles using only shifts an

9、d adds. The algorithm is derived from the general (Givens) rotation transform:</p><p>　　which rotates a vector in a Cartesian plane by the angle φ</p><p>　　These can be rearranged so that:</p

10、><p>　　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 ob

11、tainable 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.Th

12、e iterative rotation can now be expressed as:</p><p><b>　　Where:</b></p><p>　　Removing the scale constant from the iterative equations yields a shift-add algorithm for vector rotatio

13、n. 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

14、algorithm has a gain, An , of approximately 1.647. The exact gain depends on the number of iterations, and obeys the relation.</p><p>　　The angle of a composite rotation is uniquely defined by the sequence o

15、f 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 betw

16、een 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</p>

17、<p>　　Obviously, in cases where the angle is useful in the arctangent base, this extra element is not needed.</p><p>　　The CORDIC rotator is normally operated in one of two modes. The first, called ro

18、tation by Volder\[4], 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 rotatio

19、n.</p><p>　　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 ang

20、le 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 accumulat

21、or may be eliminated. For rotation mode, the CORDIC equations are:</p><p><b>　　Where</b></p><p>　　di=-1 if zi<0,+1 otherwise</p><p>　　Which provides the following res

22、ult:</p><p>　　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 ro

23、tation 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

24、 residual y component is used to determine which direction to rotate next. If the angl</p><p><b>　　Where</b></p><p>　　di=+1 if yi<0,-1 otherwise</p><p><b>　　Th

25、en:</b></p><p>　　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 iterati

26、on. For composite rotation angles larger than π/2, an additional rotation is required. Volder\[4] describes an initial rotation ±π/2. This gives the correction iteration:</p><p><b>　　Where</b

27、></p><p>　　di=+1 if yi<0,-1 otherwise</p><p>　　There is no growth for this initial rotation. Alternatively, an initial rotation of either π or 0 can be made, avoiding the reassignment of

28、 the x and y components to the rotator elements. Again, there is no growth due to the initial rotation:</p><p>　　z'=z if d=1,or z-π if d=-1</p><p>　　d=-1 if x<0,+1 otherwise.</p>

29、<p>　　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

30、 wiring is restricted, as is often the case with FPGAs.</p><p>　　The CORDIC rotator described is usable to compute several trigonometric functions directly and others indirectly. Judicious choice of initial

31、 values and modes permits direct computation of sine, cosine, arctangent, vector magnitude and transformations between polar and Cartesian coordinates.</p><p>　　4. IMPLEMENTATION IN AN FPGA</p><p&

32、gt;　　There 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

33、direct translation from the CORDIC equations. From there, we will look at a minimum hardware solution and a maximum performance solution.</p><p>　　5. CONCLUSIONS</p><p>　　The CORDIC algorithms

34、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 backgr

35、ound 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 po

36、werful tool in the DSP toolbox. This paper</p><p>　　基于FPGA的CORDIC算法綜述</p><p><b>　　1.摘要</b></p><p>　　目前趨向于硬件的信號處理卻缺乏對硬件信號處理結(jié)構(gòu)的理解。雖然有許多硬件的高效算法存在，但這些一般沒被很好的認識到，這是由于在過去四分之一世

37、紀里軟件系統(tǒng)位于統(tǒng)治地位。在這些算法中，是由一系列移位加法算集成的被稱為ORDIC算法，它用來計算一系列函數(shù)如三角函數(shù)，雙曲函數(shù)，線性函數(shù)和對數(shù)函數(shù)。雖然有許多文章涉及的CORDIC算法的各個方面，但是只有很少的能在FPGAs上實現(xiàn)。本文嘗試用CORDIC結(jié)構(gòu)完成一些普通的函數(shù)來解釋這些算法是如何實現(xiàn)的，并探討如何用FPGA實現(xiàn)。</p><p><b>　　2.簡介</b></p&g

38、t;<p>　　數(shù)字信號處理的前景早已被用來做諸如單周期乘法積累器和特殊尋址方式的增強微處理器所主導。雖然這些處理器低消耗以及能提供靈活的使用，但他們的速度往往不能滿足實際中DSP任務的要求?？芍貥?gòu)邏輯計算機的優(yōu)點在于能提供更高速的專用硬件解決方案，并與傳統(tǒng)的軟件方法的消耗差不多。不幸的是，這些基于微處理器的系統(tǒng)通常不能很好地把算法優(yōu)化映射到硬件中去。雖然硬件能高效的解決問題，但由于軟件系統(tǒng)一直處于主導地位是這些解決方案得

39、不到關(guān)注。在這些硬件高效的算法中是通過一種迭代的方法解決三角函數(shù)和其他抽象函數(shù)的，這樣就只使用了移位器和加法器來實現(xiàn)。三角函數(shù)是基于坐標旋轉(zhuǎn)，而其他功能函數(shù)，例如平方方根的實現(xiàn)是通過一種所需函數(shù)的增量表述。三角函數(shù)算法稱為CORDIC算法，它是坐標旋轉(zhuǎn)數(shù)字計算機的縮寫。增加的函數(shù)是通過簡單的擴展硬件結(jié)構(gòu)來實現(xiàn)的，而不是嚴格意義上的CORDIC算法，這是因為它們極為相似。在每次迭代后CORDIC算法通常會產(chǎn)生一個附加位。</p>

40、;<p>　　3.CORDIC算法理論：矢量旋轉(zhuǎn)算法</p><p>　　在三角函數(shù)都可以從函數(shù)計算所得或使用矢量旋轉(zhuǎn)，這將在下面的章節(jié)中討論。矢量旋轉(zhuǎn)也可用于極坐標和直角坐標的相互轉(zhuǎn)換，矢量大小以及某些諸如的DFT和DCT的變換。CORDIC算法提供了一種實現(xiàn)向量旋轉(zhuǎn)的迭代法，它通過用移位器和加法器來實現(xiàn)任意角度。該算法是從一般的（吉文斯）旋轉(zhuǎn)變換得到的：</p><p>

41、　　旋轉(zhuǎn)向量在直角坐標系中為角度φ</p><p><b>　　重新排列為：</b></p><p>　　到目前為止，還沒有得到簡化。但是，如果旋轉(zhuǎn)角度受到限制，那么由正切函數(shù)的乘法簡化為簡單移位操作。通過一系列連續(xù)的小角度旋轉(zhuǎn)便可得到任意角度的旋轉(zhuǎn)。如果在每次迭代后取值，i是決定旋轉(zhuǎn)的方向，而不是是否旋轉(zhuǎn)，這時變成連續(xù)的了?，F(xiàn)在迭代旋轉(zhuǎn)可以表述為：</p>

42、;<p><b>　　其中：</b></p><p>　　去掉從迭代方程不斷產(chǎn)生的一個移位加法算就得到旋轉(zhuǎn)向量。Ki的結(jié)果可以用到系統(tǒng)中的任何地方或作為系統(tǒng)處理增益的一部分。隨著無限次迭代之后這個結(jié)果約為0.6073。因此，旋轉(zhuǎn)算法的增益An約為1.647。增益的精度取決于迭代的次數(shù)，以及下面的關(guān)系。</p><p>　　復合旋轉(zhuǎn)的角度是被基本旋轉(zhuǎn)方向序

43、列唯一定義的。該序列被向量所代表。所有可能的向量是一個基于二進制反正切的角測量系統(tǒng)。這個角度系統(tǒng)和任何其它系統(tǒng)之間轉(zhuǎn)換都可以通過查找來完成。一個更好的轉(zhuǎn)換方法是用一個額外的加法器和減法器，它們在每次迭代中積累了基本旋轉(zhuǎn)角度?；窘嵌瓤梢杂媒嵌葐卧奖愕谋硎境鰜怼＿@些角的值是通過查表或者硬件來實現(xiàn)的。角度累加器加上三分之一差分方程得到CORDIC算法：</p><p>　　顯然，在這種情況下，角度對反正切是有用的，

44、這里不需要額外的元素。</p><p>　　CORDIC算法通常用到兩種操作模式之中的一種。第一種模式，稱為旋轉(zhuǎn)模式，通過一個特殊角度（作為參數(shù)提供）旋轉(zhuǎn)輸入的向量。第二種模式，稱為矢量模式，旋轉(zhuǎn)輸入向量到x軸，同時記錄下作出的旋轉(zhuǎn)角度。</p><p>　　在旋轉(zhuǎn)模式下，角度累加器被初始化為所需要的旋轉(zhuǎn)角度。角度是由每次迭代決定的，用這種方法來減少角度累加器中對冗余角度的放大。它是由每次

45、迭代所決定的，因此是基于冗余角的每一階段。當然，如果輸入角度已經(jīng)表示為二進制的反正切值，角度累加器就可以被去掉了。對于旋轉(zhuǎn)模式，CORDIC算法的方程為：</p><p><b>　　其中</b></p><p>　　如果 zi<0，di=-1 否則di=+1</p><p><b>　　于是得到如下結(jié)果：</b>&

46、lt;/p><p>　　在矢量模式下，CORDIC算法旋轉(zhuǎn)輸入向量通過的任何角度都需要使輸出向量和x軸對齊。該向量運算的結(jié)果是一個旋轉(zhuǎn)角度和初始向量的放大。向量運算是通過找到在每次旋轉(zhuǎn)后y分量的冗余向量的最小值來運算的。冗余的Y分量是用來確定下次向哪個方向旋轉(zhuǎn)的。如果角度累加器被初始化為零，它在迭代完后包含中間角。在矢量模式下，CORDIC算法的方程是：</p><p><b>　　

47、其中</b></p><p>　　如果 yi<0，di=+1 否則di=-1</p><p><b>　　于是：</b></p><p>　　CORDIC旋轉(zhuǎn)和矢量算法都被限制在旋轉(zhuǎn)角度為-π/ 2到π/ 2之間。這個限制是由于在第一次迭代時用了20的正切值。對于大于π/ 2復合旋轉(zhuǎn)角度，就需要附加一個旋轉(zhuǎn)角度。Volder\

48、[4]描述了一種初始旋轉(zhuǎn)角度為±π/ 2的情況。這樣就給出了正確的迭代方程：</p><p><b>　　其中</b></p><p>　　如果 yi<0，di=+1 否則di=-1</p><p>　　這里沒初始旋轉(zhuǎn)值的增加。另外，π或0的初始旋轉(zhuǎn)值都是可以的，這樣避免把x和y分量調(diào)換為旋轉(zhuǎn)因子。接著，這里沒有增長是由于初始旋

49、轉(zhuǎn)：</p><p>　　如果 d=1,z'=z 或者如果d=-1,z'=z-π</p><p>　　如果 x<0, d=-1 否則 d=+1</p><p>　　這兩種縮減形式都可以仿真一個2π的輸入角度。第一種更蒹容旋轉(zhuǎn)角的連續(xù)性，而第二種是當接線受到限制時更為方便，它往往用于FPGA中。</p><p>　　COR

50、DIC算法適用于直接計算很多三角函數(shù)和間接計算其他函數(shù)。恰當?shù)倪x擇初始值和模式可以直接計算正弦，余弦，反正切，矢量幅度以及極坐標和直角坐標之間的轉(zhuǎn)換。</p><p><b>　　4.FPGA的實現(xiàn)</b></p><p>　　現(xiàn)在有許多方法都可以實現(xiàn)CORDIC算法。理想的結(jié)構(gòu)通過速度與在預定的應用領(lǐng)域之間的權(quán)衡。首先，我們測試一種迭代結(jié)構(gòu)，它直接通過CORDIC算

51、法方程得到的。然后，我們用最簡單和最復雜的硬件來實現(xiàn)要求。</p><p><b>　　5.結(jié)論</b></p><p>　　本文提出的CORDIC算法現(xiàn)在已經(jīng)被廣泛的用于研究和無限循環(huán)計算中。然而，現(xiàn)在絕大多數(shù)的硬件DSP設(shè)計很少被工程師用到或者被沒有學過硬件的工程師有效地實現(xiàn)DSP算法。新的DSP設(shè)計者必須熟悉在FPGA上實現(xiàn)他們的這些算法和技術(shù)以便保持競爭力。C