CORDIC算法在FPGA中的實(shí)現(xiàn)

1、微處理機(jī)M I CROPROCESS ORS大規(guī)模集成電路設(shè)計(jì)、制造與應(yīng)用C ORD I C 算法在FPG A 中的實(shí)現(xiàn)王智霞,王廣生(北京工業(yè)大學(xué)電控學(xué)院,北京100022摘要:CORD I C 算法是在許多角度計(jì)算方面有著廣泛應(yīng)用的經(jīng)典算法,通過(guò)考慮FPG A 的結(jié)構(gòu)、精度局限和速度要求,采用流水線技術(shù)(p i peline ,在FPG A 上用CORD I C 算法實(shí)現(xiàn)了對(duì)于大吞吐量數(shù)據(jù)的向量?jī)A角的計(jì)算,并對(duì)實(shí)際應(yīng)用中內(nèi)部步驟寄存器精度的選取給出了較為詳細(xì)的方法。關(guān)鍵詞:坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算;FPG A;流水線中圖分類號(hào):T N4文獻(xiàn)標(biāo)識(shí)碼:B 文章編號(hào):1002-2279(200701-0

2、004-04FP GA B a sed R ea li za ti o n o f CO RD I C A l go rithmWANG Zhi -xia,WANG Guang -sheng(B eijing university of technology,B eijing 100022,China Abstract:CORD I C algorithm is a classic algorith m with many app licati ons .Considering the archi 2tecture,p recisi on and s peed of FPG A ,the p

3、i peline technol ogy is used in computing large number of vect or angle values .This article p r ovides the way of confir m the wide of inner p r ocessing register .Key words:CORD I C;FPG A;Pi peline1引言FPG A 以其靈活性和使用方便在現(xiàn)今的數(shù)字領(lǐng) 域已經(jīng)得到了廣泛的應(yīng)用。但FPG A 實(shí)現(xiàn)數(shù)字系統(tǒng)也有其自身的局限性,其一是器件資源的門陣列規(guī)模的限制,其二是單元延遲限制,所以,這就需要設(shè)計(jì)者充分

4、考慮器件的實(shí)際工作能力。角度的旋轉(zhuǎn)計(jì)算在數(shù)字領(lǐng)域尤其是數(shù)字通信領(lǐng)域是一種應(yīng)用非常廣泛的計(jì)算,如果用傳統(tǒng)的除法器、乘法器等計(jì)算方法,需要占用大量的FPG A 資源,這樣就不能滿足設(shè)計(jì)者的要求,需要設(shè)計(jì)者考慮其他的算法實(shí)現(xiàn)這種類型的計(jì)算。CORD I C 算法在硬件電路的實(shí)現(xiàn)上只用到了加法器和移位器,這樣就大大節(jié)約了FPG A 的資源,從而可以滿足設(shè)計(jì)者的要求。2CORD I C 算法簡(jiǎn)介CORD I C (Coordinate Rotati on D igital Computer , 又名:坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算,是J.Voider 等人于1959年在設(shè)計(jì)美國(guó)航空導(dǎo)航控制系統(tǒng)的過(guò)程中提出來(lái)的一種算法

5、。下面就簡(jiǎn)要地介紹一下CORD I C 算法的基本數(shù)學(xué)思想。如圖1所示,向量逆時(shí)針旋轉(zhuǎn)度角得到向量OB ,這個(gè)關(guān)系可以用矩陣表示如式11:X j Y j=cos -sin sincos X i Y i=cos1-tan tan1X i Y j(1圖1向量旋轉(zhuǎn)坐標(biāo)圖如果假設(shè)是由n 個(gè)n 角度疊加而成的,那么根據(jù)式(1得出每一步的疊加操作需要按照式(2行X n +1Y n +1=cos n1-tan ntan n 1X n Y n(2利用式2經(jīng)過(guò)n 步疊加可以表示由向量旋轉(zhuǎn)到向量OB ,如下表示:X j Y j =cos 0cos 1.cos n1-tan 0tan 01.1-tan n tan

6、n 1X i Y i(3作者簡(jiǎn)介:王智霞(1980-,女,北京人,碩士研究生,主研方向:嵌入式系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn),大規(guī)模集成電路系統(tǒng)設(shè)計(jì),數(shù)字通信。收稿日期:2005-02-23第1期2007年2月No .1Feb .,2007王智霞等:CORD I C 算法在FPG A 中的實(shí)現(xiàn)由于計(jì)算機(jī)進(jìn)行計(jì)算采用二進(jìn)制形式,所以我們選取n =arctan (12n ,這樣選取n 方便了tan n 的計(jì)算,即tan n =S n 2-n,式3前面的cos n 可以取累乘的極限即:K =n =0cos n =n =0cosarctan (12n 0.607253如果我們?cè)谠O(shè)計(jì)的系統(tǒng)中提前計(jì)算K,那么當(dāng)拋開(kāi)K 不

7、算時(shí),式(2就可以表示成式(41: X n +1Y n +1=1-Sn 2-nS n 2-n1X n Y n =m i =0S i i (S i =-1,1(4至此,我們可以得出結(jié)論,由向量OA ,在先計(jì)算K 的情況下,我們可以由式4逐步的計(jì)算旋轉(zhuǎn)角度后得出向量OB 。計(jì)算的精度由n 的大小決定,式(4中的S n 由每一步的具體情況而定。3CORD I C 算法的應(yīng)用利用CORD I C 算法可以進(jìn)行許多運(yùn)算,比如計(jì)算角度正弦、角度余弦、復(fù)數(shù)的乘法、向量的角度和模的運(yùn)算等等。下面就介紹兩種CORD I C 算法的實(shí)際應(yīng)用實(shí)例:(1已知:角度,求:cos ?這個(gè)問(wèn)題我們可以轉(zhuǎn)換為利用CORD I

8、 C 這種向量旋轉(zhuǎn)的思想進(jìn)行解析,建模如下(見(jiàn)圖2: 圖2向量旋轉(zhuǎn)坐標(biāo)圖起始向量OA 為X i ,Y i ,i =1,0,0終止向量為X j ,Y j ,j =cos ,sin ,由OA 經(jīng)過(guò)n 步旋轉(zhuǎn)到OB ,即可以得到cos設(shè):Zn 表示經(jīng)過(guò)n 步旋轉(zhuǎn)后,得到的結(jié)果與的差值,即:Z n =-ni =0i ,通過(guò)這樣的假設(shè),就可以得到:S n =1Zn 0-1Z n =0X (n +1=X (n -Y (n 2-nY (n +1=Y (n +X (n 2-nZ (n +1=Z (n -arctan (2-nE LSEX (n +1=X (n +Y (n 2-n Y (n +1=Y (n -X

9、 (n 2-nZ (n +1=Z (n +arctan (2-n(2已知:點(diǎn)A (X i ,Yi ,求:向量在坐標(biāo)系中的傾角?這個(gè)問(wèn)題我們可以轉(zhuǎn)換為利用CORD I C 這種向量旋轉(zhuǎn)的思想進(jìn)行解析,建模如下(見(jiàn)圖3:圖3坐標(biāo)系旋轉(zhuǎn)圖如圖3所示,為了方便對(duì)角度的計(jì)算,我們旋轉(zhuǎn)了一下坐標(biāo)軸,可以推斷出起始向量OA 為X i ,Y i ,Z i =X i ,Y i ,0終止向量OB 為X j ,Y j ,Z j =R,0,-設(shè)Z n =n =0n ,就可以得到:S n =1Y n 0-1Y n 0(6將式(4和式(6結(jié)合,就可以得到它的邏輯表述:I F Y (n =0X (n +1=X (n -Y

10、(n 2-n Y (n +1=Y (n +X (n 2-nZ (n +1=Z (n -arctan (2-nE LSEX (n +1=X (n +Y (n 2-n Y (n +1=Y (n -X (n 2-nZ (n +1=Z (n +arctan (2-n4CORD I C 的FPG A 實(shí)現(xiàn)下面就上述的第二種應(yīng)用實(shí)例,描述一下用veril og 語(yǔ)言實(shí)現(xiàn)CORD I C 算法的具體步驟和實(shí)現(xiàn)方法。(1系統(tǒng)要求接口類型和精度1輸入X Y 的精度為(11,10,T :10位整數(shù)、無(wú)小數(shù)位的有符號(hào)數(shù)。2輸出角度為Z,Z 為弧度值的前的系數(shù),精度為(8,1,T :6位小數(shù)、1位整數(shù)的有符號(hào)數(shù),它5

11、1期微處理機(jī)的范圍是(-1,1。3系統(tǒng)的接口,見(jiàn)表1,其中clk 為80MHz表1cordic 模塊的接口表接口名稱長(zhǎng)度類型clk 1I N rst 1I N enin 1I N xin 11I N yin 11I N okout 1OUT zout8OUT(2計(jì)算中間寄存器寬度的選取分析系統(tǒng)要求的輸入X 和Y 的精度和輸出的Z的精度進(jìn)行比較,可以分析出,輸出和輸入的精度不對(duì)稱,即:Z 的精度為(8,1,T 對(duì)應(yīng)的最小可以表示的角度為2.8125X Y 的精度為(11,10,T ,對(duì)應(yīng)的可以表示的最小的角度為:45-arctan (10221023=0.028017可見(jiàn),輸入和輸出誤差的允許值

12、相差非常遠(yuǎn),這樣就得到了兩種精度的分析。1如果允許輸出的角度Z 的最后一位不準(zhǔn)確,那么可以以2.8125為精度進(jìn)行分析,分析如下:假設(shè)計(jì)算中用到的角度精度為(9,0,T ,即:8位小數(shù),1位符號(hào)位的值,這個(gè)值與z 值相同,都表示弧度值的前的系數(shù),小數(shù)位的最高位表示1/4(45度,所以它能表示的最小角度為0.3515625度。根據(jù)上述假設(shè),arctan (2-n可以表示為下表2:表2arctan2-n 值實(shí)際值取值計(jì)算值誤差arctan 1/226.5650500000000100110026.718750000000.1537arctan 1/414.036240000000001010001

13、4.062500000000.02626arctan 1/87.125020000000000101007.0312*.09377arctan 1/163.57633000000000001010 3.515624500000.060706arctan 1/321.789910000000000001011.757812500000.032097誤差合計(jì)0.366533從表2中我們不難看出,由于arctan (2-n用精度為(9,0,T 表示,有部分的誤差,誤差的最大合計(jì)為0.366533度,這樣可以得出如下結(jié)論:用(9,0,T 表示中間計(jì)算的角度寄存器的精度,運(yùn)行5步疊加結(jié)果的最大誤差為:0

14、.366533(前者的誤差+1.78991(后者的誤差=2.156443度上述計(jì)算出的最大誤差為2.156度,小于2.8125度,符合z 的精度范圍,計(jì)算結(jié)果只會(huì)在最后一位上與z 的真實(shí)結(jié)果有出入,誤差在允許范圍之內(nèi)。2如果不允許輸出角度Z 有任何的偏差,6位小數(shù)位必須全部準(zhǔn)確,那么需要用0.028017精度進(jìn)行計(jì)算,分析方法同上,最后得出的選取中間計(jì)算角度的精度是(15,0,T ,即:14位小數(shù),1位符號(hào)位的值,這個(gè)值與z 值相同,都表示弧度值的前系數(shù),小數(shù)位的最高位表示1/4(45度,需要進(jìn)行12步計(jì)算,這個(gè)過(guò)程要比第一個(gè)過(guò)程需要增加數(shù)倍的資源,而且速度會(huì)明顯變慢。根據(jù)綜合后的經(jīng)驗(yàn)得知9位

15、加法器的延遲時(shí)間大約為3ns,而16位加法器的延遲時(shí)間大約為5ns,系統(tǒng)輸入的clk 為80MHz,周期為1/80MHz =12.5ns,16位加法器(X n Y n 的計(jì)算的延遲時(shí)間可以滿足clk 的速度,所以考慮到運(yùn)算速度的要求,使用第一種精度和步數(shù)選取結(jié)果,即:Z n 的精度為(9,0,T ,5步迭代運(yùn)算。(3 一個(gè)計(jì)算過(guò)程的處理一個(gè)計(jì)算過(guò)程的實(shí)現(xiàn)步驟如圖4所示。圖4計(jì)算過(guò)程步驟圖1由于系統(tǒng)要求輸入點(diǎn)A (X,Y 的范圍為4個(gè)象限,而文章的二.2中講述的方法只是針對(duì)象限的,所以我們需要在開(kāi)始的計(jì)算前判斷點(diǎn)A (X,Y 所在的象限,并將它轉(zhuǎn)換到象限;另外,由于我們是判斷Y (n 正負(fù)來(lái)確定

16、S (n 的正負(fù),角度小于45的角,角度的變化對(duì)于Y 值的影響比較明顯,所以如果所求向量角度在4590度的范圍內(nèi),需要先將X 和Y 互換,轉(zhuǎn)換到045度的范圍內(nèi)進(jìn)行計(jì)算,這樣可以減少誤差。下面介紹一個(gè)具體的例子,說(shuō)明一下具體的變換過(guò)程:如圖5已知點(diǎn)A 在第三象限,經(jīng)過(guò)變換后變換到第一象限變成(-X,-Y ,經(jīng)過(guò)判斷-X -Y,以45度為對(duì)稱軸進(jìn)行對(duì)稱操作得到最終的變換結(jié)果(X ,Y 為(-Y,-X 。2對(duì)于得到的向量進(jìn)行5步的迭代過(guò)程:每一步的迭代過(guò)程需要對(duì)X (n 和Y (n 進(jìn)行除法操作,下面詳細(xì)說(shuō)明一下帶符號(hào)數(shù)的除2的倍數(shù)操作。X =b1b2b3b4b5bn (b1代表符號(hào)位X /2m=

17、b1b1b1(共M 個(gè)b2b3b n -m +1例如:實(shí)現(xiàn)運(yùn)算-56/4=-14-56=1111100100062007年王智霞等:CORD I C算法在FPG A中的實(shí)現(xiàn)-56/4=1111110010=-143這步與第一步形成了對(duì)應(yīng)的關(guān)系,如圖5所示,這一步的作用是將在第一象限計(jì)算出來(lái)的角度轉(zhuǎn)換成,步驟正好與步驟一中的相反。圖5象限轉(zhuǎn)換圖示首先,判斷第一步是否進(jìn)行了以45度角分界線為軸進(jìn)行的對(duì)稱操作,如果進(jìn)行了,則將角度轉(zhuǎn)換為2-;其次,判斷第一步判斷的點(diǎn)(X,Y在第三象限,所以最后的結(jié)果=-2-。(4由于這種角度運(yùn)算多數(shù)應(yīng)用在通訊領(lǐng)域的FPG A設(shè)計(jì)中,通訊領(lǐng)域要求計(jì)算的數(shù)據(jù)吞吐量非常大

18、,所以在這里引入了流水線技術(shù)進(jìn)行數(shù)據(jù)的處理。上述已經(jīng)說(shuō)明,完成一個(gè)完整的運(yùn)算需要7個(gè)子操作過(guò)程。所以我們就設(shè)計(jì)了7重疊的一個(gè)流水線,如圖6所示。第一個(gè)clk上升沿時(shí),數(shù)據(jù)1進(jìn)行預(yù)先步驟處理,第二個(gè)clk 上升沿時(shí)第二個(gè)數(shù)據(jù)進(jìn)行預(yù)先處理,同時(shí)數(shù)據(jù)1進(jìn)行第一步處理,到第七個(gè)clk時(shí)一共同時(shí)處理7個(gè)數(shù)據(jù),但是這7個(gè)數(shù)據(jù)在不同的步驟狀態(tài)下。這樣就可以實(shí)現(xiàn)如果大數(shù)據(jù)量需要計(jì)算時(shí),一個(gè)clk最多可以同時(shí)處理7個(gè)數(shù)據(jù),大大提高了數(shù)據(jù)的吞吐能力。圖6流水線示意圖5總結(jié)經(jīng)過(guò)綜合工具I SE的綜合后得出:最大延時(shí)為6.50ns時(shí)占用資源為4500。延時(shí)和占用資源符合系統(tǒng)要求,此模塊可以良好地運(yùn)行。FPG A有著規(guī)

19、整的內(nèi)部邏輯陣列和豐富的連線資源,特別適合于數(shù)字信號(hào)處理任務(wù),相對(duì)于串行運(yùn)算為主導(dǎo)的通用DSP芯片來(lái)說(shuō),其并行性和可擴(kuò)展性更好。但長(zhǎng)期以來(lái),FPG A一直被用于系統(tǒng)邏輯或時(shí)序控制上,很少有信號(hào)處理和數(shù)字通信方面的應(yīng)用,其原因主要是因?yàn)樵贔PG A中缺乏實(shí)現(xiàn)一些象CORD I C這樣的,可以通過(guò)數(shù)字電路完成數(shù)學(xué)運(yùn)算的有效結(jié)構(gòu)。現(xiàn)在這個(gè)問(wèn)題正逐步得到解決,使FPG A在數(shù)字信號(hào)處理方面有了長(zhǎng)足的發(fā)展,也使CORD I C這種經(jīng)典算法得到更廣泛的應(yīng)用。參考文獻(xiàn):1R ichard Herveille.Cordic Core Specificati onE B/OL.htt p:/.2李波.80位嵌入式超越函數(shù)運(yùn)算器的設(shè)計(jì)J/OL.計(jì)算機(jī)工程與科學(xué),2004(12:52-57.3夏宇聞.復(fù)雜數(shù)字電路與系統(tǒng)的veril og HDL設(shè)計(jì)技術(shù)(第一版M.北京:北京航空航天大學(xué)出版社,1998-08.(上接第3頁(yè)5結(jié)束語(yǔ)多核、多線程處理器技術(shù)具有普通單核、單線程處理器所未有的性能優(yōu)勢(shì),目前已成為提高處理器性能的主要途徑,同時(shí),多核、多線程處理器也為很多的應(yīng)用領(lǐng)域提供了新的解決方案。發(fā)揮出多核處理器硬件的優(yōu)勢(shì),需要從編譯器技術(shù),操作系統(tǒng)及其它系統(tǒng)軟件的架構(gòu)上來(lái)加以發(fā)掘。這個(gè)全新的領(lǐng)域?yàn)槲覈?guó)發(fā)展系統(tǒng)軟件帶來(lái)了機(jī)遇和挑戰(zhàn)。如何面對(duì)這