基于改進(jìn)的CORDIC算法的FFT復(fù)乘及其FPGA實(shí)現(xiàn)

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算法只需簡(jiǎn)單的移位與加減運(yùn)算就能實(shí)現(xiàn)向量旋轉(zhuǎn)，具有使用資源少、硬件規(guī)模小等優(yōu)勢(shì)。因此在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)，對(duì)CORDIC算法做了一些改進(jìn)，在節(jié)省資源的同時(shí)保證了工作速度。
1 CORDIC算法原理
假設(shè)直角坐標(biāo)系中有一向量A(Xa，Ya)，逆時(shí)針旋轉(zhuǎn)?茲角度后得到另一個(gè)向量B(Xb，Yb)，這個(gè)過程可用如下矩陣表示：

針對(duì)這一特點(diǎn)，可在CORDIC算法上做一點(diǎn)改進(jìn)，把旋轉(zhuǎn)因子所對(duì)應(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)因子所對(duì)應(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)更為簡(jiǎn)單。此CORDIC算法還采用流水線結(jié)構(gòu)提高了運(yùn)算的速度，從當(dāng)前VLSI的發(fā)展趨勢(shì)上來看，芯片內(nèi)的門資源相對(duì)富裕，對(duì)流水線CORDIC的實(shí)現(xiàn)規(guī)模約束很小。此外，流水線CORDIC不存在迭代式CORDIC的反饋回路，使得單元結(jié)構(gòu)更加規(guī)則，有利于VLSI實(shí)現(xiàn)。