基于QR分解的低復(fù)雜度RLS算法研究

楊鐵軍，李軍華

● （1．中國(guó)人民解放軍92957部隊(duì)，舟山 316001；2．海軍工程大學(xué)，武漢 430033）

基于QR分解的低復(fù)雜度RLS算法研究

楊鐵軍1，李軍華2

● （1．中國(guó)人民解放軍92957部隊(duì)，舟山 316001；2．海軍工程大學(xué)，武漢 430033）

為避免RLS算法在迭代過(guò)程中的數(shù)值發(fā)散現(xiàn)象，研究了復(fù)數(shù)域下基于QR分解的RLS估計(jì)算法，推導(dǎo)了基于Givens旋轉(zhuǎn)的免開(kāi)方、免除法的逆QR-RLS算法，通過(guò)變換可直接得到濾波系數(shù)更新所需增益向量，避免了QR-RLS算法的回代運(yùn)算，同時(shí)消除了逆QR-RLS算法在每次迭代時(shí)的N次開(kāi)方、2N次除法運(yùn)算，有效降低了運(yùn)算量。

信道估計(jì)；RLS算法；QR分解；Givens旋轉(zhuǎn)

0 引言

在短波數(shù)據(jù)通信系統(tǒng)中，為能夠正確接收數(shù)據(jù)，需要對(duì)信道的統(tǒng)計(jì)特性進(jìn)行估計(jì)。 信道估計(jì)技術(shù)的本質(zhì)是實(shí)時(shí)提取信道的特征參數(shù)，用以支持?jǐn)?shù)據(jù)檢測(cè)。 為能夠快速跟蹤信道特性的變化，通常采用最小二乘方法進(jìn)行信道估計(jì)。

RLS算法是一種自適應(yīng)橫向?yàn)V波器的遞歸算法，它的重要特點(diǎn)是收斂速率比一般 LMS濾波器快一個(gè)數(shù)量級(jí)，這是因?yàn)镽LS濾波器通過(guò)利用數(shù)據(jù)相關(guān)矩陣的逆矩陣對(duì)輸入數(shù)據(jù)進(jìn)行白化處理。然而，RLS濾波器性能的改善是以復(fù)雜度的增加為代價(jià)，如何降低RLS算法的復(fù)雜度是其實(shí)用化的關(guān)鍵。

1 開(kāi)方根自適應(yīng)濾波器

1由于RLS算法中自相關(guān)矩陣R(n)及其逆矩陣P(n)是厄米特對(duì)稱和正定的，當(dāng)P(n)在遞推過(guò)程中失去厄米特對(duì)稱或正定的，RLS算法將是數(shù)值不穩(wěn)定的。該不穩(wěn)定性問(wèn)題可采用開(kāi)方根變形來(lái)改善[1]。開(kāi)方根RLS算法在遞歸過(guò)程中傳遞的是由R(n)（或P(n)）定義的開(kāi)方根下三角陣R1/2(n)（或P1/2(n)）。R(n)與R1/2(n)之間的關(guān)系為：

式中：RH/2(n) 為R1/2(n) 的厄米特轉(zhuǎn)置。由于開(kāi)方根RLS算法在遞歸過(guò)程中傳遞的是開(kāi)方根矩陣 R1/2(n) 或P1/2(n)=R-1/2(n)，所以 R(n)=R1/2(n) RH/2(n)和 P(n)=P1/2(n)PH/2(n)確定的矩陣必定是厄米特型的，大多數(shù)情況下能保持它們的正定性。因此，這樣的算法比標(biāo)準(zhǔn)的RLS算法有更好的數(shù)值特性[1]。

RLS算法中兩個(gè)重要的開(kāi)方根自適應(yīng)濾波算法是基于QR分解的QR-RLS算法和逆QR-RLS算法?？柭鼮V波器的開(kāi)方根變形為這兩種算法的導(dǎo)出提供了總體框架，這兩種算法分別利用與卡爾曼開(kāi)方根信息濾波器和開(kāi)方根協(xié)方差濾波器的一一對(duì)應(yīng)關(guān)系而得到[2]?；赒R分解的RLS算法是通過(guò)傳遞經(jīng)QR分解后的開(kāi)方根矩陣來(lái)完成最小二乘權(quán)向量的計(jì)算。QR-RLS算法和逆QR-RLS算法分別傳遞單個(gè)開(kāi)方根R1/2(n)和P1/2(n)=R-1/2(n)。對(duì)于只要求先驗(yàn)誤差 ξ(n)或后驗(yàn)誤差 e(n)的應(yīng)用情況，選擇使用Givens旋轉(zhuǎn)[2]的QR-RLS 算法更適用；而對(duì)于信道估計(jì)、均衡等要求抽頭權(quán)矢量的應(yīng)用情況，基于Givens旋轉(zhuǎn)的逆QR-RLS算法更適合，這是因?yàn)槟鍽R-RLS算法可通過(guò)Givens旋轉(zhuǎn)得到更新抽頭的增益向量k(n)，而QR-RLS算法還需要通過(guò)回代的方法求解k(n)。因此本節(jié)重點(diǎn)討論基于Givens旋轉(zhuǎn)的逆QR-RLS算法。

1.1 逆QR-RLS算法

逆QR-RLS算法是基于對(duì)P1/2(n)=R-1/2(n)的Givens旋轉(zhuǎn)變換得到的，每次迭代都可直接求得增益矢量k(n)，從而可通過(guò)遞歸方程更新抽頭權(quán)向量。而QR-RLS算法在每次迭代后需要利用R-1/2(n)的下三角結(jié)構(gòu)，通過(guò)回代的方法求解抽頭權(quán)向量，因而逆QR-RLS算法在直接更新抽頭權(quán)矢量時(shí)更有效。

就開(kāi)方根而言，逆QR-RLS算法在遞歸過(guò)程中傳遞的是開(kāi)方根矩陣P1/2(n)=R-1/2(n)，由卡爾曼濾波器與RLS算法變量之間的對(duì)應(yīng)關(guān)系[2]，可以從卡爾曼開(kāi)方根協(xié)方差濾波算法導(dǎo)出逆QR-RLS算法。逆QR-RLS算法通過(guò)Givens旋轉(zhuǎn)來(lái)迭代更新增益矢量k(n)和開(kāi)方根矩陣P1/2(n)。如式（2）所示，前陣列A是由P1/2(n-1)和當(dāng)前時(shí)刻輸入x(n)構(gòu)成的(N+1)維方陣，通過(guò)Givens旋轉(zhuǎn)變換，可在后陣列B中獲得更新的開(kāi)方根矩陣P1/2(n)和增益矢量k(n)。前后陣列變換關(guān)系為：

其中，P1/2(n)為上三角矩陣，0為N×1的零矢量，γ(n)為前面提到的收斂因子。G(n)為正交矩陣或酉旋轉(zhuǎn)，它對(duì)前陣列中的塊項(xiàng)λ-1/2XH(n)P1/2(n)進(jìn)行運(yùn)算，從而一一消其中的元素，并在后陣列第一行產(chǎn)生零塊項(xiàng)。

利用矩陣分解引理[1]可得

將等式（3）兩邊矩陣相乘，比較矩陣兩邊對(duì)應(yīng)項(xiàng)，可得，

[1]知，逆QR-RLS算法與標(biāo)準(zhǔn)的RLS算法在遞推過(guò)程中是等價(jià)的，它保留了標(biāo)準(zhǔn)RLS算法收斂速度快，以及對(duì)相關(guān)矩陣特征值擴(kuò)散度變化不敏感等優(yōu)點(diǎn)；同時(shí)，QR分解嚴(yán)格保證了矩陣P(n)在遞歸過(guò)程中的厄米特對(duì)稱性和正定性。

(N+1)維的正交矩陣 G(n)用來(lái)對(duì)前矩陣A中第一行右邊的N項(xiàng)進(jìn)行N次Givens旋轉(zhuǎn)，將第一行N個(gè)元素λ-1/2XH(n)P1/2(n)進(jìn)行逐一置零，從而在后矩陣B中第一列產(chǎn)生與增益矢量k(n)相關(guān)的量，如式（2）。對(duì)應(yīng)地，后矩陣中 P1/2(n)提供了需要更新前矩陣的量， 從而啟動(dòng)下一次迭代。因此，G(n)是 N個(gè) Givens旋轉(zhuǎn)的乘積，即G(n)=G(1)(n)·G(2)(n)……G(N)(n)。下面說(shuō)明如何利用 N 個(gè)Givens旋轉(zhuǎn)，依次消去塊λ-1/2XH(n)P1/2(n-1)中的元素。需要注意的是，前矩陣中的 λ-1/2P1/2(n)為上三角矩陣，因此首先構(gòu)造Givens旋轉(zhuǎn)矩陣G(1)(n)，它對(duì)前矩陣的第一列和第二列起作用，使得第一行中第二個(gè)元素為零；依次類推，構(gòu)造旋轉(zhuǎn)矩陣G(i)(n)，它對(duì)前矩陣的第一列和第i +1列起作用，使得第一行中第i +1個(gè)元素為零，直到構(gòu)造旋轉(zhuǎn)矩陣G(N)(n)，它對(duì)前矩陣的第一列和最后一列作用，消去第一行中最后一個(gè)元素。Givens旋轉(zhuǎn)矩陣G(i)(n)定義為(N+1)×(N+1)的方陣。

令 ρ(n)=[ρ1(n), ρ2(n),…ρN(n)]=λ-1/2XH(n)P1/2(n-1)為輸入數(shù)據(jù)，單獨(dú)抽出矩陣中需要更新的列，則第i次旋轉(zhuǎn)為

由式（2）可知，b(0)(n) =1，b(N)(n) = γ-1/2(n)，u(0)(n) =[u(0)1(n)，u(0)2(n)，…，u(0)N(n)]T=0N，uN(n)=k(n)γ-1/2(n)。

將式（7）展開(kāi)可得

增益失量k(n)可由后矩陣的第一列求得

由式（8）可以看出，基于Givens旋轉(zhuǎn)的逆QR-RLS算法在每輸入一個(gè)數(shù)據(jù)都需要進(jìn)行N次Givens旋轉(zhuǎn)變換，也就需要N次開(kāi)方和2N次除法運(yùn)算。

1.2 低復(fù)雜度的逆QR-RLS算法

無(wú)論是基于QR分解的RLS算法還是逆QR分解的RLS算法，都需要進(jìn)行開(kāi)方和除法運(yùn)算，基于Givens旋轉(zhuǎn)的逆QR-RLS算法在每次輸入數(shù)據(jù)時(shí)都需N次開(kāi)方、2N次除法運(yùn)算，在定點(diǎn)DSP和VLSI等實(shí)用化過(guò)程中，開(kāi)方和除法運(yùn)算所消耗的資源遠(yuǎn)遠(yuǎn)大于乘法和加減法，在高速實(shí)時(shí)數(shù)據(jù)傳輸中，其計(jì)算復(fù)雜度將成為數(shù)據(jù)處理的瓶頸。Frantzeskakis和Liu[3-5]等總結(jié)了各種免開(kāi)方根QR RLS算法，通過(guò)變量代換，提出了一種基于Givens旋轉(zhuǎn)的免開(kāi)方、免除法的QR RLS算法框架。本節(jié)在此基礎(chǔ)上，通過(guò)變量代換，推導(dǎo)了復(fù)數(shù)域下的免開(kāi)方、免除法運(yùn)算的逆QR-RLS算法，消除了每次迭代時(shí)的N次開(kāi)方、2N次除法運(yùn)算，為該算法的實(shí)用化鋪平了道路。

令 ρ(n)=[ρ1(n), ρ2(n),…ρN(n)]=λ-1/2XH(n)P1/2(n)，β=λ-1/2，省略掉時(shí)間遞推標(biāo)號(hào)n，式（2）的N次Givens旋轉(zhuǎn)可表示為

第i次Givens旋轉(zhuǎn)為

令上式中m(i)和分別為，

其中，ti, νi為正數(shù)。將式（18）、（19）分別代入式（15）、（16）、（17）中，則可消去其開(kāi)方和除法運(yùn)算，得

為了避免式（20）～（22）在迭代過(guò)程中數(shù)據(jù)的溢出，需要用參數(shù)ti, νi對(duì)其進(jìn)行歸一化處理。ti、νi的歸一化處理通常采用2的冪次方，在定點(diǎn)處理器中只需進(jìn)行移位操作。

在迭代過(guò)程中只需對(duì)式（20）～（22）進(jìn)行移位處理。

2 仿真分析

利用RLS算法、逆QR-RLS算法和免開(kāi)方、免除法的逆 QR-RLS算法進(jìn)行信道估計(jì)，信道模型選用文獻(xiàn)[1]中的余弦脈沖響應(yīng)，式（27）中取W=2.9。三種算法中遺忘因子λ=0.99，F(xiàn)IR 濾波器階數(shù)為 11，SNR=30 dB，δ=10-4。

圖1是100次集平均的MSE學(xué)習(xí)曲線。免開(kāi)方、免除法的逆QR-RLS算法與逆QR-RLS算法和RLS算法具有相同的收斂特性和穩(wěn)態(tài)誤差，但前者不但克服了 RLS算法的數(shù)值發(fā)散現(xiàn)象，省掉了逆QR-RLS算法的N次開(kāi)方、2N次除法運(yùn)算，同時(shí)還可通過(guò)變換直接得到增益向量，避免了QR-RLS算法的回代運(yùn)算，有效降低了運(yùn)算量。

圖1 不同RLS算法下的信道估計(jì)均方誤差曲線

3 結(jié)語(yǔ)

由于RLS算法中自相關(guān)矩陣在迭代過(guò)程中會(huì)失去正定性，從而導(dǎo)致算法不穩(wěn)定。為避免RLS算法在迭代過(guò)程中的數(shù)值發(fā)散現(xiàn)象，本文通過(guò)變換推導(dǎo)了基于 Givens旋轉(zhuǎn)的免開(kāi)方、免除法逆QR-RLS算法，避免了QR-RLS算法的回代運(yùn)算，同時(shí)消除了逆QR-RLS算法在每次迭代時(shí)的N次開(kāi)方、2N次除法運(yùn)算。采用本文介紹算法可有效降低信道估計(jì)的復(fù)雜度，對(duì)于適時(shí)性高的場(chǎng)合具有一定的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1]Haykin S. Adaptive filter theory[M]. 北京：電子工業(yè)出版社, 2006.

[2]Manolakis D G. 統(tǒng)計(jì)與自適應(yīng)信號(hào)處理[M]. 北京:機(jī)械工業(yè)出版社, 2003.

[3]Frantzeskakis E N, Liu K J R. A class of square root and division free algorithms and architectures for QRD-based adaptive signal processing[R]. Maryland:University of Maryland, institute for systems research center, college park, 1993.

[4]Frantzeskakis E N, Liu K J R. A class of square root and division free algorithms and architectures for QRD-based adaptive signal processing [J]. IEEE Trans.on Signal Processing, 1994, 42(9): 2455-2469.

[5]Realization of QR-RLS Adptive Equalization Algorithm with Low Complexity[J]. Journal of Wuhan University of Technology, 2010,1671:19-0153-06.

Low Complexity RLS Algorithm Based on QR Decomposition

YANG Tie-jun1, LI Jun-hua2
(1. 92957 Army of Chinese People's Liberation Army, Zhoushan 316001, China; 2. Naval Engineering University, Wuhan 430033,China)

To avoid the divergence problem encountering in RLS algorithm, the adaptive RLS filtering algorithm based on the QR decomposition over complex plane is analyzed. Then the Givens-based inverse QR-RLS algorithm, which wis a square-root-free and division-free scheme, is deduced in detail, which can overcome the divergence problem of RLS algorithm. Meanwhile, the square-root-free and division-free scheme can obtain the gain vector directly for coefficients-updated and save N square root and 2N division operations compared with inverse QR-RLS algorithm.

channel estimation; RLS algorithm; QR decomposition; Givens-based

TN911.5

A

楊鐵軍（1975-），男，高級(jí)工程師。研究方向：船機(jī)電監(jiān)測(cè)。