基于FPGA的串并集合排序在雷达系统中的应用

钱孝桃，刘 超

（南京电子技术研究所 江苏 南京 210039）

在雷达抗干扰处理以及空时二维处理过程中数据排序将必不可免[1]，在传统的DSP、CPU等常规软件排序已经不能够满足雷达系统实时性要求，使用FPGA排序的趋势将势不可当。FPGA由于具有较高的并行处理能力，目前已成为雷达阵列信号处理中的主流处理器件。计算耗费的时间和消耗的硬件资源成为处理的主要矛盾，如何解决这个矛盾，本人将提出解决方案。

1 算法描述与分析

排序就是将数据元素的一个任意序列，重新排列成一个按关键字有序的序列[2]。各种传统串行排序算法如冒泡，大多都是以两两之间顺序比较为基础[3]，不能满足实时性要求。如果将传统的串行排序在FPGA中进行分段串行排序再排序，可以减少排序时间，但却大大增加设计难度。本文提出基于并行比较思路，通过将逻辑比较结果求和，用此和值确定排序结果的位置，从而达到实现排序结果的目的。

图1 算法示意图Fig.1 Algorithm diagram

假设待排序数据元素个数为N，全并行比较就是在同一时刻将N个数两两比较，再在下一时刻进行累加求和以确定排序结果。这样需要耗费N*N个比较器，如果元素个数较多，将耗费大量逻辑资源。本算法采用N个比较器，用N倍时间实现比较。算法如上图所示。

不同的比较器将有不同的比较结果输出，下表列出了4种比较器输出结果形式。

表1 4种比较器结果形式Tab.1 The format of result for four comparisons

2 工程实现

排序算法在FPGA内进行，整个实现过程如下图。使用verilog语言设计，做到模块化、参数化，以适应不同数量的排序以及各自逻辑资源的控制，主要有以下几步：

1)将流水线上的待排序的N个数据存储到RAM中，同时对相等值数量的RAM写零；

2)读取N个赋给N个变量准备比较；

3)读取数据和N个变量同时比较；

4)将比较结果累加求和；

5)将和值作为地址读取此数据的个数，将此个数和累加和相加写到排序结果RAM中，同时将个数加1写入相等值数量的RAM中。

图2 工程实现框图Fig.2 Project realizing frame

相等值数量RAM主要处理待排序数据流有过个相同数值大小的数据排序的情况。

读取N个赋给N个变量准备比较需要N个时钟周期，比较需要N个时钟周期，多级累加需要3*N个时钟周期（N≤512），相同数值排序需要3*N个时钟周期，合计需要8*N个时钟周期。

3 仿真与验证

本算法Verilog代码以及IP核模块的新建基于Xilinx vp690[4]，功能级仿真在Modsim[5]中完成。图3是待排序数据流截图，待排序数据是从20到319的300个递增数据，图4是图3输入数据的从小到大的排序结果，其中m_data_h是是排序后原先数据的序号，m_data_l是排序后从小到大的结果；为了验证相同数值的排序情况，将上述待排序数据的第2、39个数改成和第1个数相同，即20，再排序，其结果如图5所示，圆圈标出了相同数据及相同数据的排序结果。

图3 待排序数据流Fig.3 The data stream waiting for sorting

图4 排序结果Fig.4 The result of sort

图5 有相同数据的排序结果Fig.5 The result of sort with same data in data stream

4 算法在工程应用中的性能分析

通过实际建立工程，综合、仿真分析分别得出128点、256点以及512点排序，分别使用全并行算法、串行（冒泡）算法和本文串并结合的算法得到的逻辑资源使用情况以及运算时钟周期。从表中可以看出，全并行算法速度最快，但数据点数翻倍时消耗的资源消耗平方级翻倍，256点排序已经超出了芯片的范围；串行冒泡算法消耗的资源较少，但数据点数翻倍时消耗的时间却是平方级翻倍；只有本文提出的算法消耗的资源和时钟周期都能接收，具有可行性意义。

表2 不同算法消耗的资源和时间Tab.2 The resource and time of different algorithm

采用240 MHz时钟，512点排序，只需要8μs。

5 结束语

排序在雷达信号处理过程中只是其中的一个功能，这要求我们逻辑资源不能消耗太多，而雷达的实时性要求又要求我们必须快速的完成排序。从上述论述可知，单纯的串行和并行排序[6]都不能满足要求，只有本文这种基于FPGA技术的串并行结合处理排序算法才能够满足实际工程要求，达到了实时排序的效果。该算法具有通用性，可以应用到各种数据快速排序运算领域。

[1]吴顺君，梅晓春.雷达信号处理和数据处理计数[M].北京：电子工业出版社，2004.

[2]周建钦.超快速排序算法[J].计算机工程与应用，2006，42(29)：41-42.

[3]王昌厚.无符号整数按位快速排序算法[J].计算机应用与软件，2006，23(8)：120-124.

[4]喝宾.Xinlinx FPGA设计权威指南[M].北京：清华大学出版社，2012.

[5]于斌，米秀杰.ModSim电子系统分析及仿真[M].北京：电子工业出版社，2011.

[6]师延伟，金长江.基于FPGA并行全比较排序算法[J].数字技术与应用，2013(10)：126-127.