基于改進的CORDIC算法的FFT復乘及其FPGA實現(xiàn)

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

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