0 引言

　　傳統(tǒng)信號(hào)獲取和處理過程主要采用奈奎斯特采樣定律實(shí)現(xiàn)，而奈奎斯特采樣定律要求采樣頻率不得低于模擬信號(hào)頻譜中最高頻率的兩倍，這使得高頻信號(hào)采集實(shí)現(xiàn)受到極大限制。隨著信息技術(shù)快速發(fā)展，信號(hào)帶寬急劇增加，工業(yè)進(jìn)入大數(shù)據(jù)時(shí)代，因此對(duì)信號(hào)處理能力和硬件設(shè)備要求也越來越高，給龐大數(shù)據(jù)處理帶來了挑戰(zhàn)[1]。

　　壓縮感知理論[2]具有數(shù)據(jù)采集與壓縮同時(shí)進(jìn)行處理的優(yōu)點(diǎn)，用較少的數(shù)據(jù)就可以準(zhǔn)確地恢復(fù)原始信號(hào)，從而使得受制于奈奎斯特采樣定理的采樣頻率能夠掙脫束縛，在較低的采樣頻率下也能夠?qū)崿F(xiàn)。壓縮感知理論包括三方面內(nèi)容：信號(hào)稀疏表示、測(cè)量矩陣的構(gòu)造、信號(hào)重構(gòu)算法設(shè)計(jì)。信號(hào)重構(gòu)算法設(shè)計(jì)是壓縮感知理論研究關(guān)鍵的優(yōu)化算法和基于貪婪迭代的匹配追蹤算法。以正交匹配追蹤算[4](Orthogonal Matching Pursuit，OMP)為代表的貪婪類及其改進(jìn)算法[5-6]相對(duì)于其他方法具有信號(hào)重建速度快、運(yùn)算量小等優(yōu)點(diǎn)。

　　目前，壓縮感知信號(hào)重構(gòu)硬件設(shè)計(jì)還處于初步階段，仍有許多問題值得探究，學(xué)者們?cè)谶@方面做了一系列工作。文獻(xiàn)[7]對(duì)壓縮感知信號(hào)重構(gòu)算法進(jìn)行超大規(guī)模集成電路(Very Large Scale Integration，VLSI)設(shè)計(jì)。按照特定順序?qū)MP算法硬件設(shè)計(jì)執(zhí)行資源復(fù)用技術(shù)，提高了資源利用率，運(yùn)行速率更快[8]。文獻(xiàn)[9]闡述了基于FPGA的LU分解方法，能夠在計(jì)算機(jī)平臺(tái)上得到很好的加速性能，然而，在LU分解過程中存在大量矩陣乘除法運(yùn)算，需要占用FPGA大量硬件資源，導(dǎo)致運(yùn)算延遲。本文在矩陣分解部分采用修正Cholesky分解方法，回避了開方運(yùn)算，減少了乘法運(yùn)算次數(shù)，使運(yùn)算速度更快。

1 正交匹配追蹤算法

　　在壓縮感知采樣過程中，原始信號(hào)x∈RN稀疏度為K(K<<N)，設(shè)計(jì)一個(gè)M×N(M<<N)的隨機(jī)測(cè)量矩陣，將隨機(jī)測(cè)量矩陣中的列向量fl(l=1，2，…，n)稱為原子。根據(jù)壓縮感知理論，將稀疏信號(hào)在隨機(jī)測(cè)量矩陣中進(jìn)行投影，得到一個(gè)比原始信號(hào)長度小很多的M×l觀測(cè)向量y∈RN。匹配追蹤算法的核心思想是在第N次迭代中從隨機(jī)測(cè)量矩陣?椎中選擇與當(dāng)前觀測(cè)信號(hào)余量r(初始化為觀測(cè)信號(hào)y)最匹配的原子。將選出的原子增加至候選子集?祝中形成新的候選子集。根據(jù)候選子集，計(jì)算新的估計(jì)信號(hào)和新的觀測(cè)信號(hào)余量r，在下一次迭代中，繼續(xù)選擇與觀測(cè)信號(hào)余量最匹配的原子形成新的候選子集，用以計(jì)算r直至迭代結(jié)束。

2 優(yōu)化正交匹配追蹤算法設(shè)計(jì)

　　2.1 優(yōu)化正交匹配追蹤算法原子選擇準(zhǔn)則

　　利用參考文獻(xiàn)[6] 結(jié)論，得出測(cè)量值y在Vn+1上的正交投影式：

　　在式(3)基礎(chǔ)上得出y在Vn+1上的正交投影系數(shù)為（其中K=1，2，…，n）：

　　經(jīng)過第n+1次迭代后，||rn+1||2=||y||2-〈Py，y〉測(cè)量值y固定不變，要使觀測(cè)信號(hào)余量r最小，等價(jià)于〈Py，y〉最大化，由式(1)~式(4)可得：

　　2.2 優(yōu)化正交匹配追蹤算法計(jì)算步驟

　　分析了優(yōu)化正交匹配追蹤算法原子選擇準(zhǔn)則后，優(yōu)化后的OMP算法的重構(gòu)算法計(jì)算步驟如下：

　　步驟1：初始化=0，r0=0，n=1。

　　步驟2：選擇當(dāng)前觀測(cè)信號(hào)余量rn-1最匹配的原子索引n=argmaxl=1，2，…，N Cl。

　　步驟3；更新候選子集?祝n=?祝n-1∪?姿n，記錄傳感矩陣中的重構(gòu)原子集合n=[n-1，f]。

　　步驟4：利用索引集中現(xiàn)有的原子逼近原始信號(hào)：n=argminy-n。

　　步驟5：更新殘差：。

　　步驟6：n=n+1，如果n<k，則返回到步驟2，直到得到最后的近似信號(hào)，否則停止迭代。

　　2.3 優(yōu)化正交匹配追蹤算法硬件結(jié)構(gòu)設(shè)計(jì)

　　優(yōu)化OMP算法可以分為4個(gè)模塊，第1個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟2，經(jīng)過原子選擇，利用式(1)~式(5)求出殘差最匹配原子。

　　第2個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟3，通過更新候選子集?祝，生成增廣矩陣n。

　　第3個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟4，求解l0范數(shù)最小模型問題，解決最小二乘法問題，得到原始信號(hào)的估計(jì)值。求解增廣矩陣逆的方法來得出原始估計(jì)值。然而，矩陣是非方形矩陣，對(duì)于求非方形矩陣一般是使用偽逆(Moore-Penrose)的方法求解，矩陣偽逆可以表示為：

　　式(7)中，令G=T×，以上問題就直接轉(zhuǎn)換成求解G逆。G∈Rt×t是一個(gè)對(duì)稱正定矩，如直接進(jìn)行求解，在FPGA上不易實(shí)現(xiàn)，可以先對(duì)矩陣G進(jìn)行矩陣分解，再求逆。

　　矩陣分解有QR分解[10]、奇異值分解、LU分解、Cholesky分解[11]。QR分解和奇異值分解計(jì)算過程復(fù)雜，不易于FPGA的實(shí)現(xiàn)，LU分解在分解過程中會(huì)有大量的矩陣乘法和除法的計(jì)算操作，它一方面占用FPGA硬件資源，另一方面影響計(jì)算效率。雖然，在Cholesky分解計(jì)算中會(huì)產(chǎn)生開方操作的延時(shí)以及除法計(jì)算，但是復(fù)雜度相對(duì)于LU分解較少。針對(duì)Cholesky分解在計(jì)算中產(chǎn)生開方操作的延時(shí)問題，利用Cholesky分解，回避了開方運(yùn)算帶來的延時(shí)問題。具體修正Cholesky分解計(jì)算公式如下：

　　第4個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟5，計(jì)算殘差r，為下次迭代做準(zhǔn)備。3 基于FPGA實(shí)現(xiàn)的優(yōu)化OMP算法

　　硬件電路主要由四個(gè)模塊組成，分為兩大部分。具體電路圖如圖1所示。

　　第一部分給定兩個(gè)輸入量，分別是測(cè)量矩陣觀測(cè)矢量y，由輸入的觀測(cè)矢量y∈RN對(duì)殘差r進(jìn)行初始化。每個(gè)矩陣的列向量長為N，設(shè)計(jì)N個(gè)乘法器和N-1個(gè)加法器并行處理，它們可以在一個(gè)時(shí)鐘周期內(nèi)完成工作，測(cè)量矩陣?椎和殘差r同時(shí)也在一個(gè)時(shí)鐘內(nèi)完成。觀測(cè)矢量y用多個(gè)寄存器組進(jìn)行存儲(chǔ)，用多個(gè)RAM存儲(chǔ)測(cè)量矩陣值。利用式(1)~式(6)優(yōu)化后的原子選擇準(zhǔn)則求出原子索引?姿n，通過步驟3更新候選子集得到重構(gòu)矩陣，得出矩陣G。

　　第二部分對(duì)矩陣G求逆過程，硬件電路由Cholesky分解硬件電路、矩陣L求逆硬件電路和相乘運(yùn)算硬件電路組成。利用修正的Cholesky分解矩陣G，分解矩陣G分別要求出下三角矩陣L和對(duì)角矩陣D。然后進(jìn)行相乘，使得G=L×D×LT，從而回避平方操作。其中矩陣L和矩陣D之間是相互依存的，其元素必須按照特定的順序進(jìn)行計(jì)算。最后對(duì)G-1求解，G-1=(L-1)T×D-1×L-1，可以先令O=(L-1)T×D-1，對(duì)O進(jìn)行計(jì)算，然后可方便計(jì)算G-1=O×L-1。

4 仿真驗(yàn)證

　　通過一維信號(hào)對(duì)優(yōu)化OMP算法和OMP算法進(jìn)行重建實(shí)驗(yàn)比較。假設(shè)稀疏信號(hào)x的長度N=256，稀疏系數(shù)k=6，OMP、優(yōu)化OMP算法采用高斯隨機(jī)測(cè)量矩陣RM×N，分別記錄優(yōu)化OMP算法和OMP算法的重建成功率，將其結(jié)果繪制成圖，如圖2所示。

　　在同樣處理器工作下，通過二維圖像信號(hào)實(shí)驗(yàn)驗(yàn)證優(yōu)化OMP算法的有效性。實(shí)驗(yàn)中選取尺度為256像素×256像素的經(jīng)典實(shí)驗(yàn)圖像Lena，采用高斯隨機(jī)矩陣作為測(cè)量矩陣。OMP算法與本文優(yōu)化OMP算法進(jìn)行重構(gòu)實(shí)驗(yàn)對(duì)比，重構(gòu)結(jié)果如圖3所示。

　　當(dāng)采樣率M/N=50%，采用Lena圖像測(cè)試時(shí)，優(yōu)化OMP算法、OMP算法信噪比分別為34.53 dB、33.72 dB。因此，優(yōu)化后的OMP算法比OMP算法重建精度要高。

　　通過FPGA仿真軟件Modelsim對(duì)優(yōu)化OMP算法硬件電路進(jìn)行了仿真，如圖4所示。

5 結(jié)論

　　本文通過優(yōu)化原子選擇準(zhǔn)則，使得OMP重建本文算法能夠在很短的時(shí)間內(nèi)選擇最優(yōu)原子，縮短了信號(hào)重構(gòu)時(shí)間，提高了算法重建速率。同時(shí)，本文優(yōu)化設(shè)計(jì)了FPGA硬件結(jié)構(gòu)，較好地平衡了占用資源和運(yùn)算時(shí)間。本設(shè)計(jì)采用硬件描述語言Verilog HDL對(duì)優(yōu)化OMP重建算法實(shí)現(xiàn)，運(yùn)用Quartus軟件進(jìn)行算法綜合，進(jìn)行了RTL級(jí)描述，通過Matlab和Modelsim進(jìn)行聯(lián)合仿真，得到了較好的重建效果。結(jié)果表明，優(yōu)化后的OMP算法能夠以較少時(shí)間恢復(fù)原始信號(hào)。

　　參考文獻(xiàn)

　　[1] 任越美，張艷寧，李映.壓縮感知及其圖像處理應(yīng)用研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào)，2014，40(8)：1563-1575.

　　[2] DONOHO D.Compressed sensing[J].IEEE Trans.Info.Theory，2006，52(4)：1289-1306.

　　[3] 莫禹鈞，柏正堯，黃振，等.正交匹配追蹤算法的優(yōu)化設(shè)計(jì)與FPGA實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，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重構(gòu)算法及應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，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分解的快速矩陣求逆方法設(shè)計(jì)[J].電子設(shè)計(jì)工程，2014，22(1)：159-164.