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

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