典型陣列快速MUSIC算法研究

張興良* 王可人 樊甫華

?

典型陣列快速MUSIC算法研究

張興良王可人 樊甫華

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

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

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

1 引言

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

遺憾的是，超分辨空間譜估計算法需要大量的乘法和三角函數(shù)求值，因此其計算耗時難以滿足工程需要。在圓陣、方陣等2維陣列中，該問題表現(xiàn)得更加突出。實際上，巨大的計算量已成為超分辨空間譜估計技術(shù)完全走向?qū)嵱没闹饕款i之一。

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

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

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

2 典型陣列分析

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

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

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

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

2.1 均勻線陣

其中

圖1 均勻線陣結(jié)構(gòu)圖

(3)

(4)

(6)

性質(zhì)1均勻線陣導(dǎo)向矢量具有共軛對稱性，即

證明

(8)

2.2 均勻圓陣

(10)

圖2 均勻圓陣列結(jié)構(gòu)圖

性質(zhì)2均勻圓陣導(dǎo)向矢量具有對稱性，記

（12）

證明

(14)

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

證明

證畢

本質(zhì)上，性質(zhì)1-性質(zhì)3都是由特殊的陣列結(jié)構(gòu)決定的。

3 MUSIC算法的改進

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

(18)

分別令：

(20)

(21)

(23)

(24)

再令：

(26)

(28)

(29)

(31)

3.1 均勻線陣MUSIC算法改進

同理可得

（35）

(37)

其中

則

(38)

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

3.2 均勻圓陣MUSIC算法改進

令

(40)

可得

(42)

同理

表1 改進前后乘法運算次數(shù)

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

4 改進的查表法

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

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

4.1 均勻線陣情形

對于均勻線陣，由性質(zhì)1可得

（45）

因此

4.2 均勻圓陣情形

對于均勻圓陣，記

由性質(zhì)2可得

(49)

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

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

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

5 仿真分析

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

表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倍，實際耗時倍數(shù)與理論耗時倍數(shù)基本一致。橫向比較，標準MUSIC算法譜估計耗時超過查表法的60倍，查表法的優(yōu)勢非常明顯?？梢钥闯?，精確譜估計需要的代價很大，實時性較差；標準MUSIC算法很難滿足工程需要，但是本文的查表法大幅提高了MUSIC算法的實時性。

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

表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相同的結(jié)論。橫向比較，改進的查表法和直接查表法譜估計耗時相近；標準MUSIC算法譜估計耗時是改進查表法和直接查表法的50–60倍，是間接查表法的10倍以上。標準MUSIC算法耗時最為嚴重，間接查表法次之，直接查表法和改進的查表法耗時最少。通過譜估計圖可以看出改進的查表法譜估計準確性較好。

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

表5 制表占用內(nèi)存大小比較

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

6 總結(jié)

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

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

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

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] 郭躍. 超分辨波達方向估計技術(shù)的研究[D]. [博士論文], 華中科技大學(xué), 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] 莊學(xué)彬, 陸明泉, 馮振明. 一種數(shù)值穩(wěn)健且低復(fù)雜度的信號子空間估計新方法[J]. 電子與信息學(xué)報, 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]. 計算機工程與設(shè)計, 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 算法的實現(xiàn)[J]. 現(xiàn)代電子技術(shù), 2006, 23(7): 21-23.

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

[12] 張興良, 阮懷林, 王樹亮. 圓陣列MUSIC 算法快速測向技術(shù)[J]. 數(shù)據(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網(wǎng)絡(luò)優(yōu)先出版

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

張興良 305755450@qq.com

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

E-mail: tianyawubian@sina.com

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

E-mail: wangkeren0512@126.com

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

E-mail: davidfaneei@163.com