《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 基于改進(jìn)的CORDIC算法的FFT復(fù)乘及其FPGA實(shí)現(xiàn)
基于改進(jìn)的CORDIC算法的FFT復(fù)乘及其FPGA實(shí)現(xiàn)
來源：電子技術(shù)應(yīng)用2011年第4期
張 偉，張安堂，肖 宇
空軍工程大學(xué) 導(dǎo)彈學(xué)院，陜西 三原713800
摘要： 根據(jù)定點(diǎn)FFT中旋轉(zhuǎn)因子所對應(yīng)的CORDIC旋轉(zhuǎn)方向可預(yù)先求解的特點(diǎn)，改進(jìn)了CORDIC算法中旋轉(zhuǎn)方向的計(jì)算方法，在節(jié)約乘法器資源的同時(shí)兼顧了速度與精度的要求，并基于改進(jìn)的CORDIC算法，利用FPGA實(shí)現(xiàn)了這種FFT復(fù)乘模塊。仿真結(jié)果表明該設(shè)計(jì)可行，具有一定的實(shí)際意義和應(yīng)用前景。
中圖分類號(hào)： TN713
文獻(xiàn)標(biāo)識(shí)碼： A
文章編號(hào)： 0258-7998(2011)04-0051-04
Improved cordic-based FFT plural-multiplication and its FPGA implementation
Zhang Wei，Zhang Antang，Xiao Yu
The Missile Institute, Air Force Engineering University, Sanyuan 713800，China
Abstract： This paper improved the algorithm of rotate direction in CORDIC according to the characteristic of CORDIC rotation direction of rotation factor can be solved in advance in fixed point FFT, meeting the requirements of high-speed and precision as well as resources-saving. And realized this FFT plural-multiplication module based on improved CORDIC algorithm by using FPGA, and the simulation result shows that it is feasible and has some practical meaning and applied foreground.
Key words : CORDIC algorithm；plural-multiplication；mod correction factor；FPGA


    FFT(快速傅里葉變換)在無線通信、語音識(shí)別、圖像處理和頻譜分析等領(lǐng)域有著廣泛應(yīng)用。在FFT運(yùn)算中，核心操作是蝶形運(yùn)算，而蝶形運(yùn)算的主要操作是向量旋轉(zhuǎn)，實(shí)現(xiàn)向量旋轉(zhuǎn)可用復(fù)數(shù)乘法運(yùn)算來實(shí)現(xiàn)，但復(fù)數(shù)乘耗費(fèi)了FFT運(yùn)算中大量的乘法器資源。CORDIC算法只需簡單的移位與加減運(yùn)算就能實(shí)現(xiàn)向量旋轉(zhuǎn)，具有使用資源少、硬件規(guī)模小等優(yōu)勢。因此在FFT蝶形運(yùn)算中用其代替?zhèn)鹘y(tǒng)FFT運(yùn)算中的復(fù)數(shù)乘法器，可以獲得更好的性能。但傳統(tǒng)CORDIC算法中每次CORDIC迭代方向需由剩余角度的計(jì)算來確定，影響了工作速度。為此，本文根據(jù)定點(diǎn)FFT復(fù)乘中旋轉(zhuǎn)因子的旋轉(zhuǎn)方向可預(yù)先確定的特點(diǎn)，對CORDIC算法做了一些改進(jìn)，在節(jié)省資源的同時(shí)保證了工作速度。
1 CORDIC算法原理
    假設(shè)直角坐標(biāo)系中有一向量A(Xa，Ya)，逆時(shí)針旋轉(zhuǎn)?茲角度后得到另一個(gè)向量B(Xb，Yb)，這個(gè)過程可用如下矩陣表示：
  
 

    針對這一特點(diǎn)，可在CORDIC算法上做一點(diǎn)改進(jìn)，把旋轉(zhuǎn)因子所對應(yīng)的CORDIC旋轉(zhuǎn)系數(shù)預(yù)先存在ROM中（人工計(jì)算旋轉(zhuǎn)系數(shù)比較麻煩，可用MATLAB編一段程序來計(jì)算，并把旋轉(zhuǎn)系數(shù)存為.mif文件以便ROM初始化），而不是把旋轉(zhuǎn)因子角度預(yù)先存在ROM中。這樣，在進(jìn)行CORDIC運(yùn)算時(shí)，直接從ROM中取出旋轉(zhuǎn)系數(shù)，從而減少計(jì)算Zi來確定下一步旋轉(zhuǎn)方向的步驟，減少CORDIC模塊設(shè)計(jì)的復(fù)雜性，提高了運(yùn)算速度，并且旋轉(zhuǎn)系數(shù)不比旋轉(zhuǎn)因子角度占用的ROM資源多。另外由于旋轉(zhuǎn)因子需要進(jìn)行0°、-90°或+90°三種預(yù)旋轉(zhuǎn)，所以預(yù)旋轉(zhuǎn)還要分配兩位二進(jìn)制數(shù)，這樣存儲(chǔ)旋轉(zhuǎn)系數(shù)的ROM就為18位的ROM。
    改進(jìn)的CORDIC算法結(jié)構(gòu)如圖1所示，所有旋轉(zhuǎn)因子所對應(yīng)的CORDIC旋轉(zhuǎn)系數(shù)都存儲(chǔ)在ROM中，通過地址產(chǎn)生器的控制實(shí)現(xiàn)序列與相應(yīng)的旋轉(zhuǎn)因子的復(fù)乘運(yùn)算。與傳統(tǒng)CORDIC算法相比去掉了預(yù)旋轉(zhuǎn)角與已旋轉(zhuǎn)角之差的計(jì)算來確定下一次旋轉(zhuǎn)方向的結(jié)構(gòu)，不但增加了系數(shù)寄存器模塊，而且總體上結(jié)構(gòu)更為簡單。此CORDIC算法還采用流水線結(jié)構(gòu)提高了運(yùn)算的速度，從當(dāng)前VLSI的發(fā)展趨勢上來看，芯片內(nèi)的門資源相對富裕，對流水線CORDIC的實(shí)現(xiàn)規(guī)模約束很小。此外，流水線CORDIC不存在迭代式CORDIC的反饋回路，使得單元結(jié)構(gòu)更加規(guī)則，有利于VLSI實(shí)現(xiàn)。

3.3 模校正因子的實(shí)現(xiàn)
    基本CORDIC算法中在n級迭代執(zhí)行之后，被旋轉(zhuǎn)向量的模已經(jīng)被改變了，算法的完全實(shí)現(xiàn)應(yīng)該附加一個(gè)模校正環(huán)節(jié)，即Xn、Yn乘以模校正因子。對于迭代次數(shù)N大于10的CORDIC算法，其模校正因子可認(rèn)為已趨近常數(shù)K=0.607 25。而直接在流水結(jié)構(gòu)后附加乘法器的直接實(shí)現(xiàn)方法，使原本由移位器和加法器組成的整體結(jié)構(gòu)變得不規(guī)則，同時(shí)乘法器一級速度的變慢會(huì)降低整個(gè)流水的吞吐率[3，4]。

這樣分解后，被旋轉(zhuǎn)向量與K的乘轉(zhuǎn)化為簡單的移位加減運(yùn)算，從而可以解決乘法器一級速度變慢而降低整個(gè)流水線吞吐率的問題。其硬件實(shí)現(xiàn)結(jié)構(gòu)如圖2所示。這種結(jié)構(gòu)進(jìn)一步降低了硬件復(fù)雜度，與前面的流水線CORDIC結(jié)構(gòu)相似，使整體結(jié)構(gòu)更加規(guī)則統(tǒng)一，有利于VLSI實(shí)現(xiàn)。

4 FFT復(fù)乘的FPGA實(shí)現(xiàn)
    由于軟件和DSP實(shí)現(xiàn)的速度較慢，而FPGA資源豐富，組織結(jié)構(gòu)便于采用流水線結(jié)構(gòu)和并行運(yùn)算，其速度快、擴(kuò)展能力強(qiáng)，所以CORDIC算法的移位、加減法運(yùn)算和流水線結(jié)構(gòu)更容易在FPGA上實(shí)現(xiàn)。本文在Altera公司的QuartusⅡ7.2軟件環(huán)境下使用VHDL，利用上述各種算法設(shè)計(jì)了16 bit寬的FFT復(fù)乘模塊并在CycloneⅡ EP2C35F672C6芯片上進(jìn)行驗(yàn)證。
    圖3為改進(jìn)的16級流水線結(jié)構(gòu)的CORDIC算法實(shí)現(xiàn)復(fù)乘模塊的頂層結(jié)構(gòu)圖，address為ROM的地址，Xi_re、Xi_im為輸入序列的實(shí)部和虛部，Xo_re、Xo_im為旋轉(zhuǎn)后的實(shí)部和虛部。輸入數(shù)據(jù)為16 bit寬，為提高精度，對所有內(nèi)部信號(hào)及輸出信號(hào)都用20 bit的補(bǔ)碼。整個(gè)復(fù)乘主要由系數(shù)ROM、預(yù)旋轉(zhuǎn)、16級流水線CORDIC迭代、系數(shù)寄存器和模校正因子K 5個(gè)模塊組成。

    小，但不能完全消除。

    圖5為改進(jìn)的CORDIC算法實(shí)現(xiàn)FFT復(fù)乘資源消耗與最高工作速度情況。傳統(tǒng)的復(fù)乘要4個(gè)乘法器，所以傳統(tǒng)的復(fù)乘要實(shí)現(xiàn)16 bit位寬復(fù)乘需用此芯片中的8個(gè)9 bit乘法單元，而從資源消耗情況來看，改進(jìn)的CORDIC算法實(shí)現(xiàn)此復(fù)乘沒有用乘法器，整個(gè)邏輯單元消耗也只有4%；另外基于改進(jìn)的CORDIC算法的復(fù)乘最高工作頻率達(dá)到了190 MHz，與傳統(tǒng)CORDIC算法的復(fù)乘速度（約130 MHz）相比有較大提高，在節(jié)約資源的同時(shí)提高了工作速度。

    本文利用定點(diǎn)FFT復(fù)乘運(yùn)算中旋轉(zhuǎn)因子的旋轉(zhuǎn)系數(shù)可預(yù)先求出的特點(diǎn)，采用改進(jìn)流水線結(jié)構(gòu)的CORDIC算法，與傳統(tǒng)的CORDIC算法的復(fù)乘相比，不僅不需要乘法器實(shí)現(xiàn)了FFT運(yùn)算中序列與旋轉(zhuǎn)因子的復(fù)數(shù)乘運(yùn)算，并且在節(jié)約資源的同時(shí)提升了工作速度。這種基于改進(jìn)的CORDIC算法的復(fù)乘運(yùn)算對提高FFT處理器的速度和減少資源消耗有較大意義。同時(shí)，利用VHDL語言，采用模塊化設(shè)計(jì)思想，使得本設(shè)計(jì)可移植性強(qiáng)、通用性好，只需作少量改動(dòng)（如增加位寬，增加迭代次數(shù)），便可滿足精度上的更高要求，具有一定的工程實(shí)際意義和應(yīng)用前景。
參考文獻(xiàn)
[1] 李成詩，初建朋.基于CORDIC的一種高速實(shí)時(shí)定點(diǎn)FFT的FPGA實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2004，21(4).
[2] 吳偉，唐斌.現(xiàn)代雷達(dá)中的高速FFT設(shè)計(jì)[J].空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2005(10).
[3] KHARRAT M W，LOULOU M，MASMOUDI N，et al.A new method to implement CORDIC algorithm[C].IEEE International Conference on Electronic，Circuit and Systems，2001(2)：715-718.
[4] 楊宇，毛志剛，來逢昌.一種改進(jìn)的流水線CORDIC算法結(jié)構(gòu)[J].微處理機(jī)，2006(8).
[5] 李滔.流水線CORDIC算法及其應(yīng)用研究[D].北京理工大學(xué)，1999.

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。