鄧凌煊 ， 安軍社

（1.中國科學(xué)院大學(xué) 北京 100190；2.中國科學(xué)院 空間科學(xué)與應(yīng)用研究中心，北京 100190）

隨著航天技術(shù)的發(fā)展，航天任務(wù)對于導(dǎo)航計(jì)算機(jī)的性能要求越來越高。導(dǎo)航計(jì)算機(jī)除了要對傳感器數(shù)據(jù)進(jìn)行采集，與控制系統(tǒng)進(jìn)行實(shí)時(shí)通訊，還要能進(jìn)行實(shí)時(shí)的計(jì)算[1]。盡管目前航天任務(wù)中使用的處理器芯片性能越來越強(qiáng)，但大多數(shù)CPU并沒有處理常用超越函數(shù)（sin，cos，arctan，exp，sqrt，ln 等）的專用指令。而通過純軟件循環(huán)迭代求解超越函數(shù)往往需要CPU數(shù)十甚至上百個(gè)周期[2]，這極大降低了導(dǎo)航計(jì)算機(jī)的實(shí)時(shí)性。本文提出了一種高實(shí)時(shí)性、低復(fù)雜度的CORDIC協(xié)處理器核，提供了高吞吐率的超越函數(shù)運(yùn)算能力，從而提高了導(dǎo)航計(jì)算機(jī)的并行運(yùn)算能力。此IP核使用verilog編寫,由于其資源占用率低，可以非常容易地被集成入各種航天用FPGA中。

1 CORDIC算法

1.1 CORDIC旋轉(zhuǎn)

CORDIC算法最早由Volder提出[3]，用于求解一般三角函數(shù)，之后由Walther改進(jìn)[4]，使得CORDIC可以用于計(jì)算雙曲函數(shù)和進(jìn)行乘除運(yùn)算。由于幾乎所有的通用CPU都具有硬件乘法除法功能,因此對數(shù)坐標(biāo)模式所提供的乘除功能很少被實(shí)際使用,故CORDIC算法的主要應(yīng)用是三角函數(shù)和雙曲函數(shù)的運(yùn)算。CORDIC的基本思想是通過一系列預(yù)定大小角度的旋轉(zhuǎn)，使得輸入向量被旋轉(zhuǎn)到所期望的位置，從而求解出一系列函數(shù)。CORDIC的旋轉(zhuǎn)方程可以表示為

其中m為1時(shí)CORIDC工作在圓坐標(biāo)系下，m為-1時(shí)工作在雙曲坐標(biāo)系下。dn為1時(shí)向量按順時(shí)針方向旋轉(zhuǎn)，當(dāng)dn為-1時(shí)按逆時(shí)針方向旋轉(zhuǎn)。

雖然每一步迭代只需要進(jìn)行加減操作和固定位的移位操作，但由（1）可知，CORIDC每一次旋轉(zhuǎn)都會(huì)改變向量的模。所以為了得到正確的向量分量x和y，需要補(bǔ)償旋轉(zhuǎn)后的向量，而由于向量模的變化與旋轉(zhuǎn)的方向無關(guān)，這可以通過一個(gè)常數(shù)乘法器實(shí)現(xiàn)。補(bǔ)償常數(shù)為：

CORDIC每次旋轉(zhuǎn)的方向由工作模式?jīng)Q定。在旋轉(zhuǎn)模式下，CORDIC試圖讓向量與x軸之間的夾角z趨近于0。在向量模式下，CORDIC試圖讓向量的y分量趨近于0。故每次旋轉(zhuǎn)的方向由運(yùn)行模式和向量的yz分量符號決定：

綜上，各個(gè)模式下CORDIC的迭代結(jié)果以及可實(shí)現(xiàn)的函數(shù)如表1所示。

表1 各模式CORDIC旋轉(zhuǎn)結(jié)果Tab.1 Rotation result of CORDIC under all modes

1.2 收斂性

Cordic能輸出正確結(jié)果的前提是旋轉(zhuǎn)結(jié)束時(shí)向量能夠被旋轉(zhuǎn)到預(yù)期的位置（在誤差范圍內(nèi)），即旋轉(zhuǎn)收斂。可以通過遞歸證明的是[5]，對于圓坐標(biāo)模式，對于任意n總有

令剩余角度為rn+1，

總rn<2·arctan2-n有。但是對于雙曲坐標(biāo)模式，類似的結(jié)論并不成立。然而可以證明的是

對于m=3i+1，i=1，2，3…成立。故對于雙曲坐標(biāo)模式，為了保證算法收斂，需要將第4，13，40...次循環(huán)重復(fù)。此外，由于在每一級旋轉(zhuǎn)的角度是預(yù)先固定的，故CORDIC所能將向量旋轉(zhuǎn)的角度有限，即系的收斂域分別為A∈[-1.743，1.743]，對于雙曲坐標(biāo)模式為A∈[-1.055，1.055]。

2 系統(tǒng)實(shí)現(xiàn)

為了保證協(xié)處理器能夠提供足夠的計(jì)算吞吐量并使協(xié)處理器的計(jì)算延遲可預(yù)測，本文使用流水線實(shí)現(xiàn)整個(gè)CORDIC核[6]。協(xié)處理器的流水線結(jié)構(gòu)如圖1所示。

2.1 系統(tǒng)輸入

圖1 CORDIC協(xié)處理器流水線框圖Fig.1 Pipeline structure of CORDICcoprocessor

協(xié)處理器核從輸入FIFO獲得初始輸入數(shù)據(jù)，包括3個(gè)坐標(biāo)分量以及1個(gè)控制命令字。輸入?yún)?shù)的格式為1位符號位，2位整數(shù)位，小數(shù)位的位數(shù)作為IP核的參數(shù)可以在例化時(shí)調(diào)整。這樣的輸入格式使得此IP核可以容易地被應(yīng)用于使用定點(diǎn)運(yùn)算的許多DSP處理器。對于浮點(diǎn)數(shù)運(yùn)算，實(shí)際上CPU可以通過簡單的移位縮放操作使得輸入范圍外的xyz分量落到協(xié)處理器可接受的范圍內(nèi)，這是由于規(guī)格化浮點(diǎn)數(shù)的尾數(shù)本來就在區(qū)間[1，2）內(nèi)。相對的，已有的很多CORDIC協(xié)處理器實(shí)現(xiàn)[7]使用了浮點(diǎn)數(shù)進(jìn)行中間運(yùn)算，然而這不僅顯著地增加了資源的使用，而且使得每一個(gè)CORDIC旋轉(zhuǎn)需要通過多級流水線完成，增大了每個(gè)運(yùn)算的延遲。

此外，為了降低CPU和協(xié)處理器之間交互次數(shù)，本IP核允許CPU在計(jì)算某些函數(shù)時(shí)不對所有的輸入寄存器進(jìn)行寫入。對于輸入?yún)?shù)少于3個(gè)的函數(shù)，協(xié)處理器自動(dòng)生成其他分量的輸入。比如對于cos（x），CPU只需要對協(xié)處理器的a0寄存器和控制字寄存器寫入即可觸發(fā)cos（x）的運(yùn)算，CORDIC協(xié)處理器會(huì)自動(dòng)把x分量初始化成2.0，y分量初始化成0，z分量初始化成a0。對于有效位數(shù)較小的配置如18位，可以進(jìn)一步將控制命令字和a0放到同一個(gè)32位寄存器中，則對于單輸入函數(shù)，CPU只需向一個(gè)地址寫入數(shù)據(jù)即可完成操作。18位數(shù)據(jù)精度時(shí)的輸入寄存器格式如圖2所示。

圖2 18位配置時(shí)的CORDIC核輸入寄存器Fig.2 Input register of CORDICcore under 18 bits configuration

2.2 預(yù)處理單元

如表1所示，CORDIC的運(yùn)算結(jié)果并不直接對應(yīng)所要求的函數(shù)，故需要對與輸入?yún)?shù)進(jìn)行處理。例如對于ln（a）和sqrt（a）運(yùn)算，需要令 x=a+1，y=a-1，對于 cos（x），sin（x）等運(yùn)算，需要生成相應(yīng)的其他分量輸入。此外，由于雙曲坐標(biāo)的性質(zhì)，arctanh1并不存在，故雙曲坐標(biāo)模式只能從i=1開始迭代，而圓坐標(biāo)系可以從i=0開始迭代，這導(dǎo)致了兩種模式的旋轉(zhuǎn)過程不同。為了能用同一個(gè)流水線實(shí)現(xiàn)2種模式的操作，本文令所有模式都從i=1開始迭代。但這樣會(huì)導(dǎo)致在圓坐標(biāo)模式下的收斂域過小，只有。解決的辦法是在預(yù)處理單元加入象限折疊，即通過三角函數(shù)關(guān)系，將[-π，π]上的向量折疊到[0，]上，再在后處理單元對結(jié)果進(jìn)行修正。

2.3 旋轉(zhuǎn)單元

旋轉(zhuǎn)單元是CORDIC協(xié)處理器的核心，實(shí)現(xiàn)（1）所描述的向量旋轉(zhuǎn)操作。其結(jié)構(gòu)如圖3所示。

圖3 CORDIC旋轉(zhuǎn)單元的原理圖Fig.3 Schematic sheet of CORDICrotation unit

此模塊首先通過控制命令字、yz分量計(jì)算出旋轉(zhuǎn)的方向，然后對向量作旋轉(zhuǎn)。由于圓坐標(biāo)和雙曲坐標(biāo)模式下旋轉(zhuǎn)的角度不同，所以需要根據(jù)控制命令字進(jìn)行選擇。由于使用了流水線結(jié)構(gòu)，移位操作實(shí)際上通過布線而靜態(tài)確定，不需要專門的移位器。模塊使用3個(gè)可進(jìn)行加減運(yùn)算的ALU單元分別對xyz分量進(jìn)行修正。Rom存儲了圓坐標(biāo)和雙曲坐標(biāo)模式下的旋轉(zhuǎn)角度，其精度根據(jù)IP核的配置而定，可以簡單地通過在實(shí)例化verilog模塊時(shí)指定參數(shù)來進(jìn)行配置。

2.4 后處理單元

由圖2可知，旋轉(zhuǎn)單元的輸出結(jié)果并不直接對應(yīng)CORDIC協(xié)處理器所提供的函數(shù)。后處理單元對CORDIC旋轉(zhuǎn)單元的輸出結(jié)果進(jìn)行處理，實(shí)現(xiàn)所需要的函數(shù)。具體的處理如表2所示。

表2 命令字對應(yīng)的輸出處理Tab.2 Control words and corresponding post processing operations

此外，由于前處理單元對圓坐標(biāo)輸入進(jìn)行了象限折疊，后處理單元需要進(jìn)行相應(yīng)的修正。例如對于圓坐標(biāo)旋轉(zhuǎn)模于是相應(yīng)的后處理單元需要將x和y的值相交換。

2.5 補(bǔ)償單元

由（4）可知，CORDIC每次旋轉(zhuǎn)都會(huì)改變向量的模，故需要對最終的xy分量進(jìn)行補(bǔ)償。由于向量模變化只與坐標(biāo)系模式有關(guān)，故補(bǔ)償單元可以用一個(gè)常數(shù)乘法器實(shí)現(xiàn)。常數(shù)乘法器可以通過用華萊士樹把移位后幾個(gè)向量相加來實(shí)現(xiàn)。本文在線下通過程序窮舉找出了一組加減操作數(shù)最少乘數(shù)編碼方式，對于18位的配置，可以使用一個(gè)9輸入的華萊士樹和一個(gè)加法器實(shí)現(xiàn)，這使得該核在缺乏硬件乘法器的基于flash的Actel FPGA上也可以輕松使用。華萊士樹中一位的結(jié)構(gòu)如圖4所示。

圖4 9位華萊士樹結(jié)構(gòu)Fig.4 The structure of a 9 input Wallace tree

3 性能分析

為了證明所提出的IP核的實(shí)用性，本文選取了迭代次數(shù)16-20，擴(kuò)展位數(shù)為5位的幾種配置進(jìn)行了綜合。綜合平臺使用了航天電子系統(tǒng)常用的2種 FPGA：A3P3000E和xc4vf40。綜合結(jié)果如表3所示。

可見本IP核具有較高的性能和較低的資源占用率，可以較容易地被集成，且隨著迭代次數(shù)和精度的提高，資源的增長趨勢穩(wěn)定，速度的下降并不明顯。

表3 本文提出的CORIDC協(xié)處理器實(shí)現(xiàn)與基于冗余數(shù)實(shí)現(xiàn)方案的綜合對比Tab.3 Comparison between proposed CORDIC coprocessor and redundant arithmetic based

一直以來有很多為加速CORDIC運(yùn)算而提出的方法，其中很多使用了冗余數(shù)，試圖通過冗余數(shù)進(jìn)位傳播有限的特點(diǎn)來降低加法器的延遲。但本文通過對比發(fā)現(xiàn)，基于冗余數(shù)的算法僅在A3P3000E的實(shí)現(xiàn)上有一定速度優(yōu)勢，而在virtex4上沒有速度優(yōu)勢，還在資源利用率上有很大劣勢。原因是當(dāng)前的大多數(shù)FPGA針對常見運(yùn)算邏輯，如加法器的實(shí)現(xiàn)作出了特殊優(yōu)化，使用了快速進(jìn)位鏈降低加法器的進(jìn)位延遲。相對的，由于FPGA缺乏對冗余數(shù)邏輯的支持，冗余數(shù)加法器需要由基本單元綜合生成，具有較大的布線延遲，且需要消耗大量的LUT或邏輯門資源。此外，由于冗余數(shù)使用2倍于補(bǔ)碼長度的編碼方式來表示數(shù)值，冗余數(shù)需要使用更多的寄存器寄存每級流水線的中間結(jié)果。綜上，對于有效位數(shù)較少的配置，本文提出的CORDIC協(xié)處理器具有更好的性能與資源利用更具優(yōu)勢。

4 精度與誤差

根據(jù)參考文獻(xiàn)[8]可知，CORDIC計(jì)算的誤差主要來自2部分：由于每次迭代時(shí)用來修正z分量的角度有限而產(chǎn)生的近似誤差和由于計(jì)算位數(shù)有限而產(chǎn)生的xy分量截?cái)嗾`差。為了盡量降低誤差，首先應(yīng)該保證旋轉(zhuǎn)過程中用來修正z的數(shù)值是經(jīng)過舍入得到的，而不是簡單通過截?cái)嗟玫降模@樣可以減小由于使用近似的旋轉(zhuǎn)角度而產(chǎn)生的舍入誤差。其次可以考慮在最終階段運(yùn)算結(jié)果前進(jìn)行舍入。運(yùn)算結(jié)果的舍入可以在補(bǔ)償單元通過增加華萊士樹的輸入實(shí)現(xiàn)。即增加一個(gè)輸入變量，其大小為最低有效位的一半，符號與補(bǔ)償單元的輸入相同。除此之外，需要根據(jù)所需的精度合理選擇CORDIC協(xié)處理器的數(shù)據(jù)位數(shù)，增加擴(kuò)展位，即對于n位的CORDIC運(yùn)算，在迭代運(yùn)算時(shí)使用n+m位，在迭代結(jié)束后舍棄m位，這樣做可以保證前面的n位不受到截?cái)嗾`差的影響.。本文選取了18位CORDIC來說明擴(kuò)展位和迭代次數(shù)對精度的影響。對于圓坐標(biāo)旋轉(zhuǎn)模式，輸入向量為x=2.0，y=0.0，z∈[-π，π]的所有可能輸入向量；對于圓坐標(biāo)向量模式，輸入為模為2.0，夾角屬于[-π，π]的所有可能輸入向量；對于雙曲旋轉(zhuǎn)模式，輸入為 x=2.0，y=0.0，z∈[-1.0，1.0]的所有可能輸入向量；對于雙曲向量模式，輸入為 x=a+1，y=a-1，α∈[0.25，1.0]的所有可能輸入。各個(gè)函數(shù)的誤差與所選取的迭代次數(shù)和擴(kuò)展位的關(guān)系如表4所示。

表4 幾種配置下的各函數(shù)的計(jì)算誤差，單位為ulpTab.4 Error of functions under several configurations

其中ulp為最低位單位。對于20位定點(diǎn)數(shù)有1ulp=2-18。配置為擴(kuò)展位數(shù)和迭代次數(shù)。通過實(shí)驗(yàn)可以發(fā)現(xiàn)，對擴(kuò)展后的向量進(jìn)行截?cái)鄷?huì)帶來顯著的誤差增長。并且只會(huì)在使用較長擴(kuò)展位時(shí)對結(jié)果進(jìn)行舍入才有明顯的效果，因?yàn)閿U(kuò)展位較少的情況下舍入反而可能會(huì)讓結(jié)果向錯(cuò)誤的方向舍入。最后值得注意的是雙曲模式下的函數(shù)誤差高于圓坐標(biāo)模式，由（8）可知這是由于雙曲模式向量角度收斂性更差而導(dǎo)致的。

5 結(jié)束語

本文提出的CORDIC協(xié)處理器可以容易地集成進(jìn)目前常見的航天級FPGA中，為CPU提供更強(qiáng)的三角函數(shù)和超越函數(shù)運(yùn)算能力。在中端的V4系列FPGA中實(shí)現(xiàn)萬分之1精度的三角函數(shù)和超越函數(shù)只需要不到10%的資源，并可運(yùn)行于較高的系統(tǒng)時(shí)鐘下。CORDIC協(xié)處理器提供了并行運(yùn)算幾種常用三角和超遠(yuǎn)函數(shù)的功能，不僅適用于導(dǎo)航計(jì)算機(jī)，也可以被用于其他有大量實(shí)時(shí)性計(jì)算需求的嵌入式系統(tǒng)中。

[1]閆捷，徐曉蘇，李瑤，等.基于DSP與FPGA的嵌入式組合導(dǎo)航計(jì)算機(jī)系統(tǒng)設(shè)計(jì) [J].測控技術(shù)，2013，32（12）:61-64 YAN Jie，XU Xiao-su，LI Yao，et al.Design of embedded integrated navigation system based on DSP and FPGA[J].Measurement&Control Technology，2013，32（12）:61-64.

[2]Texas Instrument.TMS320C54x DSP Library Programmer’s Reference[EB/OL].（2013）.http://www.ti.com.cn/lit/ug/spru518d/spru518d.pdf.

[3]Volder JE.The birth of CORDIC[J].Journal of VLSI Signal Processing Systems，2000，25（2）:101-105.

[4]Walther J S.The story of unified CORDIC[J].Journal of VLSI Signal Processing Systems，2000，25（2）:107-112.

[5]Jean-Michel Muller.Elementary Functions Algorithms and Implementation Second Edition[M].Boston:Birkh?user，2005.

[6]王思聰，文治平，于立新.空間用CORDIC處理器的結(jié)構(gòu)級設(shè)計(jì)方法[J].微電子學(xué)與計(jì)算機(jī)，2006，23（8）:57-60.WANG Si-cong，WEN ZHi-ping，YU Li-xin.The architecture desing method of CORDIC processor used in space[J].Microelectronics&Computer，2006，23（8）:57-60.

[7]Munoz DM，Sanchez DF，Llanos CH，et al.FPGA based floating-point library for CORDIC algorithms[A].Programmable Logic Conference （SPL） 2010 VI Southern[C]//Ipojuca，2005:55-60.

[8]Sarbishei O，Radecka K.On the Fixed-Point Accuracy Analysis and Optimization of FFT Units with CORDICMultipliers[A].Computer Arithmetic （ARITH），2011 20th IEEE Symposium[C]//Tubingen，2011:62-69.