第31卷第4期2011年4月
文章编号：1001－9081（2011）04－0907－03
计算机应用
JournalofComputerApplicationsVol．31No．4Apr．2011
doi：10．3724/SP．J．1087．2011．00907
基于改进子空间追踪算法的稀疏信道估计
郭
12莹，邱天爽
（1．沈阳工业大学信息科学与工程学院，沈阳110870；2．大连理工大学电子与信息工程学院，大连116024）
(lovelygy2002@yahoo．com．cn)
要：由于许多通信系统的信道具有稀疏多径的特性，因此可以将信道估计问题归结为稀疏信号的恢复问题，
——子空间追踪法（SP）需要对稀疏度有继而应用压缩感知理论（CS）的算法求解。针对CS中现存的信号重构方法—
摘
先验知识的缺点，提出一种改进的子空间追踪法（MSP）。该方法的反馈和精选过程与SP算法一致，不同之处是MSP
算法每次迭代时向备选组合中反馈添加的向量个数是随着迭代次数而逐一增加的，而SP算法中备选组合被添加的向量个数与稀疏度相同。仿真结果表明，基于MSP方法所得到的稀疏多径信道估计结果优于基于传统SP的方法，且无需已知信道的多径个数。
关键词：稀疏信道；压缩感知；子空间追踪；信道估计中图分类号：TN911．7文献标志码：A
Sparsechannelestimationbasedonmodifiedsubspacepursuitalgorithm
GUOYing1，QIUTian-shuang2
(1．SchoolofInformationScienceandEngineering，ShenyangUniversityofIndustry，ShenyangLiaoning110870，China；
2．SchoolofElectronicandInformationEngineering，DalianUniversityofTechnology，DalianLiaoning116023，China)
Abstract:Duetothesparsestructureofchannelsinanumberofcommunicationsystems，thesparsechannelestimationproblemcanbeformulatedasthereconstructionproblemofsparsesignals，andthenbeingsolvedbycertainalgorithminCompressiveSensing(CS)theory．Toavoidneedingpriorknowledgeforsparseness，aModifiedSubspacePursuit(MSP)wasproposed．ThefeedbackandrefiningprocessesofMSParethesameasthoseoftheexistingSubspacePursuit(SP)，thedifferencebetweenthemisthat，inMSP，thenumberofvectorsaddedtothecandidatesetisincreasedonebyone，notequaltothenumberofsparsenessinSPineveryiteration．Thesimulationresultsshowthat，comparedwiththeexistingsubspacepursuitmethod，themaininnovativefeatureoftheproposedalgorithmisthatitdoesnotneedtoassumethesparsenessofchannelbutofferssuperiorestimationresolution．
Keywords:sparsechannel;CompressiveSensing(CS);subspacepursuit;channelestimation
0引言
在高清数字电视系统或水下数字通信系统等许多领域中，由于存在较大的扩展延迟，传输信道往往呈现出稀疏特性，即其时域脉冲响应只在一部分时间上具有较大幅值，而在其他时间都为零或很小。对于这种稀疏多径信道，可以应用
CS）理论将其归结为稀疏信号压缩感知（CompressiveSensing，
［1－2］
。的重构，继而完成信道估计和均衡
［3－4］
压缩感知理论是最近几年出现在信号处理、编码和信息论领域的一种新技术。该理论突破了奈奎斯特采样定理中要求采样速率必须达到信号带宽两倍以上才能准确重构信号的限制，可以根据信号的结构特点以较低的采样速率采样信号，并能有效完成对稀疏信号的重构，从而降低系统对采样
数据存贮和传输能力的要求，节省了资源，提高了效率。器件、
CS理论的本质就是高维稀疏信号可以通过线概括地说，
然后通过优化算法以高概率完性映射投影到一个低维空间，
成对原信号的重构。实际上，很多变换如Fourier变换、离散
DCT）、余弦变换（DiscreteCosineTransform，小波变换都可以
理解为信号的重构表示，但是这些变换中的信号变换域维数
即这些重构表示是唯一的，而CS理论中都等于原信号维数，
的信号变换域维数大于信号维数，且对线性映射矩阵中的向量没有正交性要求。
目前，在CS理论框架下的众多信号重构算法中，贪婪算
快速的特点而倍受关注。典型的一类贪婪法以其计算简单、
MP）［5］及其衍生算法，算法是匹配追踪（MatchPursuit，如［6］
OMP（OrthogonalMatchPursuit）等，其中的MP和OMP已被
每用于实现稀疏信道估计。这类算法是一个逐次迭代过程，
次迭代都要找到与信号最相关的元素，然后消除该元素对原
它们的缺点之一是至今仍没有得到理论支持。信号的影响，
2007年Dai等人提出一种特殊的贪婪算法———子空间追踪算
［7］SP），该算法不仅具有与MP算法类似法（SubspacePursuit，
的计算简便性，而且从理论上得到了对信号重构有效性的证明。但是无论是MP算法还是SP算法都需要预先知道信号的稀疏度，对应到稀疏信道估计问题就是要求已知信道的多径个数。本文针对二者的这个缺点，提出一种无需预知稀疏度的子空间追踪算法，称之为改进的子空间追踪法（ModifiedSubspacePursuit，MSP），并将其应用到稀疏信道估计问题中。仿真结果表明基于MSP的信道估计精度高于基于SP法的估
且不要求任何先验知识。计结果，
1
1．1
问题及方法描述
问题模型
一种典型的稀疏信道（高清数字电视系统信道）如图1［8］
所示。假设在一定时间内信道脉冲响应是不变的，则其可
收稿日期：2010－10－08；修回日期：2011－02－24。基金项目：国家自然科学基金资助项目（[1**********]）。
作者简介：郭莹（1975－），女，辽宁铁岭人，讲师，博士，主要研究方向：非高斯信号处理、参数估计；邱天爽（1954－），男，江苏海门人，教授，博士生导师，主要研究方向：数字信号处理、生物医学信号处理、非平稳与非高斯信号处理。
908描述为：
h（t）=
计算机应用第31卷
∑ag（t－τ）
k
k
k=0
K－1
（1）
（8）这样的欠定方程，一般是没有确定解的，但是由于信号的稀疏特性，只要找到Θ中非零元素的位置，即可得到确定解。CS理论已经证明，只要观测矩阵Φ与字典ψ是不相干的，那么信号x可以以很高的概率从y中恢复。采用何种技术实现由观测向量y对稀疏信号x的重构，是CS理论研究的一个重要方面。子空间追踪是其中的一种贪婪算法，其核心是通过贪婪策略，逐步寻找稀疏信号中的非零元素。为介绍SP法的主要步骤，这里首先介绍矩阵的截断、投影向量和残差向量。1）截断。设矩阵Φ∈RM×N、I｛1，2，…，N｝，则矩阵ΦI被称为矩阵Φ的截断，表示其列向量标号i∈I，由ΦI的列向量扩展成空间记为span（ΦI）。
2）投影向量。设y∈R，ΦI∈R
M
M×I
其中：ak和τk分别表示第k条路径的幅度和延时；g（t）表示
脉冲成型函数（包括传输和接收滤波器），这里使用sinc函数。将式（1）写成矩阵形式为：
h=G（τ）a
T
T
（2）
…，a=［a0，a1，…，aK－1］，G（d）是其中：τ=［τ0，τ1，τK－1］，
M×K的矩阵，其每一列是包含延迟的sinc函数：
G（τ）=［g（τ0），g（τ1），…，g（τK－1）］
（3）
T
sinc（－τk），sinc（1－τk），…，sinc（M－τk）］。其中g（τk）=［
则信道输出为：
y（n）=hs（n）+w（n）
T
（4）
（|I|表示集合I的大
T
s（n），s（n－1），…，s（n－L）］其中：s（n）=［表示训练数据
w（n）表示与输入数据独立同分布的高斯噪声。将式向量，
（4）写成矩阵形式：
H
小），并设ΦIΦI是可逆的，则y在span（ΦI）的投影向量定义为：
H
yp=proj（y，ΦI）ΦIΦIy
H*－1*
其中：ΦI（ΦIΦI）ΦI，上标H表示共轭。
3）残差向量。投影的残差向量定义为：
（9）
y=Sh+W（5）
W是噪声向量。我们的目式中：S是L×M的已知信号矩阵，
的就是通过观测向量y和已知的训练数据矩阵S，得到权向在式（5）中，因为信道向量h是稀疏的，所量即信道向量h。
以该问题可以理解为由带噪的观测信号完成对稀疏信号的重
从而可以应用CS理论和方法进行求解
。构，
yr=resid（y，ΦI）y－yp
由上面的定义很容易得到关于残差向量的重要定理
———正交性定理。
定理
M
正交性定理。对于任意向量y∈R，若ΦI∈
RM×|I|是列满秩的，则yr=resid（y，ΦI）满足：
*
ΦIyr=0
（10）
－1
*
ΦIy］=
证明**
y－ΦI（Φ*ΦIyr=ΦI［IΦI）
**
ΦIy－ΦIy=0证毕。
CS理论中，信号重构的最大问题就是找到一个由Φ中
不多于K个列向量组成的子空间，然后就可以通过计算伪逆得到不为零的信号系数。子空间追踪算法的目标就是直接寻找这个子空间，它与序列编码理论中的反馈追踪思想类似。在解码时，备选集合中的码字由本次选的K个列向量和上次然后根从Φ中选择的K个列向量组成最可靠的2K个码字，
舍弃一半，只留下K个，成为最终所选集合。此据优选准则，
用最终从备选集合中选取到迭代过程一直执行到满意为止，
的K个列向量组成的集合完成信号重构。在这个过程中，备
另一选集合由两部分组成：一部分是上次选择的K个列向量，部分是本次从Φ中重新选出的K个列向量。优选准则是：在
每次迭代时，本次残差向量与Φ中的这K个列向量内积最大，第一次迭代时，残差向量设为观测向量y。而最终所选集合的选择准则是：在备选的伪逆与观测向量y的乘积中选择最大的K个列向量。该算法的优选步骤如图2所示
。
图1典型的高清数字电视系统信道
1．2子空间追踪算法及其改进算法
由于绝大多数信号都可以在通过某种变换成为某个变换域的稀疏信号，因此近年迅速崛起的压缩感知理论成为研究该类信号的一个热门工具。该理论的研究内容是如下欠定方程的求解问题：
y=Φx
（6）
NM
其中：x∈Q，是N维未知向量；y∈Q表示M维向量，被称为
大小为M×N（M＜观测向量；Φ被称为观测（编码）矩阵，
N）。若x是稀疏的，则只需在一个维数大于信号维数的集合（称之为冗余字典，…ψP］中，其元素称为原子）ψ=［ψ1，ψ2，找到对原信号最佳的线性表示组合，即：
x=从而：
∑θ
i=1
K
li
ψli=ψΘ
（7）（8）
图2
子空间追踪法的优选步骤
y=ΦψΘ
这里的Θ称为系数向量，在式（7）中，之所以用下标li而不是i，是因为这表示在字典ψ中用来表示x的原子，并不一定是…，按顺序连续（如［ψ1，ψ2，ψK］）选择的，Θ的每个元素θli表示原子ψli对信号x的作用大小。信号重构的目的就是在给定y的情况下，由式（3）求得系数向量Θ。对于式（6）和式
SP算法最大的特点是：1）K个列向量是由此可以看到，
而此备选集合与本次选从列向量个数为2K的备选中选出的，
择和上次选择均有关联；2）每次迭代的备选集合、备选子集
K和K。因此，合和终选集合的大小是固定的，分别为2K、该算法需要稀疏度K作为先验知识。
1信号为说明SP算法对先验知识的依赖性，对稀疏的0-（即信号x是0-1序列，在维数为N的x中有K个为1的值，其余均为0，但具体的这K个非零值的位置是随机均匀地分
0，N］的）应用SP法进行重构。仿真过程中，取M=布在［
150，N=500，K≤M/2，观测矩阵Φ是标准的随机高斯矩阵，对于每一个K，实验重复次数为300。真正的稀疏度是K=3。图3所示为在不同信噪比条件下，稀疏度的已知与否对SP算法的重构信号能力的影响。以均方根误差（RootMeanSquaredError，RMSE）作为性能衡量参数，RMSE=
由于本算法所选列向量是逐次递加的，在算法复杂致。因此，
度上必定高于SP算法。
2仿真实验结果
在计算机仿真实验中，分别考查了基于SP方法和基于本
文提出的MSP方法的稀疏信道估计性能及其对应的系统接假设接收端已完成较好的时收端的符号检测能力。仿真中，
间和相位同步，训练数据为长度为50的QPSK基带信号，信信道采样长度为100，其参数为：道为图1所示的稀疏信道，
a=［0．1+0．1j，0．2，1；0．08－0．17j，0．15－0．2j，－0.16+
TT
0.19j］，4．11，16．39，28，60．71，90．95，91．71］，即多径τ=［
1^‖2，Q为仿真次数
。‖x－x
Q∑q=1
个数为6（对应为稀疏度）。以RMSE和接收端符号错误率（SymbolErrorRate，SER）性能作为性能衡量标准，仿真次数为300。由图5的RMSE曲线和图6的SER曲线可以看到，SP算法估计结果的精度略当准确已知稀疏度即多径个数时，
SP算法的低于本文的MSP方法；而当过分估计多径个数时，
9］性能远低于MSP法。且本文算法的估计精度高于文献［提10］提出的自出的基于匹配追踪（MP）的信道估计法和文献［LMS）的信道估计法
。适应匹配追踪（MP-图3
SP法中稀疏度先验知识对估计结果的影响
SP算法估由图3可见，当对稀疏度没有准确的估计时，计结果的性能将大大降低。因此，寻求无需稀疏度作为先验知识的方法也是必要的。本文提出一种改进的自适应SP算称之为MSP（ModifiedSP）算法，该方法无需预先设定稀疏法，度K，其迭代过程如下所示。
1）输入观测信号y，观测矩阵Φ。2）初始化。
所选列向量个数T=1；
F0=｛f：在Φ中，对每个列向量Φj（j=1：N）求使
图5
信道估计性能比较
|ΦHjy|
i=1。
最大的T个列向量对应标号｝；
e0=y－ΦF0ΦHF0y；
3）确定备选集合C。P=｛p：在Φ中，对每个列向量Φj（j=1：N）求使
|ΦHjei+1|T最大的T个列向量对应标号｝；
C=Fi－1∪P。4）更新。
Fi=｛f：在ΦC中，对每个列向量Φj（j=1：2K）求使
|ΦHjy|最大的T个列向量对应标号｝。
新的残差：
ei=y－ΦFiΦHFiyFi－1=Fii=i+1T=T+1
停止条件：‖ei‖2≤‖ei－1‖2。
^=ΦH5）输出：xFy。
i
图6符号率性能比较
3结语
CS理论是最近几年刚刚兴起的一门新的理论和技术，它
解放了原来奈奎斯特定理对采样率的要求，可有效节省成本和传输效率，在图像、编码和医学等众多领域都有广泛的应用前景。本文首先介绍了一种完成信号重构的子空间追踪算法，接着考虑它需要对稀疏度有先验知识这一缺陷，提出了一——MSP，种无需预知稀疏度的改进子空间追踪法—并将其应基于该算法的信道用于稀疏信道估计问题。仿真结果表明，
估计结果优于基于原来的子空间追踪算法和已有的信道估计方法的估计结果，且无需先验知识。
（下转第995页）
SP算法与MSP算法在迭代过程中的不同之处在于，MSP算法在每次迭代反馈、扩大备选组合时是逐次地增加一个所选向量，而不像SP算法那样每次都向备选集合增加与稀疏度相同的K个向量。当T=K，本算法的过程与SP算法完全一
^，^，^）。RV协议，然后输出伪造签名（U
当签名者发现有敌手伪造自己的签名时，提出仲裁请求。通过知识证明向仲裁者说明自己的部分私钥S2的确是PKG
G2上的乘法运上的指数运算次之，然后是G1上的点乘运算，算和G1上的加法运算，其他运算和这五种运算相比起来可以忽略不计，因此以这五种运算来考虑三种方案的计算效率。
Ex表示一次G2上的指数运假设Pa表示一次双线性对运算，
算，Mu表示一次G1上的点乘运算，M表示G2上的乘法运（）表示预运算。由于在算，Ad表示一次G1上的点加运算，
c）和签名者公钥的条件下，e（Q2，Qpub），e（Q2+已知消息（m，
FENG方案以及H3（c），Q1）可以实行预计算。本文方案、Chow方案的效率和性能对比如表1所示。可见，通过有效地
利用预计算，本文的方案减少了最复杂的双线性对运算，达到比其他两个方案在整体性能上了最少的双线性对运算：1次，有较大的优势，适合在需要频繁传递和验证签名的电子商务和电子政务领域使用。
所颁发的，过程如下：
3）仲裁者先验证签名者是否是身份信息ID的所有者，若
*
是，仲裁者选择一个随机数a∈zq，计算aP发送给签名者。
4）签名者计算e（S2，aP）发送给仲裁者。
5）仲裁者验证e（S2，aP）=e（Q2，Qpub）是否成立，若成
^与Q是否相同，若不同，说明PKG立，比较伪造签名中的Q22
是不诚实的，伪造了签名者的自选私钥和公钥。5．2效率分析
由于在所有的运算中双线性对运算是最耗时的，据统计，
［11］
G2一次双线对运算大约相当于有限域上的8个模幂运算，
表1
方案Chow方案FENG方案本文方案
签名(用户)4Mu+3Ad(2Mu)3Mu+1Ad(1Mu)2Ex+1M+1Mu(1Pa)
a
三个类似方案的比较
验证
3Pa+1M+1Ad(1Mu)3Pa+1M+1Ad(1Mu)1Pa+1Ex(1Pa)
［4］［5］
密钥托管
是否否
安全性安全不安全安全
签名(签名者)2Mu+1Ad(2Mu)2Mu+1Ad(1Mu)1Ex+2Mu(1Pa)
6结语
成林，亢宝元，王国瞻．一种部分盲签名方案［J］．计算机工程，
2010，36(8):163－164．
SHAMIRA．Identitybasedcryptosystemsandsignatureschemes［C］//CRYPTO'84:AdvancesinCryptology．Berlin:Springer-Verlag，1984:47－53．
本文先分析了FENG方案的安全性缺陷，给出了具体的伪造签名方法。为了克服FENG方案的缺陷，提出一个新的
在随机预言模型下和高效的无可信PKG的部分盲签名方案，
CDHP困难的假设下，新方案被证明能够抵抗三种类型敌手
因此方案是安全的。通过有效地利用预的存在性伪造攻击，
计算，新方案总共只需要1个双线性对运算，比FENG方案和Chow方案都减少了2个双线性对运算，在计算效率方面具有较大的优势，整体性能较高，具有一定的实用性。参考文献：
［1］
CHAUMD．Blindsignaturesforuntraceablepayments［C］//CRYP-TO'82:AdvancesinCryptology．Berlin:Springer-Verlag，1983:199－203．［2］
ABEM，FUJISAKIE．Howtodateblindsignatures［C］//ASIA-CRYPTO'96:AdvancesinCryptology．Berlin:Springer-Verlag，1996:244－251．［3］
ABEM，OKAMOTOT．Provablysecurepartiallyblindsignatures［C］//CRYPTO2000:AdvancesinCryptology．Berlin:Springer-Verlag，2000:271－286．
［6］CHOWS，HUIL，YIUS．Twoimprovedpartiallyblindsignatureschemesfrombilinearpairings［C］//ASIACRYPTO2005:Ad-vancesinCryptology．Berlin:Springer-Verlag，2005:316－328．
［7］CHENX，ZHANGF，LIUS．ID-basedrestrictivepartiallyblindsignaturesandapplications［J］．JournalofSystemandSoftware，2007，80(2):164－171
［8］［9］
崔巍，辛阳，胡程瑜等．高效的基于身份的(受限)部分盲签名［J］．北京邮电大学学报，2008，31(4):53－57．
冯涛，彭伟，马建峰．安全的无可信PKG的部分盲签名方案［J］．通信学报，2010，31(1):128－133．
的安全性证明［J］．软件学报，2007，18(4):1007－1014．
［10］顾纯祥，祝跃飞，潘晓豫．Forking引理与一类基于身份签名体制［11］KAWAHARAY，TAKAGIT，OKAMOTOE．Efficientimplementa-tionofTatepairingonamobilephoneusingJava［C］//CIS'2006:2006InternationalConferenceonComputationalIntelligenceandSe-curity，LNCS4456．Berlin:Springer-Verlag，2007:396－405．
（上接第909页）参考文献：
［1］
COTTERSF，RAOBD．Theadaptivematchingpursuitalgorithmforestimationandequalizationofsparsetime-varyingchannels［C］//Thirty-FourthAsilomarConferenceonSignals，SystemsandComput-ers．Washington，DC:IEEE，2000:1772－1776．［2］
KARABULUTGZ，YONGACOGLUA．Estimationoftime-varyingchannelswithorthogonalmatchingpursuitalgorithm［C］//2005IEEESymposiumonAdvancesinWiredandWirelessCommunica-tion．Washington，DC:IEEE，2005:141－144．［3］［4］［5］
DONOHOD．Compressedsensing［J］．IEEETransactionsonInfor-mationTheory，2006，4(52):1289－1306．
BARANIUKR．Alectureoncompressivesensing［J］．IEEESignalProcessingMagazine，2007，24(4):118－121．
MALLATS，ZHANGZ．Matchingpursuitswithtime-frequencydic-tionaries［J］．IEEETransactionsonSignalProcessing，1993，12
［9］［8］［7］［6］
(41):3397－3415．
TROPPJA，GILBERTAC．Signalrecoveryfrompartialinforma-tionbyorthogonalmatchingpursuit［EB/OL］．［2010－09－16］．http://www．
personal．
umich．
edu/-jtropp/papers/
TG052SignalRecovery．Pdf．
DAIW，MILENKOVICO．Subspacepursuitforcompressivesensingsignalreconstruction［J］．IEEETransactionsonInformationTheory，2009，55(5):2230－2249．
GHOSHM．Blinddecisionfeedbackequalizationforterrestrialtele-visionreceivers［J］．IEEESignalProceeding，1998，86(10):2070－2081．
朱行涛，刘郁林，赵翔，等．MIMO_OFDM系统中稀疏信道估计算法研究［J］．云南大学学报，2007，29(6):574－578．
［10］胡健，张延华，周作成．一种改进的稀疏信道估计算法［J］．通信
技术，2009，42(7):31－33．
第31卷第4期2011年4月
文章编号：1001－9081（2011）04－0907－03
计算机应用
JournalofComputerApplicationsVol．31No．4Apr．2011
doi：10．3724/SP．J．1087．2011．00907
基于改进子空间追踪算法的稀疏信道估计
郭
12莹，邱天爽
（1．沈阳工业大学信息科学与工程学院，沈阳110870；2．大连理工大学电子与信息工程学院，大连116024）
(lovelygy2002@yahoo．com．cn)
要：由于许多通信系统的信道具有稀疏多径的特性，因此可以将信道估计问题归结为稀疏信号的恢复问题，
——子空间追踪法（SP）需要对稀疏度有继而应用压缩感知理论（CS）的算法求解。针对CS中现存的信号重构方法—
摘
先验知识的缺点，提出一种改进的子空间追踪法（MSP）。该方法的反馈和精选过程与SP算法一致，不同之处是MSP
算法每次迭代时向备选组合中反馈添加的向量个数是随着迭代次数而逐一增加的，而SP算法中备选组合被添加的向量个数与稀疏度相同。仿真结果表明，基于MSP方法所得到的稀疏多径信道估计结果优于基于传统SP的方法，且无需已知信道的多径个数。
关键词：稀疏信道；压缩感知；子空间追踪；信道估计中图分类号：TN911．7文献标志码：A
Sparsechannelestimationbasedonmodifiedsubspacepursuitalgorithm
GUOYing1，QIUTian-shuang2
(1．SchoolofInformationScienceandEngineering，ShenyangUniversityofIndustry，ShenyangLiaoning110870，China；
2．SchoolofElectronicandInformationEngineering，DalianUniversityofTechnology，DalianLiaoning116023，China)
Abstract:Duetothesparsestructureofchannelsinanumberofcommunicationsystems，thesparsechannelestimationproblemcanbeformulatedasthereconstructionproblemofsparsesignals，andthenbeingsolvedbycertainalgorithminCompressiveSensing(CS)theory．Toavoidneedingpriorknowledgeforsparseness，aModifiedSubspacePursuit(MSP)wasproposed．ThefeedbackandrefiningprocessesofMSParethesameasthoseoftheexistingSubspacePursuit(SP)，thedifferencebetweenthemisthat，inMSP，thenumberofvectorsaddedtothecandidatesetisincreasedonebyone，notequaltothenumberofsparsenessinSPineveryiteration．Thesimulationresultsshowthat，comparedwiththeexistingsubspacepursuitmethod，themaininnovativefeatureoftheproposedalgorithmisthatitdoesnotneedtoassumethesparsenessofchannelbutofferssuperiorestimationresolution．
Keywords:sparsechannel;CompressiveSensing(CS);subspacepursuit;channelestimation
0引言
在高清数字电视系统或水下数字通信系统等许多领域中，由于存在较大的扩展延迟，传输信道往往呈现出稀疏特性，即其时域脉冲响应只在一部分时间上具有较大幅值，而在其他时间都为零或很小。对于这种稀疏多径信道，可以应用
CS）理论将其归结为稀疏信号压缩感知（CompressiveSensing，
［1－2］
。的重构，继而完成信道估计和均衡
［3－4］
压缩感知理论是最近几年出现在信号处理、编码和信息论领域的一种新技术。该理论突破了奈奎斯特采样定理中要求采样速率必须达到信号带宽两倍以上才能准确重构信号的限制，可以根据信号的结构特点以较低的采样速率采样信号，并能有效完成对稀疏信号的重构，从而降低系统对采样
数据存贮和传输能力的要求，节省了资源，提高了效率。器件、
CS理论的本质就是高维稀疏信号可以通过线概括地说，
然后通过优化算法以高概率完性映射投影到一个低维空间，
成对原信号的重构。实际上，很多变换如Fourier变换、离散
DCT）、余弦变换（DiscreteCosineTransform，小波变换都可以
理解为信号的重构表示，但是这些变换中的信号变换域维数
即这些重构表示是唯一的，而CS理论中都等于原信号维数，
的信号变换域维数大于信号维数，且对线性映射矩阵中的向量没有正交性要求。
目前，在CS理论框架下的众多信号重构算法中，贪婪算
快速的特点而倍受关注。典型的一类贪婪法以其计算简单、
MP）［5］及其衍生算法，算法是匹配追踪（MatchPursuit，如［6］
OMP（OrthogonalMatchPursuit）等，其中的MP和OMP已被
每用于实现稀疏信道估计。这类算法是一个逐次迭代过程，
次迭代都要找到与信号最相关的元素，然后消除该元素对原
它们的缺点之一是至今仍没有得到理论支持。信号的影响，
2007年Dai等人提出一种特殊的贪婪算法———子空间追踪算
［7］SP），该算法不仅具有与MP算法类似法（SubspacePursuit，
的计算简便性，而且从理论上得到了对信号重构有效性的证明。但是无论是MP算法还是SP算法都需要预先知道信号的稀疏度，对应到稀疏信道估计问题就是要求已知信道的多径个数。本文针对二者的这个缺点，提出一种无需预知稀疏度的子空间追踪算法，称之为改进的子空间追踪法（ModifiedSubspacePursuit，MSP），并将其应用到稀疏信道估计问题中。仿真结果表明基于MSP的信道估计精度高于基于SP法的估
且不要求任何先验知识。计结果，
1
1．1
问题及方法描述
问题模型
一种典型的稀疏信道（高清数字电视系统信道）如图1［8］
所示。假设在一定时间内信道脉冲响应是不变的，则其可
收稿日期：2010－10－08；修回日期：2011－02－24。基金项目：国家自然科学基金资助项目（[1**********]）。
作者简介：郭莹（1975－），女，辽宁铁岭人，讲师，博士，主要研究方向：非高斯信号处理、参数估计；邱天爽（1954－），男，江苏海门人，教授，博士生导师，主要研究方向：数字信号处理、生物医学信号处理、非平稳与非高斯信号处理。
908描述为：
h（t）=
计算机应用第31卷
∑ag（t－τ）
k
k
k=0
K－1
（1）
（8）这样的欠定方程，一般是没有确定解的，但是由于信号的稀疏特性，只要找到Θ中非零元素的位置，即可得到确定解。CS理论已经证明，只要观测矩阵Φ与字典ψ是不相干的，那么信号x可以以很高的概率从y中恢复。采用何种技术实现由观测向量y对稀疏信号x的重构，是CS理论研究的一个重要方面。子空间追踪是其中的一种贪婪算法，其核心是通过贪婪策略，逐步寻找稀疏信号中的非零元素。为介绍SP法的主要步骤，这里首先介绍矩阵的截断、投影向量和残差向量。1）截断。设矩阵Φ∈RM×N、I｛1，2，…，N｝，则矩阵ΦI被称为矩阵Φ的截断，表示其列向量标号i∈I，由ΦI的列向量扩展成空间记为span（ΦI）。
2）投影向量。设y∈R，ΦI∈R
M
M×I
其中：ak和τk分别表示第k条路径的幅度和延时；g（t）表示
脉冲成型函数（包括传输和接收滤波器），这里使用sinc函数。将式（1）写成矩阵形式为：
h=G（τ）a
T
T
（2）
…，a=［a0，a1，…，aK－1］，G（d）是其中：τ=［τ0，τ1，τK－1］，
M×K的矩阵，其每一列是包含延迟的sinc函数：
G（τ）=［g（τ0），g（τ1），…，g（τK－1）］
（3）
T
sinc（－τk），sinc（1－τk），…，sinc（M－τk）］。其中g（τk）=［
则信道输出为：
y（n）=hs（n）+w（n）
T
（4）
（|I|表示集合I的大
T
s（n），s（n－1），…，s（n－L）］其中：s（n）=［表示训练数据
w（n）表示与输入数据独立同分布的高斯噪声。将式向量，
（4）写成矩阵形式：
H
小），并设ΦIΦI是可逆的，则y在span（ΦI）的投影向量定义为：
H
yp=proj（y，ΦI）ΦIΦIy
H*－1*
其中：ΦI（ΦIΦI）ΦI，上标H表示共轭。
3）残差向量。投影的残差向量定义为：
（9）
y=Sh+W（5）
W是噪声向量。我们的目式中：S是L×M的已知信号矩阵，
的就是通过观测向量y和已知的训练数据矩阵S，得到权向在式（5）中，因为信道向量h是稀疏的，所量即信道向量h。
以该问题可以理解为由带噪的观测信号完成对稀疏信号的重
从而可以应用CS理论和方法进行求解
。构，
yr=resid（y，ΦI）y－yp
由上面的定义很容易得到关于残差向量的重要定理
———正交性定理。
定理
M
正交性定理。对于任意向量y∈R，若ΦI∈
RM×|I|是列满秩的，则yr=resid（y，ΦI）满足：
*
ΦIyr=0
（10）
－1
*
ΦIy］=
证明**
y－ΦI（Φ*ΦIyr=ΦI［IΦI）
**
ΦIy－ΦIy=0证毕。
CS理论中，信号重构的最大问题就是找到一个由Φ中
不多于K个列向量组成的子空间，然后就可以通过计算伪逆得到不为零的信号系数。子空间追踪算法的目标就是直接寻找这个子空间，它与序列编码理论中的反馈追踪思想类似。在解码时，备选集合中的码字由本次选的K个列向量和上次然后根从Φ中选择的K个列向量组成最可靠的2K个码字，
舍弃一半，只留下K个，成为最终所选集合。此据优选准则，
用最终从备选集合中选取到迭代过程一直执行到满意为止，
的K个列向量组成的集合完成信号重构。在这个过程中，备
另一选集合由两部分组成：一部分是上次选择的K个列向量，部分是本次从Φ中重新选出的K个列向量。优选准则是：在
每次迭代时，本次残差向量与Φ中的这K个列向量内积最大，第一次迭代时，残差向量设为观测向量y。而最终所选集合的选择准则是：在备选的伪逆与观测向量y的乘积中选择最大的K个列向量。该算法的优选步骤如图2所示
。
图1典型的高清数字电视系统信道
1．2子空间追踪算法及其改进算法
由于绝大多数信号都可以在通过某种变换成为某个变换域的稀疏信号，因此近年迅速崛起的压缩感知理论成为研究该类信号的一个热门工具。该理论的研究内容是如下欠定方程的求解问题：
y=Φx
（6）
NM
其中：x∈Q，是N维未知向量；y∈Q表示M维向量，被称为
大小为M×N（M＜观测向量；Φ被称为观测（编码）矩阵，
N）。若x是稀疏的，则只需在一个维数大于信号维数的集合（称之为冗余字典，…ψP］中，其元素称为原子）ψ=［ψ1，ψ2，找到对原信号最佳的线性表示组合，即：
x=从而：
∑θ
i=1
K
li
ψli=ψΘ
（7）（8）
图2
子空间追踪法的优选步骤
y=ΦψΘ
这里的Θ称为系数向量，在式（7）中，之所以用下标li而不是i，是因为这表示在字典ψ中用来表示x的原子，并不一定是…，按顺序连续（如［ψ1，ψ2，ψK］）选择的，Θ的每个元素θli表示原子ψli对信号x的作用大小。信号重构的目的就是在给定y的情况下，由式（3）求得系数向量Θ。对于式（6）和式
SP算法最大的特点是：1）K个列向量是由此可以看到，
而此备选集合与本次选从列向量个数为2K的备选中选出的，
择和上次选择均有关联；2）每次迭代的备选集合、备选子集
K和K。因此，合和终选集合的大小是固定的，分别为2K、该算法需要稀疏度K作为先验知识。
1信号为说明SP算法对先验知识的依赖性，对稀疏的0-（即信号x是0-1序列，在维数为N的x中有K个为1的值，其余均为0，但具体的这K个非零值的位置是随机均匀地分
0，N］的）应用SP法进行重构。仿真过程中，取M=布在［
150，N=500，K≤M/2，观测矩阵Φ是标准的随机高斯矩阵，对于每一个K，实验重复次数为300。真正的稀疏度是K=3。图3所示为在不同信噪比条件下，稀疏度的已知与否对SP算法的重构信号能力的影响。以均方根误差（RootMeanSquaredError，RMSE）作为性能衡量参数，RMSE=
由于本算法所选列向量是逐次递加的，在算法复杂致。因此，
度上必定高于SP算法。
2仿真实验结果
在计算机仿真实验中，分别考查了基于SP方法和基于本
文提出的MSP方法的稀疏信道估计性能及其对应的系统接假设接收端已完成较好的时收端的符号检测能力。仿真中，
间和相位同步，训练数据为长度为50的QPSK基带信号，信信道采样长度为100，其参数为：道为图1所示的稀疏信道，
a=［0．1+0．1j，0．2，1；0．08－0．17j，0．15－0．2j，－0.16+
TT
0.19j］，4．11，16．39，28，60．71，90．95，91．71］，即多径τ=［
1^‖2，Q为仿真次数
。‖x－x
Q∑q=1
个数为6（对应为稀疏度）。以RMSE和接收端符号错误率（SymbolErrorRate，SER）性能作为性能衡量标准，仿真次数为300。由图5的RMSE曲线和图6的SER曲线可以看到，SP算法估计结果的精度略当准确已知稀疏度即多径个数时，
SP算法的低于本文的MSP方法；而当过分估计多径个数时，
9］性能远低于MSP法。且本文算法的估计精度高于文献［提10］提出的自出的基于匹配追踪（MP）的信道估计法和文献［LMS）的信道估计法
。适应匹配追踪（MP-图3
SP法中稀疏度先验知识对估计结果的影响
SP算法估由图3可见，当对稀疏度没有准确的估计时，计结果的性能将大大降低。因此，寻求无需稀疏度作为先验知识的方法也是必要的。本文提出一种改进的自适应SP算称之为MSP（ModifiedSP）算法，该方法无需预先设定稀疏法，度K，其迭代过程如下所示。
1）输入观测信号y，观测矩阵Φ。2）初始化。
所选列向量个数T=1；
F0=｛f：在Φ中，对每个列向量Φj（j=1：N）求使
图5
信道估计性能比较
|ΦHjy|
i=1。
最大的T个列向量对应标号｝；
e0=y－ΦF0ΦHF0y；
3）确定备选集合C。P=｛p：在Φ中，对每个列向量Φj（j=1：N）求使
|ΦHjei+1|T最大的T个列向量对应标号｝；
C=Fi－1∪P。4）更新。
Fi=｛f：在ΦC中，对每个列向量Φj（j=1：2K）求使
|ΦHjy|最大的T个列向量对应标号｝。
新的残差：
ei=y－ΦFiΦHFiyFi－1=Fii=i+1T=T+1
停止条件：‖ei‖2≤‖ei－1‖2。
^=ΦH5）输出：xFy。
i
图6符号率性能比较
3结语
CS理论是最近几年刚刚兴起的一门新的理论和技术，它
解放了原来奈奎斯特定理对采样率的要求，可有效节省成本和传输效率，在图像、编码和医学等众多领域都有广泛的应用前景。本文首先介绍了一种完成信号重构的子空间追踪算法，接着考虑它需要对稀疏度有先验知识这一缺陷，提出了一——MSP，种无需预知稀疏度的改进子空间追踪法—并将其应基于该算法的信道用于稀疏信道估计问题。仿真结果表明，
估计结果优于基于原来的子空间追踪算法和已有的信道估计方法的估计结果，且无需先验知识。
（下转第995页）
SP算法与MSP算法在迭代过程中的不同之处在于，MSP算法在每次迭代反馈、扩大备选组合时是逐次地增加一个所选向量，而不像SP算法那样每次都向备选集合增加与稀疏度相同的K个向量。当T=K，本算法的过程与SP算法完全一
^，^，^）。RV协议，然后输出伪造签名（U
当签名者发现有敌手伪造自己的签名时，提出仲裁请求。通过知识证明向仲裁者说明自己的部分私钥S2的确是PKG
G2上的乘法运上的指数运算次之，然后是G1上的点乘运算，算和G1上的加法运算，其他运算和这五种运算相比起来可以忽略不计，因此以这五种运算来考虑三种方案的计算效率。
Ex表示一次G2上的指数运假设Pa表示一次双线性对运算，
算，Mu表示一次G1上的点乘运算，M表示G2上的乘法运（）表示预运算。由于在算，Ad表示一次G1上的点加运算，
c）和签名者公钥的条件下，e（Q2，Qpub），e（Q2+已知消息（m，
FENG方案以及H3（c），Q1）可以实行预计算。本文方案、Chow方案的效率和性能对比如表1所示。可见，通过有效地
利用预计算，本文的方案减少了最复杂的双线性对运算，达到比其他两个方案在整体性能上了最少的双线性对运算：1次，有较大的优势，适合在需要频繁传递和验证签名的电子商务和电子政务领域使用。
所颁发的，过程如下：
3）仲裁者先验证签名者是否是身份信息ID的所有者，若
*
是，仲裁者选择一个随机数a∈zq，计算aP发送给签名者。
4）签名者计算e（S2，aP）发送给仲裁者。
5）仲裁者验证e（S2，aP）=e（Q2，Qpub）是否成立，若成
^与Q是否相同，若不同，说明PKG立，比较伪造签名中的Q22
是不诚实的，伪造了签名者的自选私钥和公钥。5．2效率分析
由于在所有的运算中双线性对运算是最耗时的，据统计，
［11］
G2一次双线对运算大约相当于有限域上的8个模幂运算，
表1
方案Chow方案FENG方案本文方案
签名(用户)4Mu+3Ad(2Mu)3Mu+1Ad(1Mu)2Ex+1M+1Mu(1Pa)
a
三个类似方案的比较
验证
3Pa+1M+1Ad(1Mu)3Pa+1M+1Ad(1Mu)1Pa+1Ex(1Pa)
［4］［5］
密钥托管
是否否
安全性安全不安全安全
签名(签名者)2Mu+1Ad(2Mu)2Mu+1Ad(1Mu)1Ex+2Mu(1Pa)
6结语
成林，亢宝元，王国瞻．一种部分盲签名方案［J］．计算机工程，
2010，36(8):163－164．
SHAMIRA．Identitybasedcryptosystemsandsignatureschemes［C］//CRYPTO'84:AdvancesinCryptology．Berlin:Springer-Verlag，1984:47－53．
本文先分析了FENG方案的安全性缺陷，给出了具体的伪造签名方法。为了克服FENG方案的缺陷，提出一个新的
在随机预言模型下和高效的无可信PKG的部分盲签名方案，
CDHP困难的假设下，新方案被证明能够抵抗三种类型敌手
因此方案是安全的。通过有效地利用预的存在性伪造攻击，
计算，新方案总共只需要1个双线性对运算，比FENG方案和Chow方案都减少了2个双线性对运算，在计算效率方面具有较大的优势，整体性能较高，具有一定的实用性。参考文献：
［1］
CHAUMD．Blindsignaturesforuntraceablepayments［C］//CRYP-TO'82:AdvancesinCryptology．Berlin:Springer-Verlag，1983:199－203．［2］
ABEM，FUJISAKIE．Howtodateblindsignatures［C］//ASIA-CRYPTO'96:AdvancesinCryptology．Berlin:Springer-Verlag，1996:244－251．［3］
ABEM，OKAMOTOT．Provablysecurepartiallyblindsignatures［C］//CRYPTO2000:AdvancesinCryptology．Berlin:Springer-Verlag，2000:271－286．
［6］CHOWS，HUIL，YIUS．Twoimprovedpartiallyblindsignatureschemesfrombilinearpairings［C］//ASIACRYPTO2005:Ad-vancesinCryptology．Berlin:Springer-Verlag，2005:316－328．
［7］CHENX，ZHANGF，LIUS．ID-basedrestrictivepartiallyblindsignaturesandapplications［J］．JournalofSystemandSoftware，2007，80(2):164－171
［8］［9］
崔巍，辛阳，胡程瑜等．高效的基于身份的(受限)部分盲签名［J］．北京邮电大学学报，2008，31(4):53－57．
冯涛，彭伟，马建峰．安全的无可信PKG的部分盲签名方案［J］．通信学报，2010，31(1):128－133．
的安全性证明［J］．软件学报，2007，18(4):1007－1014．
［10］顾纯祥，祝跃飞，潘晓豫．Forking引理与一类基于身份签名体制［11］KAWAHARAY，TAKAGIT，OKAMOTOE．Efficientimplementa-tionofTatepairingonamobilephoneusingJava［C］//CIS'2006:2006InternationalConferenceonComputationalIntelligenceandSe-curity，LNCS4456．Berlin:Springer-Verlag，2007:396－405．
（上接第909页）参考文献：
［1］
COTTERSF，RAOBD．Theadaptivematchingpursuitalgorithmforestimationandequalizationofsparsetime-varyingchannels［C］//Thirty-FourthAsilomarConferenceonSignals，SystemsandComput-ers．Washington，DC:IEEE，2000:1772－1776．［2］
KARABULUTGZ，YONGACOGLUA．Estimationoftime-varyingchannelswithorthogonalmatchingpursuitalgorithm［C］//2005IEEESymposiumonAdvancesinWiredandWirelessCommunica-tion．Washington，DC:IEEE，2005:141－144．［3］［4］［5］
DONOHOD．Compressedsensing［J］．IEEETransactionsonInfor-mationTheory，2006，4(52):1289－1306．
BARANIUKR．Alectureoncompressivesensing［J］．IEEESignalProcessingMagazine，2007，24(4):118－121．
MALLATS，ZHANGZ．Matchingpursuitswithtime-frequencydic-tionaries［J］．IEEETransactionsonSignalProcessing，1993，12
［9］［8］［7］［6］
(41):3397－3415．
TROPPJA，GILBERTAC．Signalrecoveryfrompartialinforma-tionbyorthogonalmatchingpursuit［EB/OL］．［2010－09－16］．http://www．
personal．
umich．
edu/-jtropp/papers/
TG052SignalRecovery．Pdf．
DAIW，MILENKOVICO．Subspacepursuitforcompressivesensingsignalreconstruction［J］．IEEETransactionsonInformationTheory，2009，55(5):2230－2249．
GHOSHM．Blinddecisionfeedbackequalizationforterrestrialtele-visionreceivers［J］．IEEESignalProceeding，1998，86(10):2070－2081．
朱行涛，刘郁林，赵翔，等．MIMO_OFDM系统中稀疏信道估计算法研究［J］．云南大学学报，2007，29(6):574－578．
［10］胡健，张延华，周作成．一种改进的稀疏信道估计算法［J］．通信
技术，2009，42(7):31－33．