基于FPGA的快速并行FFT及其在空間太陽(yáng)望遠鏡圖像鎖定系統中的應用

摘要：在空間太陽(yáng)望遠鏡的在軌高速數據處理中，運算時(shí)間是影響系統性能的重要環(huán)節之一。利用FPGA豐富的邏輯單元實(shí)現快速傅里葉變換（FFT），解決 了在軌實(shí)時(shí)大數據量圖像處理與航天級DSP運算速度不足之間的矛盾；利用溢出監測移位結構解決了定點(diǎn)運算的動(dòng)態(tài)范圍問(wèn)題。經(jīng)過(guò)實(shí)驗驗證，各項指標均達到了設計要求。 關(guān)鍵詞：FFT FPGA 蝶形運算 空間太陽(yáng)望遠鏡項目是我國太陽(yáng)物理學(xué)家為了實(shí)現對太陽(yáng)的高分辨率觀(guān)測而提出的科學(xué)計劃。它可以得到空間分辨率為0.1"的向量磁圖和0.5"的X射線(xiàn)圖像，實(shí)現這樣高的觀(guān)測精度的前提就是采用高精度的姿態(tài)控制系統和高精度的相關(guān)跟蹤系統。從整個(gè)系統來(lái)看，相關(guān)運算所需的時(shí)間成為限制系統性能能否提高的一個(gè)重要環(huán)節。 目前，國際國內相關(guān)計算比較通用的實(shí)現方法有兩種：用高速DSP或者專(zhuān)用（FFT）處理芯片。用DSP完成相關(guān)計算（關(guān)鍵是FFT）受到航天級DSP性能的限制，現有的航天級DSP（如ADSP21020）計算一個(gè)32%26;#215;32點(diǎn)8bit的二維FFT所用時(shí)間需要1.5ms以上，遠遠不能滿(mǎn)足系統設計要求；而現有的FFT處理芯片在處理速度、系統兼容性、抗輻射能力等方面不能滿(mǎn)足空間太陽(yáng)望遠鏡所提出的要求。 為克服這一矛盾，本文利用FPGA資源豐富、易于實(shí)現并行流水的特點(diǎn)設計專(zhuān)用的FFT處理芯片來(lái)完成復雜的、大量的數據處理；并通過(guò)在運算中作溢出監測來(lái)保證定點(diǎn)運算的精度，從而大大縮短系統的響應時(shí)間，將極大地提高空間太陽(yáng)望遠鏡的在軌實(shí)時(shí)圖像處理能力；同時(shí)由于FPGA具有抗輻射能力，可以提高系統的可靠性，其在航天遙測遙感和星載高速數據處理等方面將有廣泛的應用前景。 1 算法構成 1.1 FFT算法選擇 提高FFT速度的兩個(gè)主要途徑是采用流水結構和并行運算[1]。采用高基數結構也可以提高速度，只是用FPGA實(shí)現時(shí)必須綜合考慮系統要求、結構特點(diǎn)及片內資源。針對本系統自身特點(diǎn)，這里按時(shí)間抽選算法進(jìn)行分析。由于32不滿(mǎn)足N=4m，所以32點(diǎn)FFT算法不能采用基-4 FFT運算。當詳細分析基-2蝶形圖時(shí)，有些蝶形運算并不需要做乘法，例如 等[2]；對于32點(diǎn)DIT-FFT，一共80個(gè)蝶形運算，這種結構就有46個(gè)，極大地降低了運算復雜度。在一維FFT計算效率提高的基礎上對二維FFT采用最常用的行列算法[3]，綜合各項指標本系統采用基-2 DIT行列算法。 1.2 算術(shù)運算方案 本系統是針對32%26;#215;32點(diǎn)16bit的二維圖像進(jìn)行快速傅里葉變換（FFT），設計要求運算在0.5ms之內完成，所以采用定點(diǎn)運算更符合系統對時(shí)間的要求。對于定點(diǎn)運算，必須用定比例的方法防止溢出，即必須解決動(dòng)態(tài)范圍問(wèn)題。下面對其進(jìn)行理論分析： 若{x(n)}是-N點(diǎn)序列，其DFT為{X(K)}，由Parseval定理得[4]： 由式（1）可知變換結果的均方值是輸入序列均方值的N倍?？紤]基-2算法的第m級蝶形運算，用Xm(i)、Xm(j)表示原來(lái)的復數，則新的一對復數Xm+1(i)、Xm+1(j)為： Xm+1(i)=Xm(i)+Xm(j)%26;#215;W (2) Xm+1(j)=Xm(i)-Xm(j)%26;#215;W 其中，W為旋轉因子。首先，考慮復數的均方程根值。由（2）式可得： 因此，從均方根意義上看，數據（實(shí)數或復數）復級都增加（2的平方根）倍。其次，再考慮復數的最大模。由（2）式可以證明[5]。 max{|Xm(i)|,|Xm(j)|}≤max{|Xm+1(i)|,|Xm+1(j)|}≤2max{|Xm(i)|,|Xm(j)|} 因此，復數數組的最大模是非減的。所以，對于DITFFT，其每一級的蝶形運算之后數值都會(huì )增加1+(2的平方根)≈2.414倍。在每一次運算完成之后，須將結果右移2bits以滿(mǎn)足要求。 2 系統實(shí)現 系統原理如圖1所示，整個(gè)FFT運算處理單元分為三部分：存儲單元（兩個(gè)輸入/運算存儲器、一個(gè)輸出存儲器及旋轉因子存儲器）、蝶形運算單元、地址產(chǎn)生器。 2.1 存儲器 本系統實(shí)時(shí)接收前端CCD相機的圖像。為保證CCD相機采集圖像的準確率，圖像的每一行、每一幀之間都必須有一定的時(shí)間間隔,故采用兩個(gè)存儲單元作為輸入數據和中間數據的暫存單元（如圖1所示），以節省時(shí)間實(shí)現實(shí)時(shí)處理。當系統工作時(shí)，將圖像存入存儲器、計算上一次采集的圖像、將存儲器中的結果輸出，這三個(gè)工作同時(shí)進(jìn)行，用簡(jiǎn)單的流水方式減少存儲數據所需的時(shí)間。旋轉因子則預先存儲在器件的內置ROM中。根據級數不同選用不同的因子。 2.2 蝶形運算單元 一個(gè)基-2蝶形運算由一個(gè)復乘和兩個(gè)復加（減）組成，采用完全并行運算，進(jìn)一步分解為四個(gè)實(shí)數乘法，六個(gè)實(shí)數加（減）法，分三級并行完成，加上前后輸入輸出的數據鎖存，共需要6個(gè)時(shí)鐘周期。32點(diǎn)的FFT需要16%26;#215;5=80個(gè)基-2的蝶形運算，一幅圖像一共是32行32列，不考慮不需要做乘法的蝶形運算，一路串行共需要6%26;#215;80%26;#215;32%26;#215;2=30720個(gè)時(shí)鐘周期，采用頻率為10MHz的時(shí)鐘，即為3ms。對于蝶形運算的第一、第二級都可以由不帶乘法器的蝶形結構來(lái)實(shí)現同步并行運算，每一個(gè)蝶形運算加上前后的數據鎖存僅需4個(gè)時(shí)鐘周期即可完成；對于第三、第四、第五級，由于帶乘法器不帶乘法器的兩種蝶形運算結構同時(shí)存在，必須加入等待時(shí)間才可以實(shí)現嚴格同步。同時(shí)由于各級計算時(shí)間不同，所以不能實(shí)現深度流水。因此，采用多路并行及部分流水，在時(shí)間上即可滿(mǎn)足系統要求。 上面討論了當運算從一級轉到另一級時(shí)，序列中數值的幅度一般會(huì )增大。因而，運算方法是在內循環(huán)中作溢出監測。如果沒(méi)有溢出，則計算照常進(jìn)行；若有溢出，則把產(chǎn)生溢出的數據右移，一直到?jīng)]有溢出為止。記錄下移位的次數（0、1或2），并把整個(gè)序列右移同樣位數，移位總數進(jìn)行累計，累計數的負值作為2的冪，由此得出最終序列的總的比例因子。比例因子s由下式定義[6][7]： 這里bi為比例參數。 k=0,1,2,…，N-1 （6） 根據公式(6)，FFT的最終結果要除以比例因子。式中x(n)為原始數據，X(k)為除以比例因子之前的結果，X"(k)為最終結果，1/s為比例因子的倒數。 如圖2所示，對于一個(gè)基-2蝶形單元，當從存儲器中讀取的Bbit輸入數據進(jìn)入蝶形運算單元PE1后，經(jīng)過(guò)乘法運算（MU1）乘以旋轉因子，數據變?yōu)椋˙+Bω）bit，然后作加（減）法，得到蝶形運算結果（B+Bω+1）bit。為防止溢出，進(jìn)行移位操作。M1、M2為比例選擇器，根據不同的級數，選擇不同的比例因子。最后，輸出數據再放回到存儲器中。 3 FPGA器件選擇 本設計采用XILINX公司的VERIEX系列XCV300-4HQ240芯片。該芯片有豐富的可配置邏輯模塊CLBs(Configurable Logic Blocks)、大量的觸發(fā)器以及內置的不占系統資源的塊RAM。系統最大工作頻率可達200MHz，兼容多種接口標準，有相應的航天級產(chǎn)品，是目前市場(chǎng)上為數不多的能達到此項要求的高性能可編程邏輯器件。 VERTEX系列器件的一個(gè)顯著(zhù)特點(diǎn)是內置的延遲鎖相環(huán)DLL（Delay-Locked Loop），它可以減少時(shí)鐘傳輸的衰減，每一個(gè)DLL可以驅動(dòng)兩個(gè)全局時(shí)鐘信號。DLL可以倍頻，或者1.5、2、2.5、3、4、5、8以及16分頻。VERTEX系列器件內部的4-輸入查找表LUTs(Look-Up Tables)也具有多種功能：可以作為16 %26;#215;1bit的同步RAM，而且一個(gè)塊（Slice）中的兩個(gè)LUTs可以組合成一個(gè)16%26;#215;2bit或者一個(gè)32%26;#215;1bit的同步RAM或者一個(gè)16%26;#215;1bit的同步多口RAM。另外，LUTs還可作為一個(gè)16bit的移位寄存器使用，該寄存器用來(lái)獲取高速或者突發(fā)數據非常理想，特別適用于數字圖像處理中的數據存儲[8]。 本設計充分利用了VERTEX器件的LUTs替代觸發(fā)器和基本門(mén)電路搭建乘法器和加法器這兩個(gè)顯著(zhù)的結構特點(diǎn)，節省大量觸發(fā)器資源，避免了缺少觸發(fā)器而LUTs大量剩余的尷尬；增加了器件利用率、布通率，降低布線(xiàn)延遲。由于本系統最終用于空間太陽(yáng)望遠鏡，所以板上時(shí)鐘頻率不可超過(guò)20MHz。但基于地面測試的需要，特利用DLL對外部時(shí)鐘信號進(jìn)行了倍頻，以提高芯片內部的運行速度。 本設計利用FPGA易于實(shí)現并行運算的特點(diǎn)實(shí)現專(zhuān)用的FFT處理芯片，解決了在軌實(shí)時(shí)大數據量圖像處理與航天級DSP運算速度不足之間的矛盾，提高了系統實(shí)時(shí)處理能力。兩維FFT不到400μs即可完成，高于航天級DSP(ADSP21020)1.5ms的處理速度。對太陽(yáng)米粒組織圖像進(jìn)行處理（實(shí)驗數據如表1所示），結果顯示數據誤差都在1%左右。這樣的誤差滿(mǎn)足空間太陽(yáng)望遠鏡中的相關(guān)擺鏡的系統要求。實(shí)驗證明用高性能FPGA實(shí)現空間化的FFT處理芯片是完全可行的。 表1 實(shí)驗數據 序 號原始數據浮點(diǎn)數據定點(diǎn)數據誤差% 序 號原始數據浮點(diǎn)數據定點(diǎn)數據誤差% 1 -32768 420104 419328 0.18 17 19072 5048 5120 1.43 2 -32768 154298 155008 0.46 18 18704 5943 6016 1.23 3 7216 97679 98304 0.64 19 18796 9445 9600 1.64 4 14800 106224 106688 0.44 20 19152 26885 27200 1.17 5 16080 93313 93760 0.48 21 16304 31028 31232 0.66 6 19840 76389 76800 0.54 22 14752 33592 33600 0.02 7 23104 65472 65672 0.68 23 14576 38986 39168 0.47 8 20000 604403 60672 0.45 24 15200 58786 59136 0.60 9 19104 69973 70400 0.61 25 8160 39973 70400 0.61 10 23376 58786 59136 0.60 26 7048 60403 60736 0.55 11 20128 38986 39104 0.30 27 14384 65472 65920 0.68 12 18688 33592 33600 0.02 28 11584 76389 76800 0.54 13 19680 31028 31232 0.66 29 11472 93313 93760 0.48 14 19536 26885 27200 1.17 30 11456 106224 106752 0.50 15 19680 9445 9600 1.64 31 11760 97679 98304 0.64 16 18720 5943 6016 1.23 32 11488 154298 154944 0.42