一種低復(fù)雜度的OS―CFAR排序算法

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

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

3、12385。如圖2和圖3所示，地址映射表的意義為，maplist1（i）表示排序后Y的第i個(gè)單元是X的第maplist1（i）個(gè)單元，maplist2（i）則表示X的第i個(gè)單元排序后是Y的第maplist（i）個(gè)單元，如在x5的背景窗X中x6的地址序號(hào)為5，排序后x6在Y的地址序號(hào)為2，則maplist1（ 2） =5，maplist2（5）=2。（注：X的地址下標(biāo)并非xi的下標(biāo)，X的第i個(gè)數(shù)并非xi的第i個(gè)數(shù)，如x5的背景窗X中x6序號(hào)為5，而非6）。（2）得到x5的排序后的背景窗和地址映射表之后，然后處理下一個(gè)檢測(cè)單元x6。x6的背景窗和x5的背景窗相比，需要?jiǎng)h除x1和x6,補(bǔ)充x5和x1

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

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

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

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