0 引言

2006年，CANDES D E等人提出了壓縮感知（Compressed Sensing，CS）理論[1]，CS理論利用與表達(dá)基不相干的觀測矩陣，以低于奈奎斯特的采樣速率非自適應(yīng)地采樣可稀疏表示的信號，得到低維的離散信息矢量，該信息矢量包含了原始信號的全部信息，然后通過非線性重建算法完美地重建信號。

壓縮感知理論主要包含了三大核心部分：信號的稀疏表示、測量矩陣的構(gòu)造和信號重構(gòu)算法的設(shè)計。在壓縮感知理論的三個核心問題中，如何設(shè)計并用硬件實現(xiàn)根據(jù)離散信息樣點(diǎn)準(zhǔn)確重構(gòu)原始信號的行之有效的算法是該理論中較為重要的一環(huán)。目前，壓縮感知信號重構(gòu)算法主要分為兩類：基于凸松弛的優(yōu)化算法，如基追蹤（Basis Pursuit，BP）算法；

基于貪婪迭代的匹配追蹤算法，如OMP算法[2]。這兩類算法各有優(yōu)缺點(diǎn)：凸松弛算法具有很好的魯棒性，然而由于需要將求解問題轉(zhuǎn)化為線性規(guī)劃問題，計算量大，信號重構(gòu)效率低；貪婪算法雖然不具有強(qiáng)保證性，但實現(xiàn)簡單，重構(gòu)效率高，在工程應(yīng)用中得到廣泛使用[3]。

首次對壓縮感知恢復(fù)算法進(jìn)行VLSI設(shè)計是在參考文獻(xiàn)[4]中，而之后，有文獻(xiàn)進(jìn)行優(yōu)化設(shè)計。參考文獻(xiàn)[5]根據(jù)OMP算法必須按照特定順序執(zhí)行這一特征，采用資源復(fù)用技術(shù)，提高了資源利用率。參考文獻(xiàn)[6]設(shè)計了一個快速求逆平方根算法，在矩陣分解部分采用QR算法。參考文獻(xiàn)[7]對OMP算法進(jìn)行優(yōu)化，減少了計算延時。參考文獻(xiàn)[8]同時進(jìn)行了OMP算法和AMP算法的VLSI設(shè)計。本文先對OMP算法進(jìn)行理論分析，然后對OMP算法進(jìn)行改進(jìn)，通過增加一個閾值來減少乘法運(yùn)算次數(shù)，使運(yùn)算速度更快。在矩陣分解部分采用ACD方法避免開方運(yùn)算，同時在硬件實現(xiàn)上也進(jìn)行了相應(yīng)的優(yōu)化。仿真結(jié)果驗證了設(shè)計的可行性。

1 OMP算法

1.1 基本OMP算法

在壓縮感知中，原始信號x的稀疏度為k，觀測矢量y是所采集的數(shù)據(jù)，y可通過測量矩陣Φ與x相乘而得。本設(shè)計的目的是在已知y和Φ的前提下恢復(fù)出x。OMP算法主要分為兩部分，即尋找稀疏矢量中非零元素的位置和計算非零元素的值。

在OMP算法中殘差r是一個很關(guān)鍵的參數(shù)，殘差是通過當(dāng)前選取的列向量和原始信號的線性組合不能對壓縮測量值進(jìn)行表示的部分。

1.2 改進(jìn)OMP算法

令原始信號x的稀疏度為k，測量矩陣Φ大小為M×N，那么y為M維的離散信息矢量。本文提出一種新的方法，即加閾值法，通過添加一個閾值來減少乘法運(yùn)算次數(shù)，閾值定為內(nèi)積和的平均值的α倍，內(nèi)積小于閾值的那些列在下一次迭代中不再求內(nèi)積。每次迭代計算后都要對閾值進(jìn)行更新。信號估計的均方誤差隨著α的增大而增大，當(dāng)α為0時均方誤差最小。改進(jìn)的OMP算法步驟如下：

2 計算步驟

本文利用硬件實現(xiàn)重構(gòu)長度N=256、稀疏度k=8的原始信號，觀測矢量長度M=64。

改進(jìn)后的OMP算法可分為4個模塊。第1個模塊對應(yīng)重建過程的第(1)和第(2)步，也就是在剩余列的集

中尋找對殘差貢獻(xiàn)最大的列為最匹配原子。

第2個模塊對應(yīng)重建過程的第(3)步，即計算新殘差，為下次迭代做準(zhǔn)備。

第3個模塊對應(yīng)重建過程的第(4)和第(5)步，即計算新的閾值并除去剩余列的集

中和殘差求內(nèi)積小于閾值的列。求閾值前要先求內(nèi)積的平均值。第t次迭代的內(nèi)積平均值可用以下公式計算：

為解決對Φ的列的定位問題，用一個256位的標(biāo)志位來追蹤Φ的列，標(biāo)志位的第i位對應(yīng)Φ的第i列。在第i列和殘差求內(nèi)積后，下一個時鐘和殘差求內(nèi)積的就是下一個標(biāo)志位為非零所對應(yīng)的列，跳過標(biāo)志位為零對應(yīng)的列。開始前先把標(biāo)志位的每一位全部初始化成1，在每一次迭代之后對標(biāo)志位進(jìn)行更新。

第4個模塊對應(yīng)重構(gòu)過程的第(7)步，求解非零元素的值，即解決最小二乘問題。對于這類運(yùn)算一般用Moore-Penrose偽逆的方法求解：

求出C的逆矩陣后，就可以求得原始信號的估計：

由于OMP算法的迭代性質(zhì)，4個模塊是不能并行執(zhí)行的，只能每個模塊依次執(zhí)行。

3 硬件設(shè)計

硬件電路主要由以上4個模塊組成，分為兩個部分。整體硬件電路如圖1所示。

首先用觀測矢量y對殘差r進(jìn)行初始化。y用寄存器組存儲，而觀測矩陣Φ用多個RAM存儲，這樣就能在一個時鐘內(nèi)讀出y的所有值和Φ的一列值。數(shù)據(jù)用24位定點(diǎn)數(shù)表示，10位整數(shù)，14位小數(shù)。設(shè)計64個24位乘法器并行工作來求內(nèi)積，然后找到內(nèi)積最大值來更新

。矩陣

的大小變化從N×1～N×8。

每次迭代后會把Φ中和殘差內(nèi)積小于閾值的列過濾掉，根據(jù)式(9)、(10)和(11)，剩余列的集中的每一列和殘差的內(nèi)積都送到累加器進(jìn)行求和，然后通過求內(nèi)積平均值求得閾值。閾值參數(shù)α設(shè)置為一個常數(shù)。

256位標(biāo)志位作為Φ的地址尋址，標(biāo)志位每一位對應(yīng)Φ每一列，初始化為所有位為1。每次迭代后對標(biāo)志位進(jìn)行更新，把Φ中和殘差內(nèi)積小于閾值的列所對應(yīng)的標(biāo)志位賦為零，否則保持為1。然后在下一次迭代時跳過標(biāo)志位為零所對應(yīng)的Φ的列，也就是直接用下一個非零標(biāo)志位所對應(yīng)的列與殘差進(jìn)行求內(nèi)積。通過把標(biāo)志位的前32位送到一個32位前導(dǎo)零計算器可以找出下一個非零位。

在尋找非零元素位置的部分迭代8次后，就開始計算非零元素的值。首先要計算矩陣

可通過以下等式計算：

此處復(fù)用之前的64個乘法器。C是一個對稱矩陣，所以只需要計算C的對角線上8個元素和對角線下半部（或上半部）的28個元素。

然后要對C進(jìn)行交替的柯列斯基分解，矩陣分解要求出下三角矩陣L和對角矩陣D。從式(13)和(14)可以看出，L和D是相互依存的，必須以特定的順序計算。本設(shè)計中稀疏度k=8，L和D可以按照圖2箭頭所指順序計算。設(shè)計7個乘法器并行計算D中的元素，那么每計算一個元素需要一個時鐘周期。計算D-1時采用參考文獻(xiàn)[9]的方法進(jìn)行除法運(yùn)算。由于L的同一列的各個元素并不是相互依存的，所以求L的每一列值都設(shè)計為并行計算各個元素，那么每一列的計算只需要一個時鐘周期。

矩陣L的求逆需要迭代進(jìn)行，如式(18)：

由于L的逆矩陣的各列的各個元素是相互依存的，所以列和列可以并行運(yùn)算，每一列要按照特定的順序運(yùn)算，那么計算L-1需要7個時鐘周期。

求C-1=(L-1)T×D-1×L-1時可以先求A=(L-1)T×D-1，然后再計算C-1=A×L-1。

4 仿真及結(jié)果分析

考慮到兩個模塊的最大運(yùn)行頻率不一樣，本設(shè)計在尋找非零元素部分采用85 MHz的時鐘，在求解非零元素值部分采用65 MHz的時鐘。為了進(jìn)行更好的對比，在MATLAB上用相同的算法、測量矩陣和觀測矢量來重構(gòu)原始估計值。當(dāng)α=0.25時，軟件和硬件的重構(gòu)結(jié)果進(jìn)行歸一化后的對比如圖3所示。

當(dāng)α取值為零時，尋找非零元素部分共需要2 100個時鐘周期，而僅僅是計算內(nèi)積就需要256×8=2 048個時鐘周期，計算非零元素部分共需要110個時鐘周期，總的重構(gòu)時間為26.40 μs。當(dāng)α取值為0.25時，計算內(nèi)積所需減少到約1 300個時鐘周期，總的重構(gòu)時間減少到約16.99 μs。在相同條件下，參考文獻(xiàn)[7]重構(gòu)時間為17.61 μs。而在參考文獻(xiàn)[4]中，測量矩陣維數(shù)為32×128，觀測向量維數(shù)為32×1，原始信號的稀疏度為5，總的重構(gòu)時間就需要24 μs。

但是改進(jìn)OMP算法歸一化誤差會隨著α的增大而增大，當(dāng)α取值為零時，歸一化均方誤差為0.001 5，取α=0.25時，歸一化均方誤差增加到0.007 1。

5 結(jié)論

本文采用一種閾值法，使得OMP恢復(fù)算法的求內(nèi)積次數(shù)大大減少，從而縮短了信號重構(gòu)所需要的時間，提高了恢復(fù)速率。同時，本文在硬件結(jié)構(gòu)設(shè)計上也進(jìn)行了一些優(yōu)化，較好地平衡了占用資源和運(yùn)算時間。本設(shè)計采用VHDL對改進(jìn)的OMP算法進(jìn)行了RTL級描述，在Quartus II上針對Altera公司的Cyclone II EP2C70F672C6進(jìn)行設(shè)計和仿真，結(jié)果表明信號能夠以更少的重構(gòu)時間較好地恢復(fù)。

參考文獻(xiàn)

[1] DONOHO D L.Compressed sensing[J].Information Theory，IEEE Trans. on，2006，52(4)：1289-1306.

[2] TROPP J A，GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit[J].Information Theory，IEEE Trans.on，2007，53(12)：4655-4666.

[3] 趙貽玖.稀疏模擬信號壓縮采樣與重構(gòu)算法研究[D].成都：電子科技大學(xué)，2012.

[4] SEPTINUS A，STEINBERG R.Compressive sampling hardware reconstruction[C].Circuits and Systems(ISCAS)，Proc.of 2010 IEEE International Symposium on.IEEE，2010：3316-3319.

[5] BLACHE P，RABAH H，AMIRA A.High level prototyping and FPGA implementation of the orthogonal matching pursuit algorithm[C].Information Science，Signal Processing and their Applications(ISSPA)，2012 11th International Conference on.IEEE，2012：1336-1340.

[6] 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.

[7] STANISLAUS J，MOHSENIN T.Low-complexity fpga implementation of compressive sensing reconstruction[C].International Conference on Computing，Networking and Communications.2013.

[8] BAI L，MAECHLER P，MUEHLBERGHUBER M，et al.High-speed compressed sensing reconstruction on FPGA using OMP and AMP[C].Proc.19th Int.Conf.Electronics，Circuits and Systems(ICECS)，Dec.2012：53-56.

[9] 周殿鳳，王俊華.基于FPGA的32位除法器設(shè)計[J].信息化研究，2010(3)：26-28.

編輯：jq