低复杂度的新型球形译码检测算法

王艳丽， 阴国富

(渭南师范学院 网络安全与信息化学院， 陕西 渭南　714000)



·信息科学·

低复杂度的新型球形译码检测算法

王艳丽， 阴国富

(渭南师范学院 网络安全与信息化学院， 陕西 渭南714000)

在多输入多输出(MIMO)信号检测算法中,球形译码检测算法的复杂度会随着半径的增大而迅速增加,代价较高。为了避免这一问题,提出一种改进的球形译码算法,该算法考虑改变搜索的起始位置,从最接近信号点上下限中间位置开始搜索,并根据信号点和中间位置的距离对信号点升序排序,随着译码半径的改变，排序不变,这样就减少搜索次数,降低算法复杂度。仿真结果表明,随着半径取值的增加,新型球形译码算法复杂度大幅度降低的同时,仍然保证了译码性能最接近性能最优的最大似然检测算法。

多输入多输出;球形译码算法;译码半径;译码复杂度

多输入多输出(multiple input multiple output, MIMO)技术利用多天线抑制信道衰落,其出发点是将多发送天线与多接收天线相结合,改善每个用户的通信质量或提高通信效率,无线信道容量随着天线数目的增加而线性增大[1],在4G移动通信系统中，作为一项关键技术得到长足发展[2],但多天线的引入导致了MIMO系统接收端信号检测复杂度的提高,寻找一种低复杂度、高检测性能的信号检测算法仍是研究的热点。

MIMO系统的信号检测算法主要有最大似然(maximum likelihood,ML)算法、线性检测算法、非线性检测算法和许多次优检测算法及其改进算法。传统的ML算法是最优检测算法,但其复杂度呈指数增长,实际应用很难;线性检测算法包括迫零(zero-forcing,ZF)算法和最小均方误差(minimum mean-square error,MMSE)算法,ZF算法付出了增加噪声的代价,并在低信噪比时性能较差,MMSE算法虽然考虑了噪声的干扰,但在高信噪比时,其检测性能收敛于ZF算法;非线性检测算法主要包括串行干扰消除(successive interference cancellation,SIC)算法,其拥有较低的复杂度,但检测效果不佳;许多次优检测算法及其改进算法进一步提高了检测效率和检测性能,文献[3]针对MIMO系统信号检测的V-BLAST算法预处理具有较高运算复杂度的问题,提出了降低复杂度的V-BLAST算法。文献[4]联合SIC和QRD-M树搜索,提出一种低复杂度的V-BLAST算法。

在众多的信号检测算法中,最接近ML算法检测性能的是球形译码(sphere decoding,SD)算法[4-5],SD算法仍存在复杂度较高的问题。各种改进算法仍存在对矩阵的复杂计算,并没有真正降低复杂度[6]。文献[5]指出球形译码算法可以用准正交空时编码,达到降低系统复杂度的目的。文献[7]利用QAM复数调制信号表达式中的相似性并通过减少单个节点的计算量达到简化球形译码的目的。文献[8]基于传统的Dijkstra球形译码算法,引入查找表机制和单树更新软值的算法,改进Dijkstra球形译码进出栈的方法,减少系统的存储开销,有效减少接收机的复杂度。文献[9]根据信道质量的好坏和噪声的大小选择SD算法的初始半径,并通过减少搜索点数降低算法的复杂度,但检测性能损失较大。文献[10]考虑噪声对检测效果的影响,为提高SD算法半径的收缩速度,将控制半径收缩参数k(t)的取值修改为常量0.1,从而达到降低复杂度的目的。本文针对以往研究的不足,提出一种新型球形译码检测算法,该算法的搜索起始位置不同于其他算法，是从最接近信号点上下限的中间位置开始搜索，根据信号点和中间位置的距离，对信号点升序排序;当半径更新时,排序不变，因此，无需再次进行排序,避免对已经确定的有效点进行再次搜索,进一步降低算法复杂度。

1　系统模型

在nR×nTMIMO系统中,发送天线数nT,接收天线数nR,接收信号矢量Y表示为

Y=HX+V，

(1)

其中,X=[x1,x2,…，xnT]T是发送信号矢量,每个信号分量等概率地选自复星座集合S,Y=[y1,y2,…，ynR]T,各分量列数与每根发送天线传输的符号数有关,H表示nR×nT复信道矩阵,用hi,j表示第i根发射天线到第j根接收天线的信道频域响应,V是均值为零,方差为σ2的高斯噪声,

2　球形译码算法及其改进算法

2.1ML检测算法

假设接收端是理想信道估计,接收端信道矩阵H已知,信号检测过程是求解‖Y-HX‖2的最小值,即在星座调制图上进行译码搜索,寻找与接收信号距离最近的点,则ML检测算法可表示为

(2)

ML检测算法是遍历的搜索方法,可以获得最佳的性能。但是，复杂度高达Ο(2QnT),其中,Q是调制比特数。ML检测算法由于较高的复杂度,影响了其在工程上的应用。

2.2传统球形译码算法

球形译码算法[11]与ML算法的不同之处体现在球形译码算法的搜索范围是在以Y为圆心,c为半径的球内。若以c2表示球的平方化半径,则球中点满足下式:

‖Y-HX‖2≤c2。

(3)

图1　球形译码算法检测过程Fig.1　Process of the sphere decoding algorithm

2.3现有的改进球形译码算法

2.3.1改进算法一文献[9]针对传统球形译码检测算法在噪声方差较大时,译码复杂度较高的问题,提出一种新的译码半径选择方法,主要改进思想体现在，半径的选取根据信道的状态和噪声的大小进行动态调整。

初始半径用c表示,半径c的选择方法由式(4)给出

(4)

if(a

elsec=b。

(5)

由式(4)和式(5)可以看出,当噪声方差较小时,a与b接近;当噪声方差较大时,a

文献[9]所提改进算法在信噪比较低的情况下,是以牺牲10%的性能为代价换取复杂度40%～50%的降低。

2.3.2改进算法二文献[10]考虑初始半径的选取和噪声对检测效果的影响,改进思路主要体现在以下两个方面:

1)由于球形译码算法半径的选取存在不确定性,当球形译码算法进行有效点搜索时,若找到第一个有效点后,新的搜索半径c′2=k(t)*c2,针对k(t)的不确定性以及计算k(t)会进一步提高算法复杂度的缺点,将k(t)用常数0.1替换,克服存在问题。

2) 由于噪声影响算法的复杂度,当信噪比较低时,即噪声干扰较强时,算法的搜索次数会增多,进一步导致复杂度的提高。考虑MMSE检测算法的优点,将MMSE检测算法和球形译码算法相结合达到提高检测性能的目的。

文献[10]算法在实现过程中引入MMSE检测,滤波矩阵的求取会进一步增加计算量,如何降低算法的复杂度并进一步提高检测性能是本文的出发点。

2.3.3改进算法三文献[12]提出适用于较大MIMO系统和较高信噪比情况下的SPSD(statisticalpruningspheredecoder)算法,该算法对原始SD算法进行了改进,主要体现在以下两个方面:

1) 选取初始半径c=∞,对信道矩阵H进行QR分解,可得

(6)

2) 搜索顺序从顶层到底层,以第k层为例,SPSD算法以满足式(6)节点的局部分支路径为代价作升序排序;若没有满足式(6)的节点,则进入下一层搜索,直至搜索到最底层,更新球半径,继续下一轮搜索。

文献[12]对比了不同裁剪策略下各种算法的性能,采用深度裁剪函数,获得近似ML算法的性能。但是,该算法复杂度在低信噪比时仍旧较高[13]。

3　新型球形译码算法

3.1原算法问题分析

传统SD算法在实现过程中存在以下问题:

1) 从图1可以看出,传统SD算法实现过程中需要对半径的大小实时更新,当找到候选向量后,便将半径更新为找到的候选向量到球心的距离,然后在新半径的球内搜索,直至没有解为止;

2) 传统SD算法及现有的改进算法考虑从球面开始搜索,没有最大程度减少搜索次数。

3.2新算法描述

根据原算法和现有改进算法存在的问题,本文在现有改进算法的基础上,考虑搜索的位置并将排序思想应用于SD算法。具体检测过程是:

1) 确定检测顺序

初始半径c的选取根据传统SD算法中的经验公式[14]

c2=αnσ2，

(7)

(8)

其中,Γ(·)为Gamma函数,n是接收信号维数,α是控制收缩速度的参数,ξ表示搜索不到网格点的概率,取值为0.01。

(9)

其中,「⎤和⎣」分别表示上限和下限。

式(9)中上限用Ui表示,下限用Li表示,依据点到Ui和Li中间位置的距离,根据|zij-Si|2对调制星座点中的格点进行升序排序,zij表示第i个坐标的可能值，其中,1≤j≤Ni,Ni表示在S中介于Li和Ui之间的点,Ni=length(Li,Ui,S)。

2) 确定搜索位置和半径更新

传统SD算法从球的表面开始搜索直至找到与球中心最接近的有效点为止,这种方法不是有效的方法,特别是在高维球体的情况下。为了降低算法复杂度,本文算法不同于传统SD算法从最接近Li的位置开始搜索,考虑从最接近Ui和Li中间位置开始。

当搜索到一个有效点后,用cnew表示该点到球心的距离,需要对球的半径进行更新:

(10)

设置k为自适应量[15],即

(11)

其中,q是每个信号对应的比特数,γs是信噪比。

k值的选择影响SD算法复杂度,表1给出k值对算法复杂度的影响。

表1　k值对算法复杂度影响

从表1可以看出，当0.1

半径更新后需要重新计算上限Ui和下限Li,同时,Ni也会随着上限和下限的变化而发生改变。本质上,更新后的界限是在Ni减少的条件下以及在原有的Ui和Li的基础上得到的,其排序是在原有的基础上进行的,不进行重新排序,避免了对已经确定的有效点进行二次搜索。

综上所述，新型球形译码检测算法的过程可以归纳为如下3步:

1) 排序过程

① 利用式(7)和式(8)计算初始半径,根据初始半径的取值,利用式(9)计算发送信号向量的上限和下限,并进一步确定信号空间S中介于Ui和Li之间的信号点个数。

② 在集合S中,根据星座调制图上所有点与Ui和Li的中间位置的距离，对其升序排序。

2) 半径的更新过程

① 从最接近Ui与Li中间位置开始搜索,当发现第一个有效点后,该点到球心的距离设为cnew,根据式(10)计算新的搜索半径。

② 在Ni减少的情况下,根据新半径取值重新计算上限和下限,此时,不需要重新排序,避免了重复搜索。

3) 循环实现所有发送符号向量检测过程

① 若检测出有效点的数目在Ni范围内,需要重复(2)步骤,直到检测完Ni个有效点。

② 与网格矢量的成分个数相比,若检测的是最后一个矢量成分,则输出结果,否则,继续返回上述过程,直到所有矢量成分被检测出。

4　算法复杂度及检测性能分析

实验采用MATLAB进行仿真,构造2×2MIMO系统,信道为已知的平坦瑞利衰落信道,均值为0且独立同分布的高斯白噪声,调制方式为4QAM。

仿真1各检测算法的误比特性能仿真分析

图2对比了不同算法的误比特性能。其中,横坐标表示信噪比,纵坐标表示误比特率。REV-SD算法是文献[9]提出的改进球形译码算法,KSD-MMSE算法是文献[10]提出的改进球形译码算法。SPSD算法是文献[12]提出的改进球形译码算法。

图2　不同算法的误比特性能对比Fig.2　BER comparison with different algorithms

从图2可以看出,ML算法和SD算法的曲线几乎重合,验证了SD算法能够达到ML算法的检测效果。在信噪比较小的情况下,SD，REV-SD，KSD-MMSE，SPSD算法和本文算法与ML算法的性能接近,并且本文算法与KSD-MMSE算法、SPSD算法性能相当。在信噪比较大的情况下,5种算法误码率增加的很小,特别是SPSD算法和本文算法依然十分接近ML算法。

仿真2各检测算法的复杂度仿真分析

图3示出SD，REV-SD，KSD-MMSE和本文算法的复杂度随初始半径变化的结果。其中,横坐标表示初始半径,纵坐标表示浮点运算次数。

图3　不同算法复杂度对比Fig.3　Complexity comparison of different algorithms

从图3可以看出,与SD，REV-SD和KSD-MMSE算法相比,随着初始半径的增加,本文算法浮点运算次数曲线呈现平稳状态,而其他3种算法呈现急速增长趋势。本文算法的运算量主要体现在H=QR的计算以及在Ni范围内对有效点的搜索。本文算法计算复杂度有了显著的降低,是因为算法在执行过程中进行了排序并且搜索的过程是从最接近Ui与Li的中间位置开始,而并非其他算法从最接近Li的位置开始搜索。

图4示出SD，REV-SD，KSD-MMSE和本文算法的复杂度随信噪比变化的结果。

图4　不同算法复杂度与信噪比关系Fig.4　Complexity comparison of different algorithms with SNR

从图4可以看出,传统SD算法具有较高复杂度,而其他算法复杂度较低。低信噪比时，KSD-MMSE体现了其优势,计算复杂度较低。随着信噪比的增高,噪声的影响随之减少,REV-SD算法和本文算法体现了优势,计算复杂度较低,与前面的分析一致,从而验证了本文算法在保证检测性能的前提下降低了算法计算复杂度这一结论。

SPSD算法初始半径为无穷大,当到达叶子节点时，对半径进行更新,根据SPSD算法的特征,采用实际经过的节点数衡量其复杂度,图5示出SPSD算法和本文算法实际经过的节点数随信噪比变化的结果。

从图5可以看出,SPSD算法在低信噪比情况下具有较高的复杂度,当信噪比增大时,呈现平缓趋势;本文算法复杂度低于SPSD算法,说明限制初始半径可以有效降低复杂度。

图5　 本文算法和SPSD算法复杂度比较Fig.5　Complexity comparison of SPSD algorithm and this paper′s algorithm

5　结　语

本文在原有改进算法的基础上,基于MIMO系统，提出一种新型球形译码检测算法,选择不同于其他算法的搜索方法,改进算法从最接近信号点上限和下限的中间位置开始,并对调制空间集中的信号点升序排序,当半径更新时,无需二次排序,避免已经发现的有效点再次被搜索的可能,新型球形译码算法在保证检测性能的同时,相对于其他算法有着更低的复杂度。本文算法为降低MIMO系统复杂度提供了一种良好的选择。

[1]GOLDSMITH A,JAFAR S A,JINDAL N, et al.Capa-city limits of MIMO channels[J].IEEE Journal on Selected Areas in Communications,2003,21 (5): 684-702.

[2]赵新雪,李琼,肖维杰,等.低复杂度最大似然MIMO信号检测算法[J].计算机工程与设计,2014,35(1): 144-147.

[3]刘谦雷,杨绿溪,许道峰.用于MIMO信号检测的降低复杂度V-BLAST算法[J].通信学报,2007,28(9): 40-45.

[4]熊春林,王德刚,刘伟,等.联合SIC和QRD-M 树搜索的低复杂度VBLAST检测算法[J].信号处理, 2009, 25(5):746-750.

[5]PENG A Y C, KIM I M, YOUSELFI S. Low-complexity sphere decoding algorithm for quasi-orthogonal space-time block codes[J]. IEEE Transactions on Communications,2006, 54(3): 377-382.

[6]LIU L, LÖFGREN J, NILSSON P. Low-complexity likelyhood information generation for spatial-multiplexing MIMO signal detection[J].IEEE Trans Vehicular Technology,2012, 61(2): 607-617.

[7]岳珍梅,蔺俊杰,杜少波.一种改进的球形译码算法性能分析[J].兰州理工大学学报,2013,39(6):94-96.

[8]卢炳山,刘伟,余晖,等.一种低复杂度多输入多输出球形译码算法[J].上海交通大学学报(自然科学版),2012,46(11)：1833-1837.

[9]陈发堂,侯彦庄.基于MIMO-OFDM系统的一种低复杂度球形译码检测算法[J].计算机应用研究, 2011,28(9):3436-3438.

[10] 李世平,王隆.结合最小均方误差的改进球形译码检测算法[J].计算机应用,2012,32(2): 385-387.

[11] CHAN A M, LEE I. A new reduced-complexity sphere decoder for multiple antenna systems[J]. IEEE Trans Vehicular Technology, 2012, 61(2):607-617.

[12] CUI T, HAN S, TELLAMBURA C. Probability distribution based node pruning for sphere decoding[J].IEEE Transactions on Vehicular Technology,2013,62(4):1586-1596.

[13] 金鑫,倪芸,姚晓东. 基于概率裁剪的球形译码算法[J].华东理工大学学报(自然科学版),2014,40(3):371-375.

[14] VITERBO E,BOUTROS J.A universal lattice code decoder for fading channels[J].IEEE Transactions on Information Theroy,1999, 45(5)：1639-1642.

[15] 刘凯,行双双.基于可靠性度量排序的λ-广义球形解码算法[J].计算机应用,2013,33(4): 923-930.

(编辑李静)

A new type of sphere decoding detection algorithm with low complexity

WANG Yan-li， YIN Guo-fu

(College of Network Security and Information Technology, Weinan Normal University, Weinan 714000， China)

The performance of sphere decoding algorithm is similar to the optimal maximum likelihood detection algorithm and the decoding complexity is greatly reduced in MIMO system. However, the complexity of detection will increase rapidly as the radius increasing and lead to the higher price. In order to avoid the complexity increasing in the detection process, this paper consider changing the search position, and make the nearest signal point to the upper and lower intermediate position as the starting position. Meanwhile, the detection order is in ascending order according to the signal point and the distance of the length of the intermediate position, the order remains unchanged with the radius changing. This method reduces the number of searches and complexity of the algorithm. Simulation results show that the new sphere decoding algorithm can greatly reduce complexity with the increase of radius and make the performance close to the maximum likelihood decoding algorithm.

MIMO; sphere decoding; decoding radius; decoding complexity

2014-12-19

国家自然科学基金资助项目(61172071);渭南市科技计划基金资助项目(2015KYJ-2-2);渭南师范学院科研基金资助项目(15YKP006); 渭南市科技计划基金资助项目(2015KYJ-2-3)

王艳丽，女，陕西咸阳人，从事无线通信信号处理、无线网络技术研究。

TP3391.9；TN929

A

10.16152/j.cnki.xdxbzr.2016-02-008