OFDM 稀疏信道估計中改進的OMP算法

趙龍慧，潘樂炳，李寶清

（1.中國科學院 上海微系統與信息技術研究所 無線傳感網與通信重點實驗室，上海200050；2.中國科學院 上海微系統與信息技術研究所 微系統技術國防科技重點實驗室，上海200050；3.中國科學院大學，北京100049）

0 引 言

在基于相干解調的OFDM 系統中，接收端的相干檢測和均衡通常需要精確的信道信息，信道估計性能的好壞直接影響接收機的性能。研究結果表明，無線信道具有稀疏性［1］，如水聲信道、數字電視信道等，而常見的基于導頻的信道估計算法如LS、最小均方誤差 （MMSE）等沒有考慮信道的稀疏性［2］，為準確估計信道信息，需要插入大量的導頻，頻譜利用率比較低。

文獻［3］指出，OFDM 系統中基于導頻的信道估計算法實際上是利用導頻符號重建信道頻率相應，結合無線信道的稀疏性，可以將壓縮感知的重構算法應用于OFDM 系統的信道估計中。目前壓縮感知用于稀疏信道估計的有基追蹤 （basis pursuit）算法、OMP 算法等。BP 算法是基于線性規劃的凸優化問題，需要的觀測次數少，但計算復雜度高，不能滿足信道估計的實時性要求，硬件也難以實現。OMP算法相比BP算法降低了計算復雜度，是一種次優的算法，已經在FPGA （field－programmable gate array）上實現［4，5］。本文提出一種改進的OMP算法，應用在信道估計中，該算法可以減少OMP算法中向量點乘運算的次數。仿真結果表明，與OMP算法相比，在與OMP算法估計精度相差不多的情況下，該算法可以減少計算復雜度和運算時間，對于實際應用具有一定的指導意義。

1 壓縮感知理論簡介

壓縮感知的基本原理［6］如下：一個長度為N 的實值離散信號X，為RN空間的列向量，元素為 X ［n］ ，n＝1，2...N，RN空間的任何向量都可以用N×1維的基向量的線性組合表示，假設這些基都正交。由構成N×N 維基矩陣Ψ ＝ ｛Ψ1，Ψ2，...，ΨN｝，則信號X 可以表示為

其中，Θ是投影系數Θ＝［θi］＝ ［＜X，Ψi＞ ］構成的N×1的列向量。如果Θ中只有K 個較大的非零值，且K＜＜N，則稱信號X 在Ψ域是稀疏或是可壓縮的。對于K 稀疏的信號X，通過一個滿足有限等距性質 （restricted isometry property，RIP）［7］的測量矩陣Φ，從中選取M（M ＜＜N）個觀測值，接收端利用這M 個觀測值重構原信號。利用矩陣形式描述上述過程

其中，Y：M×1的列向量，即為M 個觀測值，Φ：M×N 的測量矩陣。常見的測量矩陣有高斯隨機矩陣、伯努利隨機矩陣等。在接收端由式 （2）通過一定的重構算法求解出信號X 的N 個元素。

目前的重構算法主要有凸優化算法和貪婪追蹤算法兩類。前者將欠定問題轉換成凸優化問題，重構精度高，但運算復雜度高，不是本文的研究重點。本文主要研究貪婪追蹤算法中的OMP 算法，從硬件實現的角度對其進行改進，降低硬件實現的復雜度和計算時間。

2 OFDM 系統模型

在寬帶無線通信中，系統采樣周期通常遠遠小于信道時延擴展，大部分信道系數為0或接近于0，信道具有稀疏性［8］。一個時變無線信道的脈沖響應如式 （3）所示

式中：N ——多經數，hi（t）和τi（t）——t時刻第i 條路徑的復增益和時延，0≤τi（t）≤τmax，τmax為多徑時延最大值。在慢衰落信道中，信道相干時間遠大于符號周期，信道沖激響應在一個OFDM 符號周期里近似不變，此時對h（τ）以系統采樣周期TS進行采樣，有

文獻 ［9］中提出了壓縮感知理論應用在OFDM 信道估計時的數學模型，具體如下：假設OFDM 系統子載波數為N，信道長度為L，則經過沖激響應h（n）得到系統信道傳輸模型為

其中N×N 矩陣X＝diag （x1，x2，...xN）表示OFDM符號內的數據，包含數據映射符號和導頻符號；N×1向量H 為信道頻域響應采樣值，N×1向量n為復加性高斯白噪聲，L×1向量h＝ ［h0，h1，...，hL－1］T是信道時域響應，K 稀疏。N×L 矩陣W 為標準傅里葉變換的前L 列

設S為P×N 的矩陣，用于從N 個子載波中提取出P個導頻數據，從N×N 數據矩陣中選擇出P 個導頻位置對應的行，則有

其中，P×1向量yP＝Sy，P×P 矩陣XP＝SXS′，P×L 矩陣WP＝SW，P×1向量nP＝Sn。上式中，yp是接收端的導頻數據，Xp是發射端的導頻數據，WP是選擇出的部分傅里葉矩陣，三者對接收端均為已知，接收端通過信道估計算法恢復出h向量，則信道頻域響應H 為

3 信道估計算法

3.1 傳統的LS估計算法

文獻 ［10］指出，在式 （7）中，當OFDM 子載波中插入的導頻數大于信道長度即P≥L 時，用LS算法可以得到較為精確的信道估計值，此時，LS估計為

3.2 基于OMP的稀疏信道估計算法

式 （7）中，令y＝yP為觀測向量，T ＝XpWp為測量矩陣，則壓縮感知信道估計模型為

OMP算法的基本思想是在每一次迭代過程中，從T 中選取與y 最匹配的原子來對h 進行近似。經過一定的迭代之后，信號可由已選原子進行線性表示。用OMP算法進行信道估計的具體步驟如下：

（1）初始化殘差r0＝y，迭代次數k＝1，選中的索引集Λ ＝，選中的列集合S＝；

（2）尋找匹配向量

（3）擴展索引集

擴展選中的列集合

Sk中有k 個列向量。

綜上，新型“互聯網+”下的教學模式改革是高校教學工作改革面臨的新挑戰。我們將以網絡化、多樣化、個性化為著力點，對教學目標、教學方案和教學方式進行綜合性的改革，形成合力，以達到培養高質量多樣化人才的目的。

（4）更新殘差

（5）k＝k＋1，如果k＜K，返回（2），K 為h的稀疏度。

3.3 基于改進OMP的稀疏信道估計算法

本文采用了一種基于動態門限的方法來減少上述OMP算法步驟 （2）中向量的點乘運算的次數，進而減少復雜度和運算時間。其基本思想是：每次OMP算法內部迭代過程中，在步驟 （2）中向量運算之后，設置一個門限值，使小于該門限的值所對應的矩陣T 的列不參與下次迭代中的向量乘法運算，以此來降低程序的運行時間。本文中門限值的選取采用向量運算結果的平均值，每次OMP算法內部迭代過程中都會更新。具體步驟如下：

（1）始化殘差r0＝y，迭代次數k＝1，索引集Λ ＝，選中的列集合S＝，初始化一個長度為N 的全1行向量flag，flag 中的每一個元素對應測量矩陣T 的每一列；

（2）尋找匹配向量：檢查flag 中元素是否為零，若不為零，計算其對應的列與殘差的內積，若為零，則跳過其對應的列。T 中所有的列都參與計算之后，找出內積的最大值所對應的列

（3）擴展索引集

擴展選中的列集合

Sk中有k 個列向量。

（4）更新殘差

（5）計算 （2）中向量運算結果的平均值

其中，m 是T 中矩陣的列數。

（6）去除矩陣T 中小于門限值threshk的列

（7）k＝k＋1，如果k＜K，返回（2），K 為h的稀疏度。

（8）利用S中的向量求解h∧

上述算法中的flag 向量用來標記在OMP 算法內部迭代過程中沒有被置零的列，若在某一次迭代過程中某個內積值小于該次迭代的門限值，則將該列所對應的flag 向量中的元素置0，下次迭代時直接尋找flag 中非零元素所對應的列來計算，以此來降低運算時間。

4 仿真結果與性能分析

為了驗證改進的OMP 算法在OFDM 系統中信道估計的性能，本文進行了幾組仿真，系統參數設置如下：信道為L＝100、稀疏度為6 的信道，OFDM 系統子載波總數N＝512，循環前綴為子載波數的，采用帶有格雷映射的16QAM （quadrature amplitude modulation）調制。考慮 以下幾組仿真：

（1）導頻數P＝24時，OMP算法和改進的OMP 算法與P＝32 時的LS 算法進行對比，比較指標為誤碼率（symbol error rate）。其中OMP算法和改進的OMP算法采用文獻 ［3］中提出的最優導頻，導頻位置集合為 ｛1，67，130，162，171，187，199，221，228，239，250，294，299，310，325，333，340，365，416，423，429，438，470，489｝，α取為0.2，LS算法采用均勻導頻。仿真結果如圖1所示。

由圖1可知，隨信噪比增加，3種方法的SER 均減小，LS算法下降的很慢，而OMP 算法和改進的OMP 算法的SER 隨信噪比增加下降的比較快。但當系統信噪比小于5 dB時，OMP算法和改進的OMP算法SER 與LS算法相比沒有優勢，這是因為壓縮感知技術在信道高斯白噪聲很大時采樣值失真較大，重建方法失效［10］。隨著信噪比的增加，基于壓縮感知的估計算法優越性不斷增加，信道估計性能優于導頻數為32的LS算法，與OMP算法最大相差約25dB，與改進的OMP算法最大相差約22dB。由此可見，OMP算法和改進的OMP算法用較少的導頻獲得了更好的估計性能，節省的導頻可以用來傳送用戶數據，提高系統吞吐量。信噪比小于20dB時，OMP算法和改進的OMP算法的估計性能幾乎沒有差別，信噪比大于20dB時，二者的性能差距隨信噪比增加而增大，但是相差的也不是太多。

圖1 LS算法、OMP算法和改進的OMP算法估計性能比較

（2）比較不同門限值時改進OMP算法的性能。導頻數為24，仍然采用 （1）中的最優導頻。比較α取值為0.05～0.35，間隔為0.05時OMP 算法和改進的OMP 算法的均方誤差 （mean squared error），此時固定信噪比為25dB。MSE定義如下

圖2是當取不同的門限值時改進的OMP算法的估計性能，同時用OMP算法的估計性能作為參照。理論上OMP算法的MSE應該是一條直線，即不受門限值的影響，但是仿真過程產生的高斯噪聲在每次迭代過程中都不一樣，因此會出現一定的起伏。由圖2對比可知，當α取值為0.05和0.1 時，改進的OMP 算法和OMP 算法性能相當；α＞0.1時，二者開始出現差異，相比于OMP 算法，改進的OMP算法的MSE開始增大，但在0.1～0.2之間增大的不是很多；α＞0.2時，兩者開始出現比較顯著的差異。

圖2 改進的OMP算法在不同的門限值下的估計性能比較

（3）比較不同門限值時改進OMP算法在每次迭代過程中平均濾除的列數。仿真參數設置如下：導頻數為24，仍然采用 （1）中的最優導頻。比較α取值為0.05～0.35，間隔為0.05時改進的OMP算法每次濾除的列數，此時固定信噪比為30dB。

表1中的 “列數”指不同門限值時平均每次迭代中參與運算的列數，這里的迭代指改進的OMP算法運行一次，衡量指標為改進的OMP算法運行一次之后flag 向量中非零元素的個數。

表1 不同門限值時平均每次迭代中參與運算的列數

圖3更加直觀的說明了隨門限值增大，濾除的列數增多的趨勢。仿真中OFDM 符號取為5，對其中的兩個符號進行估計，其它的通過線性插值來得到，即系統每迭代一次每個門限值下改進的OMP 算法要運行2 次。以α＝0.2為例，由圖2 知，此時平均每次濾除列數為83，以100次迭代為列，則100 次迭代之后，共濾除的列數為2×100×83＝16600，由此減少了運算時間，降低了復雜度。

圖3 改進的OMP算法在不同的門限值下平均每次迭代濾除的列數

（4）比較不同門限值時改進的OMP算法的運行時間，同時用OMP 算法的運行時間作為參照。相關參數和 （2）中保持一致。仿真工具為MATLAB R2013a，仿真機配置為Intel四核，主頻3.40 GHz，RAM 4 GB，32 位Windows 7操作系統。

由圖4可知，與OMP算法相比，改進的OMP算法運行時間減少，并且隨著門限值的增大，兩者的差距逐漸增大，這是因為改進算法中，隨門限值增大，每次迭代過程中測量矩陣T 有更多的列被濾除，不參與下次迭代過程中的向量點乘運算。

圖4 改進的OMP算法在不同的門限值下的運算時間比較

5 結束語

本文研究了基于壓縮感知的稀疏信道估計算法，從硬件實現的角度出發，提出一種基于動態門限的OMP算法來降低OMP算法的復雜度。仿真結果表明，與傳統的LS算法相比，改進的OMP算法可以使用較少的導頻獲得更好的估計效果，提高了傳輸效率；與OMP相比，改進算法在取合適的門限值的情況下，可以在估計精度稍微下降的情況下降低OMP算法的復雜度，減少運行時間，對于硬件實現具有一定的指導意義。

［1］Bajwa WU，Haupt J，Sayeed AM，et al.Compressed channel sensing：A new approach to estimating sparse multipath channels ［J］.Proceedings of the IEEE，2010，98 （6）：1058－1076.

［2］Bajwa WU，Haupt J，Raz G，et al.Compressed chanel sensing ［C］／／42nd Annual Conference on Information Sciences and Systems.IEEE，2008：5－10.

［3］HE Xueyun，SONG Rongfang，ZHOU Keqin.Design of pilot pattern for compressive sensing based sparse channel estimation in OFDM systems［J］.Journal of Nanjing University of Posts and Telecommunications（Natural Science），2012，31 （5）：7－11 （in Chinese）. ［何雪云，宋榮方，周克琴.基于壓縮感知的OFDM 稀疏信道估計導頻圖案設計 ［J］.南京郵電大學學報 （自然科學版），2012，31 （5）：7－11.］

［4］Septimus A，Steinberg R.Compressive sampling hardware reconstruction ［C］／／Proceedings of 2010 IEEE International Symposium on Circuits and Sytems.IEEE，2010：3316－3319.

［5］Stanislaus JLVM，Mohsenin T.Low－complexity FPGA implementation of compressive sensing reconstruction ［C］／／International Conference on Computing，Networking and Communications.IEEE，2013：671－675.

［6］SHI Guangming，LIU Danhua，GAO Dahua，et al.Advanced in theory and application of compressed sensing ［J］.Acta Electronica Sinica，2009，37 （5）：1070－1081 （in Chinese）. ［石光明，劉丹華，高大化，等.壓縮感知理論及其研究進展［J］.電子學報，2009，37 （5）：1070－1081.］

［7］Candes EJ.The restricted isometry property and its implications for compressed sensing ［J］.Comptes Rendus Mathematique，2008，346 （9）：589－592.

［8］Qi C，Wu L.Optimized pilot placement for sparse channel estimation in OFDM systems ［J］.Signal Processing Letters，IEEE，2011，18 （12）：749－752.

［9］HE Xueyun，PAN Lin，PENG Weigang.Application of compressive sensing theory in sparse channel estimation ［J］.Communications Technology，2011，44 （9）：27－29 （in Chinese）.［何雪云，潘林，彭偉剛.壓縮感知在稀疏信道估計中的應用［J］.通信技術，2011，44 （9）：27－29.］

［10］HE Xueyun，SONG Rongfang，ZHOU Keqin.Study of compressive sensing based sparse channel estimation in OFDM systems［J］.Journal of Nanjing University of Posts and Telecommunictions（Natural Science），2010，30 （2）：60－65 （in Chinese）. ［何雪云，宋榮方，周克琴.基于壓縮感知的OFDM 系統稀疏信道估計新方法研究 ［J］.南京郵電大學學報 （自然科學版），2010，30 （2）：60－65.］