改進(jìn)的并行CORDIC算法研究及其FPGA實(shí)現(xiàn)

1、    改進(jìn)的并行CORDIC算法研究及其FPGA實(shí)現(xiàn)        張 甜， 王祖強(qiáng)， 徐 輝 時間:2008年06月18日     字 體: 大 中 小        關(guān)鍵詞:        摘要：關(guān)鍵詞：CORDIC(Coordinated Rotation Digital

2、 Computer)，即協(xié)調(diào)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)，可廣泛應(yīng)用于基本函數(shù)的計(jì)算，如DSP、FFT、DCT等技術(shù)函數(shù)的計(jì)算。CORDIC算法是Jack Volder于1959年首先提出的。為了擴(kuò)展可解決的基本函數(shù)個數(shù)，J.Walter于1971年提出了統(tǒng)一的CORDIC算法(The Unified Cordic Algorithms)；2004年，Tso-Bing Juang等又提出了一種改進(jìn)的并行的CORDIC算法，該改進(jìn)的算法主要運(yùn)用BBR(Binary-To-Bipolar Recoding)和MAR(Microrotation Angle Recoding)，大大提高了CORDIC算法的迭代速度

3、，并且達(dá)到了很高的精度。隨著可編程邏輯器件規(guī)模的增大和應(yīng)用范圍的擴(kuò)大，使得利用硬件電路實(shí)現(xiàn)該算法成為可能并具有良好的應(yīng)用價值。1 CORDIC算法原理CORDIC算法可分為旋轉(zhuǎn)(rotation)和定向(vectoring)兩種方式，還可分為圓形坐標(biāo)、雙曲線坐標(biāo)和線形坐標(biāo)三種方式，圓形坐標(biāo)下旋轉(zhuǎn)方式的原理公式如下：式中，xi,yi和xi+1,yi+1分別表示旋轉(zhuǎn)前后的向量，i-1,1表示每次旋轉(zhuǎn)的方向。從公式可知，該運(yùn)算只有移位和相加(相減)運(yùn)算。為了獲得i的值，需另設(shè)一個變量zi表示每次旋轉(zhuǎn)后的角度與目標(biāo)角度的差值，然后利用公式zi+1=zi-i·arctan(2-i)進(jìn)行計(jì)算。根

4、據(jù)Jack Volder的推導(dǎo)，經(jīng)過n次迭代，最終可以得到迭代公式如下：通過上面的算法介紹可以看出，每次都要先通過計(jì)算zi+1和zi才能得到i的值，這樣降低了運(yùn)算速度。參考文獻(xiàn)3就是在此基礎(chǔ)上，提出了一種提前算出i的方法，使得速度得以提高。2 并行CORDIC算法原理把需要旋轉(zhuǎn)的角度范圍限定在-/4/4之間，并把它分解成下式：3 利用FPGA實(shí)現(xiàn)算法利用FPGA實(shí)現(xiàn)算法時,采用32位精度，即B=32。根據(jù)m計(jì)算公式可以計(jì)算出m=11。根據(jù)輸入的值和公式(6)，可以計(jì)算出前11個值。根據(jù)已經(jīng)計(jì)算出的表1可得出。再根據(jù)公式(8)，(9)計(jì)算出剩下的值。經(jīng)過移位器，加法器最終可以得到旋轉(zhuǎn)后的向量坐標(biāo)

5、。根據(jù)上述原理，需要移位40次。所以可通過反復(fù)調(diào)用圖1所示的模塊來節(jié)約資源。對于本算法，第i+1個模塊的輸入為第i個模塊的輸出，因此，對模塊的工作時序有一定的要求。針對FPGA中寄存器資源較為豐富的特點(diǎn)，在上述模塊的輸入輸出端分別加入寄存器，對輸入和輸出進(jìn)行鎖存;使用兩個進(jìn)程描述移位加法和控制信號，并且使用不同的時鐘信號作為敏感信號;為了保持整個設(shè)計(jì)的同步性，又采用了兩相門控時鐘進(jìn)行控制(如圖2所示)。圖中clk_in作為輸入寄存器的時鐘，而clk_out作為輸出寄存器的時鐘。兩相門控時鐘生成的相關(guān)程序如下：always (cnt)begincase (cnt)2d0: clk_out,clk

6、_in=2b01;2d1: clk_out,clk_in=2b10;2d2: clk_out,clk_in=2b00;default:clk_out,clk_in=2b00;endcaseend4 仿真結(jié)果本文在Quartus II環(huán)境下對利用Verilog編寫的RTL代碼進(jìn)行了綜合，使用了115個LAB。由于在一片F(xiàn)PGA芯片中可集成其他相關(guān)模塊，在系統(tǒng)設(shè)計(jì)中具有良好的應(yīng)用價值。對其進(jìn)行時序分析，本設(shè)計(jì)可達(dá)到的最大時鐘為58MHz，滿足高速系統(tǒng)設(shè)計(jì)的要求。圖3是在Quartus II下以初始角度0度、旋轉(zhuǎn)角度30度為例的一個仿真結(jié)果，經(jīng)過118個時鐘周期后可以得到旋轉(zhuǎn)后的正弦值和余弦值。通過理論分析及仿真實(shí)驗(yàn)結(jié)果可以看出，這種新的并行CORDIC算法在FPGA上實(shí)