蘇煥程，張 君，陳昌云，程亦涵

(中國航天科工集團(tuán)8511研究所，江蘇 南京 210007)

一種基于最長路徑的脈沖序列抽取算法

蘇煥程，張 君，陳昌云，程亦涵

(中國航天科工集團(tuán)8511研究所，江蘇 南京 210007)

針對(duì)傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)算法在脈沖序列抽取方面存在的不足，提出了一種基于最長路徑原理的脈沖序列抽取算法。該算法首先將待抽取的脈沖序列轉(zhuǎn)換為一個(gè)經(jīng)過拓?fù)渑判虻挠邢驘o環(huán)圖，然后求解該有向無環(huán)圖的最長路徑，最后根據(jù)該最長路徑抽取出相應(yīng)的脈沖序列。相比較于傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)算法，基于最長路徑的算法性能受設(shè)置的容差大小的影響較小，可以有效地提高脈沖序列抽取的正確率，并且具有較高的穩(wěn)定性，從而能夠更好地滿足信號(hào)分選算法的實(shí)際工程需要。仿真實(shí)驗(yàn)表明了該算法的有效性。

信號(hào)分選；序列抽??；有向無環(huán)圖；最長路徑

0 引言

雷達(dá)截獲系統(tǒng)的作用是截獲一定頻域和空域范圍內(nèi)的雷達(dá)輻射源信號(hào)并確定其特征。如何在密集的電磁環(huán)境中正確地分離出各部雷達(dá)輻射源信息，得到正確的參數(shù)，實(shí)時(shí)地識(shí)別、告警,正確引導(dǎo)反輻射導(dǎo)彈進(jìn)行攻擊或干擾系統(tǒng)進(jìn)行干擾已變得越來越重要。而信號(hào)分選在雷達(dá)截獲系統(tǒng)設(shè)備中是重要的組成部分之一,信號(hào)分選的正確與否直接關(guān)系到設(shè)備的性能指標(biāo)。從目前的信號(hào)分選技術(shù)來看，一般將信號(hào)分選分為兩級(jí)處理,首先根據(jù)到達(dá)方向(DOA)、載頻(RF)等參數(shù)對(duì)雷達(dá)信號(hào)進(jìn)行預(yù)分選,再利用脈沖重復(fù)間隔(PRI)對(duì)信號(hào)做進(jìn)一步的分選[1]。

傳統(tǒng)的PRI分選算法的處理過程可分為PRI估計(jì)和脈沖序列抽取兩部分[2]，即先通過PRI估計(jì)得到一個(gè)可能的雷達(dá)輻射源PRI，再以該可能的PRI數(shù)值為參考對(duì)脈沖序列進(jìn)行抽取，從而實(shí)現(xiàn)對(duì)雷達(dá)輻射源脈沖的分選。目前的研究重點(diǎn)基本都集中在對(duì)PRI的快速、準(zhǔn)確估計(jì)上，這是由于準(zhǔn)確的PRI可以提高脈沖抽取的準(zhǔn)確率。然而在復(fù)雜電磁環(huán)境下，大量的脈沖互相交錯(cuò)，想要準(zhǔn)確地估計(jì)出雷達(dá)輻射源的PRI是非常困難的，并且由于TOA測(cè)量精度偏差較大，即使是估計(jì)出準(zhǔn)確的PRI也難以保證脈沖序列抽取的準(zhǔn)確率。相比較于不斷出現(xiàn)的各種PRI估計(jì)算法，對(duì)脈沖序列抽取技術(shù)的研究相對(duì)較少，基本都集中在動(dòng)態(tài)關(guān)聯(lián)算法及其改進(jìn)算法上。而動(dòng)態(tài)關(guān)聯(lián)算法雖然在簡單環(huán)境下具有較高的性能，但是在復(fù)雜電磁環(huán)境下受所選擇的PRI窗口大小影響較大，一旦發(fā)生抽取錯(cuò)誤可能導(dǎo)致后續(xù)抽取均錯(cuò)誤，性能波動(dòng)較大。

為了克服動(dòng)態(tài)關(guān)聯(lián)算法的缺陷，本文提出了一種基于最長路徑的脈沖序列抽取算法。該算法首先將待抽取的脈沖序列轉(zhuǎn)換為一個(gè)拓?fù)渑判虻挠邢驘o環(huán)圖，然后求解該有向無環(huán)圖的最長路徑，最后根據(jù)該最長路徑抽取出相應(yīng)的脈沖序列。相比較于傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)算法，該算法的性能受PRI窗口大小的影響較小，可以有效地提高脈沖序列抽取的準(zhǔn)確性，并且具有較高的穩(wěn)定性，從而能夠更好地滿足信號(hào)分選算法的實(shí)際需求。仿真實(shí)驗(yàn)表明了該算法的有效性。

1 動(dòng)態(tài)關(guān)聯(lián)法描述

動(dòng)態(tài)關(guān)聯(lián)法又稱為擴(kuò)展關(guān)聯(lián)法或PRI窗口預(yù)置法[3-4]，其基本工作原理是：先按一定規(guī)則形成準(zhǔn)PRI，然后利用準(zhǔn)PRI對(duì)脈沖序列進(jìn)行關(guān)聯(lián)匹配，完成對(duì)脈沖序列的抽取。算法步驟大致可分為：

Step1 形成準(zhǔn)PRI：采用任意一種PRI估計(jì)算法得到一個(gè)可能的雷達(dá)輻射源PRI作為準(zhǔn)PRI。

Step2 搜索基準(zhǔn)對(duì)：在脈沖流內(nèi)選擇兩個(gè)脈沖間隔等于準(zhǔn)PRI(容差范圍內(nèi))的脈沖對(duì)，以這兩個(gè)脈沖對(duì)作為基準(zhǔn)脈沖對(duì)，通常稱脈沖對(duì)的第一個(gè)脈沖為基準(zhǔn)脈沖，第二個(gè)脈沖為參考脈沖。

Step3 產(chǎn)生預(yù)置窗口：預(yù)置窗口的中心為參考脈沖的TOA加上準(zhǔn)PRI，預(yù)置窗口的寬度根據(jù)脈沖的抖動(dòng)、TOA測(cè)量誤差等因素確定。

Step4 移動(dòng)預(yù)置窗口：若沒有脈沖落入預(yù)置窗口內(nèi)，則將窗口的中心向右移動(dòng)一個(gè)準(zhǔn)PRI的時(shí)間長度；如果在規(guī)定的移動(dòng)次數(shù)內(nèi)均無脈沖落入預(yù)置窗口內(nèi)，或預(yù)置窗口超出了最后一個(gè)脈沖的TOA則結(jié)束動(dòng)態(tài)關(guān)聯(lián)算法，并輸出抽取成功的脈沖。

Step5 提取脈沖序列：對(duì)于落入預(yù)置窗口內(nèi)的脈沖，根據(jù)一定的準(zhǔn)則提取其中一個(gè)脈沖，并將該脈沖作為新的參考脈沖，同時(shí)轉(zhuǎn)到Step3。

動(dòng)態(tài)關(guān)聯(lián)法的脈沖抽取過程如圖1所示，以第一個(gè)參考脈沖開始生成預(yù)置窗口，根據(jù)選擇的窗口內(nèi)脈沖作為新的參考脈沖再不斷地生成新的預(yù)置窗口，并不斷地進(jìn)行窗口內(nèi)脈沖抽取。

在動(dòng)態(tài)關(guān)聯(lián)法的脈沖抽取過程中，預(yù)置窗口寬度的選擇非常重要，窗口選得較窄可以更準(zhǔn)確地抽取到正確的脈沖，但實(shí)際雷達(dá)脈沖總存在抖動(dòng)，TOA測(cè)量總存在誤差，窗口窄了就會(huì)漏失脈沖；窗口選得較寬就可以減少漏失，但是在信號(hào)密集環(huán)境下會(huì)同時(shí)有多個(gè)脈沖落入窗口內(nèi)，在沒有其他可靠參考因素的條件下，通常會(huì)造成錯(cuò)選。無論是脈沖的漏失或錯(cuò)選，都會(huì)導(dǎo)致下一次產(chǎn)生的預(yù)置窗口的準(zhǔn)確性下降，導(dǎo)致漏失或錯(cuò)選的概率進(jìn)一步的增加，如圖2所示。

在圖2中，由于真實(shí)的雷達(dá)脈沖丟失，動(dòng)態(tài)關(guān)聯(lián)算法錯(cuò)誤地抽取了編號(hào)為7的干擾脈沖，結(jié)果導(dǎo)致后續(xù)的脈沖抽取全部發(fā)生錯(cuò)誤。

通過上面的分析可知，動(dòng)態(tài)關(guān)聯(lián)法對(duì)所選擇的預(yù)置窗口的寬度非常敏感，算法穩(wěn)定性較差，一旦發(fā)生脈沖漏失或錯(cuò)選就會(huì)造成更嚴(yán)重的漏失或錯(cuò)選。

2 基于最長路徑的脈沖序列抽取算法

2.1 最長路徑理論

對(duì)于給定的圖G=(V，E，W)，V是節(jié)點(diǎn)集合；E是邊的集合，是二元關(guān)系V×V的子集；W是權(quán)值的集合，是E上的實(shí)值函數(shù)W：E→R。若E是無序的二元關(guān)系集合，則稱圖G是無向圖；若E是有序的二元關(guān)系集合，則稱圖G是有向圖，若圖G中不存在回路，則稱圖G是有向無環(huán)圖[5]。

在圖論中，圖的最長路徑(Longest path)問題就是在圖中尋找一條無回路的最長路徑的問題。對(duì)于無權(quán)圖，是求解一條經(jīng)過邊數(shù)最多的路徑；而對(duì)于有權(quán)圖，是求解一條權(quán)值最大的路徑。

在無向圖中求解最長路徑問題是著名的NP難題，但是在有向圖中求解最長路徑卻存在著多項(xiàng)式時(shí)間內(nèi)的算法[6]。文獻(xiàn)[7～8]分別在區(qū)間圖(Interval Graphs)、共相似圖(CoComparability Graphs)中，根據(jù)圖中節(jié)點(diǎn)的次序關(guān)系采用動(dòng)態(tài)規(guī)劃的策略在多項(xiàng)式時(shí)間內(nèi)求解最長路徑問題。

文獻(xiàn)[5]提出了一種將帶權(quán)值的有向無環(huán)圖進(jìn)行拓?fù)渑判?，然后求解最大路徑的算法。有向無環(huán)圖的拓?fù)渑判蚴侵笇⒂邢驘o環(huán)圖的所有節(jié)點(diǎn)排成一個(gè)線性序列，若圖中有邊(u，v)∈E，則在最終的排序結(jié)果中，節(jié)點(diǎn)u總排在節(jié)點(diǎn)v的前面。圖3是一個(gè)有向無環(huán)圖的實(shí)例，經(jīng)過上述的拓?fù)渑判蚝蟮玫饺鐖D4所示的一個(gè)線性序列：S、C、A、B、D、E。

如圖4所示，拓?fù)渑判虻玫搅斯?jié)點(diǎn)的一個(gè)線性排序，且源點(diǎn)S到節(jié)點(diǎn)E的最大路徑是建立在S到節(jié)點(diǎn)B和S到節(jié)點(diǎn)D的基礎(chǔ)上。這表示在求解源點(diǎn)到后面節(jié)點(diǎn)的最長路徑時(shí)，根據(jù)有向邊之間的連接關(guān)系，可以參照前面已經(jīng)求得最大路徑值的節(jié)點(diǎn)。這意味著如果按照線性序列來求解最長路徑，源點(diǎn)到節(jié)點(diǎn)間的最長路徑滿足最優(yōu)子結(jié)構(gòu)：源點(diǎn)到節(jié)點(diǎn)的最大路徑中的任意節(jié)點(diǎn)的路徑也是最大的。因此可以采用動(dòng)態(tài)規(guī)劃的方法求解最大路徑問題[5]。

如果將有向無環(huán)圖所有邊的權(quán)值均設(shè)置為相等的值，則對(duì)帶權(quán)值的向無環(huán)圖求解最大路徑等效于對(duì)無權(quán)值的有向無環(huán)圖求解最長路徑。

2.2 脈沖序列抽取分析

下面采用有向無環(huán)圖的相關(guān)理論，對(duì)基于動(dòng)態(tài)關(guān)聯(lián)法的脈沖序列抽取過程進(jìn)行分析。

由于脈沖序列是按照TOA順序排列的，所以如果上述轉(zhuǎn)換過程中嚴(yán)格按照各個(gè)節(jié)點(diǎn)對(duì)應(yīng)TOA的順序產(chǎn)生相應(yīng)的有向邊，則可以直接得到經(jīng)過拓?fù)渑判蚝蟮挠邢驘o環(huán)圖，省去了拓?fù)渑判蜻^程。圖4是一個(gè)脈沖序列的轉(zhuǎn)換實(shí)例，其中門限M=2。

如圖5所示，如果脈沖3落在脈沖1形成的預(yù)置窗口內(nèi)，則等效于在有向無環(huán)圖中節(jié)點(diǎn)1和節(jié)點(diǎn)3之間存在一條節(jié)點(diǎn)1到節(jié)點(diǎn)3的有向邊。故采用動(dòng)態(tài)關(guān)聯(lián)法的脈沖抽取過程等效于在有向無環(huán)圖中從節(jié)點(diǎn)1找一條到節(jié)點(diǎn)12的路徑，而在該條路徑上的每一個(gè)節(jié)點(diǎn)等效于抽取得到的脈沖。

綜上所述，通過采用有向無環(huán)圖模型，可將基于動(dòng)態(tài)關(guān)聯(lián)法的脈沖序列抽取過程轉(zhuǎn)換為在有向無環(huán)圖中搜索兩個(gè)節(jié)點(diǎn)之間路徑的問題。

2.3 脈沖序列抽取算法

通過對(duì)大量實(shí)際偵測(cè)到的脈沖序列深入分析可知，除干擾脈沖外，脈沖序列中其余的每一個(gè)脈沖都對(duì)應(yīng)于某一部雷達(dá)，并以某一脈沖作為參考脈沖，其對(duì)應(yīng)雷達(dá)的幀周期作為準(zhǔn)PRI在時(shí)間上向前(或向后)進(jìn)行抽取時(shí)，可以抽取到的脈沖個(gè)數(shù)多于以其它準(zhǔn)PRI抽取得到的脈沖個(gè)數(shù)[7]。

反之，如果采用動(dòng)態(tài)關(guān)聯(lián)法進(jìn)行脈沖抽取，則最優(yōu)的抽取結(jié)果應(yīng)當(dāng)可以保證最終抽取得到的脈沖數(shù)最多。根據(jù)該分析，在采用動(dòng)態(tài)關(guān)聯(lián)法進(jìn)行抽取時(shí)，落在預(yù)置窗口內(nèi)的多個(gè)脈沖中能夠保證以該脈沖為參考脈沖繼續(xù)進(jìn)行抽取，最終抽取得到的脈沖數(shù)最多的那個(gè)脈沖就是正確脈沖的概率是最大的。

魏樂村：斗渠長度由2 170 m變?yōu)? 605 m，比原設(shè)計(jì)增加435 m，1-1農(nóng)渠長度由850 m變?yōu)? 300 m，1-2農(nóng)渠長度由820 m變?yōu)?00 m，1-3農(nóng)渠長度由930 m變?yōu)? 700 m，1-4農(nóng)渠長度由980 m變?yōu)? 410 m，1-5農(nóng)渠長度由990 m變?yōu)? 200 m，變更后農(nóng)渠總長比原設(shè)計(jì)增加2 740 m。

在上節(jié)中，本文已經(jīng)通過有向無環(huán)圖對(duì)基于動(dòng)態(tài)關(guān)聯(lián)法的脈沖序列抽取過程進(jìn)行描述。故對(duì)于脈沖序列的最多脈沖數(shù)抽取問題即可轉(zhuǎn)換為在相應(yīng)的有向無環(huán)圖中求解最長路徑的問題。根據(jù)以上分析，可以給出基于最長路徑的脈沖序列抽取處理流程：

Step1 形成準(zhǔn)PRI：采用任意一種PRI估計(jì)算法得到一個(gè)可能的雷達(dá)輻射源PRI作為準(zhǔn)PRI。

Step2 序列轉(zhuǎn)換：根據(jù)2.2節(jié)提供的方法，將待抽取的脈沖序列轉(zhuǎn)換為一個(gè)拓?fù)渑判虻挠邢驘o環(huán)圖。

Step3 窗口形成：將有向無環(huán)圖首節(jié)點(diǎn)設(shè)置為起點(diǎn)，以起點(diǎn)為基準(zhǔn)形成N個(gè)預(yù)置窗口，預(yù)置窗口的寬度根據(jù)容差設(shè)置，預(yù)置窗口的中心分別為起點(diǎn)對(duì)應(yīng)脈沖的TOA加上i×準(zhǔn)PRI數(shù)值(i=1，2，3，…，N)，應(yīng)當(dāng)保證第N個(gè)窗口的中心點(diǎn)大于脈沖序列最后一個(gè)脈沖的TOA數(shù)值，如圖6所示。

Step4 終點(diǎn)設(shè)置：從第N個(gè)預(yù)置窗口開始搜索，如果預(yù)置窗口內(nèi)存在脈沖，則選擇與窗口中心點(diǎn)最近的脈沖并設(shè)置為終點(diǎn)，轉(zhuǎn)到Step5；否則搜索第N-1個(gè)預(yù)置窗口，依次類推。

Step5 路徑搜索：采用文獻(xiàn)[5]的算法，從有向無環(huán)圖起點(diǎn)開始，搜索到終點(diǎn)之間的最長路徑，如果搜索成功則輸出對(duì)應(yīng)的脈沖，否則刪除有向無環(huán)圖的首節(jié)點(diǎn)，將第2個(gè)節(jié)點(diǎn)設(shè)置為首節(jié)點(diǎn)并轉(zhuǎn)到Step3。

如圖6所示，根據(jù)首節(jié)點(diǎn)形成了多個(gè)預(yù)置窗口，并根據(jù)形成的預(yù)置窗口確定相應(yīng)的終點(diǎn)。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證基于最長路徑的脈沖序列抽取算法的有效性和算法的穩(wěn)定性，本文進(jìn)行了以下實(shí)驗(yàn)。

實(shí)驗(yàn)1：仿真信號(hào)源為5部PRI固定的雷達(dá)輻射源，PRI在50μs～50ms之間隨機(jī)，TOA測(cè)量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)法以及最長路徑法進(jìn)行脈沖序列抽取，共測(cè)試了100組數(shù)據(jù)。抽取時(shí)的容差設(shè)置為500ns，即PRI預(yù)置窗口寬度為1μs，仿真結(jié)果見表1。

表1 抽取算法性能比較(簡單環(huán)境)

從表1仿真結(jié)果可以得出，在信號(hào)環(huán)境較為簡單且測(cè)量精度較高的條件下，兩種算法的抽取正確率和性能穩(wěn)定性均較高，算法性能差異較小。

實(shí)驗(yàn)2：設(shè)置仿真信號(hào)源為20部PRI固定的雷達(dá)輻射源，PRI在50μs～50ms之間隨機(jī)，TOA測(cè)量誤差小于1μs，脈沖丟失率小于30%。分別采用傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)法以及最長路徑法進(jìn)行脈沖抽取，共測(cè)試了100組數(shù)據(jù)。抽取時(shí)的容差設(shè)置為500ns，即PRI預(yù)置窗口寬度為1μs，仿真結(jié)果見表2。

表2 抽取算法性能比較(復(fù)雜環(huán)境)

從表2仿真結(jié)果可以得出，在信號(hào)環(huán)境較為復(fù)雜且測(cè)量精度較差的條件下，動(dòng)態(tài)關(guān)聯(lián)法的抽取正確率明顯低于最長路徑法。

實(shí)驗(yàn)3：設(shè)置仿真信號(hào)源為5部PRI固定的雷達(dá)輻射源，PRI在50μs～50ms之間隨機(jī)，TOA測(cè)量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)法以及最長路徑法進(jìn)行脈沖抽取，共測(cè)試了100組數(shù)據(jù)。抽取時(shí)的容差設(shè)置為5μs，對(duì)應(yīng)預(yù)置窗口寬度為10μs，仿真結(jié)果見表3。

表3 抽取算法性能比較(5μs容差)

從表3仿真結(jié)果可以得出，在與實(shí)驗(yàn)1同樣的仿真環(huán)境，增大了抽取容差后，動(dòng)態(tài)關(guān)聯(lián)法的穩(wěn)定性發(fā)生了較大的下降，而最長路徑法基本沒有變化。

實(shí)驗(yàn)4：設(shè)置仿真信號(hào)源為5部PRI固定的雷達(dá)輻射源，PRI在50μs～50ms之間隨機(jī)，TOA測(cè)量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動(dòng)態(tài)關(guān)聯(lián)法以及最長路徑法進(jìn)行脈沖抽取，共測(cè)試了100組數(shù)據(jù)。抽取時(shí)的容差設(shè)置為50ns，對(duì)應(yīng)預(yù)置窗口寬度為100ns，仿真結(jié)果見表4。

表4 抽取算法性能比較(50ns容差)

從表4仿真結(jié)果可以得出，在與實(shí)驗(yàn)1同樣的仿真環(huán)境下，通過減小抽取容差，動(dòng)態(tài)關(guān)聯(lián)法的抽取正確率和算法性能穩(wěn)定性均發(fā)生了明顯的下降，而最長路徑法的抽取正確率均雖然也發(fā)生了下降，但是算法性能仍然保持較為穩(wěn)定。

通過對(duì)實(shí)驗(yàn)1～4的仿真結(jié)果進(jìn)行分析，可得出結(jié)論：在復(fù)雜環(huán)境或測(cè)量精度較低的情況下，動(dòng)態(tài)關(guān)聯(lián)算法的抽取正確率明顯低于最長路徑法。當(dāng)對(duì)抽取的容差進(jìn)行調(diào)整后，動(dòng)態(tài)關(guān)聯(lián)算法的抽取正確率發(fā)生較大波動(dòng)，而最長路徑法的算法性能較為穩(wěn)定。這是由于動(dòng)態(tài)關(guān)聯(lián)算法對(duì)抽取錯(cuò)誤的敏感度較強(qiáng)，一旦發(fā)生脈沖抽取就會(huì)影響到下一次的抽取，甚至導(dǎo)致后續(xù)的抽取全部錯(cuò)誤，而最長路徑法則具有較強(qiáng)的自我“糾錯(cuò)”能力，一旦抽取到錯(cuò)誤的脈沖，導(dǎo)致后續(xù)可抽取脈沖數(shù)減少，算法就會(huì)回到抽取錯(cuò)誤的位置重新進(jìn)行脈沖抽取，保證算法最終抽取到的脈沖數(shù)最多。

4 結(jié)束語

本文提出了一種基于最長路徑的脈沖序列抽取算法，該算法能夠克服傳統(tǒng)關(guān)聯(lián)比較法的不足，受算法容差影響較小，可以有效地提高脈沖序列抽取的正確率，且具有較高的穩(wěn)定性，能夠更好地滿足信號(hào)分選算法的實(shí)際需求。但是，該算法也具有自身的局限性，即該算法所要求的計(jì)算量相對(duì)較大，算法的實(shí)時(shí)性還有待進(jìn)一步優(yōu)化和提升。■

[1] 楊文華, 高梅國. 基于PRI的雷達(dá)脈沖序列分選方法[J].現(xiàn)代雷達(dá), 2005, 27(3):50-59.

[2] 關(guān)一夫,張國毅,劉志鵬. 一種基于脈沖樣本序列的PRI 周期信號(hào)分選算法[J]. 電訊技術(shù),2014,54(7):915-920.

[3] 朱紅亮. 脈沖重頻分選算法的研究[D]. 西安：西安電子科技大學(xué), 2010.

[4] 何煒. 雷達(dá)信號(hào)分選關(guān)鍵算法研究[D]. 成都：電子科技大學(xué),2007.

[5] 尤磊, 符利勇, 宋新宇. 最大路徑算法在原條量材優(yōu)化中的應(yīng)用及其優(yōu)化[J]. 信陽師范學(xué)院學(xué)報(bào),2014,27(4):605-624.

[6] Sedgewick R,Wayne K. Algorithms [M]. 4th ed. Pearson Education, 2011.

[7] Ioannidou K,Mertzios GB,Nikolopoulos SD. The longest path problem has a polynomial solution on interval graphs[J]. Algorithmica，2011, 61(2):320-341．

[8] Mertzios GB,Corneil DG. A simple polynomial algorithm for the longest path problem on cocomparability graphs[J]. SIAM Journal on Discrete Mathematics，2012, 26(3):940-963．

[9] 李英達(dá),肖立志.一種脈沖重復(fù)間隔復(fù)雜調(diào)制雷達(dá)信號(hào)分選方法[J]. 電子與信息學(xué)報(bào), 2013, 35(10):2493-2497.

An algorithm of extracting pulse sequence based on longest path

Su Huancheng, Zhang Jun, Chen Changyun, Cheng Yihan

(No.8511 Research Institute of CASIC, Nanjing 210007, Jiangsu, China)

For the defects in pulses sequence drawing out of traditional dynamic association algorithm, a new algorithm of pulses sequence drawing out based on longest path is put forward. The algorithm firstly transforms the pulses sequence to directed acyclic graph which topological sorted, then searches the longest path, extracting the pulse sequence based on the longest path at last. Compared with the traditional dynamic association algorithm, the performance of this algorithm is not fluctuate on toler vary, and increase the pulse extracting accurate rate, which satisfies the requirement of the signal sorting process. Simulation results verify the validity of the proposed algorithm.

signal sorting; pulse extracting; directed acyclic graph; longest path

2017-01-11；2017-03-06修回。

蘇煥程(1983-)，男，高工，主要研究方向?yàn)殡娮訉?duì)抗信息處理。

TJ76;TN972

A