基于FPGA的串并集合排序在雷達系統(tǒng)中的應用

錢孝桃，劉 超

（南京電子技術研究所 江蘇 南京 210039）

在雷達抗干擾處理以及空時二維處理過程中數據排序將必不可免[1]，在傳統(tǒng)的DSP、CPU等常規(guī)軟件排序已經不能夠滿足雷達系統(tǒng)實時性要求，使用FPGA排序的趨勢將勢不可當。FPGA由于具有較高的并行處理能力，目前已成為雷達陣列信號處理中的主流處理器件。計算耗費的時間和消耗的硬件資源成為處理的主要矛盾，如何解決這個矛盾，本人將提出解決方案。

1 算法描述與分析

排序就是將數據元素的一個任意序列，重新排列成一個按關鍵字有序的序列[2]。各種傳統(tǒng)串行排序算法如冒泡，大多都是以兩兩之間順序比較為基礎[3]，不能滿足實時性要求。如果將傳統(tǒng)的串行排序在FPGA中進行分段串行排序再排序，可以減少排序時間，但卻大大增加設計難度。本文提出基于并行比較思路，通過將邏輯比較結果求和，用此和值確定排序結果的位置，從而達到實現(xiàn)排序結果的目的。

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

假設待排序數據元素個數為N，全并行比較就是在同一時刻將N個數兩兩比較，再在下一時刻進行累加求和以確定排序結果。這樣需要耗費N*N個比較器，如果元素個數較多，將耗費大量邏輯資源。本算法采用N個比較器，用N倍時間實現(xiàn)比較。算法如上圖所示。

不同的比較器將有不同的比較結果輸出，下表列出了4種比較器輸出結果形式。

表1 4種比較器結果形式Tab.1 The format of result for four comparisons

2 工程實現(xiàn)

排序算法在FPGA內進行，整個實現(xiàn)過程如下圖。使用verilog語言設計，做到模塊化、參數化，以適應不同數量的排序以及各自邏輯資源的控制，主要有以下幾步：

1)將流水線上的待排序的N個數據存儲到RAM中，同時對相等值數量的RAM寫零；

2)讀取N個賦給N個變量準備比較；

3)讀取數據和N個變量同時比較；

4)將比較結果累加求和；

5)將和值作為地址讀取此數據的個數，將此個數和累加和相加寫到排序結果RAM中，同時將個數加1寫入相等值數量的RAM中。

圖2 工程實現(xiàn)框圖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].北京：電子工業(yè)出版社，2004.

[2]周建欽.超快速排序算法[J].計算機工程與應用，2006，42(29)：41-42.

[3]王昌厚.無符號整數按位快速排序算法[J].計算機應用與軟件，2006，23(8)：120-124.

[4]喝賓.Xinlinx FPGA設計權威指南[M].北京：清華大學出版社，2012.

[5]于斌，米秀杰.ModSim電子系統(tǒng)分析及仿真[M].北京：電子工業(yè)出版社，2011.

[6]師延偉，金長江.基于FPGA并行全比較排序算法[J].數字技術與應用，2013(10)：126-127.