代鸝鵬，王布宏，沈海鷗，賈月嶺

(1．空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西西安710077; 2．空軍工程大學(xué)裝備管理與安全工程學(xué)院，陜西西安710077)

?

基于文法派生解析表的多功能雷達(dá)快速參數(shù)估計(jì)方法

代鸝鵬1，王布宏1，沈海鷗1，賈月嶺2

(1．空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西西安710077; 2．空軍工程大學(xué)裝備管理與安全工程學(xué)院，陜西西安710077)

摘要:隨機(jī)上下文無(wú)關(guān)文法(SCFG)在多功能雷達(dá)(MFR)狀態(tài)識(shí)別和威脅估計(jì)中具有良好的應(yīng)用前景．為了減少常規(guī)算法的運(yùn)算復(fù)雜度，本文提出一種基于解析表構(gòu)造的多功能雷達(dá)參數(shù)快速估計(jì)方法．該方法通過(guò)對(duì)截獲的每個(gè)雷達(dá)數(shù)據(jù)序列構(gòu)造庫(kù)克-楊-卡塞米(CKY)解析表，排除了大量未參與序列派生過(guò)程的產(chǎn)生式，隨后在解析表的基礎(chǔ)上采用改進(jìn)的Inside-Outside(IO)算法對(duì)雷達(dá)文法產(chǎn)生式概率和多功能雷達(dá)狀態(tài)進(jìn)行快速估計(jì)．理論分析與實(shí)驗(yàn)仿真證明，該算法在參數(shù)估計(jì)精度相同的條件下，其運(yùn)算時(shí)間相對(duì)于常規(guī)IO算法和Viterbi-Score(VS)算法減少了50％以上．

關(guān)鍵詞:電子戰(zhàn);多功能雷達(dá);隨機(jī)上下文無(wú)關(guān)語(yǔ)法;參數(shù)學(xué)習(xí)

1　引言

電子支持系統(tǒng)(Electronic Support，ES)在復(fù)雜電磁環(huán)境下截獲分析輻射源信號(hào)，并向載機(jī)提供實(shí)時(shí)的戰(zhàn)場(chǎng)環(huán)境態(tài)勢(shì)等情報(bào)［1］．對(duì)于常規(guī)體制雷達(dá)，ES系統(tǒng)通過(guò)雷達(dá)信號(hào)的瞬時(shí)特性，采用基于參數(shù)類的建模方法便可對(duì)雷達(dá)類型及其工作狀態(tài)進(jìn)行有效識(shí)別［2］．而多功能雷達(dá)(Multi-Function Radars，MFR)采用靈活復(fù)雜的軟件算法對(duì)波束進(jìn)行控制，能夠以高捷變的方式對(duì)多個(gè)目標(biāo)進(jìn)行操作，若通過(guò)參數(shù)類的建模方式來(lái)描述MFR的信號(hào)變化規(guī)律，其參數(shù)空間將成指數(shù)增長(zhǎng)［3］．為了對(duì)MFR的這種動(dòng)態(tài)性進(jìn)行有效描述，Nikita等人利用Markov調(diào)制的隨機(jī)上下文無(wú)關(guān)文法(Stochastic Context-Free Grammars，SCFG)對(duì)MFR輻射信號(hào)進(jìn)行建模［4］，這為MFR參數(shù)估計(jì)提出了新的思路—基于模型類的ES系統(tǒng)．

在截獲的雷達(dá)情報(bào)基礎(chǔ)上對(duì)MFR雷達(dá)參數(shù)進(jìn)行估計(jì)和威脅分析是模型類ES系統(tǒng)面臨的技術(shù)瓶頸，而對(duì)文法產(chǎn)生式概率進(jìn)行學(xué)習(xí)是SCFG應(yīng)用的一個(gè)關(guān)鍵問(wèn)題．通常將期望最大化算法(Expectation-Maximization，EM)應(yīng)用于Inside-Outside(IO)算法［5］和Viterbi-Score (VS)算法［6］對(duì)文法概率進(jìn)行迭代估計(jì)．其中，IO算法通過(guò)尋求訓(xùn)練數(shù)據(jù)集的最大全局似然對(duì)概率進(jìn)行估計(jì)，計(jì)算量較大，對(duì)于文法模型比較復(fù)雜的MFR并不適用．VS算法利用訓(xùn)練數(shù)據(jù)集最優(yōu)派生過(guò)程的最大似然對(duì)產(chǎn)生式概率分布進(jìn)行估計(jì)，相對(duì)于IO算法而言，雖然減少了運(yùn)算量，但是以降低估計(jì)精度為代價(jià)的，且這兩種方法的收斂速度和運(yùn)算量均無(wú)法滿足實(shí)戰(zhàn)需求．針對(duì)上述問(wèn)題，本文主要做了以下工作:

(1)在基于IO算法的MFR狀態(tài)識(shí)別基礎(chǔ)上，提出一種基于解析表(parse chart)的IO算法(P(IO) )對(duì)文法參數(shù)和MFR狀態(tài)進(jìn)行快速估計(jì);

(2)理論分析并比較了IO、VS和P(IO)算法的計(jì)算復(fù)雜度;

(3)通過(guò)仿真實(shí)驗(yàn)證明P(IO)算法在保證參數(shù)估計(jì)精度的同時(shí)可以有效降低運(yùn)算時(shí)間．

2　MFR雷達(dá)信號(hào)的文法建模

利用文法技術(shù)對(duì)MFR進(jìn)行建模，需引進(jìn)雷達(dá)字和雷達(dá)短語(yǔ)的概念．雷達(dá)字為MFR的最小輻射單元［7］，由有限個(gè)數(shù)脈沖的特定排列構(gòu)成，雷達(dá)短語(yǔ)為有限雷達(dá)字的特定排列．在ES系統(tǒng)中，可將MFR信號(hào)當(dāng)做依據(jù)某種特定文法產(chǎn)生的形式語(yǔ)言，然后利用文法分析技術(shù)對(duì)MFR雷達(dá)參數(shù)進(jìn)行估計(jì)．

由于上下文無(wú)關(guān)文法(Context-Free Grammars，CFG)的表達(dá)能力十分突出［8］，且形式比較簡(jiǎn)單，使得我們可以構(gòu)造有效的分析算法對(duì)其產(chǎn)生的語(yǔ)言進(jìn)行分析，因此可利用CFG對(duì)MFR進(jìn)行文法建模．CFG為一個(gè)四元組G = { V，N，R，S}，其中V為非終結(jié)符集合，即雷達(dá)短語(yǔ)集; N為終止符集合，即雷達(dá)字集，N∩V =; R為產(chǎn)生式集合，其形式為A→λ，其中A∈V，λ∈(V∪N)+; S∈V為初始符．CFG的語(yǔ)言集定義為L(zhǎng)g(G)，SCFG為CFG的擴(kuò)展，即Gs= { G，P}，我們稱G為Gs的文法結(jié)構(gòu)，其中，P為賦予文法產(chǎn)生式的概率，且滿足的約束條件．

利用SCFG對(duì)MFR建模，可將MFR系統(tǒng)結(jié)構(gòu)分為五個(gè)模塊，其中雷達(dá)管理模塊依據(jù)態(tài)勢(shì)感知模塊提供的態(tài)勢(shì)評(píng)估結(jié)果選擇雷達(dá)需要執(zhí)行的任務(wù)狀態(tài)，其狀態(tài)選擇機(jī)制是一個(gè)Markov過(guò)程，MFR的M個(gè)任務(wù)狀態(tài)構(gòu)成狀態(tài)空間Nr．在每個(gè)狀態(tài)ei∈Nr，雷達(dá)依據(jù)文法產(chǎn)生特定的雷達(dá)信號(hào)，不同狀態(tài)對(duì)應(yīng)的文法之間除了產(chǎn)生式概率不同之外其余參數(shù)均相同［9］．依據(jù)該建模方法，可得到MFR雷達(dá)的信號(hào)產(chǎn)生機(jī)制如圖1所示．

3　CKY圖表解析算法

一個(gè)隨機(jī)文法Gs從初始符S開始產(chǎn)生序列η∈Lg(Gs)的最左導(dǎo)出稱為η的派生過(guò)程，派生過(guò)程僅與文法結(jié)構(gòu)有關(guān)，而與文法的概率無(wú)關(guān)［10］，因此我們可以對(duì)每一個(gè)序列利用CKY解析法［11］或Early解析法［12］提前構(gòu)造一個(gè)可以精確描述該派生過(guò)程的解析表，利用這種解析表排除沒(méi)有參與派生過(guò)程的產(chǎn)生式，從而可以減少算法運(yùn)算量．

CKY算法所處理的文法結(jié)構(gòu)必須滿足Chomsky正則形式［13］，即R中只含有輻射規(guī)則A→w和轉(zhuǎn)移規(guī)則A →C兩種形式的產(chǎn)生式．根據(jù)不同的產(chǎn)生式定義不同的子樹結(jié)構(gòu)來(lái)確定η的子序列母節(jié)點(diǎn)，其中產(chǎn)生式A→a對(duì)應(yīng)的子樹結(jié)構(gòu)為A(i，j)→a，表示wj= a，且A→wj∈R．產(chǎn)生式A→BC對(duì)應(yīng)的子樹結(jié)構(gòu)為A (i，j)→B(i，k) C(k +1，j)，表示文法以A為母節(jié)點(diǎn)產(chǎn)生子序列wi，wi +1，…，wj，在該子序列中，wi，…，wk以B為母節(jié)點(diǎn)，wk +1，…，wj以C為母節(jié)點(diǎn)，且A→BC∈R．

長(zhǎng)度為L(zhǎng)的序列的解析表T是一個(gè)三角形表，每個(gè)表中第i行第j列的參數(shù)為T(i，j) (1≤i≤L，1≤j≤L +1 －i)．對(duì)于η的某個(gè)子串，若有A?wi，wi +1，…，wj，則把A(i，j)→…存入T(i，j)中．在構(gòu)造出解析表后，當(dāng)且僅當(dāng)S(1，L)→…存在于T(1，L)中時(shí)，η∈Lg(Gs)．

對(duì)于序列η= (w1，…，wL)，按照下列步驟從左到右、從最高行到最低行順次構(gòu)造解析表:

Step1按照i =1到i = L的次序求T(i，i)，若A→wi∈R，則將A(i，i)→wi填入T(i，i)．

Step2假設(shè)對(duì)1≤i≤L已經(jīng)求出T(i，j－1)，現(xiàn)在求T(i，j)．對(duì)于i = L－1: 1，有j = i +1: L，則對(duì)于1≤k≤j －1中的任何一個(gè)k值，當(dāng)A→BC∈R，且B(i，k)→…∈T(i，k)，C(k + 1，j)→…∈T(k + 1，j)，則將A(i，j)→B (i，k) C(k +1，j)填入T(i，j)．

Step3重復(fù)第二步直至完成此表或表的整行都是空項(xiàng)．

假設(shè)文法G具有如下產(chǎn)生式: S→AB，S→AC，A→a，B→b，C→SB，其語(yǔ)言集為L(zhǎng)g(G) = {η|ambm，m≥1}．假設(shè)輸入序列為aabb，通過(guò)CKY算法可得該序列的CKY解析表如圖2所示．由于S處于T(1，4)中，因此序列aabb∈Lg(G)．

4　基于解析表的MFR參數(shù)快速估計(jì)算法

通過(guò)對(duì)每個(gè)序列提前構(gòu)造如圖4所示的解析表可以發(fā)現(xiàn)，解析表中的子樹結(jié)構(gòu)參數(shù)描述了文法產(chǎn)生η的所有派生過(guò)程，我們可在算法每次迭代過(guò)程中利用解析表排除不參與派生的參數(shù)，從而可以減少計(jì)算量．

4.1MFR文法概率快速估計(jì)算法

令x1: m= (x1，x2，…，xm)為MFR雷達(dá)的狀態(tài)序列，xk∈Nr．η1: m= (η1，η2，…，ηm)表示截獲得到的MFR產(chǎn)生的m個(gè)終結(jié)符序列，其中ηi= (w1，w2，…，wLi)，Li表示ηi的長(zhǎng)度．首先引入內(nèi)部概率和外部概率［14］的概念，內(nèi)部概率αA(i，j)= P(wij|A，Gs)，表示Gs從非終結(jié)符A開始，生成終結(jié)符序列wi，…，wj的概率．外部概率βA(i，j)= P(w1(i－1)，A，w(j +1) m| Gs)，表示從Gs的起始符S開始生成非終結(jié)符A以及wi，…，wj外部所有終結(jié)符序列的概率．

P(IO)算法首先利用解析表計(jì)算ηt的內(nèi)部概率和外部概率，然后對(duì)文法Gs(n)產(chǎn)生序列ηt時(shí)產(chǎn)生式的期望使用次數(shù)求解，然后在此基礎(chǔ)上對(duì)文法概率進(jìn)行重估，算法步驟如下:

Step1自底到頂求解內(nèi)部概率．若子序列只由一個(gè)終止符wj= a，且有A→a∈R，則依據(jù)該序列對(duì)應(yīng)的CKY解析表中子樹結(jié)構(gòu)A(j，j)→a計(jì)算內(nèi)部概率:

若子序列有多個(gè)終止符wi，…，wj，則利用A(i，j)→B(i，k) C(k +1，j)計(jì)算子序列對(duì)應(yīng)的內(nèi)部概率:

Step2在序列內(nèi)部概率的基礎(chǔ)上自頂?shù)降浊蠼馔獠扛怕剩紫葘?duì)外部概率進(jìn)行初始化:

Step3求解產(chǎn)生式使用次數(shù)．在序列內(nèi)部概率和外部概率基礎(chǔ)上，文法G(n)產(chǎn)生序列ηt時(shí)產(chǎn)生式的期望使用次數(shù)為:

Step4概率重估．在得到文法產(chǎn)生每個(gè)序列的產(chǎn)生式期望使用次數(shù)以后，文法產(chǎn)生式的概率便可估計(jì)為:

其中ξt(i，j) = P(xt= ei，xt +1= ej|η1: m)表示在t時(shí)刻MFR處于ei狀態(tài)，t +1時(shí)刻處于ej狀態(tài)的概率．χt(i，j) = P(xt=ei|η1: m)表示MFR在t時(shí)刻處于狀態(tài)ei的概率．則雷達(dá)管理模塊對(duì)應(yīng)的Markov鏈狀態(tài)轉(zhuǎn)移概率可估計(jì)為:

通過(guò)對(duì)上述步驟進(jìn)行迭代計(jì)算，一直到文法概率變化很小時(shí)結(jié)束．每經(jīng)過(guò)一次迭代，模型對(duì)于給定數(shù)據(jù)的似然性都會(huì)增加，這保證了每次迭代都會(huì)產(chǎn)生更優(yōu)的模型參數(shù)．

4.2MFR狀態(tài)估計(jì)算法

通過(guò)P(IO)算法得到文法參數(shù)后，便可利用Viterbi算法對(duì)MFR所處狀態(tài)進(jìn)行估計(jì)．MFR雷達(dá)在k時(shí)刻的狀態(tài)估計(jì)為)xk= arg maxiP(xk= ei|η1: m)，定義Viterbi變量δi(t) = maxx1，x2，…，xt－1P(xk= ei|η1: t)，其含義為MFR在時(shí)刻t處于狀態(tài)ei，產(chǎn)生η1，…，ηt的最佳狀態(tài)轉(zhuǎn)換序列為x1，…，xt的概率．令Ψi(t)記錄MFR在時(shí)刻t到達(dá)狀態(tài)ei的最佳狀態(tài)轉(zhuǎn)換序列t－1時(shí)刻的最佳狀態(tài)，則估計(jì)MFR狀態(tài)的算法可歸納如下:

Step1初始化:

Step 2迭代計(jì)算:

Step 3終止:

Step 4求解MFR最佳狀態(tài)轉(zhuǎn)換序列:

其中，Οi(ηk)表示文法G(i)產(chǎn)生序列ηk的概率，即:

由上述分析可知，P(IO)算法在迭代計(jì)算之前對(duì)每個(gè)訓(xùn)練序列構(gòu)造解析表，排除了并未參與序列派生過(guò)程的參數(shù)，可以提高運(yùn)算效率，并保證算法精度不變．

4.3算法計(jì)算復(fù)雜度分析

計(jì)算復(fù)雜度T表示對(duì)一個(gè)序列進(jìn)行一次迭代所需要的乘法和除法運(yùn)算次數(shù)，為了對(duì)其進(jìn)行理論分析，首先引進(jìn)表1所示的參數(shù)概念．

表1　參數(shù)說(shuō)明

則對(duì)于IO算法而言，其計(jì)算復(fù)雜度TIO為:

對(duì)于VS算法而言，其計(jì)算復(fù)雜度TVS為:

對(duì)于P(IO)算法，其平均計(jì)算復(fù)雜度TP(IO)為:

給定一個(gè)文法，φt、φe和|Δlt|反應(yīng)了文法的模糊性，因此，P(IO)算法的計(jì)算復(fù)雜度與文法的模糊性具有很大關(guān)聯(lián)．文獻(xiàn)［4］中所描述的“水星”MFR雷達(dá)部分文法產(chǎn)生式為S→ACQ RR、ACQ→ACQ NA|W1W1|W2W2|W3W3|W4W4|、NA→S1T、RR→RR NA|RRpACQ、T→W2W5、NAp→W2| W3、RRp→W4| W5、S1→W1| W2| W3、W1→w1、W2→w2、W3→w3、W4→w4和W5→w5，其中非終止符集V = { S，ACQ，RR，NA，S1，T，NAP，RRP，W1，W2，W3，W4，W5}，終止符集N = { w1，w2，w3，w4，w5}，初始符為S．該MFR雷達(dá)具有兩個(gè)狀態(tài)，即M = 2，由該文法產(chǎn)生序列構(gòu)造的解析表中，|Δlt|max=3，而|φt|和|φe|與序列的長(zhǎng)度有關(guān)．考慮最壞條件下，即文法產(chǎn)生式完全分布時(shí)，|φt|max= Mnt·(L2－1)，|φe|max= Mnt·L，此時(shí)文法則該文法的計(jì)算復(fù)雜度為:

依據(jù)式(17)、(18)和(20)，可對(duì)不同序列長(zhǎng)度與不同算法的計(jì)算復(fù)雜度進(jìn)行比較，結(jié)果如圖3所示．

5　實(shí)驗(yàn)仿真與分析

為了驗(yàn)證本文的算法，我們利用上述的“水星”MFR雷達(dá)部分文法產(chǎn)生式進(jìn)行分析．在該文法基礎(chǔ)上，我們?cè)O(shè)計(jì)兩個(gè)實(shí)驗(yàn):第一個(gè)實(shí)驗(yàn)對(duì)算法時(shí)間復(fù)雜度進(jìn)行分析．第二個(gè)實(shí)驗(yàn)對(duì)算法的收斂時(shí)間和精度進(jìn)行分析．

5.1算法時(shí)間復(fù)雜度分析

假設(shè)該MFR的兩個(gè)狀態(tài)分別對(duì)應(yīng)文法G(1)和G(2)，由狀態(tài)轉(zhuǎn)移矩陣為(A = (0.7，0.3; 0.4，0.6) )的Markov鏈隨機(jī)產(chǎn)生一系列雷達(dá)狀態(tài)，每個(gè)狀態(tài)依據(jù)文法G(1)或G(2)產(chǎn)生終結(jié)符序列，然后對(duì)產(chǎn)生式概率和狀態(tài)轉(zhuǎn)移概率進(jìn)行估計(jì)．經(jīng)過(guò)100次Monte Carlo實(shí)驗(yàn)，得到算法的運(yùn)行時(shí)間結(jié)果如圖4所示．

圖4為算法對(duì)50個(gè)訓(xùn)練序列進(jìn)行不同迭代次數(shù)所需的運(yùn)行時(shí)間．由圖4可知，隨著訓(xùn)練序列個(gè)數(shù)與迭代次數(shù)的增加，IO算法的運(yùn)行時(shí)間也急劇增加，這導(dǎo)致了其實(shí)際應(yīng)用的局限性．VS算法只對(duì)最優(yōu)派生過(guò)程進(jìn)行求解，算法對(duì)序列進(jìn)行一次迭代運(yùn)行時(shí)間比IO算法減少60％左右．P(IO)算法由于提前計(jì)算得到訓(xùn)練序列的解析表，且計(jì)算過(guò)程中只對(duì)解析表中的路徑求解，其每次迭代所需的時(shí)間僅為VS算法的四分之一左右，通過(guò)與圖3比較可知，實(shí)驗(yàn)值可以很好的符合理論分析．

5.2算法性能分析

該實(shí)驗(yàn)通過(guò)對(duì)比IO算法、VS算法和P(IO)算法的收斂時(shí)間以及收斂后估計(jì)結(jié)果的精度來(lái)判別算法性能．定義第n +1次迭代結(jié)果和第n次迭代結(jié)果的均方誤差和［15］小于0.001時(shí)結(jié)束，定義真實(shí)值與算法估計(jì)值的就均方誤差和、MFR狀態(tài)估計(jì)概率來(lái)度量文法參數(shù)估計(jì)精度，經(jīng)過(guò)100次Monte Carlo實(shí)驗(yàn)，不同序列個(gè)數(shù)的收斂時(shí)間與收斂后文法估計(jì)精度結(jié)果如圖5所示．算法對(duì)50個(gè)訓(xùn)練序列經(jīng)過(guò)不同迭代次數(shù)后的估計(jì)精度如圖6和圖7所示．

圖5為不同序列個(gè)數(shù)與算法收斂時(shí)間的比較，由圖5可知，IO算法的收斂時(shí)間隨著序列個(gè)數(shù)的增加急劇增長(zhǎng)，而VS算法的收斂時(shí)間約為IO算法的三分之一左右，P(IO)算法的收斂時(shí)間約為VS算法的四分之一．圖6和圖7為算法對(duì)50個(gè)序列進(jìn)行迭代的估計(jì)結(jié)果，由圖6可知，隨著迭代次數(shù)的增加，文法的估計(jì)精度也逐漸增加．文法估計(jì)精度會(huì)影響到MFR狀態(tài)的估計(jì)，由圖7可知，隨著迭代次數(shù)的增加，IO算法的與P(IO)算法的狀態(tài)估計(jì)概率提高至0.87，而VS算法的狀態(tài)估計(jì)概率為0.85，因此，P(IO)算法可以在保持與IO算法精度的同時(shí)，可以有效減少運(yùn)算量．

6　結(jié)論

本文針對(duì)基于文法建模的MFR雷達(dá)參數(shù)估計(jì)算法進(jìn)行研究，提出了一種基于解析表的快速M(fèi)FR雷達(dá)參數(shù)估計(jì)算法．該算法通過(guò)CKY解析算法對(duì)截獲的訓(xùn)練序列集預(yù)先構(gòu)造解析表，在序列集解析表的基礎(chǔ)上排除未參與序列派生過(guò)程的產(chǎn)生式，從而加快參數(shù)學(xué)習(xí)過(guò)程．通過(guò)理論分析與試驗(yàn)仿真表明，該方法可以在確保與IO算法同樣精度的基礎(chǔ)下，大大加快文法產(chǎn)生式的重估過(guò)程，在ES系統(tǒng)實(shí)際應(yīng)用中具有重要意義．如何在ES系統(tǒng)中在線估計(jì)文法概率是我們下一步研究的重點(diǎn)．

參考文獻(xiàn)

［1］劉海軍，李悅，柳征，周一宇．基于隨機(jī)文法的多功能雷達(dá)識(shí)別方法［J］．航空學(xué)報(bào)，2010，31(9) : 1809-1817．LIU Hai-jun，LI Yue，LIU Zheng，ZHOU Yi-yu．Approach to multi-function radar identification based on stochastic grammars［J］．Acta Aeronautica Et Astronautica Sinica，2010，31(9) : 1809－1817．(in Chinese)

［2］劉海軍．雷達(dá)輻射源識(shí)別關(guān)鍵技術(shù)研究［D］．湖南長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué)，2010．

［3］Wang A，Krishnamurthy V．Signal interpretation of multifunction radars: modeling and statistical signal processing with stochastic context free grammar［J］．IEEE Transactions on Signal Processing，2008，56(3) : 1106－1119．

［4］Nikita V．Syntactic Modeling of Mufti-Function Radars ［D］．Canada: McMaster University，2005．

［5］Lari K，Young S．The estimation of stochastic context-Free grammars using the inside-outside algorithm［J］．Computer Speech and Language，1990，4(1) : 35－56．

［6］Ney H．Stochastic Grammars and Pattern Recognition［M］．New York: Springer Verlag，1992．319－344．

［7］馬爽，柳征，姜文利．基于幅度變化點(diǎn)檢測(cè)的多功能雷達(dá)脈沖列解析方法［J］．電子學(xué)報(bào)，2013，41 (7) : 1436 －1441．MA Shuang，LIU Zheng，JIANG Wen-li．A method for multi-function radar pulse train analysis based on amplitude change point detection［J］．Acta Elcctronica Sinica，2013，41(7) : 1436－1441．(in Chinese)

［8］陸玲，周書民．形式語(yǔ)言與自動(dòng)機(jī)及程序設(shè)計(jì)［M］．哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2014．11－16．

［9］Wang A，Krishnamurthy V．Threat estimation of multi-function radars: modeling and statistical signal processing of stochastic context free grammars［A］．IEEE International Conference on Acoustics，Speech，and Signal Processing［C］．Honolulu，USA: ICASSP，2007．793－796．

［10］Gonzalez R C，Manning G T．句法模式識(shí)別［M］．濮群，譯．北京:清華大學(xué)出版社，1984．84－88．

［11］TsuruokaY，Tsujii J．Iterative CKY parsing for probabilistic context-free grammars［A］．First International Joint Conference on Natural Language Processing［C］．Hainan Island，China: IJCNLP，2005．52－60．

［12］J．Early．An efficient context-free parsing algorithm［J］．Communication of the ACM，1970，13(2) : 84－102．

［13］Manning D，Hinrich S．統(tǒng)計(jì)自然語(yǔ)言處理基礎(chǔ)［M］．范春法，等，譯．北京:電子工業(yè)出版社，2002．241－256．

［14］Visnevski N，Krishnamurthy V，Wang A，Haykin S．Syntactic modeling and signal processing of multi-function radars: a stochastic context-free grammar approach［J］．Proceedings of the IEEE，2007，95(5) : 1000－1025．

［15］代鸝鵬，王布宏，蔡斌，劉軍利．基于SCFG建模的多功能雷達(dá)狀態(tài)估計(jì)算法［J］．空軍工程大學(xué)學(xué)報(bào)·自然版，2014，15(3) : 24－28．DAI Li-peng，WANG Bu-hong，CAI Bin，LIU Jun-li．A method for states estimation of multi-function radar based on stochastic context-free grammar［J］．Journal of Air Force Engineering University(Natural Science Edition)，2014，15(3) : 24－28．(in Chinese)

代鸝鵬男，1989年1月出生于甘肅省平?jīng)鍪校F(xiàn)為空軍工程大學(xué)信息與導(dǎo)航學(xué)院碩士研究生．主要研究方向?yàn)槎喙δ芾走_(dá)信號(hào)處理．

E-mail: dlipeng@163．com

王布宏男，1975年12月出生于山西省太原市．現(xiàn)為空軍工程大學(xué)教授、博士生導(dǎo)師．主要從事陣列信號(hào)處理、陣列校正等方面的研究工作．

E-mail: wbhyl@ aliyun．com

沈海鷗女，1990年7月出生于甘肅省蘭州市．現(xiàn)為空軍工程大學(xué)信息與導(dǎo)航學(xué)院博士研究生．主要研究方向?yàn)殛嚵行盘?hào)處理．

E-mail: haioushen1990@ sina．com

Fast Parameter Estimation of Multi-function Radar Based on Syntactic Derivation of Parse Chart

DAI Li-peng1，WANG Bu-hong1，SHEN Hai-ou1，JIA Yue-ling2
(1．School of Information and Navigation，Air Force Engineering University，Xi’an，Shaanxi 710077，China; 2．School of Equipment Management and Security Engineering，Air Force Engineering University，Xi’an，Shaanxi 710077，China)

Abstract:Stochastic context-free grammar (SCFG) has a promising application prospect in the field of mode recognition and threat estimation of multi-function radars (MFR)．The primary limitation of the existing learning algorithms is their huge computing complexity．A fast learning algorithm for the parameters of MFR grammar is proposed，in which the Cocke-Younger-Kasami(CKY) parsing chart is first pre-computed for each training sequence to delete the rules that are not involved in the signal generation．Finally，the estimation of radar grammar parameters is realized with a modified inside-outside (IO) algorithm．The computing complexity is theoretically analyzed，moreover，simulation experiments are provided to verify the algorithm efficiency．Compared with the conventional IO and Viterbi-score (VS) algorithms，more than half operation time is reduced with our proposed algorithm while the favorable estimation accuracy is maintained．

Key words:electronic warfare; multi-function radar; stochastic context free grammar; parameter learning

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No．61172148)

收稿日期:2014-05-19;修回日期: 2014-09-30;責(zé)任編輯:覃懷銀

DOI:電子學(xué)報(bào)URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．021

中圖分類號(hào):TN918.1

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):0372-2112 (2016) 02-0392-06