基于CORDIC算法的快速NCO設計_龍翔

1、總第 246期 2010年第 4期計算機與數(shù)字工程Computer &Digital EngineeringVol. 38No. 4 146基于 COR D IC 算法的快速 NCO 設計 3龍 翔(華南農業(yè)大學 廣州 510642摘 要 NCO 在軟件無線電 、 , 通過 FP GA 流水線實現(xiàn)了 CORDIC 算法 , 可替代傳統(tǒng) ROM FP GA 進行仿真及綜合 , 驗證了 該設計的正確性及可行性 。關鍵詞 CORDIC 算法 ;中圖分類號 A Rapid NCO Design Based on CORDIC Algorit hmL ong Xiang(South China

2、Agricultural University , Guangzhou 510642Abs t rac t NCO has a wide range of applications on software 2defined radio , digital signal processing. Function generator is a key part of NCO. The algorithm of CORDIC is achieved by FP GA pipeline , and it can alternative the traditional ROM look 2up tabl

3、e method. The correctness and feasibility of this design is verified by simulate and synthesize the FP GA of Altera and Xilinx Company.Ke y Words algorithm of CORDIC , FP GA , NCOClass Nu m ber TN9111 引言數(shù)字控制振蕩器 (NCO ,Numerical Controlled Oscillator 是一種基于輸入數(shù)值輸出特定波形的裝 置 , 它在當今通信系統(tǒng)中有廣泛的應用 , 是軟件無 線電 1,6

4、、 直接數(shù)字頻率合成 2(DDS ,Direct digital synt hesizer 、 快速傅立葉變換 3(FF T , Fast Fou 2 rier Transform 等的重要組成部分 , 同時也是決定 其性能的主要部件之一 。傳統(tǒng)的實現(xiàn)方法采用查找表 , 簡單 、 準確 , 但其 存放相位到幅度轉換的查找表 ROM 的大小和相 位精度的位數(shù)成指數(shù)關系 。當精度要求很高的時 候需要大容量 ROM , 使系統(tǒng)的處理速度降低 。一 些改進的查表法通過壓縮 ROM 空間實現(xiàn) 。隨著 微電子技術的發(fā)展 , 使用實時計算來替代查表能有 效地提高系統(tǒng)處理速度 。 在實時算法中 , 泰勒級數(shù)

5、法和反函數(shù)求值法是不錯的選擇 , 但泰勒級數(shù)法的 實現(xiàn)需要乘法器 , 在硬件的復雜性和速度上受到一 些限制 ; 反函數(shù)求值法在速度上要比坐標旋轉數(shù)字 計 算 機 (CORDIC , Coordinate Rotation Digital Comp uter 算法慢 。而 CORDIC 算法在硬件實現(xiàn) 上只需要移位和加 /減法即可完成復雜的計算功 能 , 能很好地兼顧速度 、 精度 、 簡單 、 高效等方面 。2 NCO 的原理NCO 通常在通信系統(tǒng)中用于產生可數(shù)控的周 期信號 , 它有實時計算法和查表法等多種實現(xiàn)方 式 。 實時計算法通過實時計算產生周期信號 ; 而查 表法是一種最簡單 、 快

6、速有效的方法 , 即事先根據 各個 NCO 正弦波相位計算好相位的正弦值 , 并以 相位角度作為地址把該相位正弦值數(shù)據存儲在表 中 , 然后通過相位累加產生地址信息讀取當前時刻3收稿日期 :2009年 11月 12日 , 修回日期 :2009年 12月 25日 作者簡介 :龍翔 , 男 , 碩士 , 研究方向 :計算機測試與智能控制 。 2010年第 4期 計算機與數(shù)字工程 147 的相位值在表中對應的正弦值 , 從而產生所需頻率 的正弦波 。 圖 1為 NCO 結構框圖。 圖 1 NCO 結構框圖 圖 1中 NCO 的工作過程如下 :每來一個時鐘 脈沖 , N 位累加器將 M 存器輸出的累加

7、相位數(shù)據相加 , 相位寄存器的輸入端 加器輸入端 , 與頻率控制數(shù)據 M 相加 ; 另一方面將這個值作為 取樣地址值送入相位 /幅度轉換電路 , 相位 /幅度轉 換電路根據這個地址輸出相位的波形數(shù)據 。累加 器在基準時鐘的作用下進行線性相位累加 , 當相位 累加器加滿時產生一次溢出 , 完成一個周期 , 這個 周期也就是 NCO 信號的頻率周期 。 一個 N 位的累加器需要 2N 個時鐘周期才會 產生一次溢出 , 如果系統(tǒng)時鐘為 f clk , 根據 Nyquist 抽樣定理 NCO 的最大輸出頻率為 f clk /2, 而在實 際設計中 , 一般不應大于 0. 4f clk 。 其頻率分辨率

8、為 f =f clk /2N , 如果每一個周期加一個數(shù) L , 則產生 的頻率為 f out =L 3f clk /2N , L 是每個周期的相位增量 , 也就是 。 所以輸出頻率為 :f out =3f clk /2N(1式 (1 中可以根據要求的輸出頻率得出相應相位增量 。3 CORDIC 算法CORDIC 算法是 Volder45于 1959年在美國 航空控制系統(tǒng)的設計中提出來的 , 它是一種用于計 算運算函數(shù)的循環(huán)迭代算法 。其基本思想是用一 系列與運算基數(shù)相關的角度的不斷偏擺 , 從而逼近 所需旋轉的角度 。從廣義上講它是一個數(shù)值計算 逼近的方法 。 這些固定的角度與計算基數(shù)有關

9、, 運 算只有移位和加減 。傳統(tǒng)上計算三角函數(shù)和其它 一些硬件不易實現(xiàn)的函數(shù) , 一般使用查表法 、 多項 式展開或近似的方法 。 這些方法不能兼顧速度 、 精 度 、 簡單性等方面的要求 。 CORDIC 算法正是為解 決這種問題而產生的 。 它從算法本身入手 , 將復雜 的算法分解成一些在硬件中容易實現(xiàn)的基本算法 , 如加法 、 移位等 , 從而使得這些算法在硬件上可以得到較好的實現(xiàn) 。 CORDIC 算法有圓周模式 、 雙曲 線模式和線性模式等三種工作模式 7, 可用來計算 包括乘 、 除 、 平方根 、 正弦 、 余弦 、 反正切 、 向量旋轉(即復數(shù)乘法 以及指數(shù)運算等 8。在本設計

10、中采用圓周模式 , 對其它不作論述 。如圖 2所示 , a(X a , Y a , b(b 這個過程可以用矩陣形式表示如下 :X b Y =cos -sin sin co s X a Y a (2把 co s提出來 ,式 (2 可以重新表示為 :X b Y =cos1-tantan1X a Y a(3如果向量 a (X a , Y a 經過 n 次旋轉才到達向量b (X b , Y b , 如圖 3所示 。 其中第 i 次旋轉的角度為i , 那么第 i次旋轉的表達式為 :X i +1Y i +1=cos i 1-tanitan i1X i Y i(4到此為止沒有任何簡化 , 為了便于硬件實現(xiàn)限

11、制tan i =±2-i , 即 i =±arctan2-i , 的值可以存放 在一個小的查找表中 。通過一系列連續(xù)的小角度 旋轉 , 可以得到任意小的旋轉角度 。旋轉角度總和為 =i =0i, 令 S i=-1; +1, 當 S i =-1時表示向量是逆時針旋轉 , 當 S i =+1時表示向量是順 時針旋轉 。 這時式 (4變?yōu)?:X i +1Y i +1=cos i 1-S i 2-S i 2-i1X i Y i(5式 (5 中的cos i =cos S i arctan2i=co s arctan2i隨著旋轉次數(shù)的增加 , 該式收斂為一個常數(shù) k :k =i =0c

12、os (arctan2-i 0. 607253(6式中 k 是一個常數(shù)增益 , 暫時不考慮這個增益因 子, 式 (5 可以寫成 : X i +1Y i +1=1-S i 2-S i 2-i1X i Y i(7 148 龍 翔 :基于 CORDIC 算法的快速 NCO 設計 第 38卷式 (7 就是 CORDIC 的迭代式 , 它只需要通過 移位和相加就可以完成矢量旋轉 。 設 Z 0是 a, b 兩向量的夾角 , 要使 a 旋轉到 b, 則S i 的符號由第 i 次旋轉時的角度 Z i 決定 , Z i =Z 0-i-1n =0n, 它們的關系如下 :Z i<0時 , S i=-1; Z

13、 i 0時 , S i =+1(特殊情況下 , Z 0<0時 , S i =-1; Z 00時 , S i =+1 。向量 a 向量 b 逼迫的精度由迭代的次數(shù)決定 , 迭代的次數(shù)越多 , 逼迫的精度就越高 n 次 n得到的最終結果為 :X n =k( X Y a Y n =k(Y a co s +X a sin Z n =Z 0-(8對于一組特殊的初始值 : X a =k Y a =0Z 0=(9得到的結果為 :X n =co s Y n =sinZ n =(10從式 (8 、(9 和 (10 可以看出 , 給適當初值 , 通 過本 算 法 可 以 計 算 出 cosine 和 sin

14、e , 這 就 是CORDIC 算法的旋轉模式 。4 4. 1, 迭代角度初始最=arctan (2-0 =45°, 可以看出 , 旋轉角 的范圍是和迭代次數(shù) n 相關的 :- n-1i =0arctan (2-i n-1i =0arctan (2-i。從表 2容易得到 取值為-99. 88°, 99. 88°即近似為 (-/2, /2 區(qū)間內 ,所以通常使用 CORDIC 算法可以直接計算 (-/2,/2 區(qū)間內的 sine 和 cosine 值 , 由相位累加器產 生的相位值是在 (0, 2 區(qū)間 , 這就需要將輸入相位 值的最高位和次高位截取下來作為象限判決

15、的依 據 , 表 1給出了象限判決規(guī)則 。 表 1 象限映射表 最高二位 象限cosine sine 00 X Y 01 Y 補 X 10 X 補 Y 補 11YX 補 表 2 不同的 N 值對應的角度范圍N123456maxNi =0i 45°71. 56°85. 60°92. 73°96. 30°98. 09°98. 99°N 78910111213maxNi =0i99. 44°99. 67°99. 77°99. 83°99. 85°99. 87°99. 88

16、°4. 2 流水線結構與 NCO 頂層電路圖CORDIC 旋轉的移位 2相加流水結構 , 每一級 流水線單元只需 3個加減法器 、 2個移位寄存器和 1個系數(shù)存儲器, 非常節(jié)省資源 , 如需提高精度 , 只需簡單地增加流水單元即可 , 擴展性很好 。這種流 水線結構在正常工作時只需一個時鐘周期就可輸 出一個數(shù)據 , 可實現(xiàn)高速實時處理 , 非常適合于在 FP GA 中實現(xiàn) 。 圖 4是 NCO 頂層電路結構圖 , 頻率控制字寄存器將接收到的頻率控制字送入相位 累加器 , 相位累加器對系統(tǒng)時鐘進行計數(shù) , 每到達 輸入頻率控制字的值 , 即對相位進行累加 , 隨后將 累加值的高 16位

17、送入相位相加器 , 與相位控制字 寄存器接收到的初始相位進行相加 , 得到當前的相 位值 。 然后把當前相位值的最高位用作象限判定 , 并把低 15位擴展 1位符號位用于基于 CORDIC 的 函數(shù)發(fā)生器 。圖 4 NCO 頂層電路圖4. 3 NCO 仿真綜合結果與驗證在本設計中 , 使用系統(tǒng)時鐘 100M , 相位累加器 32位 , 由式 (2 可得設計的頻率分辨率為 0. 024Hz ,f out =2M Hz 時 , =(85899345 10; f out =1M Hz 時 , =(42949672 10。 由圖 5可以看出 , 當頻率控制字 為 85899345時 , 輸出正弦波的周

18、期為 500ns , 即正弦 波的頻率為 2MHz ; 當頻率控制字為 42949672時 , 輸 出正 弦 波 的 周 期 為 1000ns , 即 正 弦 波 的 頻 率 為 2010年第 4期 計算機與數(shù)字工程 149 1M Hz , 仿真正確。 本設計的所有模塊用 HDL 語言編寫 , 用 ModesSim 進行了前后功能仿真 , 最后分別 實現(xiàn)在 Altera 和 X ilinx FPG A 中 , 綜合結果如表 3所示。表 3 設計綜合結果廠商FP GA 器件占用資源最高時鐘Altera Cyclone II EP2C35C61186L Es 224XilinxSpartan II

19、 XC2S10026739Slices129 圖 5 NCO 仿真結果5 結語本論文分析了 CORDIC 算法及其在 FP GA 器 件中利用 CORDIC 迭代算法實現(xiàn) NCO , 并通過流 水線 操 作 提 高 設 計 吞 吐 率 和 速 度 。結 果 表 明 , CORDIC 迭代算法的數(shù)控振蕩器 , 僅用移位寄存器和加法器就可產生數(shù)字控制的正余弦信號 , 省去了 傳統(tǒng) NCO 龐大的存儲器資源 , 還保留了一般數(shù)控 振蕩器頻率分辨率高 、 頻率變化速度快 、 相位可連 續(xù)線性變化 、 生成的正弦 /余弦信號正交特性好等特點 , 非常適用于在軟件無線電中進行高速高精度 的數(shù)字調制解調 。

20、參 考 文 獻1楊小牛 , 樓才義 , 徐建良 . 軟件無線電原理與應用 M .北京 :電子工業(yè)出版社 ,2001,12Wang Yang , Zhu ke Hao. A Direct DigitalCORDIC Algorithm FP J IEEE Transactions on :8328353Meyer 2Baese. 數(shù)字信號處理的 FP GA 實現(xiàn) M .劉凌 , 胡永生 , 譯 . 北京 :清華大學出版社 ,20024Volder , J. The CORDIC T rigonometric Computing T ech 2nique J.IRE T rans. Electro

21、nic C omputing ,1959, EC 28(9 :3303345Andraka R. A survey of CORDIC algorithms for FP GAbased computers C /Sixth International Symposium on Field Programmable Gate Arrays. Monterey ,19986A. Shoari , M. Kamarei , A. Radmand. Implementa 2tion of Costas loop using CORDIC algorithm for soft 2ware radio

22、applications J .IEE Proc. Commun. , 2005,152(17Walther , J. S. A unified algorithm for elementaryf unctions C /Spring Joint Computer Conference , 1971:3793858Valls J , Sansaloni T , Torres V , et al. The use ofCORDIC in software defined radiosJ.IEEE Commu 2nications Magazine ,2006(9 :4650(上接第 127頁 參 考 文 獻1張文修 , 梁怡 . 遺傳算法的數(shù)學基礎 M .第二版 . 西安 :西安交通大學出版社 ,2003,52加 韓家煒 , 堪博 . 數(shù)據挖掘概