摘  要: 在空間太陽(yáng)望遠(yuǎn)鏡的在軌高速數(shù)據(jù)處理中，運(yùn)算時(shí)間是影響系統(tǒng)性能的重要環(huán)節(jié)之一。利用FPGA" title="FPGA">FPGA豐富的邏輯單元實(shí)現(xiàn)快速傅里葉變換(FFT" title="FFT">FFT)，解決了在軌實(shí)時(shí)大數(shù)據(jù)量圖像處理與航天級(jí)DSP運(yùn)算速度不足之間的矛盾;利用溢出監(jiān)測(cè)移位結(jié)構(gòu)解決了定點(diǎn)運(yùn)算的動(dòng)態(tài)范圍問(wèn)題。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，各項(xiàng)指標(biāo)均達(dá)到了設(shè)計(jì)要求。

　　關(guān)鍵詞: FFT  FPGA  蝶形運(yùn)算

　　空間太陽(yáng)望遠(yuǎn)鏡項(xiàng)目是我國(guó)太陽(yáng)物理學(xué)家為了實(shí)現(xiàn)對(duì)太陽(yáng)的高分辨率觀測(cè)而提出的科學(xué)計(jì)劃。它可以得到空間分辨率為0.1″的向量磁圖和0.5″的X射線圖像，實(shí)現(xiàn)這樣高的觀測(cè)精度的前提就是采用高精度的姿態(tài)控制系統(tǒng)和高精度的相關(guān)跟蹤系統(tǒng)。從整個(gè)系統(tǒng)來(lái)看，相關(guān)運(yùn)算所需的時(shí)間成為限制系統(tǒng)性能能否提高的一個(gè)重要環(huán)節(jié)。

　　目前，國(guó)際國(guó)內(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×32點(diǎn)8bit的二維FFT所用時(shí)間需要1.5ms以上，遠(yuǎn)遠(yuǎn)不能滿足系統(tǒng)設(shè)計(jì)要求;而現(xiàn)有的FFT處理芯片在處理速度、系統(tǒng)兼容性、抗輻射能力等方面不能滿足空間太陽(yáng)望遠(yuǎn)鏡所提出的要求。

　　為克服這一矛盾，本文利用FPGA資源豐富、易于實(shí)現(xiàn)并行流水的特點(diǎn)設(shè)計(jì)專用的FFT處理芯片來(lái)完成復(fù)雜的、大量的數(shù)據(jù)處理;并通過(guò)在運(yùn)算中作溢出監(jiān)測(cè)來(lái)保證定點(diǎn)運(yùn)算的精度，從而大大縮短系統(tǒng)的響應(yīng)時(shí)間，將極大地提高空間太陽(yáng)望遠(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=4^m，所以32點(diǎn)FFT算法不能采用基-4 FFT運(yùn)算。當(dāng)詳細(xì)分析基-2蝶形圖時(shí)，有些蝶形運(yùn)算" title="蝶形運(yùn)算">蝶形運(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×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)范圍問(wèn)題。下面對(duì)其進(jìn)行理論分析:

　　若{x(n)}是一N點(diǎn)序列，其DFT為{X(K)}，由Parseval定理得^[4]:

　　由式(1)可知變換結(jié)果的均方值是輸入序列均方值的N倍。考慮基-2算法的第m級(jí)蝶形運(yùn)算，用X_m(i)、X_m(j)表示原來(lái)的復(fù)數(shù)，則新的一對(duì)復(fù)數(shù)X_m+1(i)、X_m+1(j)為:

　　其中，W為旋轉(zhuǎn)因子。首先，考慮復(fù)數(shù)的均方根值。由(2)式可得:

　　因此，從均方根意義來(lái)看，數(shù)值(實(shí)數(shù)或復(fù)數(shù))每級(jí)都增加倍。其次，再考慮復(fù)數(shù)的最大模。由(2)式可以證明[5]:

　　因此，復(fù)數(shù)數(shù)組的最大模是非減的。所以，對(duì)于DIT-FFT，其每一級(jí)的蝶形運(yùn)算之后數(shù)值都會(huì)增加倍。在每一次運(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)行，用簡(jiǎ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×5=80個(gè)基-2的蝶形運(yùn)算，一幅圖像一共是32行32列，不考慮不需要做乘法的蝶形運(yùn)算，一路串行共需要6×80×32×2=30720個(gè)時(shí)鐘周期，采用頻率為10MHz的時(shí)鐘，即為3ms。對(duì)于蝶形運(yùn)算的第一、第二級(jí)都可以由不帶乘法器的蝶形結(jié)構(gòu)來(lái)實(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è)。如果沒(méi)有溢出，則計(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]:

　　這里b_i為比例參數(shù)。

 　　根據(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)過(guò)乘法運(yùn)算(MU1)乘以旋轉(zhuǎn)因子，數(shù)據(jù)變?yōu)?B+Bω)bit，然后作加(減)法，得到蝶形運(yùn)算結(jié)果(B+B_ω+1)bit。為防止溢出，進(jìn)行移位操作。M₁、M₂為比例選擇器，根據(jù)不同的級(jí)數(shù)，選擇不同的比例因子。最后，輸出數(shù)據(jù)再放回到存儲(chǔ)器中。

3 FPGA器件選擇

　　本設(shè)計(jì)采用XILINX公司的VERTEX" title="VERTEX">VERTEX系列XCV300-4HQ240" title="XCV300-4HQ240">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×1bit的同步RAM，而且一個(gè)塊(Slice)中的兩個(gè)LUTs可以組合成一個(gè)16×2bit或者一個(gè)32×1bit的同步RAM或者一個(gè)16×1bit的同步多口RAM。另外，LUTs還可作為一個(gè)16bit的移位寄存器使用，該寄存器用來(lái)獲取高速或者突發(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)最終用于空間太陽(yáng)望遠(yuǎn)鏡，所以板上時(shí)鐘頻率不可超過(guò)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ì)太陽(yáng)米粒組織圖像進(jìn)行處理(實(shí)驗(yàn)數(shù)據(jù)如表1所示)，結(jié)果顯示數(shù)據(jù)誤差都在1%左右。這樣的誤差滿足空間太陽(yáng)望遠(yuǎn)鏡中的相關(guān)擺鏡的系統(tǒng)要求。實(shí)驗(yàn)證明用高性能FPGA實(shí)現(xiàn)空間化的FFT處理芯片是完全可行的。

參考文獻(xiàn)

1 貢三元. VLSI陣列處理. 南京:東南大學(xué)出版社，1992

2 應(yīng)啟珩，馮一云，竇維蓓. 離散時(shí)間信號(hào)分析和處理.北京:清華大學(xué)出版社，2001

3 蔣增榮，曾永泓，余品能. 快速算法. 長(zhǎng)沙:國(guó)防科技大學(xué)出版社，1998

4 劉朝暉，韓月秋. 用FPGA實(shí)現(xiàn)FFT的研究. 北京:北京理工大學(xué)學(xué)報(bào)，1999

5 清華大學(xué)無(wú)線電系快速傅里葉變換組.快速傅里葉變換.北京:清華大學(xué)出版社，1980

6 W.R.Knight， R.Kaiser. A Sample Fixed-Point Error Bound for the Fast Fourier Transform. IEEE Trans.Acous-

  tics，Speech and Signal Proc.，Vol.27.No.6，pp，615～620，Dec.1979

7 High-Performance 32-Point Complex FFT. America： XILINX，2001

8 Vertex Series Data Sheet. America： XILINX， 2001