一種低復雜度的OS―CFAR排序算法

1、一種低復雜度的OS-CFAR非序算法1引言在雷達恒虛警檢測方法中，有序統(tǒng)計恒虛警方法（OS-CFAR）在多目標環(huán)境下有較好的抗干擾目標的能力，其處理過程如圖1所示。在OS-CFARt理中，對背景單元值的排序直接影響了算法的復雜度，并成為影響其實時性的決定因素。本文對OS-CFAR非序背景窗的特點進行了分析，提出了改進的排序算法，仿真結果表明該改進算法可大大降低運算復雜度。2改進的OS-CFAR非序算法OS-CFAR寸每個檢測單元取背景單元，對背景單元進行排序，即使采用現有最高效的排序算法（希爾排序和快速排序等，比較量級為Nlog2（ND,N為背景單元個數），排序算法依然成為處理的瓶頸，甚至難以

2、滿足實時處理的要求。對相鄰兩個檢測單元的OS-CFARM乍進行分析發(fā)現，相鄰兩個檢測單元的背景窗存在大量的重復數據，根據這個特點可以將前一個檢測單元背景窗的排序信息予以保留，為后一個檢測單元背景窗的排序所用，基于此思想對OS-CFAR非序算法進行改進，步驟如下：（1）假設檢測單元表示為x1x2x3x4x5x6x7x8x9x10,OS-CFA瞰檢測單元兩側各4個參考單元作為其背景窗。從檢測單元x5開始處理，x5背景窗為Xx1x2x3x4x6x7x8x9，排序（采用普通的排序方法）后為Yx4x6x7x1x9x3x2x8，同時得到兩種地址映射表maplist145618327和maplist2476

3、12385。如圖2和圖3所示，地址映射表的意義為，maplist1（i）表示排序后Y的第i個單元是X的第maplist1（i）個單元，maplist2（i）則表示X的第i個單元排序后是Y的第maplist（i）個單元，如在x5的背景窗X中x6的地址序號為5，排序后x6在Y的地址序號為2，則maplist1（ 2） =5，maplist2（5）=2。（注：X的地址下標并非xi的下標，X的第i個數并非xi的第i個數，如x5的背景窗X中x6序號為5，而非6）。（2）得到x5的排序后的背景窗和地址映射表之后，然后處理下一個檢測單元x6。x6的背景窗和x5的背景窗相比，需要刪除x1和x6,補充x5和x1

4、0,因此，構造刪除列表droplist和補充列表renewlist。此例中刪除列表droplist為15，表示需要刪除x5排序前背景窗中地址序號為1和5的單元；補充列表renewlist為48，表示新補充進的x5和x10在x6背景窗的地址序號分別為4和8。同時兩個背景窗都擁有的單元x2x3x4x7x8x9的地址序號也發(fā)生變動，因此構造地址變動列表changelist，此例中為-1123-1567，表示x5背景窗中地址序號為i的數在x6背景窗的地址序號為changelist（i），如x2在x5的背景窗中的序號為2，在x6背景窗的序號為1，則changelist（2）被設為1，值為-1的表示已不再

5、考慮（-1所在的位置與刪除列表droplist中的值相對應，如此例中-1所在的位置分別是1和5）。對順序滑窗的OS-CFAR（不管是一維還是二維），其前后檢測單元背景窗重復樣本的地址變化一般都是一樣的，因此刪除列表、補充列表和地址變動列表都是固定不變的，其具體構造方法可參考此例上述說明。根據刪除列表droplist和地址映射表maplist2，將要刪除的單元從Y中刪除，同時將其對應的地址映射表maplist1中的映射值刪除，得到縮減后的排序數列remainY和對應的地址映射表remaplist，同時由地址變動列表更新地址映射表remaplist，過程如圖4所示（陰影表示要刪除的單元）。如dro

6、plist的第二個值為5，查找maplist2的第5個值，其為2，則表示要刪除Y和maplistl中的第2個單元，這樣得到刪除后的排序數列remainY，同時地址映射表maplist1根據地址變動列表changelist來更新，如maplist1的第一個值為4，則查找changelist的第4個值，用此值代替maplist1的第一個值，完成更新，這樣便得到刪除后并更新了的地址映射表remaplist。（3）將要補充進的數值數列（x5x10）進行排序，得到第一種地址映射表，并根據補充列表（48）更新其地址映射表（如圖5所示）。（4）將排序后的需補充進的數值數列newdata插入前一個單元背景窗縮

7、減后的剩余排序數列remainY（位置的尋找采用二分查找法），構成新的排序后的數列sortdata，同時生成新的地址映射表maplist1和maplist2（過程如圖6所示），至此，該單元背景窗的排序已經完成，并為下一個單元的背景排序準備好了兩個地址映射表。此例中新檢測單元x6背景窗排序后的序列為x4x7x10x9x3x5x2x8，兩個地址映射表為maplist1（35872416），maplist2（75162843），其代表意義前面已有說明，為下一個檢測單元x7背景窗的排序做了準備。（5）以此方法順序類推為后面檢測單元（x7,x8）的背景窗排序。3性能分析3.1 比較次數的理論分析希爾排序和快速排序法：比較次數的量級為Nlog2（N）（N為背景單元個數），僅與檢測單元背景窗長度有關。改進方法：比較的操作在刪除數值序號的排序、補充單元的排序和插入排序上，比較次數的量級為2*P*log2P+P*（2+log2（Q）,其