一种改进的HRLS算法

摘 要：HRLS(Hierarchical Lest―Squares Algorithm)算法是一种改进的RLS算法，他减少了运算量，但对FIR信道估计时，他只适用于输入信号是白噪声而且信道的非零系数少的情况。提出一种改进的HRLS算法，该算法在HRLS算法每级后面(最后一级除外)加一个RLS滤波器，其输入分别为同一级其他滤波器输入的均值和前一级新加滤波器的输出。此滤波器回收了被HRLS分组分级处理所丢掉的组间信号的联系，把握住了输入信号的整体变化规律。仿真结果和分析表明该算法与HRLS相比具有较好的收敛性，而且当把FIR信道划分后所得的每个子信道的自身系数间的差异不大时，其收敛性能与RLS算法近似，同时与RLS相比，其复杂度降低，且具有更强的抗噪能力。

关键词：HRLS算法；FIR滤波器；信道估计；收敛性

中图分类号：TN911 文献标识码：B

文章编号：1004373X(2008)0306103

An Improved HRLS Algorithm

LIU Aifei1,JIN Minglu1,QU Qiang1,2

(1.Institution of Electronic and Information Engineering,Dalian University of Technology,Dalian,116024,China;

2.Institution of Electronic and Information Engineering,Liaoning University of Science and Technology,Anshan,114044,China)

Abstract：HRLS algorithm makes improvement to RLS algorithm for its complexity reduction,however,it is only adaptive to the FIR channel when it is used for channel estimation.In this paper,an improved HRLS algorithm is proposed.This algorithm adds a RLS unit at the end of each level of HRLS scheme except the last level.The mean of inputs in each elder corresponding unit at the same level and the output of the new added unit of the upper level consist the inputs of the new added RLS unit.Therefore,the new added unit in each level collects some information lost by the hierarchical approach of HRLS,and commands the total changing behavior of the input signals.From the simulations and the analysis we can confirm that in the area of convergence performance,the proposed algorithm is better than HRLS algorithm in whatever circumstance,and close to RLS algorithm when the coefficients of every sub―channel obtained after the division of FIR channel have a little difference from each other.Furthermore,the proposed algorithm has much stronger noise resistance than RLS algorithm.

Keywords：HRLS algorithm;FIR filter;channel estimation;convergence performance

1 引 言

RLS 算法是一种自适应的最小二乘算法，该算法具有收敛速度快，跟踪能力强的优点。其主要缺点是每次迭代需要的运算量很大，对于N阶横向滤波器，其计算量在N2数量级[1,2]，为此，人们提出了一些快速算法，如平方根RLS算法、快速横向RLS算法和HRLS算法[2―4]，其中HRLS算法由于其较少的运算量和较强的抗噪能力受到人们的关注。HRLS算法是把滤波器的抽头系数组合成一个α级β进制的逻辑树，其中α,β是大于2的正整数。其计算复杂度为ο(Nβ)(N为RLS滤波器的阶数)，因为β远小于N，所以HRLS的计算复杂度远小于RLS。但HRLS算法的适用范围有一定的限制，在FIR信道估计时，只有输入信号是白噪声且被估计信道的非零系数不多时，HRLS算法才表现出比RLS算法好的收敛性能，反之则HRLS的收敛性能急剧变坏[5]。针对此问题，本文对HRLS作了一些改进，提出了一种平均HRLS算法，简记做AHRLS(Average HRLS)算法，仿真结果和分析表明该算法有较好的收敛性和较强的抗噪能力。

2 改进的HRLS方案

2.1 AHRLS算法的具体过程

根据文献[4]中所给的HRLS算法，我们用rlij代表在第l级上的第i组的第j个输入。α为HRLS的级数，β为每一级上的RLS滤波器的阶数,用wlij代表在第l级上的第i组的第j个加权系数。HRLS算法的结构有如下规律：

(1) 第l级上的所有抽头总数为N/βl-1;

(2) 级数α等于logβN；

(3) 第l级上的RLS单元个数为N/βl；

AHRLS算法的结构如图1所示。

AHRLS算法是在HRLS算法基础上，在每级(最后一级除外)的后面加一个RLS滤波器，其输入分别为HRLS中各个滤波器输入的均值与前一级增加的RLS滤波器的输出，其输出作为下一级新增的RLS滤波器的一个输入，如果下一级为最末级，其输出直接作为最后一级仅有的RLS滤波器的一个输入。所以第l级(l=2,…,α-1)新增RLS滤波器的输入个数为HRLS算法中第l级RLS滤波器个数(βα -l)加一，第1级新增滤波器的输入个数为βα-1。

图1 当α=2时，AHRLS算法的结构

下面结合具体的例子，给出AHRLS算法不同于HRLS算法的部分。假设N=27,据HRLS的结构划分可得β=3,α=3。因为AHRLS算法是在HRLS结构基础上，在每级(最后一级外)的最后又加了一个RLS滤波器，所以第1级，第2级，第3级的组数分别为10，4，1。

第1级新加RLS滤波器的输入为：(r1101,r1102,…,r1109)，其中：

第2级新加RLS滤波器的输入为：(r241,r242,r243,r244)，其中：

第3级只有一组输入：(r311,r312,r313,r314)，其中：

第3级的结果即为最终的输出：∑4k=1w31kr31k。

2.2 计算复杂度的比较

HRLS算法计算复杂度为ο(Nβ)，AHRLS算法中新增RLS滤波器所需的总运算量为：(β+1)2+(β2+1)2+…+(βα-2+1)2+(βα-1)2，大约为β2(α-1)，所以AHRLS的计算复杂度为ο(N(β+N/β2)) ，比HRLS增加β2(α-1)，但由于β+N/β2比N小很多，所以其计算复杂度较RLS降低很多。

3 仿真结果及性能分析

此部分给出利用AHRLS，HRLS和RLS进行FIR信道估计时所得仿真结果。为了便于比较，取仿真环境与文献[5]相同。设给定一离散FIR信道模型：

其中u(t)是信道的输入，y(t)为输出，e(t)是均值为零的白噪声，n

其中：w(t)是均值为零，方差为1的白序列，a=0.99。对于HRLS和AHRLS算法，级数α等于2。

运行200次独立仿真试验，计算每个信道系数的统计均方误差{MSE}nk=1,并且以分贝为单位画总的均方误差((1/n)∑[DD(]n[]k=1[DD)]MSEkMSE)曲线。

(1) e(t)的标准差为0.4，h0=h1=h2=h3=1，其他信道系数为零。所得MSE曲线如图2所示。由图可看出达到相同MSE，AHRLS和HRLS需要的迭代次数小于RLS，AHRLS的[HK]性能略好于HRLS。

这是因为当FIR信道的非零个数很少，小于等于HRLS的第一级中每个RLS滤波器的阶数时，用HRLS第一级的第一个滤波器即可很好的估计信道。而HRLS的分组分级处理，增加了收敛速度，故其收敛性能好于RLS。

图2 e(t)的标准差为0.4，H=[1 1 1 1 0 0 0 0 0…0]时

所得的MSE曲线图

(2) e(t)的标准差为0.4，信道的前8个系数为1，其余为0，得MSE函数曲线见图3，从图中能看出随着信道非零系数的增加时，HRLS的性能急剧变坏，AHRLS，RLS的性能基本不变。这是因为当信道的非零个数大于HRLS的第一级中每个RLS滤波器的阶数时，由于HRLS对输入信号的分组分级处理丢掉了组与组间的联系信息，故其收敛性能急剧恶化。而AHRLS在每一级(最后一级除外)上增加的RLS滤波器，其输入分别对应前面各个滤波器输入的均值。这样相当于回收了输入信号的一些整体信息，把握住了信号的整体变化规律，故性能要好于HRLS。

(3) e(t)的标准差为0.4，信道系数分别为[1 1 1 1 0.5 0.3 0.4 0.2 0…0]T和[1 1 1 1 1 0 0.5 0 0…0]T时，得MSE函数曲线如图4和图5所示。取级数α=2，故可把有N个系数的信道划分为N个具有N个系数的子信道，例如：[1 1 1 1 0.5 0.3 0.4 0.2 0…0]，可划分4个子信道，分别为：[1 1 1 1]，[0.5 0.3 0.4 0.2]，[0 0 0 0],[0 0 0 0]。比较图4、图5可看出，当每个子信道的自身系数间的差别不大时，AHRLS表现出良好的性能。当某一个子信道的自身系数间的差别很大时，AHRLS的性能变坏，但要比HRLS改善很多。

图3 e(t)的标准差为0.4，H=[1 1 1 1 1 1 1 1 0…0]时

所得的MSE曲线

图4 e(t)的标准差为0.4，H=[1 1 1 1 0.5 0.3 0.4 0.2 0…0]T

所得的MSE曲线

图5 e(t)的标准差为0.4，H=[1 1 1 1 1 0 0.5 0 0…0]时

所得的MSE曲线

对此我们可以从数学公式上解释。为了分析方便，设级数α=2，用(k)来表示第k个信道系数的估计值，k=1,2…n。

根据HRLS算法结构，可推得其信道参数的估计值为：

根据AHRLS算法结构，可推得其信道参数的估计值为：

对比式(6)，式(7)，可看出增加的RLS滤波器的作用是用其抽头系数来修正仅由HRLS算法所得的信道系数的估计值，而且这种修正是对第i个子信道系数的所有估计用相同的值(w1(N+1)iw21(N+1)N)进行整体修正，所以当每个子信道的自身系数间的差别不大时，AHRLS算法表现出良好的性能，反之，性能变坏。但由于AHRLS算法每级(最后一级除外)增加的RLS滤波器对输入信号整体信息的利用，使得其性能总比HRLS算法好。

(4) e(t)的标准差为3，信道系数为[1111100.500…0]，得到的MSE曲线分别如图6所示。对比图5和图6，可以看出当噪声干扰增大时，RLS的性能急剧变坏，而AHRLS的性能变化缓慢。这是因为AHRLS采用HRLS的分级结构，其信噪比逐级提高，增强了抗噪能力。所以在干扰噪声增大时，AHRLS仍表现出不错的收敛性能。

图6 e(t)的标准差为3，H=[1111100.500…0]时

所得的MSE曲线

4 结语

在AHRLS算法中，每级(最后一级除外)中最后一个RLS滤波器前面的那些RLS滤波器分别对输入信号的分组进行处理，而最后新加的那个RLS滤波器又利用了信号的整体信息，这样部分和整体相结合使AHRLS算法的性能较好。而且AHRLS算法用于信道估计时，并不像HRLS算法那样只适用于FIR信道非零系数少得情况。虽然子信道的自身系数间的差别太大时，AHRLS的性能变坏，但由于AHRLS对输入信号整体信息的利用，使得其性能较HRLS要好很多。而且由于AHRLS算法采用了HRLS算法的分组分级处理结构，其运算复杂度比RLS算法低，且具有较强的抗噪能力。

参考文献

[1]张玲华,郑宝玉.随机信号处理[M].北京:清华大学出版社,2003.

[2]Simon Haykin.自适应滤波器原理[M].北京:电子工业出版社,2003.

[3]Cioffi J,Kailath T.Fast,Recursive Least Squares Transversal Filters for Adaptive Filtering [J].IEEE Trans.Acoust.Speech,and Signal Processing,1984,32(2):304―337.

[4]Tai Kuo Woo.HRLS:A More Efficient RLS Algorithm for Adaptive FIR Filtering [J].IEEE Communications Letters,2001,5(3):81―84.

[5]Petre Stocia,Monika Agrawal,Per Ahgren.On the Hierarchical Least―Squares Algorithm [J].IEEE Communications Letters,2002,6(4):153―155.

作者简介

柳艾飞 女，1983年出生。主要研究方向为自适应滤波算法和智能天线中的波束形成技术。

金明录 男，1958年出生，教授/博导。主要研究方向为信号处理快速算法；伪随机序列的生成；混合调制编码技术；卫星通信系统的设计和性能分析；非线性失真的线性化技术；超宽带通信系统和网络；ROF(Radio over fiber)技术等。

曲 强 男，1972年出生，大连理工大学在职博士研究生，辽宁科技大学电信学院副教授。主要研究方向为自适应滤波算法和盲信号处理算法。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。