基于QR分解的低復雜度RLS算法研究

楊鐵軍，李軍華

● （1．中國人民解放軍92957部隊，舟山 316001；2．海軍工程大學，武漢 430033）

基于QR分解的低復雜度RLS算法研究

楊鐵軍1，李軍華2

● （1．中國人民解放軍92957部隊，舟山 316001；2．海軍工程大學，武漢 430033）

為避免RLS算法在迭代過程中的數值發散現象，研究了復數域下基于QR分解的RLS估計算法，推導了基于Givens旋轉的免開方、免除法的逆QR-RLS算法，通過變換可直接得到濾波系數更新所需增益向量，避免了QR-RLS算法的回代運算，同時消除了逆QR-RLS算法在每次迭代時的N次開方、2N次除法運算，有效降低了運算量。

信道估計；RLS算法；QR分解；Givens旋轉

0 引言

在短波數據通信系統中，為能夠正確接收數據，需要對信道的統計特性進行估計。 信道估計技術的本質是實時提取信道的特征參數，用以支持數據檢測。 為能夠快速跟蹤信道特性的變化，通常采用最小二乘方法進行信道估計。

RLS算法是一種自適應橫向濾波器的遞歸算法，它的重要特點是收斂速率比一般 LMS濾波器快一個數量級，這是因為RLS濾波器通過利用數據相關矩陣的逆矩陣對輸入數據進行白化處理。然而，RLS濾波器性能的改善是以復雜度的增加為代價，如何降低RLS算法的復雜度是其實用化的關鍵。

1 開方根自適應濾波器

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

式中：RH/2(n) 為R1/2(n) 的厄米特轉置。由于開方根RLS算法在遞歸過程中傳遞的是開方根矩陣 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)確定的矩陣必定是厄米特型的，大多數情況下能保持它們的正定性。因此，這樣的算法比標準的RLS算法有更好的數值特性[1]。

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

1.1 逆QR-RLS算法

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

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

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

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

將等式（3）兩邊矩陣相乘，比較矩陣兩邊對應項，可得，

[1]知，逆QR-RLS算法與標準的RLS算法在遞推過程中是等價的，它保留了標準RLS算法收斂速度快，以及對相關矩陣特征值擴散度變化不敏感等優點；同時，QR分解嚴格保證了矩陣P(n)在遞歸過程中的厄米特對稱性和正定性。

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

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

由式（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(n)可由后矩陣的第一列求得

由式（8）可以看出，基于Givens旋轉的逆QR-RLS算法在每輸入一個數據都需要進行N次Givens旋轉變換，也就需要N次開方和2N次除法運算。

1.2 低復雜度的逆QR-RLS算法

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

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

第i次Givens旋轉為

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

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

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

在迭代過程中只需對式（20）～（22）進行移位處理。

2 仿真分析

利用RLS算法、逆QR-RLS算法和免開方、免除法的逆 QR-RLS算法進行信道估計，信道模型選用文獻[1]中的余弦脈沖響應，式（27）中取W=2.9。三種算法中遺忘因子λ=0.99，FIR 濾波器階數為 11，SNR=30 dB，δ=10-4。

圖1是100次集平均的MSE學習曲線。免開方、免除法的逆QR-RLS算法與逆QR-RLS算法和RLS算法具有相同的收斂特性和穩態誤差，但前者不但克服了 RLS算法的數值發散現象，省掉了逆QR-RLS算法的N次開方、2N次除法運算，同時還可通過變換直接得到增益向量，避免了QR-RLS算法的回代運算，有效降低了運算量。

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

3 結語

由于RLS算法中自相關矩陣在迭代過程中會失去正定性，從而導致算法不穩定。為避免RLS算法在迭代過程中的數值發散現象，本文通過變換推導了基于 Givens旋轉的免開方、免除法逆QR-RLS算法，避免了QR-RLS算法的回代運算，同時消除了逆QR-RLS算法在每次迭代時的N次開方、2N次除法運算。采用本文介紹算法可有效降低信道估計的復雜度，對于適時性高的場合具有一定的實用價值。

參考文獻：

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

[2]Manolakis D G. 統計與自適應信號處理[M]. 北京:機械工業出版社, 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-），男，高級工程師。研究方向：船機電監測。