<meter id="pryje"><nav id="pryje"><delect id="pryje"></delect></nav></meter>
          <label id="pryje"></label>

          新聞中心

          EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計應(yīng)用 > 基于FPGA的串并集合排序在雷達系統(tǒng)中的應(yīng)用

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

          作者: 時間:2016-10-15 來源:網(wǎng)絡(luò) 收藏

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

          本文引用地址:http://www.ex-cimer.com/article/201610/307230.htm

          關(guān)鍵詞:排序;;;

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

          1 算法描述與分析

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

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

          不同的比較器將有不同的比較結(jié)果輸出,下表列出了4種比較器輸出結(jié)果形式。

          2 工程實現(xiàn)

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

          1)將流水線上的待排序的Ⅳ個數(shù)據(jù)存儲到RAM中,同時對相等值數(shù)量的RAM寫零;

          2)讀取N個賦給N個變量準(zhǔn)備比較;

          3)讀取數(shù)據(jù)和N個變量同時比較;

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

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

          相等值數(shù)量RAM主要處理待排序數(shù)據(jù)流有過個相同數(shù)值大小的數(shù)據(jù)排序的情況。

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

          3 仿真與驗證

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

          4 算法在工程應(yīng)用中的性能分析

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

          采用240 MHz時鐘,512點排序,只需要8μs。

          5 結(jié)束語

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



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

          評論


          相關(guān)推薦

          技術(shù)專區(qū)

          關(guān)閉
          看屁屁www成人影院,亚洲人妻成人图片,亚洲精品成人午夜在线,日韩在线 欧美成人 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();