對稱矩陣特征值分解的FPGA實現(xiàn)

劉永勤

摘 要： 針對應用于MUSIC DOA估計的數(shù)據(jù)協(xié)方差矩陣特征值分解的需要，給出一個特征值分解的硬件實現(xiàn)方案，并闡述了基本思想。設計采用基于CORDIC的Jacobi算法實現(xiàn)實對稱矩陣特征值分解，并在FPGA上對5×5矩陣進行了硬件仿真，經過理論分析和實驗驗證，該設計可以計算出全部特征值和特征向量，為MUSIC算法的FPGA實現(xiàn)奠定了基礎。

關鍵詞： MUSIC算法； 特征值分解； Jacobi算法； CORDIC算法； FPGA

中圖分類號： TN911?34； TN929.1 文獻標識碼： A 文章編號： 1004?373X（2017）12?0015?04

Abstract： Aiming at the needs of the data covariance matrix eigenvalue decomposition used in DOA estimation such as MUSIC， a hardware implementation scheme of the eigenvalue decomposition is provided and the basic idea is described in this paper. The Jacobi algorithm based on CORDIC is adopted in the design to achieve real symmetric matrix eigenvalue decomposition， and conduct the hardware emulation for 5×5 matrix in FPGA. The results of theoretical analysis and experimental verification show that the design can calculate all eigenvalues ??and eigenvectors， and has laid the foundation for FPGA implementation of MUSIC algorithm.

Keywords： MUSIC algorithm； eigenvalue decomposition； Jacobi algorithm； CORDIC algorithm； FPGA

0 引 言

多信號分類（MUSIC）[1]算法是波達方向（DOA）估計技術中最具代表性的高分辨力算法之一，因其突破了傳統(tǒng)方法的瑞利極限而廣受人們青睞。雖然MUSIC算法理論上已經成熟，但運算量大，不利于其硬件實現(xiàn)，對接收矢量的數(shù)據(jù)協(xié)方差矩陣進行特征值分解（EVD）占據(jù)了MUSIC算法60%的運算量，因此解決EVD在硬件上的實現(xiàn)是硬件實現(xiàn)MUSIC算法的關鍵所在，同時EVD作為一個相對獨立的部分，可以廣泛應用到人工視覺、電力電子、機械力學系統(tǒng)等其他眾多領域中去。

Jacobi方法是計算實對稱矩陣特征值的常用方法，它涉及到開方、除法等非線性運算，這對硬件實現(xiàn)有一定難度， Cavallaro和Luk直接利用CORDIC的兩種計算模式解決Jacobi中的反正切及坐標旋轉計算問題[2]。為進一步減小EVD計算量，Yang和Bohme應用了雙平面旋轉方法[3]，通過兩個并行矩陣的并行計算實現(xiàn)特征值分解。目前，Jacobi算法的研究集中在對所有元素的并行計算上[4]，Brent，Luk和Van Loan提出了采用脈動陣列的結構實現(xiàn)矩陣特征值求解的方法[5]，充分體現(xiàn)了Jacobi的高度并行性，是一種經典的陣列結構。A.Ahmedsaid等人在文獻[6]中對上述陣列結構進行了改進，并提出了在FPGA上的實現(xiàn)方案。并行計算雖然可以提高EVD計算速度，但是這種方法過程復雜，且占用資源多，不適合在單處理器系統(tǒng)上實現(xiàn)。因此本研究利用基于CORDIC的順序Jacobi法在單片F(xiàn)PGA上實現(xiàn)EVD計算，同時針對經典Jacobi算法單次掃描時間長這一不足，簡化操作流程，并通過合理設計算法結構來壓縮執(zhí)行時間。

1 由復數(shù)轉實數(shù)

實際中經常會遇到要求解復Hermite矩陣特征值和特征向量的問題，但復矩陣的特征值分解的計算量很大，計算復雜度[7]高達，且復對稱矩陣不具有實對稱矩陣的任何重要性質。而經典的Jacobi方法是針對實對稱矩陣的特征值分解方法，因此為了簡化計算應用Jacobi方法，需要先把復Hermite矩陣轉化為實對稱矩陣[8?9]。

對中心有一個陣元的元均勻圓陣，將天線陣列流形按中心共軛對稱形式排列，其陣列結構見圖1。

2 Jacobi方法

Jacobi方法是一種經典的求解實對稱矩陣特征值的計算方法之一。假設原實對稱的協(xié)方差矩陣為，則Jacobi方法通過構造一系列的平面旋轉矩陣，使原矩陣通過有限次的平面旋轉變換轉化為對角陣，對角陣的主對角線元素即為的特征值[10?11]。嚴格的說產生對角型所需的旋轉變換是無窮的，但在實際計算中當非對角元素小到可以忽略，就可以認為矩陣已經被對角化。

對作一系列平面旋轉變換，有：

3 CORDIC算法

從前文可以看出Jacobi方法涉及到矩陣旋轉和反正切等復雜計算，這些計算在FPGA上是難以實現(xiàn)的，而CORDIC算法正是解決這一問題的有利工具。CORDIC算法是J.Voider等人于1959年提出的，它是一種循環(huán)迭代算法，通過用一系列與運算基數(shù)有關的基本角的不斷偏擺來逼近所需要旋轉的角度，它將很多復雜的函數(shù)運算化簡為移位和加法的迭代，提供了一種適合硬件的實現(xiàn)方法[13?14]。其圓周坐標下的基本迭代公式如下：

其中每次旋轉的基本角取，為每次旋轉的方向，是根據(jù)角度累積量來判定的，即，則。CORDIC算法可以工作在旋轉模式和矢量模式，旋轉模式用來完成坐標旋轉運算，矢量模式用來完成反正切計算得到最佳旋轉角，有。在旋轉模式情況下，當， 經過n次基本角旋轉迭代后旋轉結果為：

式中：為對結果進行修正的比例因子，。通過比較式（12）和式（6）可以很明了地看出CORDIC算法可以解決Jacobi的旋轉問題。

4 FPGA實現(xiàn)方案

由于待分解矩陣是實對稱矩陣，因此在FPGA中只需要處理其上三角元素就可以取代整個矩陣，掃描順序為。在經典Jacobi算法中， 一次Jacobi掃描要進行1次CORDIC反正切計算和2次CORDIC旋轉才能完成，單次掃描時間長，針對這一不足，具體實現(xiàn)時對其進行簡化。

由于Jacobi中，將根據(jù)的正負性判定，從而確定符號集，符號集一旦確定就可以根據(jù)式（11）的迭代實現(xiàn)CORDIC旋轉，省去了反正切計算的過程。

令，由可以得到：

根據(jù)式（9）可知應取初值為，，這樣根據(jù)此更新公式和初值就可以迭代求得符號集。

將式（6）～式（8）展開可以得到：

則當符號集確定可以將符號集作為地址，通過查表的方式得到，從而實現(xiàn)對角元素式（13）的更新，而對于要掃描的非對角元素可以直接置零。式（14）中行（列）行（列）其他元素的更新則要用1次CORDIC旋轉來實現(xiàn)，初值為。這里符號計算和CORDIC旋轉可以并行進行，每算出一個值就進行一個基本角的旋轉?？傮w結構如圖2所示。

5 設計實現(xiàn)及結果

本設計所選用的器件是ALTERA公司的EP3C120F780C7器件，使用Verilog語言完成電路描述之后，在Quartus Ⅱ軟件平臺上進行編譯，在Modelsim中進行仿真。以矩陣為例，采用21 b定點數(shù)，將如下矩陣作為輸入矩陣進行系統(tǒng)仿真。

將所得定點數(shù)結果化為對應的浮點數(shù)數(shù)據(jù)在表1中給出，在Matlab中直接調用eig函數(shù)計算出的特征值和特征向量在表2中給出。表1和表2分別表示設計結果與理論結果。進行比較可以看出，本設計所得結果與理論結果基本一致；雖然第4列和第5列特征向量的符號相反，但由于各特征向量間的乘積為一個很小的接近于0的數(shù)，故其正負不影響其正交性。

假設有任意兩個信號入射到五元均勻圓陣上，入射方位角分別為120°和160°，圖3給出了用MUSIC算法進行DOA估計的結果，并對局部進行了放大。其中，圖3中（a）為理論估計結果，其EVD計算部分采用Matkab浮點計算，圖3中（b）為本文設計估計結果，其EVD計算部分采用本設計的定點操作，除了EVD計算，所有MUSIC算法中的其他計算都采用浮點操作。從圖中可以看出，本設計可以有效估計出入射信號的DOA信息，證明此硬件結構可以應用于MUSIC算法的FPGA實現(xiàn)中。

6 結 語

本文采用CORDIC算法和Jacobi算法，在FPGA上實現(xiàn)了數(shù)據(jù)協(xié)方差矩陣的特征值和特征向量計算，為MUSIC算法的FPGA實現(xiàn)提供了保證。實對稱矩陣特征分解應用廣泛，其硬件實現(xiàn)對其他算法的工程應用有重要作用。

參考文獻

[1] SCHMIDT R. Multiple emitter location and signal parameter estimation [J]. IEEE transactions on antennas and propagation， 1986， AP?34（3）： 276?280.

[2] CAVALLARO J R， LUK F T. CORDIC Arithmetic for an SVD Processor [J]. Journal of parallel and distributed computing， 1988， 5（3）： 271?290.

[3] YANG B， BOHME J F. Reducing the computations of the SVD array given by Brent and Luk [J]. SPIE advanced algorithm and architectures for signal processing IV， 1989， 1152： 92?102.

[4] GOTZE J. Parallel methods for iterative matrix decompositions [C]// IEEE International Sympoisum on Circuits and Systems. [S.l.]： IEEE， 1991： 232?235.

[5] BRENT R P， LUK F T， VAN LOAN C. Computation of the generalized singular value decomposition using mesh?connected processors [C]// Proceedings of SPIE Sympoisum on Real?Time Signal Processing， 1983， 431： 66?72.

[6] AHMEDSAID A， AMIRA A， BOURIDANE A. Improved SVD systolic array and implementation on FPGA [C]// Proceedings of 2003 IEEE International Conference on Field?Programmable Technology. [S.l.]： IEEE， 2003： 35?42.

[7] LINEBARGER D A， DEGROAT R D， DOWLING E M. Efficient direction?finding methods employing forward?backward averaging [J]. IEEE transactions on signal processing， 1994， 42（8）： 2136?2145.

[8] KIM Minseok， ICHIGE Koichi， ARAI Hiroyuki. implementation of FPGA based fast DOA estimator using unitary MUSIC algorithm [C]// Proceedings of 58th IEEE Vehicular Technology Conference. [S.l.]： IEEE， 2003： 213?217.

[9] 徐德琛，劉志文，徐友根.某測向系統(tǒng)中MUSIC算法的FPGA實現(xiàn)[J].北京理工大學學報，2010，30（9）：1107?1111.

[10] 于正文，尹慶莉.求特征值的Jacobi方法[J].山東科學，2011，24（6）：19?21.

[11] WILKINGSON J H. The algebraic eigenvalue problem [M]. UK： Oxford Science Publications， 1999.

[12] BRAVO I， JIMENEZ P， MAZO M， et al. Implementation in FPGAs of Jacobi method to solve the eigenvalue and eigenvector problem [C]// Proceedings of 2006 International Conference on Field Programmable Logic and Applications. Madrid， Spain： IEEE， 2006： 301?316.

[13] 楊宏，李國輝，劉立新.基于FPGA的CORDIC算法的實現(xiàn)[J].西安郵電學院學報，2008，13（1）：75?77.

[14] KIM Minseok， ICHIGE K.， ARAI H. Design of Jacobi EVD processor based on CORDIC for DOA estimation with MUSIC algorithm [C]// Proceedings of 2002. The 13th IEEE International Symposium on Personal， Indoor and Mobile Radio Communications. Lisboa， Portugal： IEEE， 2002： 120?124.