典型陣列快速MUSIC算法研究

張興良* 王可人 樊甫華

?

典型陣列快速MUSIC算法研究

張興良王可人 樊甫華

(電子工程學院信息系 合肥 230037)

由于MUSIC(MUltiple SIgnal Classification)算法需要大量的乘法運算和三角函數求值，導致其實時處理能力較弱。為此，該文首先對均勻線陣和均勻圓陣的陣列結構進行分析，提取導向矢量的一些性質。然后，利用Hermite矩陣的性質對復數乘法進行分解，再組建兩個實值向量以減少乘法運算次數。最后，利用導向矢量的性質提出一種基于查表的新算法。新算法既沒有三角函數求值運算，又不需要大量的存儲空間。仿真實驗結果表明新算法在沒有改變MUSIC算法譜估計的效果的前提下，將MUSIC算法的運算速率提高了50倍以上。因此，新算法具有廣闊的應用前景。

典型陣列；導向矢量；查表法；快速MUSIC(MUltiple SIgnal Classification)算法

1 引言

傳統的空間信號譜分析法是傅里葉變換法，由于陣列尺寸有限，該方法的分辨率受到瑞利限的約束。以多重信號分類 (MUltiple SIgnal Classification, MUSIC)算法為代表的子空間類處理方法，即所謂超分辨空間譜估計算法，突破了瑞利限的限制，實現了譜估計理論的重大飛躍。近年來，這類算法廣泛應用在通信、雷達和航天等諸多領域，其優點早已得到實踐證明。

遺憾的是，超分辨空間譜估計算法需要大量的乘法和三角函數求值，因此其計算耗時難以滿足工程需要。在圓陣、方陣等2維陣列中，該問題表現得更加突出。實際上，巨大的計算量已成為超分辨空間譜估計技術完全走向實用化的主要瓶頸之一。

快速空間譜估計算法一直是國內外學者研究的熱點，目前主要的研究思路有3種。第1種是尋找新的計算量小的空間譜估計算法，這類算法的估計性能往往不如MUSIC算法，并且一般只適合均勻線陣，如ESPRIT算法和Root-MUSIC算法。第2種是對現有的空間譜估計算法進行改進，這類算法實際上是在精度和計算量之間進行折中選擇。如文獻[7]改用信號子空間實現基于FFT的快速MUSIC算法，但降低了譜估計的精度；文獻[8]只降低特征分解的計算量，卻沒有降低譜峰搜索的計算量，改進效果不明顯。第3種是根據算法的運算流程和特點，合理設計和配置硬件，這類方法的效果也是有限的，而且往往是以犧牲硬件成本為代價，如多路并行譜峰搜索法。以上研究成果在一定程度上提高了超分辨空間譜估計算法的計算速度，但是仍然不能滿足要求越來越高的現代實時處理要求。

文獻[7]分析了MUSIC算法計算量大的主要原因：搜索范圍大和譜函數復雜，也就是說，譜峰搜索占MUSIC算法計算量的絕大部分。譜峰搜索的計算量主要包括乘法和三角函數求值，計算機完成這兩種運算的過程都比較復雜，耗時嚴重。為此，文獻[12]利用查表法降低了圓陣列MUSIC算法的乘法和三角函數求值次數。但該文獻提出的直接查表法對存儲量需求大；提出的間接查表法依然保留大量的三角函數求值運算，效果有限。

本文重點研究快速MUSIC算法。在減少乘法運算次數的基礎上，利用查表法避免三角函數求值運算；針對查表法需要較大存儲量的情況，利用導向矢量的性質對查表法進行了改進。相較于文獻[12]的查表法，本文提出的算法既沒有三角函數求值運算，又降低了對存儲量的需求，且本文的研究范圍包括均勻線陣和均勻圓陣兩種陣列。本文第2節深入研究陣列的內在特征，獲得導向矢量的內在性質；第3節去除蘊含在MUSIC算法中的冗余乘法；第4節介紹查表法；第5節對查表法進行了仿真分析，仿真試驗結果令人滿意；第6節總結全文。

2 典型陣列分析

雖然MUSIC算法對陣列結構沒有特殊要求，但為簡單起見，工程中都選用具有典型結構的陣列。本文研究的典型陣列包括均勻線陣和均勻圓陣，均勻線陣是典型的1維陣列，均勻圓陣是典型的2維陣列，它們的陣列結構模型分別如圖1和圖2所示。需要說明的是，本文建立的模型是以下列假設為前提的：

(1) 入射信號是遠場的，且是窄帶的；

(2) 相鄰陣元間距小于信號載波波長的一半；

(3) 接收噪聲是平穩高斯白噪聲，入射信號互不相關，各陣元接收噪聲相互獨立，信號與噪聲也相互獨立。

2.1 均勻線陣

其中

圖1 均勻線陣結構圖

(3)

(4)

(6)

性質1均勻線陣導向矢量具有共軛對稱性，即

證明

(8)

2.2 均勻圓陣

(10)

圖2 均勻圓陣列結構圖

性質2均勻圓陣導向矢量具有對稱性，記

（12）

證明

(14)

比較式(13)、式(14)，可得式(12)的結論。

證明

證畢

本質上，性質1-性質3都是由特殊的陣列結構決定的。

3 MUSIC算法的改進

MUSIC算法譜函數復雜，計算量大，而且包含一些冗余運算。MUSIC算法譜函數定義為

(18)

分別令：

(20)

(21)

(23)

(24)

再令：

(26)

(28)

(29)

(31)

3.1 均勻線陣MUSIC算法改進

同理可得

（35）

(37)

其中

則

(38)

式(38)與式(31)計算結果完全一致，但較式(31)的計算量更少。以元線陣為例，按式(31)需要/2次乘法，而按式(38)僅需次乘法運算。

3.2 均勻圓陣MUSIC算法改進

令

(40)

可得

(42)

同理

表1 改進前后乘法運算次數

標準MUSIC算法改進后(圓陣)改進后(線陣)

4 改進的查表法

MUSIC算法表示的是連續譜，但工程中只在有限的離散方向點上計算其離散譜，稱之為離散MUSIC(Discrete MUSIC，簡稱DMUSIC)算法，DMUSIC算法與離散傅里葉變換(Discrete Fourier Transform，簡稱DFT)的物理意義是相通的。MUSIC算法的三角函數求值運算量巨大，DMUSIC算法也是如此，為降低DMUSIC算法的計算量，可以采用查表的方法代替三角函數求值運算。查表法就是在DFMUSIC算法的抽樣方向上對或進行制表，運行時再對其進行查表，從而完全避免了三角函數求值運算。

查表法需要的存儲量比較大，對于2維陣列，其存儲量的需求一般都達到數百兆至數吉比特。要擴大查表法的應用范圍，必須降低其存儲量需求。前面，我們給出了典型陣列導向矢量的一些性質，利用這些性質可以對查表法進行改進，減少其對存儲量的要求。

4.1 均勻線陣情形

對于均勻線陣，由性質1可得

（45）

因此

4.2 均勻圓陣情形

對于均勻圓陣，記

由性質2可得

(49)

以五元陣列為例，按0.3°步進作譜估計，4 byte的數據精度(float型數據)，均勻線陣和均勻圓陣的存儲空間需求見表2。總體來說，均勻線陣需要的存儲空間非常小，以KB為數量級，而均勻圓陣需要的存儲空間比均勻線陣大很多，以MB為數量級。

表2 均勻線陣和均勻圓陣的存儲空間需求

均勻線陣查表法(byte)均勻圓陣查表法(byte)

5 仿真分析

仿真1 八元均勻線陣，相鄰陣元間隔為0.15 m，空間有兩個不相關的信號源入射，入射信號波長為0.3 m，入射角度分別為-45°和30°，信噪比為0 dB，接收機采樣快拍數為200，仿真軟件為MATLAB 7.0。做300次蒙特卡洛試驗，統計300次試驗耗時總時間，見表3；標準MUSIC算法查表法譜估計結果完全一致，圖3是它們某次譜估計的結果。

表3 譜估計耗時比較(300次總計)

步進標準MUSIC算法(s)本文改進的查表法(s) 0.01°95.158 1.561 0.05°19.105 0.321 0.1° 9.610 0.156 0.3° 3.173 0.052

縱向比較，理論上，0.01°步進耗時是0.05°步進耗時的5倍、是1°步進耗時的10倍、是0.3°步進耗時的30倍，實際耗時倍數與理論耗時倍數基本一致。橫向比較，標準MUSIC算法譜估計耗時超過查表法的60倍，查表法的優勢非常明顯。可以看出，精確譜估計需要的代價很大，實時性較差；標準MUSIC算法很難滿足工程需要，但是本文的查表法大幅提高了MUSIC算法的實時性。

仿真2五元均勻圓陣，半徑為0.15 m，空間有兩個不相關信號源，波長為0.3 m，來波方向分別為(60°, 30°)和(240°, 30°)，信噪比為0 dB，方位角步進和俯仰角步進相同，接收機采樣快拍數為200。為比較標準MUSIC算法、改進的查表法和文獻[12]提出的兩種查表法：直接查表法、間接查表法，利用Visual C++6.0進行100次實驗，統計譜估計平均耗時，結果見表4；將譜估計結果保存到文件中，利用MATLAB軟件觀看譜估計結果，4種譜估計算法結果完全一致，圖4是譜估計結果。

表4 譜估計耗時比較(100次平均)

步進標準MUSIC算法(s)本文改進的查表法(s)文獻[12]直接查表法(s)文獻[12]間接查表法(s) 0.1°63.6211.1361.1346.236 0.3°7.0820.1240.1250.694 0.5°2.6340.0470.0480.252 1.0°0.6460.0120.0130.060

縱向比較，可以獲得和仿真1相同的結論。橫向比較，改進的查表法和直接查表法譜估計耗時相近；標準MUSIC算法譜估計耗時是改進查表法和直接查表法的50–60倍，是間接查表法的10倍以上。標準MUSIC算法耗時最為嚴重，間接查表法次之，直接查表法和改進的查表法耗時最少。通過譜估計圖可以看出改進的查表法譜估計準確性較好。

仿真3五元均勻圓陣，半徑為0.15 m，假設入射信號波長為0.3 m，方位角步進和俯仰角步進相同，采用Visual C++6.0軟件編程。用自編的函數Nnew對庫函數new進行封裝，用以統計查表法制表所占用的內存，數據類型為float型，統計結果見表5。

表5 制表占用內存大小比較

從統計結果可以看出，直接查表法占用內存是改進查表法的兩倍，而間接查表法僅需很小的內存。隨著譜估計精度的提高，查表法占用的空間急劇增加。精確譜估計的代價不僅表現在時間上，也表現在所占用的內存空間上。

6 總結

以往的快速高分辨空間譜估計算法沒有從根本上解決計算量問題，查表法提供了一種可行的途徑。通過分析均勻線陣和均勻圓陣兩種典型陣列的陣列結構，發現均勻線陣導向矢量具有共軛對稱性，均勻圓陣導向矢量具有周期循環性和對稱性；在降低MUSIC算法的乘法運算次數的基礎上，對查表法進行改進。改進的查表法利用導向矢量的性質降低了查表法對存儲量的需求，同時保持了較快的運算速率。

本文以MUSIC算法為例，提出降低計算量的一種思路，該思路可以推廣到其它空間譜估計算法中。要進一步提高空間譜估計算法的實時處理能力還可以從多方面改進，如根據不同方向的分辨率調整搜索步進、利用先驗知識縮小搜索范圍等。

[1] 張小飛, 汪飛, 徐大專. 陣列信號處理的理論和應用[M]. 北京: 國防工業出版社, 2010, 第4.3節.

Zhang Xiao-fei, Wang Fei, and Xu Da-zhuan. Array Signal Processing Theory and Application[M]. Beijing: National Defense Industry Press, 2010, Section 4.3.

[2] 郭躍. 超分辨波達方向估計技術的研究[D]. [博士論文], 華中科技大學, 2007: 4-5.

Guo Yue. Research on direction of arrival estimation with super resolution[D]. [Ph.D. dissertation], Huazhong University of Science and Technology, 2007: 4-5.

[3] Zhuang Jie, Li Wei, and Manikas A. An IDFT-based root-MUSIC for arbitrary arrays[C]. 2010 IEEE International Conference on Acoustics, Speech and Signal Processing, Dallas, Texas, USA, May 22-27, 2010: 2613-2617.

[4] Tripathy Praveen, Srivastava S C, and Singh S N. A modified TLS-ESPRIT-Based method for low-frequency mode identification in power pystems utilizing synchrophasor measurements[J]., 2011, 26(2): 719-727.

[5] 莊學彬, 陸明泉, 馮振明. 一種數值穩健且低復雜度的信號子空間估計新方法[J]. 電子與信息學報, 2011, 33(1): 90-94.

Zhuang Xue-bin, Lu Ming-quan, and Feng Zhen-ming. A numerically robust and low-complexity method of signal subspace estimation[J].&, 2011, 33(1): 90-94.

[6] Azarbar A and Dadashzadeh G. A new DOA estimation based on direct data domain algorithm[C]. 2011 IEEE GCC Conference and Exhibition, Dubai, United Arab Emirates, Feb. 19-22, 2011: 205-208.

[7] Paine A S. Fast MUSIC for large 2-D element digitised phased array radar[C]. 2003 IEEE Rader Conference, Adelaide, Australia, May 5-8, 2003: 200-205.

[8] Liu Lu-tao, Si Xi-cai, and Wang Li-guo. Fast subspace DOA algorithm based on time-frequency distributions without eigen decomposition[C]. 3rd International Conference on Measuring Technology and Mechatronics Automation, Shanghai, China, Jan. 6-7, 2011, 2: 170-173.

[9] 鄧鍵敏, 吳瑛. 基于MH抽樣逐次搜索的快速MUSIC 算法[J]. 計算機工程與設計, 2010, 31(20): 4508-4511.

Deng Jian-min and Wu Ying. Fast MUSIC algorithm via metropolis-hastings sampler and sequential searching[J]., 2010, 31(20): 4508-4511.

[10] Minseok Kim, Koichi Ichige, and Hiroyuki Arai. Implementation of FPGA based fast DOA estimator using unitary MUSIC algorithm [C]. 2009 IEEE Rader Conference, California, USA, Apr. 20-22, 2009: 4-8.

[11] 董照飛. 基于DSP的MUSIC 算法的實現[J]. 現代電子技術, 2006, 23(7): 21-23.

Dong Zhao-fei. The realization of MUSIC arithmetic based on DSP[J]., 2006, 23(7): 21-23.

[12] 張興良, 阮懷林, 王樹亮. 圓陣列MUSIC 算法快速測向技術[J]. 數據采集與處理, 2011, 26(3): 374-378.

Zhang Xing-liang, Ruan Huai-lin, and Wang Shu-liang. A fast direction finding technology based on MUSIC algorithm with circular array[J].&, 2011, 26(3): 374-378.

[13] Wang X and Zhang X P. Optimal look-up table-based data hiding[J]., 2011, 5(2): 171-179.

[14] Zhang Q T. Probability of resolution of the MUSIC algorithm [J]., 1995, 43(4): 978-987.

Study on Fast MUSIC Algorithm with Typical Array

Zhang Xing-liang Wang Ke-ren Fan Fu-hua

(Department of Information Engineering, Electronic Engineering Institute, Hefei 230037, China)

Because MUSIC (MUltiple SIgnal Classification) algorithm needs a large number of multiplications and trigonometric function evaluations, it is weak in the real time processing. This paper is aim at resolving above problem. Firstly, by analyzing the structural features of the uniform circular array and the uniform linear array, some properties of steering vector are extracted. Then, the properties of Hermite matrix are employed to decompose the complex multiplication, and then two real vectors are constructed to reduce the number of multiplications. Finally, with the properties of steering vector, a new algorithm based on look-up-table is proposed. The new algorithm neither has any trigonometric function evaluation, nor requires much memory space. The result of simulation experiments shows that the new algorithm raises the rate of MUSIC algorithm more than 50 times, while ensures the same estimated results. Therefore, the new algorithm has a wide application prospect.

Typical array; Steering vector; Look-up-table method; Fast MUSIC (MUltiple SIgnal Classification) algorithm

TN911.7

A

2095-283X(2012)02-0149-08

10.3724/SP.J.1300.2012.20026

2012-04-23收到，2012-06-13改回；2012-06-20網絡優先出版

國家自然科學基金 (61171170) 資助課題

張興良 305755450@qq.com

張興良(1985-)，男，安徽合肥人，博士生，研究方向為雷達信號處理、智能天線。

E-mail: tianyawubian@sina.com

王可人(1957-)，男，江蘇鎮江人，教授，博士生導師，總參某站主任，研究方向為通信信號處理、雷達信號處理。

E-mail: wangkeren0512@126.com

樊甫華(1975-)，男，安徽蕪湖人，講師，研究方向為雷達信號處理。

E-mail: davidfaneei@163.com