摘要：
針對壓縮感知重構算法中正交匹配追蹤(OMP)算法在每次迭代中不能選取最優原子問題，對OMP算法進行優化設計，保證了每次迭代的當前觀測信號餘量最小，並提出了一種基於FPGA 實現的優化OMP算法硬件結構設計。在矩陣分解部分採用了修正喬列斯基(Cholesky)分解方法，迴避開方運算，以減少計算延時，易於FPGA實現。整個系統採用並行計算、資源複用技術，在提高運算速度的同時減少資源利用。在Quartus II 開發環境下對該設計進行了RTL 級描述，並在FPGA仿真平臺上進行仿真驗證。仿真結果驗證了設計的正確性。
中文引用格式：蔣沅，沈培，代冀陽，等. 一種基於FPGA實現的優化正交匹配追蹤算法設計[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 引言
傳統信號獲取和處理過程主要採用奈奎斯特採樣定律實現，而奈奎斯特採樣定律要求採樣頻率不得低於模擬信號頻譜中最高頻率的兩倍，這使得高頻信號採集實現受到極大限制。隨著信息技術快速發展，信號帶寬急劇增加，工業進入大數據時代，因此對信號處理能力和硬件設備要求也越來越高，給龐大數據處理帶來了挑戰[1]。
壓縮感知理論[2]具有數據採集與壓縮同時進行處理的優點，用較少的數據就可以準確地恢復原始信號，從而使得受制於奈奎斯特採樣定理的採樣頻率能夠掙脫束縛，在較低的採樣頻率下也能夠實現。壓縮感知理論包括三方面內容：信號稀疏表示、測量矩陣的構造、信號重構算法設計。信號重構算法設計是壓縮感知理論研究關鍵的優化算法和基於貪婪迭代的匹配追蹤算法。以正交匹配追蹤算[4](Orthogonal Matching Pursuit，OMP)為代表的貪婪類及其改進算法[5-6]相對於其他方法具有信號重建速度快、運算量小等優點。
目前，壓縮感知信號重構硬件設計還處於初步階段，仍有許多問題值得探究，學者們在這方面做了一系列工作。文獻[7]對壓縮感知信號重構算法進行超大規模集成電路(Very Large Scale Integration，VLSI)設計。按照特定順序對OMP算法硬件設計執行資源複用技術，提高了資源利用率，運行速率更快[8]。文獻[9]闡述了基於FPGA的LU分解方法，能夠在計算機平臺上得到很好的加速性能，然而，在LU分解過程中存在大量矩陣乘除法運算，需要佔用FPGA大量硬件資源，導致運算延遲。本文在矩陣分解部分採用修正Cholesky分解方法，迴避了開方運算，減少了乘法運算次數，使運算速度更快。
1 正交匹配追蹤算法
在壓縮感知採樣過程中，原始信號x∈RN稀疏度為K(K< 2 優化正交匹配追蹤算法設計 2.1 優化正交匹配追蹤算法原子選擇準則 利用參考文獻[6] 結論，得出測量值y在Vn+1上的正交投影式： 在式(3)基礎上得出y在Vn+1上的正交投影係數為（其中K=1，2，…，n）： 經過第n+1次迭代後，||rn+1||2=||y||2-〈Py，y〉測量值y固定不變，要使觀測信號餘量r最小，等價於〈Py，y〉最大化，由式(1)~式(4)可得： 2.2 優化正交匹配追蹤算法計算步驟 分析了優化正交匹配追蹤算法原子選擇準則後，優化後的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 2.3 優化正交匹配追蹤算法硬件結構設計 優化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實現的優化OMP算法
硬件電路主要由四個模塊組成，分為兩大部分。具體電路圖如圖1所示。
第一部分給定兩個輸入量，分別是測量矩陣觀測矢量y，由輸入的觀測矢量y∈RN對殘差r進行初始化。每個矩陣的列向量長為N，設計N個乘法器和N-1個加法器並行處理，它們可以在一個時鐘週期內完成工作，測量矩陣?椎和殘差r同時也在一個時鐘內完成。觀測矢量y用多個寄存器組進行存儲，用多個RAM存儲測量矩陣值。利用式(1)~式(6)優化後的原子選擇準則求出原子索引?姿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 仿真驗證
通過一維信號對優化OMP算法和OMP算法進行重建實驗比較。假設稀疏信號x的長度N=256，稀疏係數k=6，OMP、優化OMP算法採用高斯隨機測量矩陣RM×N，分別記錄優化OMP算法和OMP算法的重建成功率，將其結果繪製成圖，如圖2所示。
在同樣處理器工作下，通過二維圖像信號實驗驗證優化OMP算法的有效性。實驗中選取尺度為256像素×256像素的經典實驗圖像Lena，採用高斯隨機矩陣作為測量矩陣。OMP算法與本文優化OMP算法進行重構實驗對比，重構結果如圖3所示。
當採樣率M/N=50%，採用Lena圖像測試時，優化OMP算法、OMP算法信噪比分別為34.53 dB、33.72 dB。因此，優化後的OMP算法比OMP算法重建精度要高。
通過FPGA仿真軟件Modelsim對優化OMP算法硬件電路進行了仿真，如圖4所示。
5 結論
本文通過優化原子選擇準則，使得OMP重建本文算法能夠在很短的時間內選擇最優原子，縮短了信號重構時間，提高了算法重建速率。同時，本文優化設計了FPGA硬件結構，較好地平衡了佔用資源和運算時間。本設計採用硬件描述語言Verilog HDL對優化OMP重建算法實現，運用Quartus軟件進行算法綜合，進行了RTL級描述，通過Matlab和Modelsim進行聯合仿真，得到了較好的重建效果。結果表明，優化後的OMP算法能夠以較少時間恢復原始信號。
參考文獻
[1] 任越美，張豔寧，李映.壓縮感知及其圖像處理應用研究進展與展望[J].自動化學報，2014，40(8)：1563-1575.
[2] DONOHO D.Compressed sensing[J].IEEE Trans.Info.Theory，2006，52(4)：1289-1306.
[3] 莫禹鈞，柏正堯，黃振，等.正交匹配追蹤算法的優化設計與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].系統工程與電子技術，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.
閱讀更多 電子技術應用 的文章
