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

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

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