OFDM 稀疏信道估計(jì)中改進(jìn)的OMP算法

趙龍慧，潘樂(lè)炳，李寶清

（1.中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所 無(wú)線傳感網(wǎng)與通信重點(diǎn)實(shí)驗(yàn)室，上海200050；2.中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所 微系統(tǒng)技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室，上海200050；3.中國(guó)科學(xué)院大學(xué)，北京100049）

0 引 言

在基于相干解調(diào)的OFDM 系統(tǒng)中，接收端的相干檢測(cè)和均衡通常需要精確的信道信息，信道估計(jì)性能的好壞直接影響接收機(jī)的性能。研究結(jié)果表明，無(wú)線信道具有稀疏性［1］，如水聲信道、數(shù)字電視信道等，而常見(jiàn)的基于導(dǎo)頻的信道估計(jì)算法如LS、最小均方誤差 （MMSE）等沒(méi)有考慮信道的稀疏性［2］，為準(zhǔn)確估計(jì)信道信息，需要插入大量的導(dǎo)頻，頻譜利用率比較低。

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

1 壓縮感知理論簡(jiǎn)介

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

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

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

目前的重構(gòu)算法主要有凸優(yōu)化算法和貪婪追蹤算法兩類(lèi)。前者將欠定問(wèn)題轉(zhuǎn)換成凸優(yōu)化問(wèn)題，重構(gòu)精度高，但運(yùn)算復(fù)雜度高，不是本文的研究重點(diǎn)。本文主要研究貪婪追蹤算法中的OMP 算法，從硬件實(shí)現(xiàn)的角度對(duì)其進(jìn)行改進(jìn)，降低硬件實(shí)現(xiàn)的復(fù)雜度和計(jì)算時(shí)間。

2 OFDM 系統(tǒng)模型

在寬帶無(wú)線通信中，系統(tǒng)采樣周期通常遠(yuǎn)遠(yuǎn)小于信道時(shí)延擴(kuò)展，大部分信道系數(shù)為0或接近于0，信道具有稀疏性［8］。一個(gè)時(shí)變無(wú)線信道的脈沖響應(yīng)如式 （3）所示

式中：N ——多經(jīng)數(shù)，hi（t）和τi（t）——t時(shí)刻第i 條路徑的復(fù)增益和時(shí)延，0≤τi（t）≤τmax，τmax為多徑時(shí)延最大值。在慢衰落信道中，信道相干時(shí)間遠(yuǎn)大于符號(hào)周期，信道沖激響應(yīng)在一個(gè)OFDM 符號(hào)周期里近似不變，此時(shí)對(duì)h（τ）以系統(tǒng)采樣周期TS進(jìn)行采樣，有

文獻(xiàn) ［9］中提出了壓縮感知理論應(yīng)用在OFDM 信道估計(jì)時(shí)的數(shù)學(xué)模型，具體如下：假設(shè)OFDM 系統(tǒng)子載波數(shù)為N，信道長(zhǎng)度為L(zhǎng)，則經(jīng)過(guò)沖激響應(yīng)h（n）得到系統(tǒng)信道傳輸模型為

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

設(shè)S為P×N 的矩陣，用于從N 個(gè)子載波中提取出P個(gè)導(dǎo)頻數(shù)據(jù)，從N×N 數(shù)據(jù)矩陣中選擇出P 個(gè)導(dǎo)頻位置對(duì)應(yīng)的行，則有

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

3 信道估計(jì)算法

3.1 傳統(tǒng)的LS估計(jì)算法

文獻(xiàn) ［10］指出，在式 （7）中，當(dāng)OFDM 子載波中插入的導(dǎo)頻數(shù)大于信道長(zhǎng)度即P≥L 時(shí)，用LS算法可以得到較為精確的信道估計(jì)值，此時(shí)，LS估計(jì)為

3.2 基于OMP的稀疏信道估計(jì)算法

式 （7）中，令y＝y(tǒng)P為觀測(cè)向量，T ＝XpWp為測(cè)量矩陣，則壓縮感知信道估計(jì)模型為

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

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

（2）尋找匹配向量

（3）擴(kuò)展索引集

擴(kuò)展選中的列集合

Sk中有k 個(gè)列向量。

綜上，新型“互聯(lián)網(wǎng)+”下的教學(xué)模式改革是高校教學(xué)工作改革面臨的新挑戰(zhàn)。我們將以網(wǎng)絡(luò)化、多樣化、個(gè)性化為著力點(diǎn)，對(duì)教學(xué)目標(biāo)、教學(xué)方案和教學(xué)方式進(jìn)行綜合性的改革，形成合力，以達(dá)到培養(yǎng)高質(zhì)量多樣化人才的目的。

（4）更新殘差

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

3.3 基于改進(jìn)OMP的稀疏信道估計(jì)算法

本文采用了一種基于動(dòng)態(tài)門(mén)限的方法來(lái)減少上述OMP算法步驟 （2）中向量的點(diǎn)乘運(yùn)算的次數(shù)，進(jìn)而減少?gòu)?fù)雜度和運(yùn)算時(shí)間。其基本思想是：每次OMP算法內(nèi)部迭代過(guò)程中，在步驟 （2）中向量運(yùn)算之后，設(shè)置一個(gè)門(mén)限值，使小于該門(mén)限的值所對(duì)應(yīng)的矩陣T 的列不參與下次迭代中的向量乘法運(yùn)算，以此來(lái)降低程序的運(yùn)行時(shí)間。本文中門(mén)限值的選取采用向量運(yùn)算結(jié)果的平均值，每次OMP算法內(nèi)部迭代過(guò)程中都會(huì)更新。具體步驟如下：

（1）始化殘差r0＝y(tǒng)，迭代次數(shù)k＝1，索引集Λ ＝，選中的列集合S＝，初始化一個(gè)長(zhǎng)度為N 的全1行向量flag，flag 中的每一個(gè)元素對(duì)應(yīng)測(cè)量矩陣T 的每一列；

（2）尋找匹配向量：檢查flag 中元素是否為零，若不為零，計(jì)算其對(duì)應(yīng)的列與殘差的內(nèi)積，若為零，則跳過(guò)其對(duì)應(yīng)的列。T 中所有的列都參與計(jì)算之后，找出內(nèi)積的最大值所對(duì)應(yīng)的列

（3）擴(kuò)展索引集

擴(kuò)展選中的列集合

Sk中有k 個(gè)列向量。

（4）更新殘差

（5）計(jì)算 （2）中向量運(yùn)算結(jié)果的平均值

其中，m 是T 中矩陣的列數(shù)。

（6）去除矩陣T 中小于門(mén)限值threshk的列

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

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

上述算法中的flag 向量用來(lái)標(biāo)記在OMP 算法內(nèi)部迭代過(guò)程中沒(méi)有被置零的列，若在某一次迭代過(guò)程中某個(gè)內(nèi)積值小于該次迭代的門(mén)限值，則將該列所對(duì)應(yīng)的flag 向量中的元素置0，下次迭代時(shí)直接尋找flag 中非零元素所對(duì)應(yīng)的列來(lái)計(jì)算，以此來(lái)降低運(yùn)算時(shí)間。

4 仿真結(jié)果與性能分析

為了驗(yàn)證改進(jìn)的OMP 算法在OFDM 系統(tǒng)中信道估計(jì)的性能，本文進(jìn)行了幾組仿真，系統(tǒng)參數(shù)設(shè)置如下：信道為L(zhǎng)＝100、稀疏度為6 的信道，OFDM 系統(tǒng)子載波總數(shù)N＝512，循環(huán)前綴為子載波數(shù)的，采用帶有格雷映射的16QAM （quadrature amplitude modulation）調(diào)制。考慮 以下幾組仿真：

（1）導(dǎo)頻數(shù)P＝24時(shí)，OMP算法和改進(jìn)的OMP 算法與P＝32 時(shí)的LS 算法進(jìn)行對(duì)比，比較指標(biāo)為誤碼率（symbol error rate）。其中OMP算法和改進(jìn)的OMP算法采用文獻(xiàn) ［3］中提出的最優(yōu)導(dǎo)頻，導(dǎo)頻位置集合為 ｛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算法采用均勻?qū)ьl。仿真結(jié)果如圖1所示。

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

圖1 LS算法、OMP算法和改進(jìn)的OMP算法估計(jì)性能比較

（2）比較不同門(mén)限值時(shí)改進(jìn)OMP算法的性能。導(dǎo)頻數(shù)為24，仍然采用 （1）中的最優(yōu)導(dǎo)頻。比較α取值為0.05～0.35，間隔為0.05時(shí)OMP 算法和改進(jìn)的OMP 算法的均方誤差 （mean squared error），此時(shí)固定信噪比為25dB。MSE定義如下

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

圖2 改進(jìn)的OMP算法在不同的門(mén)限值下的估計(jì)性能比較

（3）比較不同門(mén)限值時(shí)改進(jìn)OMP算法在每次迭代過(guò)程中平均濾除的列數(shù)。仿真參數(shù)設(shè)置如下：導(dǎo)頻數(shù)為24，仍然采用 （1）中的最優(yōu)導(dǎo)頻。比較α取值為0.05～0.35，間隔為0.05時(shí)改進(jìn)的OMP算法每次濾除的列數(shù)，此時(shí)固定信噪比為30dB。

表1中的 “列數(shù)”指不同門(mén)限值時(shí)平均每次迭代中參與運(yùn)算的列數(shù)，這里的迭代指改進(jìn)的OMP算法運(yùn)行一次，衡量指標(biāo)為改進(jìn)的OMP算法運(yùn)行一次之后flag 向量中非零元素的個(gè)數(shù)。

表1 不同門(mén)限值時(shí)平均每次迭代中參與運(yùn)算的列數(shù)

圖3更加直觀的說(shuō)明了隨門(mén)限值增大，濾除的列數(shù)增多的趨勢(shì)。仿真中OFDM 符號(hào)取為5，對(duì)其中的兩個(gè)符號(hào)進(jìn)行估計(jì)，其它的通過(guò)線性插值來(lái)得到，即系統(tǒng)每迭代一次每個(gè)門(mén)限值下改進(jìn)的OMP 算法要運(yùn)行2 次。以α＝0.2為例，由圖2 知，此時(shí)平均每次濾除列數(shù)為83，以100次迭代為列，則100 次迭代之后，共濾除的列數(shù)為2×100×83＝16600，由此減少了運(yùn)算時(shí)間，降低了復(fù)雜度。

圖3 改進(jìn)的OMP算法在不同的門(mén)限值下平均每次迭代濾除的列數(shù)

（4）比較不同門(mén)限值時(shí)改進(jìn)的OMP算法的運(yùn)行時(shí)間，同時(shí)用OMP 算法的運(yùn)行時(shí)間作為參照。相關(guān)參數(shù)和 （2）中保持一致。仿真工具為MATLAB R2013a，仿真機(jī)配置為Intel四核，主頻3.40 GHz，RAM 4 GB，32 位Windows 7操作系統(tǒng)。

由圖4可知，與OMP算法相比，改進(jìn)的OMP算法運(yùn)行時(shí)間減少，并且隨著門(mén)限值的增大，兩者的差距逐漸增大，這是因?yàn)楦倪M(jìn)算法中，隨門(mén)限值增大，每次迭代過(guò)程中測(cè)量矩陣T 有更多的列被濾除，不參與下次迭代過(guò)程中的向量點(diǎn)乘運(yùn)算。

圖4 改進(jìn)的OMP算法在不同的門(mén)限值下的運(yùn)算時(shí)間比較

5 結(jié)束語(yǔ)

本文研究了基于壓縮感知的稀疏信道估計(jì)算法，從硬件實(shí)現(xiàn)的角度出發(fā)，提出一種基于動(dòng)態(tài)門(mén)限的OMP算法來(lái)降低OMP算法的復(fù)雜度。仿真結(jié)果表明，與傳統(tǒng)的LS算法相比，改進(jìn)的OMP算法可以使用較少的導(dǎo)頻獲得更好的估計(jì)效果，提高了傳輸效率；與OMP相比，改進(jìn)算法在取合適的門(mén)限值的情況下，可以在估計(jì)精度稍微下降的情況下降低OMP算法的復(fù)雜度，減少運(yùn)行時(shí)間，對(duì)于硬件實(shí)現(xiàn)具有一定的指導(dǎo)意義。

［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ì)導(dǎo)頻圖案設(shè)計(jì) ［J］.南京郵電大學(xué)學(xué)報(bào) （自然科學(xué)版），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ìn)展［J］.電子學(xué)報(bào)，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ì)中的應(yīng)用［J］.通信技術(shù)，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 系統(tǒng)稀疏信道估計(jì)新方法研究 ［J］.南京郵電大學(xué)學(xué)報(bào) （自然科學(xué)版），2010，30 （2）：60－65.］