文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2015.10.020
中文引用格式: 蔣沅,沈培,代冀陽,等. 一種基于FPGA實現的優(yōu)化正交匹配追蹤算法設計[J].電子技術應用,2015,41(10):73-76,80.
英文引用格式: Jiang Yuan,Shen Pei,Dai Jiyang,et al. An orthogonal matching pursuit algorithm optimization design based on FPGA implementation[J].Application of Electronic Technique,2015,41(10):73-76,80.
0 引言
傳統(tǒng)信號獲取和處理過程主要采用奈奎斯特采樣定律實現,而奈奎斯特采樣定律要求采樣頻率不得低于模擬信號頻譜中最高頻率的兩倍,這使得高頻信號采集實現受到極大限制。隨著信息技術快速發(fā)展,信號帶寬急劇增加,工業(yè)進入大數據時代,因此對信號處理能力和硬件設備要求也越來越高,給龐大數據處理帶來了挑戰(zhàn)[1]。
壓縮感知理論[2]具有數據采集與壓縮同時進行處理的優(yōu)點,用較少的數據就可以準確地恢復原始信號,從而使得受制于奈奎斯特采樣定理的采樣頻率能夠掙脫束縛,在較低的采樣頻率下也能夠實現。壓縮感知理論包括三方面內容:信號稀疏表示、測量矩陣的構造、信號重構算法設計。信號重構算法設計是壓縮感知理論研究關鍵的優(yōu)化算法和基于貪婪迭代的匹配追蹤算法。以正交匹配追蹤算[4](Orthogonal Matching Pursuit,OMP)為代表的貪婪類及其改進算法[5-6]相對于其他方法具有信號重建速度快、運算量小等優(yōu)點。
目前,壓縮感知信號重構硬件設計還處于初步階段,仍有許多問題值得探究,學者們在這方面做了一系列工作。文獻[7]對壓縮感知信號重構算法進行超大規(guī)模集成電路(Very Large Scale Integration,VLSI)設計。按照特定順序對OMP算法硬件設計執(zhí)行資源復用技術,提高了資源利用率,運行速率更快[8]。文獻[9]闡述了基于FPGA的LU分解方法,能夠在計算機平臺上得到很好的加速性能,然而,在LU分解過程中存在大量矩陣乘除法運算,需要占用FPGA大量硬件資源,導致運算延遲。本文在矩陣分解部分采用修正Cholesky分解方法,回避了開方運算,減少了乘法運算次數,使運算速度更快。
1 正交匹配追蹤算法
在壓縮感知采樣過程中,原始信號x∈RN稀疏度為K(K<<N),設計一個M×N(M<<N)的隨機測量矩陣,將隨機測量矩陣中的列向量fl(l=1,2,…,n)稱為原子。根據壓縮感知理論,將稀疏信號在隨機測量矩陣中進行投影,得到一個比原始信號長度小很多的M×l觀測向量y∈RN。匹配追蹤算法的核心思想是在第N次迭代中從隨機測量矩陣?椎中選擇與當前觀測信號余量r(初始化為觀測信號y)最匹配的原子。將選出的原子增加至候選子集?祝中形成新的候選子集。根據候選子集,計算新的估計信號和新的觀測信號余量r,在下一次迭代中,繼續(xù)選擇與觀測信號余量最匹配的原子形成新的候選子集,用以計算r直至迭代結束。
2 優(yōu)化正交匹配追蹤算法設計
2.1 優(yōu)化正交匹配追蹤算法原子選擇準則
利用參考文獻[6] 結論,得出測量值y在Vn+1上的正交投影式:
在式(3)基礎上得出y在Vn+1上的正交投影系數為(其中K=1,2,…,n):
經過第n+1次迭代后,||rn+1||2=||y||2-〈Py,y〉測量值y固定不變,要使觀測信號余量r最小,等價于〈P
y,y〉最大化,由式(1)~式(4)可得:
2.2 優(yōu)化正交匹配追蹤算法計算步驟
分析了優(yōu)化正交匹配追蹤算法原子選擇準則后,優(yōu)化后的OMP算法的重構算法計算步驟如下:
步驟1:初始化=0,r0=0,n=1。
步驟2:選擇當前觀測信號余量rn-1最匹配的原子索引n=argmaxl=1,2,…,N Cl。
步驟3;更新候選子集?祝n=?祝n-1∪?姿n,記錄傳感矩陣中的重構原子集合n=[
n-1,f
]。
步驟4:利用索引集中現有的原子逼近原始信號:n=argminy-
n。
步驟5:更新殘差:。
步驟6:n=n+1,如果n<k,則返回到步驟2,直到得到最后的近似信號,否則停止迭代。
2.3 優(yōu)化正交匹配追蹤算法硬件結構設計
優(yōu)化OMP算法可以分為4個模塊,第1個模塊對應重構算法計算步驟2,經過原子選擇,利用式(1)~式(5)求出殘差最匹配原子。
第2個模塊對應重構算法計算步驟3,通過更新候選子集?祝,生成增廣矩陣n。
第3個模塊對應重構算法計算步驟4,求解l0范數最小模型問題,解決最小二乘法問題,得到原始信號的估計值。求解增廣矩陣逆的方法來得出原始估計值
。然而,矩陣
是非方形矩陣,對于求非方形矩陣一般是使用偽逆(Moore-Penrose)的方法求解,矩陣
偽逆可以表示為:
式(7)中,令G=T×
,以上問題就直接轉換成求解G逆。G∈Rt×t是一個對稱正定矩,如直接進行求解,在FPGA上不易實現,可以先對矩陣G進行矩陣分解,再求逆。
矩陣分解有QR分解[10]、奇異值分解、LU分解、Cholesky分解[11]。QR分解和奇異值分解計算過程復雜,不易于FPGA的實現,LU分解在分解過程中會有大量的矩陣乘法和除法的計算操作,它一方面占用FPGA硬件資源,另一方面影響計算效率。雖然,在Cholesky分解計算中會產生開方操作的延時以及除法計算,但是復雜度相對于LU分解較少。針對Cholesky分解在計算中產生開方操作的延時問題,利用Cholesky分解,回避了開方運算帶來的延時問題。具體修正Cholesky分解計算公式如下:
第4個模塊對應重構算法計算步驟5,計算殘差r,為下次迭代做準備。3 基于FPGA實現的優(yōu)化OMP算法
硬件電路主要由四個模塊組成,分為兩大部分。具體電路圖如圖1所示。
第一部分給定兩個輸入量,分別是測量矩陣觀測矢量y,由輸入的觀測矢量y∈RN對殘差r進行初始化。每個矩陣的列向量長為N,設計N個乘法器和N-1個加法器并行處理,它們可以在一個時鐘周期內完成工作,測量矩陣?椎和殘差r同時也在一個時鐘內完成。觀測矢量y用多個寄存器組進行存儲,用多個RAM存儲測量矩陣值。利用式(1)~式(6)優(yōu)化后的原子選擇準則求出原子索引?姿n,通過步驟3更新候選子集得到重構矩陣,得出矩陣G。
第二部分對矩陣G求逆過程,硬件電路由Cholesky分解硬件電路、矩陣L求逆硬件電路和相乘運算硬件電路組成。利用修正的Cholesky分解矩陣G,分解矩陣G分別要求出下三角矩陣L和對角矩陣D。然后進行相乘,使得G=L×D×LT,從而回避平方操作。其中矩陣L和矩陣D之間是相互依存的,其元素必須按照特定的順序進行計算。最后對G-1求解,G-1=(L-1)T×D-1×L-1,可以先令O=(L-1)T×D-1,對O進行計算,然后可方便計算G-1=O×L-1。
4 仿真驗證
通過一維信號對優(yōu)化OMP算法和OMP算法進行重建實驗比較。假設稀疏信號x的長度N=256,稀疏系數k=6,OMP、優(yōu)化OMP算法采用高斯隨機測量矩陣RM×N,分別記錄優(yōu)化OMP算法和OMP算法的重建成功率,將其結果繪制成圖,如圖2所示。
在同樣處理器工作下,通過二維圖像信號實驗驗證優(yōu)化OMP算法的有效性。實驗中選取尺度為256像素×256像素的經典實驗圖像Lena,采用高斯隨機矩陣作為測量矩陣。OMP算法與本文優(yōu)化OMP算法進行重構實驗對比,重構結果如圖3所示。
當采樣率M/N=50%,采用Lena圖像測試時,優(yōu)化OMP算法、OMP算法信噪比分別為34.53 dB、33.72 dB。因此,優(yōu)化后的OMP算法比OMP算法重建精度要高。
通過FPGA仿真軟件Modelsim對優(yōu)化OMP算法硬件電路進行了仿真,如圖4所示。
5 結論
本文通過優(yōu)化原子選擇準則,使得OMP重建本文算法能夠在很短的時間內選擇最優(yōu)原子,縮短了信號重構時間,提高了算法重建速率。同時,本文優(yōu)化設計了FPGA硬件結構,較好地平衡了占用資源和運算時間。本設計采用硬件描述語言Verilog HDL對優(yōu)化OMP重建算法實現,運用Quartus軟件進行算法綜合,進行了RTL級描述,通過Matlab和Modelsim進行聯合仿真,得到了較好的重建效果。結果表明,優(yōu)化后的OMP算法能夠以較少時間恢復原始信號。
參考文獻
[1] 任越美,張艷寧,李映.壓縮感知及其圖像處理應用研究進展與展望[J].自動化學報,2014,40(8):1563-1575.
[2] DONOHO D.Compressed sensing[J].IEEE Trans.Info.Theory,2006,52(4):1289-1306.
[3] 莫禹鈞,柏正堯,黃振,等.正交匹配追蹤算法的優(yōu)化設計與FPGA實現[J].電子技術應用,2014,50(10):79-82.
[4] WANG J,KWON S,SHIM B.Generalized orthogonal matching pursuit[J].IEEE Trans.on Signal Processing,2012,60(12):6202-6216.
[5] WU R,HUANG W,CHEN D R.The exact support recoveryof sparse signals with noise via orthogonal matching pursuit[J].IEEE Trans.on signal processing letters,2013,20(4):403-406.
[6] 李少東,裴文炯,楊軍,等.貝葉斯模型下的OMP重構算法及應用[J].系統(tǒng)工程與電子技術,2015,37(2):246-252.
[7] SEPTINUS A,STEINBERG R.Compressive sampling hardware reconstruction[C].Circuits and systems(ISCAS),Proc.of2010 IEEE Internatioal symposium on.IEEE,2010:316-3319.
[8] BLACHE P,RABAH H,AMIRA A.High level prototyping and FPGA implementation of the orthogonal matching pursuitalgorithm[C].Information Scien,Signal Processing and their Applications(ISSPA),2012:1336-1340.
[9] WU G,DOU Y,PETERSON G D.Blocking LU decomposi-tion for FPGAs[C].IEEE.Proceeding of FCCM′10.ChArlotte:IEEE,2010:109-112.
[10] STANISLAUS J.L.V.M,MOHSENIN T.High performance compressive sensing reconstruction hardware with QRD process[C].Circuits and Systems(ISCAS),2012,IEEE.International Symposium on.IEEE,2012:29-32.
[11] 魏嬋,娟張春,水劉健.一種基于Cholesky分解的快速矩陣求逆方法設計[J].電子設計工程,2014,22(1):159-164.