基于可編程電路的低延時中值求取方法

李宗凌 汪路元 禹霽陽 李 珂 牛躍華 張偉功

1(中國空間技術研究院北京空間飛行器總體設計部 北京 100094)2(首都師范大學信息工程學院 北京 100048)

0 引 言

中值求取是數(shù)字雷達信號處理和圖像處理過程的基本方法，它在實際應用中能夠實現(xiàn)諸如中值濾波等功能，是一種經(jīng)典的平滑噪聲的方法。國內(nèi)外學者一直致力于快速實現(xiàn)中值求取的研究，而可編程電路具有并行計算的特點，用其實現(xiàn)排序算法能極大提高運算速度，適合于雷達信號處理和圖像處理等實時性要求較高的場合。

中值求取是一種點處理方法，處理時間與實現(xiàn)手段及序列長度等因素有關。為此，出現(xiàn)了許多快速求取中值方法，常見的方法類別有：(1) 基于軟件實現(xiàn)的改進方法：采用排序思想，優(yōu)化排序算法，減少排序運算量[1-2]。此類方法主要應用于基于處理器實現(xiàn)的軟件，無法滿足圖像或雷達信號處理等高實時性應用領域的需求。(2) 中值求取算法改進方法：包含選點法[3]、近似法[4]、均值法[5]、方差法[6]等。此類方法通過近似計算思路，改進中值求取算法，在犧牲一定精度性能的基礎上，較大幅度地減少數(shù)據(jù)處理量，從而達到快速求取中值的目的，但此類方法具有一定局限性，只限于某些特定場合應用，通用性較差。(3) 并行計算方法：主要采用FPGA等可編程電路構建并行處理單元，用以加速求取中值[7-10]。此類方法主要利用FPGA等器件的特點，構建流水處理架構，可快速實現(xiàn)中值濾波等信息處理算法。流水處理的好處顯而易見，然而，卻少有人考慮流水延時對高速實時信號處理帶來的影響；與此同時，構建流水線處理過程中，復雜的邏輯控制也成為一個不可忽視的問題。

針對上述情況，本文提出了一種基于可編程電路的快速中值求取方法，充分利用FPGA等可編程電路全并行流水處理、硬件資源易擴展、并行計算能力強等特點，實現(xiàn)了通過簡單邏輯控制實現(xiàn)低延時求取中值的目標。

1 算法原理

1.1 傳統(tǒng)中值求取算法

傳統(tǒng)中值求取算法通過快速排序尋找序列的中值，該方法對序列長度、數(shù)值沒有限制，具有更加廣泛的運用范圍，因此選擇傳統(tǒng)算法作為低延時中值求取算法的對照研究。由算法原理可知，傳統(tǒng)中值求取算法的執(zhí)行效率由快速排序算法的時間復雜度決定，其基本思想是通過每次排序將序列劃分為相互獨立的兩個子集合，其中一個子集合中所有數(shù)值都比另一個子集合中所有數(shù)值小，然后分別對這兩個子集合繼續(xù)進行排序，直到濾波窗口中所有像素點有序。傳統(tǒng)中值算法最后選取位于序列中間位置的元素作為中值的輸出。

1.2 低延時中值求取算法

x(n)是長度為N的原始數(shù)據(jù)序列，其中，n=0，1，…，N-1；對x(n)序列的每個數(shù)據(jù)進行位移和偏移處理，獲得N個位移和偏移處理后的數(shù)據(jù)xb(n)，具體為：xb(n)=x(n)·2m+n，其中，n=0，1，…,N-1，m=INT{log2(2N-1)}。由上述變換方法可知，xb(n)序列中任意兩個值不相等。

將每個位移和偏移處理后的數(shù)據(jù)依次和其余N-1個數(shù)據(jù)比較大小，獲得每個數(shù)據(jù)的N-1個比較結果的布爾值，比較結果的布爾值flag(p,q)具體為：當p>q時，flag(p,q)=1；當p

將每個數(shù)據(jù)比較值為1的個數(shù)值與(N-1)/2進行比較，確定等于(N-1)/2數(shù)據(jù)比較值為1的個數(shù)值所在變換后序列的位置。獲得變換后序列的數(shù)據(jù)進行位移和偏移的逆處理，即獲得原始數(shù)據(jù)序列x(n)的中值結果。位移和偏移逆處理方法為：x(n)=(xb(n)-n)/2m，其中，m=INT{log2(2N-1)}，n=0，1，…,N-1。

1.3 算法比較

由上可知，傳統(tǒng)中值求取方法基于排序的思想，存在循環(huán)迭代結構和計算次數(shù)不確定的缺陷，耗時長，而且受限于計算架構，并行度低，硬件加速效率低，無法發(fā)揮FPGA等可編程邏輯電路的全并行優(yōu)勢，使得求取中值的流水延時過長，無法實現(xiàn)快速獲取中值。本文設計的中值求取方法克服了以上缺點，提供了一種基于并行計算思想的中值求取方法，充分利用FPGA等可編程電路全并行流水處理、硬件資源易擴展等特點，解決了數(shù)據(jù)序列低延時中值求取問題。

2 結果與分析

2.1 可編程電路實現(xiàn)

如圖1所示，將長度為N的原始數(shù)據(jù)序列的數(shù)據(jù)分別通過寄存器緩存，使數(shù)據(jù)完全同步，然后進行變換處理，使數(shù)據(jù)互為不相等。序列長度為N的原始數(shù)據(jù)序列的數(shù)據(jù)x(n)，經(jīng)過N-1級寄存器寄存處理后，N個數(shù)據(jù)處理成完全并行同步，同時對寄存在寄存器中的每個數(shù)據(jù)進行變換處理，得到新的數(shù)據(jù)xb(n)=x(n)·2m+n，其中，m=INT{log2(2N-1)}，n=0，1，…,N-1，通過上述處理，保證了寄存在寄存器中的每個數(shù)據(jù)變量完全不相等。

圖1 變換處理

如圖2所示，變換處理完成后，讓并行數(shù)據(jù)xb(n)中各個數(shù)據(jù)變量相互比較。以每個輸入數(shù)據(jù)為比較基準，得到相應的布爾比較值。需要注意，各個數(shù)據(jù)變量是同時進行相互比較，以自身為基準同時得到相應的布爾比較值flag(n,m)，其中，n=0，1，…,N-1；m=0，1，…，N-2。

圖2 序列比較

如圖3所示，將并行比較處理后所有的布爾比較值flag(n,m)進行位拼接，其中，n=0，1，…,N-1；m=0，1，…，N-2。拼接得到N-2個位寬N-1的數(shù)據(jù)sum_flag(n)={flag(0,n),flag(1,n),flag(2,n),…,flag(m,n)}，其中，n=0，1，…,N-1；m=0，1，…，N-2。利用sum_flag(n)為輸入，分別進行查表得到數(shù)值table_value(n)，其中，n=0，1，…,N-1。其中，查找表的位寬為m、深度為2N-1、查找表的值等于該地址中比特位為1的數(shù)量。

圖3 數(shù)據(jù)拼接及查找表

如圖4所示，將所有查表結果table_value(n)同時與數(shù)值(N-1)/2進行比較，若table_value(n)=(N-1)/2，則該值對應的n即為中值所在原數(shù)據(jù)序列中的位置，其中，n=0，1，…,N-1。通過中值所在位置可得到數(shù)據(jù)長度為N的數(shù)據(jù)序列的中值median_value=x1(n)[N+m-1:m]-n，其中，m=INT{log2(2N-1)}，n為中值在序列的位置，將其向外輸出。

圖4 中值求取

當數(shù)據(jù)序列較大時，如5×5窗口中值求取運算中，如果按文中設計方法，則查找表大小將設計深度為224，硬件資源顯然占有過多。通過分析運算特點，可采用分段查表的方法解決該問題，可將比較結果分為3段，每段位寬為8，此時只需要3個深度為256的查找表，再通過一個加法器將3個查找表結果相加即解決該問題，相應流水延時也只是增加1個時鐘周期。

2.2 處理效果

中值求取廣泛應用于雷達目標探測及光學圖像處理方面。如在雷達信號處理中，中值求取可應用到探測目標航跡關聯(lián)、處理結果平滑等方面；在光學圖像處理中，中值求取可應用到圖像去噪、目標檢測與識別等方面。圖5-圖6為基于本文方法實現(xiàn)的求取中值的處理效果。

圖5 雷達信號處理方向應用

2.3 性能分析

將本文設計的中值求取方法利用硬件語言Verilog實現(xiàn)，分為3×3和5×5兩種窗口規(guī)格，并將其布置在Xilinx公司可編程器件K7-325T上，得到相應的硬件資源占用情況，并與參考文獻中相關實現(xiàn)方法對比。具體如表1所示。

通過表1可知，本文方法在占用硬件資源方面相比參考文獻多一些。但是，在流水延時方面，本文方法優(yōu)勢較為明顯，在3×3窗口時，流水延時是參考文獻[8]的50%；在5×5窗口時，流水延時僅為參考文獻[9]的37.5%。通過進一步比較分析，雖然比較次數(shù)等方面沒有優(yōu)勢，但是本文方法在利用可編程電路實現(xiàn)過程相比參考文獻簡單，通過采用較多比較邏輯資源，達到簡化流程控制的目的，同時，大大縮短了流水處理延時，最終的硬件資源綜合占用率和時序也相應得到優(yōu)化。隨著微電子技術的發(fā)展，本文方法占有的硬件資源相比大規(guī)模高性能FPGA完全可以接受。因此，本文設計的低延時高性能中值求取方法相比以前的方法優(yōu)勢明顯。

3 結 語

本文利用FPGA等可編程邏輯電路全并行流水處理、易于硬件資源擴展和復用的特點，設計了一種快速求取數(shù)據(jù)序列中值的方法。該中值求取方法完全摒棄傳統(tǒng)采用排序思想求中值的思路，創(chuàng)造性的采用可編程電路的邏輯和存儲資源搭建處理架構，提升了并行計算能力。

利用FPGA等可編程電路豐富的邏輯運算和存儲單元，便于快速實現(xiàn)移位、截取、拼接和構建查找表的特點，采用邏輯單元搭建全并行比較器，快速得到序列中各數(shù)的相互比較結果布爾值；通過位拼接操作將其組合成數(shù)據(jù)結果；采用存儲單元構建比較結果查找表，通過判定查表結果得到序列中值在變換后的序列位置。上述方法避免了大量加法運算，提升了處理效率，有效減少了流水延時。

FPGA等可編程電路在上述處理過程采用全并行流水處理架構，極大增強了數(shù)據(jù)處理速率和效率，簡化了邏輯控制流程，從而能夠實現(xiàn)低延時求取數(shù)據(jù)序列的中值。在保證電路穩(wěn)定性和可靠性的前提下，流水延時可控制在兩個處理時鐘，大大優(yōu)于當前業(yè)內(nèi)相關方法。