CORDIC 算法在正余弦函數(shù)中的應(yīng)用及其FPGA 實(shí)現(xiàn)

常柯陽(yáng)，曾岳南，陳 平，覃曾攀

廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州510006

1 引言

正余弦函數(shù)在眾多工程應(yīng)用的場(chǎng)合非常廣泛，就典型的采用空間矢量控制方法的電機(jī)控制系統(tǒng)來(lái)說(shuō)，坐標(biāo)變換模塊就需要正余弦函數(shù)的實(shí)時(shí)參與。而在電機(jī)控制芯片的發(fā)展方面，現(xiàn)場(chǎng)可編程邏輯器件（FPGA）[1]以其速度、靈活性、可靠性和集成度而逐漸受人矚目。

由于計(jì)算精度與存儲(chǔ)容量的突出矛盾[2]，在存儲(chǔ)資源有限的FPGA 芯片中，常用的查找表方法沒(méi)有優(yōu)勢(shì)；而CORDIC 算法，僅需通過(guò)移位與加減運(yùn)算和占用少量的存儲(chǔ)資源，因此能夠方便地在硬件中實(shí)現(xiàn)。但該算法過(guò)程復(fù)雜，迭代次數(shù)較多，輸出時(shí)延較長(zhǎng)，占用的硬件資源較多。因此，本文提出了一種查找表與CORDIC 相結(jié)合的算法，結(jié)合兩者的優(yōu)勢(shì)，在保證精度的前提下優(yōu)化了算法的輸出時(shí)延和資源消耗，并在QuartusII 7.2 開(kāi)發(fā)環(huán)境下完成了算法的設(shè)計(jì)、仿真和硬件測(cè)試。

2 查找表法和傳統(tǒng)CORDIC 算法介紹

2.1 查找表算法原理

查找表算法的原理是根據(jù)計(jì)算精度要求，先把一個(gè)周期內(nèi)的正余弦函數(shù)分為若干個(gè)點(diǎn)，分別求出對(duì)應(yīng)點(diǎn)的函數(shù)值，并將結(jié)果寫(xiě)入芯片存儲(chǔ)器中。然后，再通過(guò)適當(dāng)?shù)倪\(yùn)算將輸入角度與存儲(chǔ)器地址對(duì)應(yīng)起來(lái)，從而查表獲得結(jié)果。

用查找表[2]方法實(shí)現(xiàn)函數(shù)的計(jì)算，雖然沒(méi)有輸出時(shí)延，但其精度和表的容量是指數(shù)關(guān)系的，就勢(shì)必需要大規(guī)模的ROM，這在實(shí)際應(yīng)用中需要占用大量的片上資源，甚至是不可行的。

2.2 CORDIC 算法原理

坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)CORDIC（Coordinate Rotation Digital Computer）算法，是由Volder[3]于1959 年提出的，其基本思想是通過(guò)一系列與運(yùn)算基數(shù)相關(guān)的角度的不斷偏擺，從而逼近所需旋轉(zhuǎn)的角度。在圓周模式下，其基本實(shí)現(xiàn)形式有兩種：旋轉(zhuǎn)計(jì)算模式和向量計(jì)算模式。計(jì)算正余弦函數(shù)時(shí)，需采用旋轉(zhuǎn)計(jì)算模式。在文獻(xiàn)[2]中，給出了其基本形式：

其中，xn、yn、zn是當(dāng)前迭代變量；xn+1、yn+1、zn+1是下一次迭代變量；是符號(hào)函數(shù)；n是迭代次數(shù)。輸入，則輸出為，其中設(shè)增益因子，在n→∞時(shí)，K≈0.607 253。算法的角度覆蓋范圍[4]為(-99.88°～99.88°)。

3 改進(jìn)型CORDIC 算法

3.1 改進(jìn)型CORDIC 算法的思想

由上述算法描述可知，CORDIC 算法結(jié)構(gòu)僅需要移位和加減運(yùn)算，以及n-1 個(gè)旋轉(zhuǎn)常量，非常方便在FPGA 中實(shí)現(xiàn)。但其迭代次數(shù)較多，輸出時(shí)延大，占用硬件資源較多。考慮到上述因素，本文提出了一種改進(jìn)型CORDIC 算法，將查找表方法與傳統(tǒng)CORDIC 方法相結(jié)合。這樣，可以利用少部分的存儲(chǔ)資源，也能降低迭代次數(shù)，節(jié)約了硬件資源和降低輸出時(shí)延。文獻(xiàn)[4]雖然提出了這種思想，但并未給出具體的實(shí)現(xiàn)方法。

CORDIC 算法是一種逐次逼近的算法：以一個(gè)初始向量為出發(fā)點(diǎn)，按照一定的逐漸減小的角度值上下擺動(dòng)，最終逼近真實(shí)值。傳統(tǒng)的CORDIC 算法，初始向量為X軸，并依次以45°(arctan 20)、26.57°(arctan 2-1)…進(jìn)行旋轉(zhuǎn)。

如圖1，在不考慮增益因子的情況下，待求向量d需經(jīng)過(guò)2 次逆時(shí)針旋轉(zhuǎn)和1 次順時(shí)針旋轉(zhuǎn)到達(dá)臨近向量c。

圖1 CORDIC 算法角度逼近示意圖

但如果能夠知道待求向量d的范圍在向量b和c之間，并確切知道c的位置，就可以省略a、b和c三次旋轉(zhuǎn)。對(duì)于流水線型結(jié)果來(lái)說(shuō)，就可以省略幾級(jí)流水線；對(duì)迭代式結(jié)構(gòu)來(lái)說(shuō)，就可以減少迭代次數(shù)，同時(shí)降低輸出時(shí)延。正如圖2 中所示，若已知向量d所代表的初始向量對(duì)應(yīng)的坐標(biāo)為(xi,yi)，則可以省略掉前面0～i次運(yùn)算，僅需要i～n次的運(yùn)算。與傳統(tǒng)算法相比，減少了i次運(yùn)算，因此能夠?qū)⑤敵鰰r(shí)延降低i個(gè)時(shí)鐘，并降低一部分硬件資源。但同時(shí)，由于要獲取初始向量d的坐標(biāo)信息，相對(duì)于傳統(tǒng)CORDIC算法，需要占用較多的存儲(chǔ)資源，其多少取決于算法的運(yùn)算次數(shù)和精度；但相對(duì)于查找表方法[4]，其占用的存儲(chǔ)資源則要少很多。也就是說(shuō)[4]，改進(jìn)型CORDIC 算法就是解決了查找表算法占用存儲(chǔ)資源大與傳統(tǒng)CORDIC 算法輸出時(shí)延大之間的矛盾；在占用有限存儲(chǔ)資源，保證計(jì)算精度的情況下，減小了輸出時(shí)延和硬件資源。

圖2 改進(jìn)型CORDIC 算法結(jié)構(gòu)圖

3.2 改進(jìn)型CORDIC 算法的FPGA 實(shí)現(xiàn)

算法實(shí)現(xiàn)結(jié)構(gòu)主要分為三個(gè)模塊：預(yù)處理模塊、初始向量查找表模塊和算法主體及后處理模塊。

整個(gè)設(shè)計(jì)過(guò)程是在QuartusII 7.2 環(huán)境下實(shí)現(xiàn)，采用VHDL 語(yǔ)言與.bdf 原理圖編寫(xiě)；設(shè)計(jì)文件內(nèi)所有數(shù)據(jù)均采用Q14 格式；而函數(shù)floor()表示向負(fù)無(wú)窮舍入，round()表示向最接近的整數(shù)舍入。各模塊的作用如下所述。

3.2.1 預(yù)處理模塊

主要作用：擴(kuò)展輸入角度范圍，并獲得初始向量查找表地址和剩余需旋轉(zhuǎn)角度。

上文中提到CORDIC 算法的輸入角度覆蓋范圍為(-99.88°～99.88°)，所以在計(jì)算前，需將輸入角度范圍擴(kuò)大為[0 ～2π)。這里對(duì)輸入角度theta取其對(duì)的標(biāo)么值，如表1 所示。

表1 輸入角度數(shù)據(jù)格式

擴(kuò)展處理方法的偽碼如圖3。圖中，theta_m為處理后的輸出角度數(shù)據(jù)，其范圍為；verf為theta的象限狀態(tài)值，用于主體算法完成后的后處理；addra為余弦查找表地址，范圍為[0 ～255]；addrb為正弦查找表地址，范圍為[0 ～254]。

設(shè)計(jì)中，初始向量正余弦查找表由一塊ROM 存儲(chǔ)，地址范圍為[0 ～255]，存儲(chǔ)數(shù)據(jù)為故。在硬件實(shí)現(xiàn)時(shí)，僅需將theta_m右移6 位，而；仍需旋轉(zhuǎn)的角度z=theta_m-(addra+1)×26。

3.2.2 初始向量查找表模塊

模塊功能：根據(jù)輸入地址查找相應(yīng)的正余弦值。

利用宏功能模塊生成兩輸入兩輸出的ROM 模塊，其容量為16 bit×256 word。相鄰兩地址所代表的角度差的標(biāo)么值的Q格式為

3.2.3 算法主體及后處理模塊

模塊功能：計(jì)算輸入角度theta_m的正余弦值，并根據(jù)輸入象限狀態(tài)verf對(duì)輸出結(jié)果進(jìn)行調(diào)整，最終得到初始輸入角度theta的正余弦值。

流水線級(jí)數(shù)的確定：角度旋轉(zhuǎn)常量如表2。

表2 角度常量θi=round(arctan(2-i)×214)

故按照傳統(tǒng)的CORDIC 算法需要15 級(jí)流水線。而由于，故采用改進(jìn)型算法后，僅需8 級(jí)流水線，即在初始向量的基礎(chǔ)上擺動(dòng)8 次就可逼近待求向量。由2.2 節(jié)可知，調(diào)整因子，文中忽略不計(jì)。

后處理部分，是根據(jù)verf 進(jìn)行角度theta 的象限判定，并據(jù)此修改輸出結(jié)果。

將上述三部分連接，即可得到改進(jìn)型CORDIC 算法（圖4）。

圖4 改進(jìn)型CORDIC 算法的基本單元

4 仿真結(jié)果

在QuartusII 7.2 開(kāi)發(fā)環(huán)境下對(duì)上述設(shè)計(jì)文件進(jìn)行仿真。圖5 給出了傳統(tǒng)算法與改進(jìn)后算法的仿真結(jié)果，其中，輸入角度theta是利用Matlab 軟件計(jì)算得到的：

Theta涵蓋了[0 ～2π)范圍。傳統(tǒng)算法的輸出結(jié)果較改進(jìn)后算法延遲了7 個(gè)時(shí)鐘。

圖5 傳統(tǒng)與改進(jìn)型CORDIC 算法仿真結(jié)果對(duì)比圖

將兩種算法的仿真數(shù)據(jù)與Matlab 計(jì)算數(shù)據(jù)作對(duì)比，可得[0 ～2π)輸入范圍內(nèi)的誤差曲線，如圖6 所示，其中，叉號(hào)和圓圈曲線分別為余弦誤差和正弦誤差曲線。從圖中可以看出，兩種算法的誤差均在10-4數(shù)量級(jí)內(nèi)，改進(jìn)后算法誤差絕對(duì)值的最大值0.000 3較改進(jìn)前0.000 4降低了約25%。

5 實(shí)驗(yàn)結(jié)果

將上述算法編譯下載至Altera 公司CycloneII EP2C70F896C6 芯片。圖7 為編譯后芯片資源消耗的報(bào)告，編譯工具為QuartusII 7.2 自帶的；表3 將兩份報(bào)告進(jìn)行了對(duì)比。

圖8 顯示了使用嵌入式邏輯分析儀對(duì)算法進(jìn)行硬件測(cè)試的結(jié)果，系統(tǒng)時(shí)鐘為50 MHz，與仿真結(jié)果一致。

6 結(jié)論

將查找表算法結(jié)構(gòu)和傳統(tǒng)CORDIC 算法結(jié)構(gòu)相結(jié)合，提出了一種計(jì)算正余弦函數(shù)的改進(jìn)型的CORDIC 算法，并完成了該算法的仿真設(shè)計(jì)和FPGA 實(shí)現(xiàn)。其結(jié)果表明本文算法占用的存儲(chǔ)資源比查找表算法少，硬件資源比傳統(tǒng)CORDIC 算法少，但與傳統(tǒng)CORDIC 算法相比，卻實(shí)現(xiàn)了同等數(shù)量級(jí)的計(jì)算精度，并減低了將近一半的輸出時(shí)延。將仿真和硬件測(cè)試結(jié)果與Matlab 計(jì)算結(jié)果進(jìn)行了對(duì)比，驗(yàn)證了算法的正確性。如果需要更高的計(jì)算精度，可以增加算法中計(jì)算數(shù)據(jù)的位寬；而且，精度越高，數(shù)據(jù)位寬越大，改進(jìn)后的算法在資源利用方面的優(yōu)勢(shì)就越明顯。

表3 設(shè)計(jì)資源消耗及輸出時(shí)延對(duì)比

圖6 傳統(tǒng)與改進(jìn)型CORDIC 算法誤差曲線對(duì)比圖

圖7 傳統(tǒng)與改進(jìn)型CORDIC 算法資源消耗報(bào)告

圖8 改進(jìn)型CORDIC 算法硬件測(cè)試結(jié)果圖

[1] 劉輝，鄒軒.基于FPGA 和CORDIC 算法的交流電動(dòng)機(jī)直接轉(zhuǎn)矩控制[J].微特電機(jī)，2009，37（8）：57-60.

[2] 吳恒，王淦泉，陳桂林.CORDIC 算法在基于FPGA 的PMSM 控制器中的應(yīng)用[J].電機(jī)與控制學(xué)報(bào)，2009，13（1）：113-118.

[3] Volder J E.The CORDIC trigonometric computing technique[J].IRE Transactions on Electronic Computers，1959，8（3）：330-334.

[4] 孫宇峰，陳國(guó)軍，王大鳴，等.一種高精度正余弦函數(shù)的FPGA實(shí)現(xiàn)方法[J].信息工程大學(xué)學(xué)報(bào)，2007，8（3）：368-370.