潘子宇，酆广增，孔媛媛（.南京工程学院通信工程学院，南京67；.南京邮电大学通信与信息工程学院，南京0003）

一种改进的批处理常模算法✴

潘子宇1，酆广增2，孔媛媛2
（1.南京工程学院通信工程学院，南京211167；2.南京邮电大学通信与信息工程学院，南京210003）

分析了传统批处理常模算法的缺点，提出了一种新的批处理常模算法——基于共轭梯度方向的批处理常模算法（CG-BPCMA）。新算法采用共轭梯度方向作为下降方向，推导出共轭梯度方向的解析形式。在平坦瑞利衰落信道环境下的MIMO盲均衡系统中的仿真结果表明，新算法有效地克服了SD-BPCMA和NT-BPCMA的缺点，不仅获得了较低的算法复杂度，而且能快速收敛到常模代价函数的最小值点。

MIMO；盲均衡系统；批处理算法；常模算法；共轭梯度

1 引言

常模（CM）算法在盲信道估计、盲多用户检测、盲信源分离等领域有广泛的应用［1］。一般而言，常模算法基于最陡下降算法，算法简单且具有全局收敛性，但收敛速度很慢，从而限制了其在信号处理中的应用。

文献［2］提出了一种最优化方法——批处理常模算法（BPCMA）。作为一种线性搜索迭代算法，BPCMA包含三方面因素，即搜索方向、步长和初始值。基于牛顿方向的BPCMA（NT-BPCMA）有效克服了传统最陡下降算法（SD-BPCMA）收敛慢的缺点，实现了算法的快速收敛，经几步迭代即可收敛到极小值点。然而，牛顿法具有以下几点缺陷［3］：第一，牛顿法并不是全局收敛的；第二，由于信号和信道的随机性，代价函数J（g）的Hessian矩阵▽2J（g）有时候是奇异或病态的。在这种情况下，下降方向将无法确定；第三，牛顿法收敛于鞍点或极大值点的可能性并不小于最小值点；第四，牛顿法需要进行矩阵求逆运算，而这是最优化方法力求避免的问题。

综合考虑到最陡下降法和牛顿法的各种利弊，本文提出了基于共轭梯度法的批处理常模算法，称之为CG-BPCMA。本文研究了新算法的收敛性和复杂度，与SD-BPCMA和NT-BPCMA作了仿真比较。结果表明，本文提出的算法有效地兼顾了算法复杂度、收敛性两方面的矛盾，取得了较好的均衡效果。

2 信号模型和常模估计器

考虑如下的信号模型，其接收信号为

其中，s（n）=［s1（n），…，sK（n）］T是K维的发送信号，每根发送天线发送相同的信号；y（n）是P维的经过信道后的接收天线的接收信号；hk是长度为P的信道矢量；H=［h1，…，hK］则是P×K信道矩阵；w（n）是加性噪声分量。系统模型如图1所示。

为了讨论问题方便起见，我们对信道模型做如下假设。

（1）sk（n）是零均值非高斯的信号，

若sk（n）为复变量，则E｛sk（n=0，说明发送信号为均匀对称。

（3）信道转移矩阵H是满秩矩阵。

其中，J（g）=E｛（｜z（n）｜2-γ）2｝为常模代价函数，γ为输出信号的期望模值。

3 CG-BPCMA算法

本节将给出我们提出的线性搜索批处理常模算法的算法原理。我们知道，线性搜索算法首先确定一个搜索方向，继而以降低代价函数值为目标由本次迭代走向下一步迭代［4］。迭代过程的数学表达式如下：

式中，正参数μ为迭代步长。为了讨论问题简便，本文采用定步长的方法。因此，我们仅需要讨论其余两点因素——搜索方向和初始权值。

3.1 搜索方向

本文中我们将采用共轭梯度方向代替牛顿方向进行迭代。共轭梯度法是共轭方向法的一种，共轭方向法可表示如下［5］：

其中，▽iJ为常模代价函数的梯度，βi-1为修正系数且由下式确定：

在式（5）中，G是代价函数J的Hessian矩阵。在每一步迭代时计算G是比较麻烦的，因此我们必须寻求βi-1不显含G的表达形式。

注意到

由于式（6）中βi-1完全由代价函数的梯度▽J确定，我们称之为共轭梯度法。若βi-1=0，共轭梯度法便退化为最陡下降法（SD-BPCMA），牛顿法（NTBPCMA）的下降方向为pi=-G-1i▽J（gi）。

3.2 初始权值

文献［6］指出，常模估计器的权值在由信道转移矩阵H的列向量张成的信号子空间中。因此，我们可以从信号子空间中提取初始权值g1。信号子空间可以由接收信号的自相关矩阵做特征值分解（ED）得到［7］：

假设ps为一P×K矩阵，其列向量张成信号子空间，初始权值可以简单取为其中的任意一列g1= ps，k，k=1，…，K。文献［2］将矩阵ps的列向量做一线性组合，从而作为初始权值，即˜gk=x1ps，1+x2ps，2+…+xkps，k，其中组合系数xk由下式确定：

求解式（7）中xk的常规方法是做线性搜索。然而，我们注意到代价函数φ（x）=J（˜gk-1+x ps，k）是一个四次多项式：

由于期望运算和求导运算可以交换次序，其一阶导函数为

令φ′（x）=0，我们得到一个三次方程。一般而言，求解三次方程需要用数值分析的方法求解。本文中，我们采用一个比较简单的方法求解x。上述三次方程可转化为如下形式：

［（g+x p）Ty］3·（pTy）=［（g+x p）Ty］·（pTy）（10）注意，方程（10）是方程φ′（x）=0的充分条件而非充分必要条件。注意到（g+x p）Ty和pTy均为非零值，则方程的解为

最终的组合系数x由下式确定：

迭代到第K步时得到˜gK=x1ps，1+x2ps，2+…+xKps，K，这就是我们要确定的初始权值g1。

因此，CG-BPCMA的算法步骤如下：

Step 1：初始化g1、μ，令i=1；

Step 2：计算▽iJ=▽J（gi）；

4 算法复杂度

由于本文算法选取初始权值的方法和文献［2］相似，复杂度相当，我们只需比较选取搜索方向部分的算法复杂度。在共轭梯度算法中，乘法运算的计算量为K2（K为权向量g的维数），其余计算量（如加法运算）均为K的线性函数，因此整个算法的时间复杂度为O（K2）。在牛顿法中，乘法运算的计算量为1／6K3+O（K2），其余运算量同样为K的线性函数，因此整个算法的时间复杂度为O（K3）。相比之下，本文算法使得算法的时间复杂度降低了一个数量级。

5 算法仿真

本节中，我们用数值仿真的手段对新算法的收敛性能做进一步分析。考虑图1所示的系统模型，信源个数K=8，接收天线数P=10，信道采用平坦瑞利衰落信道，且在一帧数据内不变化，发送信号为QPSK信号，一帧数据长N=500，发送信噪比为SNR=20 dB，步长μ=10-8。采用均方误差（MSE）作为衡量算法收敛性能的指标，仿真结果如图2～3所示。考虑信号和信道的随机性，本文采用50次独立运行的平均。

图2 是CG-BPCMA和SD-BPCMA、NT-BPCMA的MSE性能比较图。从图中可以看出NT-BPCMA出现了发散现象，不能收敛到极小值点，这是由于信道的随机选取导致了G-1可能无法计算。若G-1能够计算，算法向收敛方向迭代；反之，算法将走向发散（在这50次独立运行的过程中，NT-BPCMA算法出现了43次发散，仅有7次是收敛的），这是图2中牛顿法曲线怪异的根本原因。但是，我们提出的CG-BPCMA则很好地避免了这一问题。从图2中还可以看出，CG-BPCMA的收敛速度明显高于SD-BPCMA。此外，在仿真过程中，我们还发现，一旦步长因子μ≥10-6，算法将走向发散。

图3是CG-BPCMA的MSE性能图，两条曲线分别对应初始权值随机选取和由子空间分解法得出。从图中可以明显看出，和随机选取初始权值的方法相比，利用子空间分解计算初始权值的方法使得算法收敛速度和稳态性能大大提高。

6 结论

本文分析了传统批处理常模算法的优缺点，针对最陡下降法收敛慢以及牛顿法不能准确收敛的问题，提出了一种基于共轭梯度法的新的批处理常模算法（CG-BPCMA），并将其和传统批处理常模算法做了仿真比较。结果表明，本文提出的新算法不仅能克服传统算法的缺点，且复杂度低，收敛速度较快。因此，CG-BPCMA有效地兼顾了收敛速度和复杂度之间的矛盾。此外，利用子空间分解计算初始权值的方法能够大大提高算法的收敛速度，使得算法收敛“赢在起点上”，但子空间分解也需要消耗相当一部分计算资源，从算法整体收敛所需的CPU绝对时间上看，该方法不比随机选取初始值节省时间。如何进一步降低子空间分解的算法复杂度、实现快速分解将是本批处理常模算法进一步研究的方向之一。

［1］Abrar S，Nandi A K.An Adaptive ConstantModulus Blind E-qualization AlgorithMand Its Stochastic Stability Analysis［J］. IEEE Signal Processing Letters，2010，17（1）：55-58.

［2］Xu Changjiang，Li Jian.A Batch processing ConstantModulus Algorithm［J］.IEEE Communications Letters，2004，8（9）：582-584.

［3］Argyros IK.Newton Method on Lie Groups［J］.Journal of Applied Mathematics and Computing，2009，31（1-2）：217-228.

［4］Wang Jian，WuWei，Zurada JM.Deterministic Convergence of Conjugate Gradient Method for Feedforward Neural Networks［J］.Neurocomputing，2011，74（14）：2368-2376.

［5］Dietl G，Botsch M，Dietrich F A，et al.Robust and reducedrankmatrixWiener filter based on the conjugate gradient algorithm［C］／／Proceedings of 2005 IEEE 6th Workshop on Signal Processing Advances in Wireless Communications.NeWYork：IEEE，2005：555-559.

［6］代松银，袁嗣杰，董书攀.基于子空间分解的信道阶数估计算法［J］.电子学报，2010，38（6）：1245-1248. DAISong-yin，YUAN Si-jie，DONG Shu-pan.Effective Channel Order Estimation Based on Subspace Decomposition［J］.Acta Electronic Sinica，2010，38（6）：1245-1248.（in Chinese）

［7］Dong Enqing，Zhu Caihua，Evans L.Blind Multiuser Detector Based on Reduced Rank Subspace and Least Square Constant Modulus Algorithm［C］／／Proceedings of the 8th International Conference on Signal Processing.Beijing：IEEE，2006：1-7.

PAN Zi-yu was born in Jiangyan，Jiangsu Province，in 1984. He received the M.S.degree froMNanjing University of Posts and Telecommunications in 2008.He is noWa lecturer.His research concernsmobile communications and communication signal processing，information processing technology.

Email：panziyu＠sohu.com，panziyu＠njit.edu.cn

酆广增（1943—），男，江苏无锡人，教授、博士生导师，主要研究方向为数字移动通信与通信信号处理；

FENG Guang-zeng was born in Wuxi，Jiangsu Province，in 1943.He is noWa professor and also the Ph.D.supervisor.His research concerns digital mobile communications and communication signal processing.

Email：gzfeng＠njupt.edu.cn

孔媛媛（1982—），女，山东烟台人，讲师，主要研究方向为移动通信与通信信号处理。

KONG Yuan-yuan was born in Yantai，Shandong Province，in 1982.She is noWa lecturer.Her research concerns digitalmobile communications and communication signal processing.

Email：yyk＠njupt.edu.cn

A Modified Batch Processing Constant Modulus Algorithm

PAN Zi-yu1，FENGGuang-zeng2，KONG Yuan-yuan2
（1.Communication Engineering Institute，Nanjing Institute of Technology，Nanjing 211167，China；2.Communication and Information Engineering Institute，Nanjing University of Posts＆Telecommunications，Nanjing 210003，China）

By analysing the shortages of traditional batch processing algorithm，a neWbatch processing constant modulus algorithMderived by conjugate gradientdirection tominimizing the constantmodulus criterion（CG-BPCMA）is presented.The neWalgorithMuses conjugate gradient direction to choose the search direction and the analytical forMof conjugate gradient direction is deduced.Simulation results shoWthat in flat Rayleigh fading synchronous channelenvironmentblind equalization system，the neWalgorithMovercomes the shortcomings of SDBPCMA and NT-BPCMA effectively，not only has lower complexity，but also can converge to theminima of the constantmodulus criterion quickly.

MIMO；blind equalization system；batch processing algorithm；constantmodulus；conjugate gradient

Youth Fund of Nanjing Institute of Technology（QKJB2010009）

TN911

A

10.3969／j.issn.1001-893x.2012.11.013

潘子宇（1984—），男，江苏姜堰人，2008年于南京邮电大学获工学硕士学位，现为讲师，主要研究方向为移动通信与通信信号处理、信息处理技术等；

1001-893X（2012）11-1774-04

2012-03-27；

2012-05-23

南京工程学院青年基金项目（QKJB2010009）