- 相關(guān)推薦
基于FPGA的快速并行FFT及其在空間太陽望遠(yuǎn)鏡圖像鎖定系統(tǒng)中的應(yīng)用
摘要：在空間太陽望遠(yuǎn)鏡的在軌高速數(shù)據(jù)處理中，運算時間是影響系統(tǒng)性能的重要環(huán)節(jié)之一。利用FPGA豐富的邏輯單元實現(xiàn)快速傅里葉變換（FFT），解決了在軌實時大數(shù)據(jù)量圖像處理與航天級DSP運算速度不足之間的矛盾；利用溢出監(jiān)測移位結(jié)構(gòu)解決了定點運算的動態(tài)范圍問題。經(jīng)過實驗驗證，各項指標(biāo)均達到了設(shè)計要求。關(guān)鍵詞：FFTFPGA蝶形運算
空間太陽望遠(yuǎn)鏡項目是我國太陽物理學(xué)家為了實現(xiàn)對太陽的高分辨率觀測而提出的科學(xué)計劃。它可以得到空間分辨率為0.1"的向量磁圖和0.5"的X射線圖像，實現(xiàn)這樣高的觀測精度的前提就是采用高精度的姿態(tài)控制系統(tǒng)和高精度的相關(guān)跟蹤系統(tǒng)。從整個系統(tǒng)來看，相關(guān)運算所需的時間成為限制系統(tǒng)性能能否提高的一個重要環(huán)節(jié)。
目前，國際國內(nèi)相關(guān)計算比較通用的實現(xiàn)方法有兩種：用高速DSP或者專用（FFT）處理芯片。用DSP完成相關(guān)計算（關(guān)鍵是FFT）受到航天級DSP性能的限制，現(xiàn)有的航天級DSP（如ADSP21020）計算一個32×32點8bit的二維FFT所用時間需要1.5ms以上，遠(yuǎn)遠(yuǎn)不能滿足系統(tǒng)設(shè)計要求；而現(xiàn)有的FFT處理芯片在處理速度、系統(tǒng)兼容性、抗輻射能力等方面不能滿足空間太陽望遠(yuǎn)鏡所提出的要求。
為克服這一矛盾，本文利用FPGA資源豐富、易于實現(xiàn)并行流水的特點設(shè)計專用的FFT處理芯片來完成復(fù)雜的、大量的數(shù)據(jù)處理；并通過在運算中作溢出監(jiān)測來保證定點運算的精度，從而大大縮短系統(tǒng)的響應(yīng)時間，將極大地提高空間太陽望遠(yuǎn)鏡的在軌實時圖像處理能力；同時由于FPGA具有抗輻射能力，可以提高系統(tǒng)的可靠性，其在航天遙測遙感和星載高速數(shù)據(jù)處理等方面將有廣泛的應(yīng)用前景。
1算法構(gòu)成
1.1FFT算法選擇
提高FFT速度的兩個主要途徑是采用流水結(jié)構(gòu)和并行運算[1]。采用高基數(shù)結(jié)構(gòu)也可以提高速度，只是用FPGA實現(xiàn)時必須綜合考慮系統(tǒng)要求、結(jié)構(gòu)特點及片內(nèi)資源。針對本系統(tǒng)自身特點，這里按時間抽選算法進行分析。由于32不滿足N=4m，所以32點FFT算法不能采用基-4FFT運算。當(dāng)詳細(xì)分析基-2蝶形圖時，有些蝶形運算并不需要做乘法，例如等[2]；對于32點DIT-FFT，一共80個蝶形運算，這種結(jié)構(gòu)就有46個，極大地降低了運算復(fù)雜度。在一維FFT計算效率提高的基礎(chǔ)上對二維FFT采用最常用的行列算法[3]，綜合各項指標(biāo)本系統(tǒng)采用基-2DIT行列算法。
1.2算術(shù)運算方案
本系統(tǒng)是針對32×32點16bit的二維圖像進行快速傅里葉變換（FFT），設(shè)計要求運算在0.5ms之內(nèi)完成，所以采用定點運算更符合系統(tǒng)對時間的要求。對于定點運算，必須用定比例的方法防止溢出，即必須解決動態(tài)范圍問題。下面對其進行理論分析：
若{x(n)}是-N點序列，其DFT為{X(K)}，由Parseval定理得[4]：
由式（1）可知變換結(jié)果的均方值是輸入序列均方值的N倍�？紤]基-2算法的第m級蝶形運算，用Xm(i)、Xm(j)表示原來的復(fù)數(shù)，則新的一對復(fù)數(shù)Xm+1(i)、Xm+1(j)為：
Xm+1(i)=Xm(i)+Xm(j)×W(2)
Xm+1(j)=Xm(i)-Xm(j)×W
其中，W為旋轉(zhuǎn)因子。首先，考慮復(fù)數(shù)的均方程根值。由（2）式可得：
因此，從均方根意義上看，數(shù)據(jù)（實數(shù)或復(fù)數(shù)）復(fù)級都增加（2的平方根）倍。其次，再考慮復(fù)數(shù)的最大模。由（2）式可以證明[5]。
max{|Xm(i)|,|Xm(j)|}≤max{|Xm+1(i)|,|Xm+1(j)|}≤2max{|Xm(i)|,|Xm(j)|}
因此，復(fù)數(shù)數(shù)組的最大模是非減的。所以，對于DITFFT，其每一級的蝶形運算之后數(shù)值都會增加1+(2的平方根)≈2.414倍。在每一次運算完成之后，須將結(jié)果右移2bits以滿足要求。
2系統(tǒng)實現(xiàn)
系統(tǒng)原理如圖1所示，整個FFT運算處理單元分為三部分：存儲單元（兩個輸入/運算存儲器、一個輸出存儲器及旋轉(zhuǎn)因子存儲器）、蝶形運算單元、地址產(chǎn)生器。
2.1存儲器
本系統(tǒng)實時接收前端CCD相機的圖像。為保證CCD相機采集圖像的準(zhǔn)確率，圖像的每一行、每一幀之間都必須有一定的時間間隔,故采用兩個存儲單元作為輸入數(shù)據(jù)和中間數(shù)據(jù)的暫存單元（如圖1所示），以節(jié)省時間實現(xiàn)實時處理。當(dāng)系統(tǒng)工作時，將圖像存入存儲器、計算上一次采集的圖像、將存儲器中的結(jié)果輸出，這三個工作同時進行，用簡單的流水方式減少存儲數(shù)據(jù)所需的時間。旋轉(zhuǎn)因子則預(yù)先存儲在器件的內(nèi)置ROM中。根據(jù)級數(shù)不同選用不同的因子。
2.2蝶形運算單元
一個基-2蝶形運算由一個復(fù)乘和兩個復(fù)加（減）組成，采用完全并行運算，進一步分解為四個實數(shù)乘法，六個實數(shù)加（減）法，分三級并行完成，加上前后輸入輸出的數(shù)據(jù)鎖存，共需要6個時鐘周期。32點的FFT需要16×5=80個基-2的蝶形運算，一幅圖像一共是32行32列，不考慮不需要做乘法的蝶形運算，一路串行共需要6×80×32×2=30720個時鐘周期，采用頻率為10MHz的時鐘，即為3ms。對于蝶形運算的第一、第二級都可以由不帶乘法器的蝶形結(jié)構(gòu)來實現(xiàn)同步并行運算，每一個蝶形運算加上前后的數(shù)據(jù)鎖存僅需4個時鐘周期即可完成；對于第三、第四、第五級，由于帶乘法器不帶乘法器的兩種蝶形運算結(jié)構(gòu)同時存在，必須加入等待時間才可以實現(xiàn)嚴(yán)格同步。同時由于各級計算時間不同，所以不能實現(xiàn)深度流水。因此，采用多路并行及部分流水，在時間上即可滿足系統(tǒng)要求。
上面討論了當(dāng)運算從一級轉(zhuǎn)到另一級時，序列中數(shù)值的幅度一般會增大。因而，運算方法是在內(nèi)循環(huán)中作溢出監(jiān)測。如果沒有溢出，則計算照常進行；若有溢出，則把產(chǎn)生溢出的數(shù)據(jù)右移，一直到?jīng)]有溢出為止。記錄下移位的次數(shù)（0、1或2），并把整個序列右移同樣位數(shù)，移位總數(shù)進行累計，累計數(shù)的負(fù)值作為2的冪，由此得出最終序列的總的比例因子。比例因子s由下式定義[6][7]：
這里bi為比例參數(shù)。
k=0,1,2,…，N-1（6）
根據(jù)公式(6)，F(xiàn)FT的最終結(jié)果要除以比例因子。式中x(n)為原始數(shù)據(jù)，X(k)為除以比例因子之前的結(jié)果，X'(k)為最終結(jié)果，1/s為比例因子的倒數(shù)。
如圖2所示，對于一個基-2蝶形單元，當(dāng)從存儲器中讀取的Bbit輸入數(shù)據(jù)進入蝶形運算單元PE1后，經(jīng)過乘法運算（MU1）乘以旋轉(zhuǎn)因子，數(shù)據(jù)變?yōu)椋˙+Bω）bit，然后作加（減）法，得到蝶形運算結(jié)果（B+Bω+1）bit。為防止溢出，進行移位操作。M1、M2為比例選擇器，根據(jù)不同的級數(shù)，選擇不同的比例因子。最后，輸出數(shù)據(jù)再放回到存儲器中。
3FPGA器件選擇
本設(shè)計采用XILINX公司的VERIEX系列XCV300-4HQ240芯片。該芯片有豐富的可配置邏輯模塊CLBs(ConfigurableLogicBlocks)、大量的觸發(fā)器以及內(nèi)置的不占系統(tǒng)資源的塊RAM。系統(tǒng)最大工作頻率可達200MHz，兼容多種接口標(biāo)準(zhǔn)，有相應(yīng)的航天級產(chǎn)品，是目前市場上為數(shù)不多的能達到此項要求的高性能可編程邏輯器件。
VERTEX系列器件的一個顯著特點是內(nèi)置的延遲鎖相環(huán)DLL（Delay-LockedLoop），它可以減少時鐘傳輸?shù)乃p，每一個DLL可以驅(qū)動兩個全局時鐘信號。DLL可以倍頻，或者1.5、2、2.5、3、4、5、8以及16分頻。VERTEX系列器件內(nèi)部的4-輸入查找表LUTs(Look-UpTables)也具有多種功能：可以作為16×1bit的同步RAM，而且一個塊（Slice）中的兩個LUTs可以組合成一個16×2bit或者一個32×1bit的同步RAM或者一個16×1bit的同步多口RAM。另外，LUTs還可作為一個16bit的移位寄存器使用，該寄存器用來獲取高速或者突發(fā)數(shù)據(jù)非常理想，特別適用于數(shù)字圖像處理中的數(shù)據(jù)存儲[8]。
本設(shè)計充分利用了VERTEX器件的LUTs替代觸發(fā)器和基本門電路搭建乘法器和加法器這兩個顯著的結(jié)構(gòu)特點，節(jié)省大量觸發(fā)器資源，避免了缺少觸發(fā)器而LUTs大量剩余的尷尬；增加了器件利用率、布通率，降低布線延遲。由于本系統(tǒng)最終用于空間太陽望遠(yuǎn)鏡，所以板上時鐘頻率不可超過20MHz。但基于地面測試的需要，特利用DLL對外部時鐘信號進行了倍頻，以提高芯片內(nèi)部的運行速度。
本設(shè)計利用FPGA易于實現(xiàn)并行運算的特點實現(xiàn)專用的FFT處理芯片，解決了在軌實時大數(shù)據(jù)量圖像處理與航天級DSP運算速度不足之間的矛盾，提高了系統(tǒng)實時處理能力。兩維FFT不到400μs即可完成，高于航天級DSP(ADSP21020)1.5ms的處理速度。對太陽米粒組織圖像進行處理（實驗數(shù)據(jù)如表1所示），結(jié)果顯示數(shù)據(jù)誤差都在1%左右。這樣的誤差滿足空間太陽望遠(yuǎn)鏡中的相關(guān)擺鏡的系統(tǒng)要求。實驗證明用高性能FPGA實現(xiàn)空間化的FFT處理芯片是完全可行的。
表1實驗數(shù)據(jù)
序號原始數(shù)據(jù)浮點數(shù)據(jù)定點數(shù)據(jù)誤差%序號原始數(shù)據(jù)浮點數(shù)據(jù)定點數(shù)據(jù)誤差%1-327684201044193280.181719072504851201.432-327681542981550080.461818704594360161.233721697679983040.641918796944596001.644148001062241066880.44201915226885272001.1751608093313937600.48211630431028312320.6661984076389768000.54221475233592336000.0272310465472656720.68231457638986391680.47820000604403606720.45241520058786591360.6091910469973704000.6125816039973704000.61102337658786591360.6026704860403607360.55112012838986391040.30271438465472659200.68121868833592336000.02281158476389768000.54131968031028312320.66291147293313937600.48141953626885272001.1730114561062241067520.501519680944596001.64311176097679983040.641618720594360161.2332114881542981549440.42
【基于FPGA的快速并行FFT及其在空間太陽望遠(yuǎn)鏡圖像鎖定系統(tǒng)中的應(yīng)用】相關(guān)文章：
1394技術(shù)及其在圖像傳輸系統(tǒng)中的應(yīng)用08-06
固定幾何結(jié)構(gòu)的FFT算法及其FPGA實現(xiàn)08-06
基于FPGA的快速傅立葉變換08-06
基于數(shù)字移相的高精度脈寬測量系統(tǒng)及其FPGA實現(xiàn)08-06
VHDL在高速圖像采集系統(tǒng)中的應(yīng)用設(shè)計08-06
基于FPGA/CPLD和USB技術(shù)的無損圖像采集卡08-06