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

摘要：基于FPGA硬件技术，以资源和时间相结合的思路，提出了一种串并结合的比较排序算法。该算法通过对数据的分时并行比较，计算出每个数据在排序中的位置实现数据排序。该算法可在较短的时间内实现数字序列的排序，通过实验证明，资源消耗少，实时性号，通用性强。

关键词：排序;FPGA;并行;串行

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

1 算法描述与分析

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

 

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

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

2 工程实现

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

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

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

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

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

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

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

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

3 仿真与验证

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

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

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

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

5 结束语

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