学文网摘 要 有序统计恒虚警算法是雷达在多目标环境下检测目标的主要方法，数值排序是有序统计恒虚警算法的必要步骤，通常采用的排序算法有希尔排序和快速排序等，本文根据OS-CFAR前后检测单元背景窗有相同单元的特点，提出了一种低复杂度的排序算法，仿真结果表明该算法较常规排序算法在运算复杂度上有很大的改善。
【关键词】OS-CFAR 排序算法 低复杂度
1 引言
在雷达恒虚警检测方法中，有序统计恒虚警方法（OS-CFAR）在多目标环境下有较好的抗干扰目标的能力，其处理过程如***1所示。
在OS-CFAR处理中，对背景单元值的排序直接影响了算法的复杂度，并成为影响其实时性的决定因素。本文对OS-CFAR排序背景窗的特点进行了分析，提出了改进的排序算法，仿真结果表明该改进算法可大大降低运算复杂度。
2 改进的OS-CFAR排序算法
OS-CFAR对每个检测单元取背景单元，对背景单元进行排序，即使采用现有最高效的排序算法（希尔排序和快速排序等，比较量级为Nlog2（N），N为背景单元个数），排序算法依然成为处理的瓶颈，甚至难以满足实时处理的要求。对相邻两个检测单元的OS-CFAR操作进行分析发现，相邻两个检测单元的背景窗存在大量的重复数据，根据这个特点可以将前一个检测单元背景窗的排序信息予以保留，为后一个检测单元背景窗的排序所用，基于此思想对OS-CFAR排序算法进行改进，步骤如下：
（1）假设检测单元表示为[x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 …]，OS-CFAR取检测单元两侧各4个参考单元作为其背景窗。从检测单元x5开始处理，x5背景窗为X[x1 x2 x3 x4 x6 x7 x8 x9]，排序（采用普通的排序方法）后为Y[x4 x6 x7 x1 x9 x3 x2 x8]，同时得到两种地址映射表maplist1[4 5 6 1 8 3 2 7]和maplist2[4 7 6 1 2 3 8 5]。如***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和x10，因此，构造删除列表droplist和补充列表renewlist。此例中删除列表droplist为[1 5]，表示需要删除x5排序前背景窗中地址序号为1和5的单元；补充列表renewlist为[4 8]，表示新补充进的x5和x10在x6背景窗的地址序号分别为4和8。同时两个背景窗都拥有的单元[x2 x3 x4 x7 x8 x9]的地址序号也发生变动，因此构造地址变动列表changelist，此例中为[-1 1 2 3 -1 5 6 7]，表示x5背景窗中地址序号为i的数在x6背景窗的地址序号为changelist（i），如x2在x5的背景窗中的序号为2，在x6背景窗的序号为1，则changelist（2）被设为1，值为-1的表示已不再考虑（-1所在的位置与删除列表droplist中的值相对应，如此例中-1所在的位置分别是1和5）。
对顺序滑窗的OS-CFAR（不管是一维还是二维），其前后检测单元背景窗重复样本的地址变化一般都是一样的，因此删除列表、补充列表和地址变动列表都是固定不变的，其具体构造方法可参考此例上述说明。
根据删除列表droplist和地址映射表maplist2，将要删除的单元从Y中删除，同时将其对应的地址映射表maplist1中的映射值删除，得到缩减后的排序数列remainY和对应的地址映射表remaplist，同时由地址变动列表更新地址映射表remaplist，过程如***4所示（阴影表示要删除的单元）。如droplist的第二个值为5，查找maplist2的第5个值，其为2，则表示要删除Y和maplist1中的第2个单元，这样得到删除后的排序数列remainY，同时地址映射表maplist1根据地址变动列表changelist来更新，如maplist1的第一个值为4，则查找changelist的第4个值，用此值代替maplist1的第一个值，完成更新，这样便得到删除后并更新了的地址映射表remaplist。
（3）将要补充进的数值数列（[x5 x10]）进行排序，得到第一种地址映射表，并根据补充列表（[4 8]）更新其地址映射表（如***5所示）。
（4）将排序后的需补充进的数值数列newdata插入前一个单元背景窗缩减后的剩余排序数列remainY（位置的寻找采用二分查找法），构成新的排序后的数列sortdata，同时生成新的地址映射表maplist1和maplist2（过程如***6所示），至此，该单元背景窗的排序已经完成，并为下一个单元的背景排序准备好了两个地址映射表。此例中新检测单元x6背景窗排序后的序列为[x4 x7 x10 x9 x3 x5 x2 x8]，两个地址映射表为maplist1（[3 5 8 7 2 4 1 6]），maplist2（[7 5 1 6 2 8 4 3]），其代表意义前面已有说明，为下一个检测单元x7背景窗的排序做了准备。
（5）以此方法顺序类推为后面检测单元（x7，x8…）的背景窗排序。
3 性能分析
3.1 比较次数的理论分析
希尔排序和快速排序法：比较次数的量级为Nlog2（N）（N为背景单元个数），仅与检测单元背景窗长度有关。
改进方法：比较的操作在删除数值序号的排序、补充单元的排序和插入排序上，比较次数的量级为2*P*log2P+P*（2+log2（Q）），其中P为相邻检测单元背景窗不同的个数，Q为重叠个数（Q=N-P）。
3.2 仿真分析
为保证统计结果的普遍性，采用Monte-carlo方法，取均匀分布数100000个，取不同的背景窗长度N（16、32、64、100），分别取不同的P（P
结果表明：N一定的情况下，希尔排序和快速排序的比较次数基本保持不变，改进算法的排序比较次数随着P的增加而增加； P
4 结束语
本文对OS-CFAR算法的排序部分进行了改进，仿真分析表明，在相邻检测单元背景窗的样本变化个数小于样本总数一半时，该算法在排序性能上显著优于希尔排序、快速排序等常用排序方法。
参考文献
[1]Rohling H.Radar CFAR Thresholding in Clutter and Multiple Target Situations.IEEE Trans.On AES， 1983，19（4）：608-621
[2]William Ford.William Topp数据结构C++语言描述[M].北京：清华大学出版社， chapter 14，pp.612-632.
作者单位
刘超（1984-），男，现为南京电子技术研究所工程师。研究方向为雷达信号处理及数字阵列处理。
钱孝桃（1981-），男，现为南京电子技术研究所工程师。研究方向为雷达信号处理及数字阵列处理。
作者单位
南京电子技术研究所 江苏省南京市 210013
转载请注明出处学文网 » 一种低复杂度的OS―CFAR排序算法