基于FPGA的串并集合排序在雷達系統中的應用

摘要：基于FPGA硬件技術(shù)，以資源和時(shí)間相結合的思路，提出了一種串并結合的比較排序算法。該算法通過(guò)對數據的分時(shí)并行比較，計算出每個(gè)數據在排序中的位置實(shí)現數據排序。該算法可在較短的時(shí)間內實(shí)現數字序列的排序，通過(guò)實(shí)驗證明，資源消耗少，實(shí)時(shí)性號，通用性強。

關(guān)鍵詞：排序;FPGA;并行;串行

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

1 算法描述與分析

排序就是將數據元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。各種傳統串行排序算法如冒泡，大多都是以?xún)蓛芍g順序比較為基礎，不能滿(mǎn)足 實(shí)時(shí)性要求。如果將傳統的串行排序在FPGA中進(jìn)行分段串行排序再排序，可以減少排序時(shí)間，但卻大大增加設計難度。本文提出基于并行比較思路，通過(guò)將邏輯 比較結果求和，用此和值確定排序結果的位置，從而達到實(shí)現排序結果的目的。

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

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

2 工程實(shí)現

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

1)將流水線(xiàn)上的待排序的Ⅳ個(gè)數據存儲到RAM中，同時(shí)對相等值數量的RAM寫(xiě)零;

2)讀取N個(gè)賦給N個(gè)變量準備比較;

3)讀取數據和N個(gè)變量同時(shí)比較;

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

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

相等值數量RAM主要處理待排序數據流有過(guò)個(gè)相同數值大小的數據排序的情況。

讀取N個(gè)賦給N個(gè)變量準備比較需要N個(gè)時(shí)鐘周期，比較需要N個(gè)時(shí)鐘周期，多級累加需要3*N個(gè)時(shí)鐘周期(N≤512)，相同數值排序需要3*N個(gè)時(shí)鐘周期，合計需要8*N個(gè)時(shí)鐘周期。

3 仿真與驗證

本算法Verilog代碼以及IP核模塊的新建基于Xilinxvp690，功能級仿真在Modsim中完成。圖3是待排序數據流截圖，待排序數據 是從20到319的300個(gè)遞增數據，圖4是圖3輸入數據的從小到大的排序結果，其中m_data_h是是排序后原先數據的序號，m_data_l是排序 后從小到大的結果;為了驗證相同數值的排序情況，將上述待排序數據的第2、39個(gè)數改成和第1個(gè)數相同，即20，再排序，其結果如圖5所示，圓圈標出了相 同數據及相同數據的排序結果。

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

通過(guò)實(shí)際建立工程，綜合、仿真分析分別得出128點(diǎn)、256點(diǎn)以及512點(diǎn)排序，分別使用全并行算法、串行(冒泡)算法和本文串并結合的算法得到的 邏輯資源使用情況以及運算時(shí)鐘周期。從表中可以看出，全并行算法速度最快，但數據點(diǎn)數翻倍時(shí)消耗的資源消耗平方級翻倍，256點(diǎn)排序已經(jīng)超出了芯片的范 圍;串行冒泡算法消耗的資源較少，但數據點(diǎn)數翻倍時(shí)消耗的時(shí)間卻是平方級翻倍;只有本文提出的算法消耗的資源和時(shí)鐘周期都能接收，具有可行性意義。

采用240 MHz時(shí)鐘，512點(diǎn)排序，只需要8μs。

5 結束語(yǔ)

排序在雷達信號處理過(guò)程中只是其中的一個(gè)功能，這要求我們邏輯資源不能消耗太多，而雷達的實(shí)時(shí)性要求又要求我們必須快速的完成排序。從上述論述可 知，單純的串行和并行排序都不能滿(mǎn)足要求，只有本文這種基于FPGA技術(shù)的串并行結合處理排序算法才能夠滿(mǎn)足實(shí)際工程要求，達到了實(shí)時(shí)排序的效果。該算法 具有通用性，可以應用到各種數據快速排序運算領(lǐng)域。