張興良* 王可人 樊甫華

?

典型陣列快速M(fèi)USIC算法研究

張興良王可人 樊甫華

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

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

典型陣列；導(dǎo)向矢量；查表法；快速M(fèi)USIC(MUltiple SIgnal Classification)算法

1 引言

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

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

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

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

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

2 典型陣列分析

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

(1) 入射信號(hào)是遠(yuǎn)場(chǎng)的，且是窄帶的；

(2) 相鄰陣元間距小于信號(hào)載波波長(zhǎng)的一半；

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

2.1 均勻線陣

其中

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

(3)

(4)

(6)

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

證明

(8)

2.2 均勻圓陣

(10)

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

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

（12）

證明

(14)

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

證明

證畢

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

3 MUSIC算法的改進(jìn)

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

(18)

分別令：

(20)

(21)

(23)

(24)

再令：

(26)

(28)

(29)

(31)

3.1 均勻線陣MUSIC算法改進(jìn)

同理可得

（35）

(37)

其中

則

(38)

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

3.2 均勻圓陣MUSIC算法改進(jìn)

令

(40)

可得

(42)

同理

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

標(biāo)準(zhǔn)MUSIC算法改進(jìn)后(圓陣)改進(jìn)后(線陣)

4 改進(jìn)的查表法

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

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

4.1 均勻線陣情形

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

（45）

因此

4.2 均勻圓陣情形

對(duì)于均勻圓陣，記

由性質(zhì)2可得

(49)

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

表2 均勻線陣和均勻圓陣的存儲(chǔ)空間需求

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

5 仿真分析

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

表3 譜估計(jì)耗時(shí)比較(300次總計(jì))

步進(jìn)標(biāo)準(zhǔn)MUSIC算法(s)本文改進(jìn)的查表法(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°步進(jìn)耗時(shí)是0.05°步進(jìn)耗時(shí)的5倍、是1°步進(jìn)耗時(shí)的10倍、是0.3°步進(jìn)耗時(shí)的30倍，實(shí)際耗時(shí)倍數(shù)與理論耗時(shí)倍數(shù)基本一致。橫向比較，標(biāo)準(zhǔn)MUSIC算法譜估計(jì)耗時(shí)超過(guò)查表法的60倍，查表法的優(yōu)勢(shì)非常明顯?？梢钥闯觯_譜估計(jì)需要的代價(jià)很大，實(shí)時(shí)性較差；標(biāo)準(zhǔn)MUSIC算法很難滿足工程需要，但是本文的查表法大幅提高了MUSIC算法的實(shí)時(shí)性。

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

表4 譜估計(jì)耗時(shí)比較(100次平均)

步進(jìn)標(biāo)準(zhǔn)MUSIC算法(s)本文改進(jìn)的查表法(s)文獻(xiàn)[12]直接查表法(s)文獻(xiàn)[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é)論。橫向比較，改進(jìn)的查表法和直接查表法譜估計(jì)耗時(shí)相近；標(biāo)準(zhǔn)MUSIC算法譜估計(jì)耗時(shí)是改進(jìn)查表法和直接查表法的50–60倍，是間接查表法的10倍以上。標(biāo)準(zhǔn)MUSIC算法耗時(shí)最為嚴(yán)重，間接查表法次之，直接查表法和改進(jìn)的查表法耗時(shí)最少。通過(guò)譜估計(jì)圖可以看出改進(jìn)的查表法譜估計(jì)準(zhǔn)確性較好。

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

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

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

6 總結(jié)

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

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

[1] 張小飛, 汪飛, 徐大專(zhuān). 陣列信號(hào)處理的理論和應(yīng)用[M]. 北京: 國(guó)防工業(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] 郭躍. 超分辨波達(dá)方向估計(jì)技術(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ù)雜度的信號(hào)子空間估計(jì)新方法[J]. 電子與信息學(xué)報(bào), 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抽樣逐次搜索的快速M(fèi)USIC 算法[J]. 計(jì)算機(jī)工程與設(shè)計(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 算法的實(shí)現(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] 張興良, 阮懷林, 王樹(shù)亮. 圓陣列MUSIC 算法快速測(cè)向技術(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)先出版

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

張興良 305755450@qq.com

張興良(1985-)，男，安徽合肥人，博士生，研究方向?yàn)槔走_(dá)信號(hào)處理、智能天線。

E-mail: tianyawubian@sina.com

王可人(1957-)，男，江蘇鎮(zhèn)江人，教授，博士生導(dǎo)師，總參某站主任，研究方向?yàn)橥ㄐ判盘?hào)處理、雷達(dá)信號(hào)處理。

E-mail: wangkeren0512@126.com

樊甫華(1975-)，男，安徽蕪湖人，講師，研究方向?yàn)槔走_(dá)信號(hào)處理。

E-mail: davidfaneei@163.com