一種基于FFT低復(fù)雜度的信道盲辨識(shí)算法

孫有銘 劉洛琨 楊正舉 郭 虹

（解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院，鄭州，450002）

引 言

隨著移動(dòng)通信的迅猛發(fā)展，對(duì)于高容量、高可靠性傳輸?shù)淖非笫沟貌恍枰?xùn)練序列的信道盲辨識(shí)技術(shù)非常具有吸引力。盲辨識(shí)技術(shù)由于其節(jié)省了信道資源，提高了信道傳輸效率受到了信號(hào)處理領(lǐng)域?qū)W者的廣泛重視。目前盲辨識(shí)算法主要分為基于高階統(tǒng)計(jì)量的傳統(tǒng)方法和基于循環(huán)平穩(wěn)二階統(tǒng)計(jì)量的方法兩大類。隨著Tong等人開創(chuàng)性地提出利用二階循環(huán)統(tǒng)計(jì)量進(jìn)行時(shí)不變信道盲辨識(shí)［1］之后出現(xiàn)了一系列的盲辨識(shí)算法［2－7］。

文獻(xiàn)［2］提出了一種利用接收端過采樣之后形成的單輸入多輸出（Single input multiple output，SIMO）信道各個(gè)子信道的交叉相關(guān)（Cross－relation，CR）性質(zhì)建立線性方程，從而獲得信道向量閉式解的CR算法。文獻(xiàn)［3］提出了一種利用接收數(shù)據(jù)的自相關(guān)矩陣可劃分為相互正交的“信號(hào)空間”和“噪聲空間”，利用噪聲子空間和信道矩陣的正交性來(lái)求解信道系數(shù)的子空間方法（Subspace，SS）。文獻(xiàn)［4］在文獻(xiàn)［3］的基礎(chǔ)上提出了一種最小噪聲子空間方法（Minimum noise subspace，MNS），巧妙地利用含有最小冗余度的子信道對(duì)來(lái)求解信道系數(shù)，降低了SS算法的運(yùn)算復(fù)雜度。文獻(xiàn)［5］將文獻(xiàn)［4］的思想推廣到了CR算法中，提出了一種最小CR算法（Minimum cross relation，MCR）。

傳統(tǒng)二階循環(huán)統(tǒng)計(jì)量盲辨識(shí)算法在短突發(fā)信號(hào)條件下性能惡化甚至失效，算法對(duì)于觀測(cè)數(shù)據(jù)的長(zhǎng)度有一定要求［8］。為了解決小樣本觀測(cè)數(shù)據(jù)條件下的信道盲辨識(shí)問題，文獻(xiàn)［6］提出了一種將CR算法通過FFT變換到離散頻域來(lái)求解信道系數(shù)的BI－FFT算法，在短突發(fā)的小樣本觀測(cè)數(shù)據(jù)（M＋1≤Ns＜3M＋1，M表示信道階數(shù)）和較高信噪比條件下獲得了良好的性能。但是文獻(xiàn)［6］采用的是標(biāo)準(zhǔn)CR算法，當(dāng)過采樣率越大時(shí)運(yùn)算的復(fù)雜度也迅速提升。本文在BI－FFT算法基礎(chǔ)上提出了一種只利用最小冗余信息建立頻域CR方程的F－MCR算法，該算法既減小了BI－FFT算法的運(yùn)算復(fù)雜度又達(dá)到了與原有算法相當(dāng)?shù)男阅堋?/p>

針對(duì)現(xiàn)有的階數(shù)估計(jì)算法（包括Liavas算法［9］、新穎的有效階數(shù)估計(jì)算法（Novel effective channel order estimation，NECOE）［10］以及基于子空間信道矩陣迭代的階數(shù)算法［1］等大多建立在自相關(guān)矩陣的奇異值分析的基礎(chǔ)上，對(duì)于觀測(cè)數(shù)據(jù)量有一定要求，在短突發(fā)（小樣本）接收數(shù)據(jù)情況下，以上算法失效。本文結(jié)合F－MCR算法中的矩陣Fy的秩信息給出了一種可行的快速階數(shù)估計(jì)算法。

本文中，nullspace（A）表示矩陣A的零空間維度，deg（p（x））表示多項(xiàng)式p（x）中的x最高次數(shù)，［·］T，［·］H，?，（·）＋，‖·‖2分別表示轉(zhuǎn)置、共軛轉(zhuǎn)置、卷積、Moore－Penrose偽逆運(yùn)算和取2范數(shù)操作。

1 信道模型和CR算法

考慮單天線以L倍波特率過采樣或用L根天線以波特率接收［1］，可得到SIMO信道。在算法建模中將其等效為有限階支撐的M階FIR信道。

式中：s（n）是統(tǒng)計(jì)獨(dú)立發(fā)射信號(hào)序列，x（n）＝［x1（n），x2（n），…，xL（n）］T為無(wú)噪的觀測(cè)向量，h（n）＝［h1（n），h2（n），…，hL（n）］T，其中hi（n）（i＝1，…，L）為第i條信道的沖激響應(yīng)，可簡(jiǎn)記為h＝（n），v2（n），…，vM（n）］T為方差為且獨(dú)立于發(fā)送信號(hào)的高斯白噪聲，y（n）為迭加了噪聲后的觀測(cè)向量。

無(wú)噪情況下，在信道階數(shù)M已知時(shí)信道i的輸出xi（n）和信道j的輸出xj（n）存在以下CR關(guān)系

式（3）寫成如下矩陣形式

式中

則關(guān)于所有子信道對(duì)（i，j），其中i，j＝1，2，…，L，i≠j，可以得到如下方程組

式中

實(shí)際中噪聲的影響不可避免。假設(shè)噪聲是加性高斯白噪聲，那么式（9）修正為

式中：YL是由迭加了噪聲影響的實(shí)際接收數(shù)據(jù)構(gòu)成，而δ則是相對(duì)應(yīng)的誤差向量。可以用最小二乘法求解方程并施加范數(shù)約束后獲得信道向量的閉式解

2 F－MCR算法

2.1 算法描述

文獻(xiàn)［5］提出的最小冗余度的 MCR算法和MNS［4］算法類似，主要是通過一種樹形的結(jié)構(gòu)來(lái)構(gòu)建，這種樹形結(jié)構(gòu)既反映出了信道間的差異性又具有最小的信息冗余度。

定理1 在SIMO系統(tǒng)中，首先從L個(gè)輸出x1，…，xL中選出L－1個(gè)不同的組，每組是兩個(gè)子信道輸出數(shù)據(jù)的組合，L－1個(gè)組合可以構(gòu)成一個(gè)樹的結(jié)構(gòu)。把每個(gè)子信道的輸出看作一個(gè)樹的結(jié)點(diǎn)，共有L個(gè)結(jié)點(diǎn)，使樹形結(jié)構(gòu)具有最小冗余度必須遵循連接所有節(jié)點(diǎn)并且不構(gòu)成回路的原則。依據(jù)此樹形結(jié)構(gòu)構(gòu)建的CR方程具有最小冗余度。

定理1的證明參見文獻(xiàn)［5］，顯然樹形結(jié)構(gòu)的連接的方法并不唯一。圖1所示為一個(gè)5倍波特率采樣的SIMO信道的樹形結(jié)構(gòu)的選取，［1，2］，［1，3］，［2，4］，［2，5］的輸出子信道組就可以列出最小冗余度的CR方程用來(lái)求解信道系數(shù)。

圖1 系統(tǒng)輸出樹形圖Fig.1 Tree diagram of system output

標(biāo)準(zhǔn)CR算法中，需要運(yùn)用到所有的子信道輸出對(duì)，即L倍過采的SIMO信道就需要用到L（L－1）／2個(gè)信道對(duì)構(gòu)成CR方程，L越大，隨之形成的YL矩陣也就越龐大，計(jì)算量也會(huì)隨之增加。但是在MCR算法中，只需要用到L－1個(gè)信道對(duì)，當(dāng)過采樣L＞2時(shí)，計(jì)算量明顯減少。

假定在無(wú)噪聲情況下，每個(gè)子信道的輸出序列xi（n）的長(zhǎng)度為Ns＋M，其中1≤i≤L，對(duì)xi（n）×hj（n）－xj（n）×hi（n）＝0，0≤i＜j≤L等式兩邊進(jìn)行N點(diǎn)FFT變換（N≥Ns＋M），可得離散頻域表達(dá)式

式（12）可以寫為

式中

式中：W＝e－j2π／N，并定義Fi，j＝其中Fj位于i個(gè)矩陣塊的位置，而Fi位于第j個(gè)矩陣塊的位置。其中將符合MCR中最小冗余度的的子信道對(duì)［i，j］組成Fi，j矩陣，再將Fi，j構(gòu) 成 一 個(gè) 大 的 矩 陣 塊Fx∈CN（L－1）×L（M＋1）

在考慮噪聲影響后，F(xiàn)x將由接收的含噪數(shù)據(jù)進(jìn)行FFT后構(gòu)成的Fy來(lái)近似，則可修正為

其中ε為噪聲引起的誤差矩陣，對(duì)式利用最小二乘方法求解并施加范數(shù)約束可得

2.2 階數(shù)估計(jì)算法

現(xiàn)假設(shè)信道階數(shù)M未知，僅階數(shù)的上界MU已知。那么原來(lái)的精確階數(shù)估計(jì)下的Fy寫成可以根據(jù)Fy（M）的零空間的維度來(lái)進(jìn)行階數(shù)估計(jì)。

定理2零空間特性定理

（1）＝M，是列秩虧為1，有唯一線性解，即nullspace）＝1。

（3）M＋1≤≤MU，是列秩虧為－M＋1，即nullspace＝－M＋1

證明：文獻(xiàn)［6］中已經(jīng)給出（1）和（2）的分析，這里不再贅述，以下將給出情況（3）的證明如下：

當(dāng)＝M＋ΔM，ΔM＝1，2…時(shí)，由于的選擇決定了WM矩陣，即相當(dāng)于選取了DFT矩陣的前＝M＋ΔM列。式（14）可以寫成

此時(shí)估計(jì)得到的和都是×1的列向量，就是對(duì)進(jìn)行N點(diǎn)DFT，由此可得的Z域形式（Z），其deg（Z））≤；同理，deg（（Z））≤。式（20）可等價(jià)于以下Z變換形式

假設(shè)輸入符號(hào)要滿足以下條件，其DFT形式下的S（k）≠0，k＝0，1，…，N－1［6］，式（21）可簡(jiǎn)化為

由于子信道之間滿足互質(zhì)條件，即zeros（Hj（Z））∩zeros（Hi（Z））＝0，且滿足Hi（Z），Hj（Z）≠0，又有（Z）），那么可得zeros（Hj（Z））?zeros（Hj（Z）），由于deg（Hi（Z））＝M，則（Z），其中0≤deg（c（z））≤ΔM。由式（21）可得可知c（z）為過估計(jì)引入的公共零點(diǎn)。得到的形式和文獻(xiàn)［12］中的形式一致，可知解空間的維度為ΔM＋1，即nullspace＝由于DFT矩陣的特殊形式，可知01×（ΔM－a）］T，a＝0，1，…，ΔM為解空間的基，得證。

定理2表明矩陣在信道階數(shù)過估計(jì)時(shí)獲得不是一維線性解而是一個(gè)解空間，其維度為＋1。由于噪聲的影響，在過估計(jì)情況下屬于的零奇異值不再為零，本文將采用矩陣相鄰的兩個(gè)奇異值比值的大小來(lái)判斷零奇異值和非零奇異值之間的分界線。設(shè)維度為（N（L－1））×L＋1）的Fy（M）的奇異值為

令ri表示相鄰奇異值λi－1和λi之比

現(xiàn)給出一個(gè)信道階數(shù)快速搜索算法，階數(shù)搜索過程如下。

（1）選擇一個(gè)較大的階數(shù)估計(jì)值，確定的零空間的維度是否為1，即最大r的位置后面的較小的比值個(gè)數(shù)。若維度為1則搜索結(jié)束。若零空間維度不為1跳入步驟（2）。

（2）零空間維度不為1，即最大的r的后面的小的比值的個(gè)數(shù)為d（d為正整數(shù)），則將－d作為新的階數(shù)估計(jì)值，并跳入步驟（1）。

2.3 算法流程

綜上所述，本文算法步驟如下：

（1）選取一個(gè)較大的階數(shù)估計(jì)值，通過進(jìn)行奇異值分解，利用給出的階數(shù)估計(jì)算法從的零空間維度估計(jì)出精確信道階數(shù)M。

（2）選取合適的FFT點(diǎn)數(shù)N滿足N≥Ns＋M，對(duì)每個(gè)子信道的輸出向量xm進(jìn)行FFT變換并計(jì)算Fm矩陣。

（3）根據(jù)樹形結(jié)構(gòu)找到最小冗余度的L－1個(gè)信道對(duì)［i，j］，1≤i，j≤L，并由相應(yīng)信道對(duì)的數(shù)據(jù)組成Fi，j，再將Fi，j組成Fy矩陣。

（4）通過式（19）求解得到信道向量的閉式解。

2.4 算法復(fù)雜度

由于BI－FFT算法中沒有階數(shù)估計(jì)環(huán)節(jié)，這里僅考慮在階數(shù)M已知情況下的復(fù)雜度分析，通過F－MCR和BI－FFT算法在對(duì)Fy矩陣的構(gòu)建不難發(fā)現(xiàn)，BI－FFT 算法下的Fy（BI－FFT）的維度是（NL（L－1）／2）×L（M＋1），而F－MCR算法下的Fy（F－MCR）的維度是（N（L－1））×L（M＋1）。參考文獻(xiàn)［13］的運(yùn)算復(fù)雜度分析方法，為簡(jiǎn)化分析主要考慮算法中運(yùn)算復(fù)雜度最高的奇異值分解部分，對(duì)于BI－FFT算法大約需要O｛NM2L4｝，而 F－MCR只需約O｛NM2L3｝。當(dāng)L越大，這種計(jì)算量的差異性就會(huì)越明顯。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證算法的性能，選取SS算法和文獻(xiàn)［6］提出的BI－FFT算法做性能對(duì)比。仿真時(shí)采用文獻(xiàn)［1］中給出過采率L＝4時(shí)形成的SIMO信道，信道階數(shù)M＝4，信道系數(shù)如表1所示。

表1 含4個(gè)子信道的SIMO信道系數(shù)Table 1 Channel coefficients of a SIMO channel with 4sub－channels

發(fā)射信號(hào)為均勻分布的QPSK信號(hào)，迭加的噪聲為高斯白噪聲。辨識(shí)結(jié)果用歸一化均方誤差（Normalized root－mean－square error，NRMSE）進(jìn)行評(píng)價(jià)。NRMSE的定義如下

其中：Nr為蒙特卡羅實(shí)驗(yàn)次數(shù)，在本次仿真試驗(yàn)中設(shè)定Nr＝100，hi是第i次實(shí)驗(yàn)的辨識(shí)結(jié)果。

3.1 信道估計(jì)性能隨信噪比變化實(shí)驗(yàn)

為了驗(yàn)證本文信道算法在小樣本觀測(cè)數(shù)據(jù)條件下的有效性，選取發(fā)射端發(fā)送符號(hào)數(shù)量Ns＝10，即每個(gè)子信道可用的數(shù)據(jù)為Ns＋M，設(shè)定FFT變換的點(diǎn)數(shù)N＝16。出于公平性，此處實(shí)驗(yàn)均假定信道階數(shù)已知。從圖2可以明顯看到SS算法已經(jīng)完全失效，而本文提出的F－MCR和BI－FFT算法性能相當(dāng)，可見F－MCR算法在降低BI－FFT算法的運(yùn)算復(fù)雜度的同時(shí)并沒有引起性能惡化。圖2的結(jié)果中可以得知小樣本觀測(cè)數(shù)據(jù)條件下傳統(tǒng)的基于二階統(tǒng)計(jì)量的盲辨識(shí)算法性能惡化甚至失效。文獻(xiàn)［8］證明傳統(tǒng)算法至少需要滿足Ns≥3M＋1，而基于BI－FFT算法和F－MCR算法只需滿足Ns≥M＋1。

圖2 SNR－NRMSE曲線圖Fig.2 Performance of NRMSE with changing

3.2 階數(shù)估計(jì)算法性能隨信噪比變化實(shí)驗(yàn)

圖3為在表1中所給信道條件下Liavas算法、NECOE算法與本文所提階數(shù)算法的階數(shù)估計(jì)正確率隨信噪比變化圖。其中本文所提算法中參數(shù)同實(shí)驗(yàn)3.1，Liavas算法和NECOE算法中接收符號(hào)數(shù)均為200。從圖3中可知，Liavas算法在SNR≥24dB估計(jì)正確率達(dá)到100%，而NECOE算法在SNR≥28dB估計(jì)正確率達(dá)到100%。雖然本文所提階數(shù)估計(jì)算法也需在SNR≥28dB估計(jì)正確率達(dá)到100%，但在同樣的短突發(fā)小樣本條件下，Liavas算法和NECOE算法完全失效。

圖3 SNR－階數(shù)估計(jì)正確率曲線圖Fig.3 Probability of correct channel order detection with changing SNR

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

本文提出了一種改進(jìn)的基于FFT的盲辨識(shí)算法（F－MCR），該算法充分利用MCR算法只需利用最小冗余度的信息建立線性方程即可估計(jì)信道的特性，將其經(jīng)過FFT后再求得信道向量閉式解，并給出了一個(gè)快速階數(shù)搜索的方法。理論分析和仿真表明：該算法在較高信噪比和樣本數(shù)目較小時(shí)性能明顯優(yōu)于經(jīng)典的二階統(tǒng)計(jì)量盲辨識(shí)算法，較BIFFT算法的復(fù)雜度明顯降低而性能幾乎相當(dāng)，同時(shí)提升了對(duì)于信道階數(shù)估計(jì)誤差的魯棒性。

［1］Tong L，Xu G，Kailath T.Blind identification and equalization based on second－order statisics：a time domin approach［J］.IEEE Trans on Inform Theory，1994，40：340－349.

［2］Xu G，Liu H，Tong L，et al.A least squares approach to blind channel identification［J］.IEEE Trans on Signal Processing，1995，43（12）：2982－2993.

［3］Moulines E，Duhannel P，Cardoso J F，et al.Subspace methods for the blind identification of multichannel FIR filters［J］.IEEE Trans on Signal Processing，1995，43（2）：516－525.

［4］Hua Y，Abed－Meraim K，Wax M.Blind system identification using minimum noise subspace ［C］／／8 th IEEE Workshop on SSAP.Corfu，Greece：［s.n.］，1996：308－311.

［5］Aissa－El－Bey A，Grebici M，Abed－Meraim K.et al.Blind system identification using cross－relation methods：further results and developments［J］.7th International Symposium on Signal Processing and Its Applications，2003，1：649－652.

［6］Wang S，Manton J，Tay D B H，et al.An FFT－based method for bind identification of FIR SIMO channels［J］.IEEE Signal Processing Letters，2007，14（7）：437－440.

［7］李森，邱天爽.基于魯棒性協(xié)方差矩陣估計(jì)的盲信道識(shí)別方法［J］.數(shù)據(jù)采集與處理，2010，25（5）：549－553.Li Sen，Qiu Tianshuang.Blind channel identification based on robust covariance matrix estimation ［J］.Journal of Data Acquisition and Processing，2010，25（5），549－553.

［8］Hua Y，Wax M.Strict identifiability of multiple FIR channels driven by an unkown arbitrary sequence［J］.IEEE Trans Signal Processing ，1996，44（3）：756－759.

［9］Liavas A P，Regalia P.On the behavior of information theoretic criteria for model order selection ［J］.IEEE Transactions on Signal Processing，2001，49（8）：1689－1695.

［10］代松銀，袁嗣杰，董書攀.基于子空間分解的信道階數(shù)估計(jì)算法［J］.電子學(xué)報(bào)，2010，38（6），1245－1248.Dai Songyin，Yuan Sijie，Dong Shupan.Effective channel order estimation based on subspace decomposition［J］.Chinese Journal of Electronics，2010，38（6）：1245－1248.

［11］孫有銘，劉洛琨，崔波，等.基于子空間信道矩陣迭代的階數(shù)估計(jì)算法［J］.電子與信息學(xué)報(bào)，2013，35（2）：432－437.Sun Youming，Liu Luokun，Cui Bo，et al.Channel order estimation algorithm based on subspace channel matrix recursion［J］.Journal of Electronics ＆Information Technology，2013，35（2）：432－437.

［12］Gunther J，Swindlehurst A.On the use of kernel structure for blind equalization［J］.IEEE Trans Signal Process，2000，48（3），799－809.

［13］Hua Y.Fast maximum likelihood for blind identification of multiple FIR channels［J］.IEEE Trans Signal Processing，1996，44（3）：661－672.