空间调制信号的低复杂度球形译码算法

王 奔, 张文彬, 赵洪林

(哈尔滨工业大学 通信技术研究所，哈尔滨 150080)

空间调制信号的低复杂度球形译码算法

王 奔, 张文彬, 赵洪林

(哈尔滨工业大学 通信技术研究所，哈尔滨 150080)

为进一步降低球型译码算法(SM-SD)的复杂度，同时不影响算法的误比特性能，提出一种SM-SD算法，采用了不同于目前存在的SM-SD算法的复变量实数化方式，具有独特的搜索树结构，搜索树的相邻两层相互独立. 分析了新算法的原理及搜索过程，通过矩阵运算理论分析了几种SM-SD算法的运算复杂度，然后在不同的空间调制系统中对SM-SD算法的误比特性能和运算复杂度进行仿真. 理论分析和仿真结果表明：新算法的性能接近于最大似然算法，运算复杂度低于已有的各种类型的球型译码算法，因此更加适合于检测空间调制信号.

空间调制；球形译码算法；SM-SD算法；最大似然检测；多输入多输出系统

大规模多输入多输出(Massive Multi-input Multi-output，Massive MIMO)系统需要复杂的天线间同步技术及多条射频链路[1]，导致系统的运算复杂度较高、能量消耗和硬件实现难度较大[2]. 空间调制(Spatial Modulation，SM)技术是一种利用激活发射天线的序号和调制符号共同表示发射信息的新型传输方案，可完全消除空间多路MIMO系统中接收信号间的相互干扰，具有较高的传输速率. 空间调制系统采用最大似然(Maximum Likelihood，ML)检测算法可获得最佳的误比特性能，但运算复杂度较高[3]. 迫零算法(ZF)、最小均方误差算法(MMSE)等次优算法虽然降低了运算复杂度，但误码性能较差[4]，球形译码(Sphere Decoding，SD)算法可平衡系统运算复杂度和误比特两方面的性能[5]. 文献[5-6]提出3种不同的空间调制下的球型译码算法，分别是：以接收端为中心的Rx-SD、以发射端为中心的Tx-SD和联合方案C-SD. 在运算复杂度和误比特性能方面，C-SD始终优于Tx-SD，Rx-SD和C-SD在不同的情况下各有优劣，3种算法的运算复杂度都低于ML，误比特性能接近于ML.

在不影响空间调制系统误比特性能的前提下，为了进一步降低球型译码算法的运算复杂度，本文提出一种新的SM-SD算法，通过理论分析和仿真比较这种新算法与已有的Rx-SD、C-SD算法的运算复杂度和误比特性能.

1 系统模型

1.1 空间调制系统模型

SM的基本思想是将待发送的信息分为两部分，一部分用于选择激活发射天线的序号，另一部分用于选择调制符号. 假设SM系统发射天线数量为Nt，接收天线数量为Nr，调制符号集合中元素总数为M，发射机每次发送m=log2(Nt)+log2(M)个二进制比特信息. log2(Nt)个比特信息由激活发射天线序号携带；log2(M)个比特信息由调制符号携带. 为了不失一般性，这里的调制符号选取正交幅度调制(QuadratureAmplitudeModulation，QAM). 本文中，激活发射天线的序号用lt表示，lt∈{1,2,…,Nt}，发射的调制符号用st表示，st∈{s1,s2,…,sM}. 图1是一个具有4根发射天线的SM系统模型，调制方式为BPSK.q是待发送的二进制序列，根据表格将q分组后产生含有4个元素的发射向量x，其中唯一的非零元素的位置表示被激活的发射天线的序号[5].

图1 空间调制系统的模型

在平坦慢衰落情况下，假设Nr×Nt维信道矩阵H中的每个元素相互独立，即各子信道相互独立，且服从均值为零与方差为1的复高斯分布，包络服从瑞利分布. 假设每根接收天线上的噪声n为理想加性复高斯白噪声，噪声功率谱密度是已知的，符号能量为1，Nt维发射向量xlt,st=[01×(lt-1),st,01×(Nt-lt)]T，Nr维的接收向量y为

y=Hxlt,st+n=hltst+n，

(1)

式中hlt位H的第lt列.

1.2 球形译码算法

在不考虑噪声情况下，每一个发射向量xl,s经过无线信道H之后对应着一个格点Hxl,s，球型译码算法的思想是仅在以接收信号y为中心、以R为半径的球体中进行搜索，球体内与y之间欧几里得距离(简称欧氏距离)最小的格点对应于检测到的发射向量.SD算法的检测性能可以逼近ML，但不需要遍历搜索所有的格点，在半径R选择恰当的情况下，运算复杂度相对于ML会大大降低[7].

SD算法实际上构造了一棵Nt层的搜索树，树中每一条路径{l,s}表示一个格点，对应着一个可能的发射向量，l为工作的发射天线序号且l∈{1,2,…Nt}，s为发射符号且s∈{s1,s2,…,sM}.路径的第一层对应发射向量的第Nt维，最后一层对应发射向量的第1维. 本文将某一层的欧氏距离称为该层的“层欧氏距离”(下简称为层距)，而该层与它之前各层的层欧氏距离之和称为“部分欧氏距离”.

2 空间调制—球形译码算法(SM-SD)

2.1 Rx-SD算法

Rx-SD遍历搜索“发射搜索空间”中所有的NtM条路径，对每条路径从最高维开始不断地累加各维的层距，只要其仍然在球体之内，就继续在此路径上搜索，否则舍弃该条路径. 每当发现一条球内的完整路径，就更新半径为此路径的欧氏距离.

式中yr和hl,r分别表示y和hl的第r维元素. 根据文献[2]，Rx-SD算法减小了“接收搜索空间”，非常适用于Nr非常大的情况.

2.2 C-SD算法

C-SD算法同时减小“发射搜索空间”和“接收搜索空间”，它只计算位于球体内的格点的欧氏距离，并不断更新搜索半径，节省了层距的计算次数. 设ΘR是位于球体内部的发射向量的集合，C-SD可以写成

}.

(2)

C-SD首先计算两个非零元素所在各自维度上的取值区间，然后从“发射搜索空间”中寻找满足取值区间的发射向量组成集合Θinterval，取值区间为

(3)

3 新SM-SD算法

3.1 新型实数化方式

(4)

第2Nt维

.

3.2 新SM-SD算法原理

式(3)中的各向量已经分别转化为实向量

(5)

图2 采用4QAM的4×4SM系统的码搜索树

Fig.2 Search tree structure of 4×4 SM system with 4QAM modulation

3.3 新SM-SD算法的步骤

此算法从搜索树第1层(i=1)开始执行以下步骤. 初始条件下，假设所有发射向量构成一个集合φ1，再定义一个φ2为空集，将来用于保存与接收向量之间具有最小欧式距离的发射向量.

(6)

遍历集合φ1中的发射向量之后:

a)如果集合φ2为空集，则增大半径R，令i=1，φ1存入全部发射向量，重新回到Step1；

b)如果集合φ2为非空集，则算法结束，φ2中唯一发射向量即是发射信号.

a) 若i≤2Nt，说明还没有搜索到搜索树最后两层，则返回到Step1.

b) 若i>2Nt，所有情况均已考虑完毕，集合φ1显然已为空，对集合φ2进行判断. 若φ2非空，则算法结束，若φ2仍为空，则增大半径R，令i=1，φ1装入全部发射向量.

(7)

(8)

如果此时集合φ2为空，则令检验门限M=R2. 如果wi+1>M，则从集合φ1中去除此发射向量，返回Step2；如果wi+1

(9)

新SM-SD算法执行过程可以由图3和图4中的流程图来表示.

图3 新SM-SD算法的流程图

图4 新SM-SD算法中Step3的流程图

4 SM-SD算法运算复杂度分析

运算复杂度可以用算法过程中实数乘法运算的数量来衡量(本文中，除法也看作乘法)，下面对各算法(SM-ML、Rx-SD、C-SD、新SM-SD算法)的实乘运算次数进行分析.

4.1 SM-ML算法

4.2 Rx-SD算法

4.3 C-SD算法

C-SD的运算复杂度就是计算球内点集ΘR的复杂度，运算复杂度为CC-SD=Cpre-com+Cinterval+Ccheck.

2)C-SD的计算取值区间以及检验过程的运算复杂度为

4.4 新SM-SD算法

新SM-SD算法的运算复杂度包括：预先复杂度Cpre-com，求取值区间的复杂度Cinterval和检验Θinterval内格点的欧几里得总距离的运算复杂度Ccheck.

2) 计算取值区间和检验Θinterval内格点欧几里得总距离的运算复杂度为

解释：

1)假设在搜索过程中，在码搜索树的第i∈(1,3,…2Nt-1)层，具有N(i)个非零可取值.

5 仿真结果分析

5.1 仿真设置及说明

在仿真实验中，选取了多个发射天线数Nt、接收天线数Nr和调制尺寸M不同的SM系统，接收端采用新SM-SD、Rx-SD、C-SD和SM-ML算法，信道矩阵元素服从(0，1)复高斯分布，噪声为加性高斯白噪声，符号能量为1，通过改变噪声的功率谱密度来设置信噪比在0至20dB的范围内.SD的初始搜索半径是在ε=10-6这一条件下根据R2=2αNrσn2来选取. 这里用“信道接入速率”表示单位时间内发射端发送的二进制比特数，用m表示，单位为“bit/信道接入”.

5.2 误比特率仿真

图5是Nt=Nr=4，采用16QAM的SM系统和Nt≠Nr，m=6的SM系统的BER. 仿真结果表明：新SM-SD和Rx-SD算法的误比特性能与SM-ML几乎完全相同，在相同的误比特率条件下(例如取10-4)，C-SD算法所需要的信噪高于新SM-SD约1dB. 5.3 运算复杂度仿真

在比较运算复杂度时，将新SM-SD、Rx-SD和C-SD算法的运算复杂度用相对于SM-ML算法的减少量Crel来表示，Crel越大表示运算复杂度越低.

5.3.1 发射天线数与接收天线数相等的情况(Nt=Nr).

图6和图7是在Nt=Nr时几种算法的运算复杂度仿真结果. 已知Rx-SD适用于Nr较大的情况，而C-SD适用于发射搜索空间较大的系统，这从图6中也可以看出. 图6和图7表明：新SM-SD同样适用于发射搜索空间大的系统，且优于C-SD，运算复杂度可达到SM-ML的10%以下. 不过，随着M的增大，新SM-SD和C-SD的运算复杂度都不断降低，新SM-SD的优势逐渐减小，当M=64时，只有在高信噪比时新SM-SD才优于C-SD. 这是因为当M足够大时，预先复杂度处于主导位置，而新SM-SD在实数化预处理时的预先复杂度高于C-SD. 此外，图6也表明：在某些Rx-SD占优的情况下，信噪比较高时，新SM-SD也可以是最优的.

(a)Nr=4

(b)Nr=8

(a)M=4

(b)M=16

(c)M=64

Fig.6ComputationalcomplexityversusRSNforNt=Nr=4

(a)M=16

(b)M=64

Fig.7ComputationalcomplexityversusRSNforNt=Nr=8

5.3.2 发射天线数与接收天线数不相等的情况(Nt≠Nr)

这里只考虑超定系统(Nr>Nt)的情况. 图8和图9是在Nt≠Nr时几种算法的运算复杂度仿真结果，从两个方面来分析新SM-SD的运算复杂度，图8和图9表明：

1)若“发射搜索空间”不变，当Nr=6和Nr=8时，新SM-SD均优于C-SD，随着Nr增大，Rx-SD的优势逐渐显现，而新SM-SD相对于C-SD的优势减小，这是由于新SM-SD中QR分解的运算复杂度受Nr的影响大.

(a)Nr=6

(b)Nr=8

(c)Nr=10

Fig.8ComputationalcomplexityversusRSNform=6,Nt=4,M=16

(a)Nr=6

(b)Nr=8

Fig.9ComputationalcomplexityversusRSNform=4,Nt=4,M=4

2)若“接收搜索空间”不变，当m增加，即频谱效率增加时，新SM-SD和C-SD的运算复杂度会降低，且新SM-SD始终优于C-SD，并在m=6时优于Rx-SD. 相比于SM-ML，m=6时的运算复杂度减少效果比m=4时提升了将近20%. 因此，新SM-SD算法更加适合于检测空间调制信号.

6 结 语

本文提出一种具有新型实数化变换方式的新SM-SD算法，实发射向量中的两维非零元素的位置相邻，且检测时相邻的两层互不影响，降低了运算复杂度. 理论上分析了新SM-SD算法的运算复杂度，在不同的SM系统中对新SM-SD算法的误比特性能和运算复杂度进行仿真，并与已有的SM-SD算法相比较. 理论分析和仿真结果表明：新SM-SD算法在一定条件下可以降低运算复杂度，同时保持了与ML相同的误比特性能，尤其在多数情况下优于C-SD. 在“发射搜索空间”较大，Nr不是很大的情况下，新SM-SD算法降低运算复杂度的效果十分理想，明显优于C-SD和Rx-SD；在某些“接收搜索空间”较大的情况下，高信噪比时新SM-SD也会优于Rx-SD成为最佳选择.

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

[2] YOUNIS A, SINANOVI S, DI RENZO M. Generalized sphere decoding for spatial modulation [J]. IEEE Transactions on Communications, 2013, 61(7):2805-2815. DOI: 10.1109/tcomm.2013.061013.120547.

[3] RAJASHEKAR R, HARI K V S, HANZO L. Reduced-complexity ML detection and capacity-optimized training for spatial modulation systems [J]. IEEE Transactions on Communications, 2014, 62(1):112-124. DOI: 10.1109/tcomm.2013.120213.120850.

[4] 张文彬, 王孝, 陶晨嵩,等. 采用格基规约算法的空间调制检测方案[J]. 哈尔滨工业大学学报, 2015, 47(11):63-68. DOI: 10.11918/j.issn.0367-6234.2015.11.011.

ZHANG W, WANG X, TAO C, et al. Spatial modulation detection schemes based on lattice reduction algorithm[J]. Journal of Harbin Institute of Technology, 2015, 47(11): 63-68. DOI:10.11918/j.issn.0367-6234. 2015. 11.011.

[5] YOUNIS A, MESLEH R, HAAS H, et al. Reduced complexity sphere decoder for spatial modulation detection receivers [C]//2010 IEEE Global Telecommunications Conference. Miami: IEEE Press, 2010:1-5. DOI: 10.1109/ glocom.2010.5683993.

[6] YOUNIS A, DI RENZO M, MESLEH R, et al. Sphere decoding for spatial modulation[C]//2011 IEEE International Conference on Communications. Kyoto: IEEE, 2011, 41(4):1-6. DOI: 10.1109/icc.2011.5963484.

[7] MAURER J, JALDEN D, SEETHALER D. Achieving a continuous diversity-complexity tradeoff in wireless MIMO systems via pre-equalized sphere decoding [J]. IEEE Journal of Selected Topics in Signal Processing, 2009, 3(6):986-999. DOI: 10.1109/jstsp.2009.2038210.

[8] XIA Xiaomei, HU Honglin, WANG Haifeng. Reduced initial searching radius for sphere decoder [C]//2007 IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications. Athens: IEEE, Press, 2007:1-4. DOI: 10.1109/pimrc.2007.4394469.

[9] LCSKEI H，GESBERT D，PAPADIAS C, et al. Space-time wireless systems: from array processing to MIMO communications [M]. Cambridge: Cambridge University Press, 2006:302-320.

[10]AZZAM L. Reduction of decoding complexity for MIMO sphere decoding, QOSTBC, and OSTBC systems[D]. Irvine: University of California, 2008. DOI: 10.1109/ita.2008.4601014.

[11]HASSIBI B, VIKALO H. On the sphere decoding algorithm I. expected complexity [J]. IEEE Transactions on Signal Processing, 2005, 53(8):2806-2818. DOI: 10.1109/tsp.2005.850352.

[12]MEN Hongzhi, JIN Minglu. A low-complexity ML detection algorithm for spatial modulation systems with MPSK constellation [J]. IEEE Communications Letters, 2014, 18(8):1375-1378. DOI: 10.1109/lcomm.2014. 2331283.

[13]AUBERT S, NOUVEL F, NAFKHA A. Complexity gain of QR decomposition based sphere decoder in LTE receivers[C]//2009 IEEE 70th Vehicular Technology Conference Fall. Anchorage: IEEE Press, 2009:1-5. DOI: 10. 1109/vetecf.2009.5378998.

(编辑 王小唯， 苗秀芝)

封面图片说明

封面图片来自第5期论文“纤维素/氧化硅有机-无机杂化复合气凝胶的研究进展”，是哈尔滨工业大学特种环境复合材料技术国家级重点实验室何飞副教授制作完成的纤维素/氧化硅有机-无机杂化复合气凝胶的溶液浸渍法流程示意图展示. 将具有生物材料特征的有机纤维素材料作为多孔模板或增强，采用原位溶液浸渍法，经溶胶-凝胶和干燥过程，可获得具有高比表面积和纳米孔结构特征的纤维素/氧化硅复合气凝胶. 在研究中，通过选用不同类型的纤维素和氧化硅先驱体，借助于先驱体提供的不同官能团作用，可赋予纤维素/氧化硅有机-无机杂化复合气凝胶多种特殊性质，使该类材料在保持气凝胶独特的低密度、高孔隙率、高比表面积和低热导率等结构与性能特点的同时，还在一定程度上改变和提高材料在力学、疏水、光学以及耐热性等方面的性能，因而，在隔热、生物、医学、吸附、包装、光学等多种领域具有广泛的应用前景和研究价值.

(图文提供：何飞，骆金，李亚，方旻翰，赫晓东. 哈尔滨工业大学特种环境复合材料技术国家级重点实验室)

Low complexity sphere decoding algorithm for spatial modulation signals

WANG Ben, ZHANG Wenbin, ZHAO Honglin

(Communication Research Center, Harbin Institute of Technology, Harbin 150080, China)

In order to reduce more complexity while maintaining a good bit error rate performance, a new SM-SD algorithm is proposed. The new SM-SD algorithm employs a different real-valued equivalent transformation from existing sphere decoding algorithms, and it has a unique search tree structure, the adjacent two layers of the search tree are independent of each other. The principle and process of the new algorithm are analyzed, and the computation complexity of SM-SD algorithms is compared by the matrix analysis. Then, the bit error rate and computational complexity of SM-SD algorithms are compared by simulation in different SM systems. Theoretical analysis and simulation results show that the new SM-SD algorithm has a very close performance to Maximum-Likelihood optimum detection, with lower computational complexity than other existing SM-SD algorithms. Thus, the new SM-SD algorithm is more suitable for SM signals detection.

spatial modulation; sphere decoding algorithm; SM-SD algorithm; ML detection；MIMO system

10.11918/j.issn.0367-6234.201607101

2016-07-25

中央高校基本科研业务费专项资金资助(HIT.MKSTISP.201613)

王 奔(1994—)，男，硕士研究生； 赵洪林(1969—)，男，教授，博士生导师

张文彬，zwbgxy1973@hit.edu.cn

TN911.3

A

0367-6234(2017)05-0022-09