獲取目標(biāo)最佳極化算法的FPGA實(shí)現(xiàn)

陳歆煒，趙建中，吳 文

(南京理工大學(xué) 近程高速目標(biāo)探測(cè)技術(shù)國(guó)防重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210094)

在雷達(dá)系統(tǒng)中，當(dāng)以某目標(biāo)的最佳極化方式發(fā)射電磁波時(shí)，該目標(biāo)回波在接收天線端的功率能夠達(dá)到最大。相干情況下，目標(biāo)最佳極化的Jones矢量就是其Graves功率矩陣最大特征值所對(duì)應(yīng)的特征矢量[1]。通常，系統(tǒng)通過計(jì)算Graves功率矩陣的特征值和特征矢量來獲取目標(biāo)的最佳極化，使得在發(fā)射功率不變的前提下提高目標(biāo)回波的信噪比。在彈載、車載、機(jī)載、星載等對(duì)體積有限制的小型化系統(tǒng)中，需使用數(shù)字信號(hào)處理芯片（如FPGA）求解矩陣特征值的相關(guān)問題。

Jacobi方法是計(jì)算矩陣特征值問題常用計(jì)算機(jī)算法之一。在FPGA中，基于CORDIC算法的硬件結(jié)構(gòu)可簡(jiǎn)化Jacobi方法復(fù)雜的旋轉(zhuǎn)操作，節(jié)約硬件資源[1-2]。然而，CORDIC算法中的多次迭代操作，使得系統(tǒng)處理時(shí)間成倍增加，并不適合在對(duì)實(shí)時(shí)性要求較高的系統(tǒng)中使用。參考文獻(xiàn)[3]對(duì)Jacobi方法進(jìn)行了并行改進(jìn)，使用多個(gè)處理器并行處理的方法同時(shí)消去待求矩陣的多個(gè)非對(duì)角元素，獲得了較高執(zhí)行效率。但是，多個(gè)處理器的結(jié)構(gòu)需要消耗大量資源，在體積和成本受到限制的小型化系統(tǒng)上難以實(shí)現(xiàn)。

為了在單處理器系統(tǒng)上實(shí)現(xiàn)實(shí)時(shí)處理，本文針對(duì)目標(biāo)Graves功率矩陣的特點(diǎn)，提出了一種獲取目標(biāo)最佳極化的FPGA實(shí)現(xiàn)方法。文章提出了一種帶門限的序列Jacobi方法，采用并行結(jié)構(gòu)設(shè)計(jì)FPGA，合理調(diào)整了有限狀態(tài)機(jī)（FSM）的執(zhí)行時(shí)序，并對(duì)相關(guān)進(jìn)程進(jìn)行并發(fā)處理，壓縮了程序執(zhí)行時(shí)間。FPGA實(shí)現(xiàn)結(jié)果表明，該方法提供了快速的特征值和特征矢量求解過程，且比CORDIC算法快21%以上。

1 帶門限的序列Jacobi方法

電磁波極化理論指出，目標(biāo)Graves功率矩陣是復(fù)矩陣，無法直接通過Jacobi方法求解特征值。可將矩陣G表示為一個(gè)實(shí)數(shù)矩陣A和純虛數(shù)矩陣B之和，即：

設(shè)矩陣C為：

通過求解矩陣C的特征值和特征向量，即可得到矩陣G對(duì)應(yīng)的特征值及其特征向量[4]。

令C0=C，依次作迭代：

其中Rm為平面(p,q)上的一個(gè)旋轉(zhuǎn)矩陣，使得矩陣Cm-1的某個(gè)非對(duì)角元素化為 0。

在傳統(tǒng)Jacobi方法中，每次旋轉(zhuǎn)前都需進(jìn)行模最大非對(duì)角元素的搜索，這個(gè)過程會(huì)占用大量的時(shí)間，影響系統(tǒng)的實(shí)時(shí)性。本文在設(shè)計(jì)中省略了上述搜索步驟，將整個(gè)計(jì)算過程改進(jìn)為“訪問-旋轉(zhuǎn)”兩個(gè)步驟。矩陣的非對(duì)角元素可按圖1所示(p,q)的取值順序進(jìn)行訪問。

在實(shí)際運(yùn)算過程中可設(shè)定一門限，一旦非對(duì)角元素的絕對(duì)值超過該門限，則進(jìn)行Jacobi旋轉(zhuǎn)；反之則維持原矩陣不變。若按圖1所示順序訪問各非對(duì)角元素后并未發(fā)生一次旋轉(zhuǎn)，則認(rèn)為矩陣已經(jīng)在預(yù)設(shè)精度下完成對(duì)角化，并輸出矩陣特征值和特征矢量，從而獲得目標(biāo)的最佳極化。該方法的收斂性以及門限的選取已在參考文獻(xiàn)[4]中進(jìn)行了討論。

2 FPGA硬件設(shè)計(jì)

根據(jù)第1節(jié)所述的算法，在FPGA中計(jì)算矩陣特征值和特征矢量的流程如圖2所示。

圖2 計(jì)算矩陣特征值和特征矢量的流程圖

圖3所示為本文設(shè)計(jì)的一種可實(shí)現(xiàn)上述流程的FPGA結(jié)構(gòu)。該結(jié)構(gòu)中，直接用乘法器和加法器模塊替代了通常為完成旋轉(zhuǎn)運(yùn)算所設(shè)計(jì)的CORDIC模塊。

圖3所示的結(jié)構(gòu)中各模塊的具體功能如下：

ROM：存儲(chǔ)在運(yùn)算過程中無需實(shí)時(shí)改變的信息。

雙端口RAM：儲(chǔ)存待求矩陣和矩陣的特征矢量。

有限狀態(tài)機(jī)(下文簡(jiǎn)稱為狀態(tài)機(jī))：負(fù)責(zé)控制執(zhí)行過程中的時(shí)序，并產(chǎn)生地址信號(hào)對(duì)相關(guān)ROM和RAM進(jìn)行訪問。

比較器：將矩陣的非對(duì)角元素與預(yù)設(shè)門限進(jìn)行比較，以確定是否要進(jìn)行旋轉(zhuǎn)。

旋轉(zhuǎn)角計(jì)算模塊：計(jì)算旋轉(zhuǎn)角的值，并將其翻譯為地址信號(hào)，用以訪問存儲(chǔ)三角函數(shù)值的ROM。

運(yùn)算模塊：完成一次矩陣Jacobi旋轉(zhuǎn)和特征矢量的更新。該模塊中的乘法器和加法器采用如圖4所示的全并行結(jié)構(gòu)實(shí)現(xiàn)，可獲得較高的執(zhí)行速度。

數(shù)據(jù)選擇/分配器：根據(jù)不同的計(jì)算內(nèi)容 （Jacobi旋轉(zhuǎn)或特征矢量更新）選擇輸入運(yùn)算模塊的數(shù)據(jù),或者將計(jì)算結(jié)果輸出到相應(yīng)的數(shù)據(jù)總線。

假設(shè)系統(tǒng)在執(zhí)行了m次門限比較和n次Jacobi旋轉(zhuǎn)后，得到了最終結(jié)果。經(jīng)過合理設(shè)計(jì)的狀態(tài)機(jī)時(shí)序示意圖如圖5所示。

由于門限比較的結(jié)果有可能會(huì)導(dǎo)致系統(tǒng)跳過Jacobi旋轉(zhuǎn)過程，圖5所示門限比較的執(zhí)行次數(shù)一般多于Jacobi旋轉(zhuǎn)的執(zhí)行次數(shù)，即m≥n。根據(jù)上文所述求解步驟，m的極大值為6n。由于兩次Jacobi旋轉(zhuǎn)之間有較長(zhǎng)時(shí)間間隔，此時(shí)運(yùn)算模塊處于空閑狀態(tài)。本文則利用這段時(shí)間執(zhí)行特征矢量的更新過程，從而提高了運(yùn)算模塊的使用效率。需要注意的是，特征矢量更新過程須在下一次旋轉(zhuǎn)角計(jì)算進(jìn)程之前開始，以免由于旋轉(zhuǎn)角值的改變，導(dǎo)致特征矢量計(jì)算錯(cuò)誤。

根據(jù)圖5所示時(shí)序,完成整個(gè)求解過程所耗時(shí)間T可表示為：

3 FPGA實(shí)現(xiàn)結(jié)果與分析

根據(jù)第2節(jié)所述的結(jié)構(gòu)和時(shí)序，本文在Altera公司Cyclone系列的FPGA EP1C12上實(shí)現(xiàn)了獲取目標(biāo)最佳極化的算法。數(shù)據(jù)格式采用16 bit定點(diǎn)格式，并將決定是否旋轉(zhuǎn)的門限設(shè)為10-3。FPGA的資源消耗情況如表1所示。

表1 FPGA的資源消耗情況

當(dāng)輸入隨機(jī)選取的6個(gè)不同Graves矩陣時(shí)，F(xiàn)PGA完成整個(gè)求解過程所需要的時(shí)間如表2所示。

表2 FPGA的運(yùn)算時(shí)間

由表2可知，F(xiàn)PGA的求解時(shí)間基本穩(wěn)定，執(zhí)行時(shí)間的浮動(dòng)是由門限比較過程的執(zhí)行次數(shù)不同引起的。

根據(jù)式(4)，可估算使用本文所提方法計(jì)算矩陣特征值和特征矢量的執(zhí)行時(shí)間最多為：

若使用參考文獻(xiàn)[1]所提CORDIC算法實(shí)現(xiàn)時(shí)，因其只包含兩個(gè)CORDIC模塊(一個(gè)模塊計(jì)算旋轉(zhuǎn)角θ，另一個(gè)模塊實(shí)現(xiàn)矩陣旋轉(zhuǎn)),從而完成一次矩陣Jacobi旋轉(zhuǎn)并更新特征矢量需執(zhí)行兩次CORDIC運(yùn)算。因此，參考文獻(xiàn)[1]的FPGA的平均執(zhí)行時(shí)間T′可表示為：

其中,TC為CORDIC模塊完成一次旋轉(zhuǎn)所需要的時(shí)間，Tother為結(jié)構(gòu)中其他模塊的總耗時(shí)。

根據(jù)相關(guān)資料[5-9]，可估算出各種模塊的FPGA執(zhí)行時(shí)間，如表3所示。

由式(5)、式(6)和表3可得：

表3 各模塊的執(zhí)行時(shí)間（估算）

由式(7)可知，Tmax＜T′，表明本文所提方法的執(zhí)行速度優(yōu)于參考文獻(xiàn)[1]所提的CORDIC算法，且性能可提升21%以上。

本文根據(jù)帶門限的序列Jacobi算法理論,設(shè)計(jì)了一種新的FPGA硬件結(jié)構(gòu)，可快速獲取目標(biāo)最佳極化的Jones矢量。文中對(duì)FPGA程序的執(zhí)行流程、模塊結(jié)構(gòu)、狀態(tài)機(jī)的時(shí)序作了詳細(xì)討論。FPGA實(shí)現(xiàn)結(jié)果表明，該方法的執(zhí)行速度優(yōu)于常用的CORDIC算法，可在小型化系統(tǒng)中實(shí)時(shí)獲取目標(biāo)的最佳極化。

[1]BRAVO I,MAZO M,LAZARO L J,et al.Novel HW architecture based on FPGAs oriented to solve the eigen problem[J].IEEE Transaction on Very Large Scale Integration(VLSI)Systems,2008,16(12)：1722-1725.

[2]袁生光,沈海斌.基于Jacobi算法對(duì)稱矩陣特征值計(jì)算的FPGA實(shí)現(xiàn)[J].機(jī)電工程,2008,25(10)：80-82.

[3]王飛,王建業(yè),張安堂,等.實(shí)對(duì)稱矩陣特征值分解高速并行算法的FPGA實(shí)現(xiàn)[J].空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,9(6)：67-70.

[4]WILKINSON J H.The algebraic eigenvalue problem[M].New York：Oxford University Press,1965：174-282.

[5]KOLOUCH J.Combinational divider in FPGA[C].Proceedings of International Conference Radioelektronika,Brno,Czech republic,Apr.24-25,2007：1-4.

[6]GURUMURTHY K S,PRAHALAD M S.Fast and power efficient 16×16 array of array multiplier using vedic multiplication[C].Proceedings of IMPACT Conference,Taipei,China,Oct.20-22,2010：1-4.

[7]DESCHAMPS J P,SUTTER G.Decimal division：Algorithms and FPGA implementations[C].Southern Programmable Logic Conference Proceedings,Ipojuca,Brazil,Mar.24-26,2010：67-72.

[8]VACHHANI L,SRIDHARAN K,MEHER P K.Efficient FPGA realization of CORDIC with application to robotic exploration[J].IEEE Transactions on Industrial Electronics,2009,56(12)：4915-4928.

[9]ARNOLD M G,COLLANGE S.A real/complex logarithmic number system ALU[J].IEEE Transactions on Computers,2011,60(2)：202-213.