王奔,张文彬,赵洪林
(哈尔滨工业大学 通信技术研究所,哈尔滨 150080)
摘要:
为进一步降低球型译码算法 (SM-SD) 的复杂度,同时不影响算法的误比特性能,提出一种SM-SD算法,采用了不同于目前存在的SM-SD算法的复变量实数化方式,具有独特的搜索树结构,搜索树的相邻两层相互独立.分析了新算法的原理及搜索过程,通过矩阵运算理论分析了几种SM-SD算法的运算复杂度,然后在不同的空间调制系统中对SM-SD算法的误比特性能和运算复杂度进行仿真.理论分析和仿真结果表明:新算法的性能接近于最大似然算法,运算复杂度低于已有的各种类型的球型译码算法,因此更加适合于检测空间调制信号.
关键词: 空间调制 球形译码算法 SM-SD算法 最大似然检测 多输入多输出系统
DOI:10.11918/j.issn.0367-6234.201607101
分类号:TN911.3
文献标识码:A
基金项目:中央高校基本科研业务费专项资金资助(HIT.MKSTISP.201613)
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)
Abstract:
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.
Key words: spatial modulation sphere decoding algorithm SM-SD algorithm ML detection MIMO system
王奔, 张文彬, 赵洪林. 空间调制信号的低复杂度球形译码算法[J]. 哈尔滨工业大学学报, 2017, 49(5): 22-30. DOI: 10.11918/j.issn.0367-6234.201607101.
![复制到剪切板](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/copy.gif)
WANG Ben, ZHANG Wenbin, ZHAO Honglin. Low complexity sphere decoding algorithm for spatial modulation signals[J]. Journal of Harbin Institute of Technology, 2017, 49(5): 22-30. DOI: 10.11918/j.issn.0367-6234.201607101.
![复制到剪切板](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/copy.gif)
基金项目 中央高校基本科研业务费专项资金资助 (HIT.MKSTISP.201613) 作者简介 王奔 (1994—),男,硕士研究生;
赵洪林 (1969—),男,教授,博士生导师 通信作者 张文彬,zwbgxy1973@hit.edu.cn 文章历史 收稿日期: 2016-07-25
Contents -->Abstract Full text Figures/Tables PDF
空间调制信号的低复杂度球形译码算法
王奔, 张文彬
![通讯作者](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/REcor.gif)
![zwbgxy1973@hit.edu.cn](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/REemail.gif)
哈尔滨工业大学 通信技术研究所,哈尔滨 150080
收稿日期: 2016-07-25
基金项目: 中央高校基本科研业务费专项资金资助 (HIT.MKSTISP.201613)
作者简介: 王奔 (1994—),男,硕士研究生;
赵洪林 (1969—),男,教授,博士生导师
通信作者: 张文彬,zwbgxy1973@hit.edu.cn
摘要: 为进一步降低球型译码算法 (SM-SD) 的复杂度,同时不影响算法的误比特性能,提出一种SM-SD算法,采用了不同于目前存在的SM-SD算法的复变量实数化方式,具有独特的搜索树结构,搜索树的相邻两层相互独立.分析了新算法的原理及搜索过程,通过矩阵运算理论分析了几种SM-SD算法的运算复杂度,然后在不同的空间调制系统中对SM-SD算法的误比特性能和运算复杂度进行仿真.理论分析和仿真结果表明:新算法的性能接近于最大似然算法,运算复杂度低于已有的各种类型的球型译码算法,因此更加适合于检测空间调制信号.
关键词: 空间调制 球形译码算法 SM-SD算法 最大似然检测 多输入多输出系统
Low complexity sphere decoding algorithm for spatial modulation signals
WANG Ben, ZHANG Wenbin
![Corresponding author](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/REcor.gif)
![zwbgxy1973@hit.edu.cn](http://hit.alljournals.cn/html/hitxb_cn/2017/5/images/REemail.gif)
Communication Research Center, Harbin Institute of Technology, Harbin 150080, China
Abstract: 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.
Key words: spatial modulation sphere decoding algorithm SM-SD algorithm ML detection MIMO system
大规模多输入多输出 (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) 个比特信息由调制符号携带.为了不失一般性,这里的调制符号选取正交幅度调制 (Quadrature Amplitude Modulation,QAM).本文中,激活发射天线的序号用lt表示,lt∈{1, 2, …, Nt},发射的调制符号用st表示,st∈{s1, s2, …, sM}. 图 1是一个具有4根发射天线的SM系统模型,调制方式为BPSK. q是待发送的二进制序列,根据表格将q分组后产生含有4个元素的发射向量x,其中唯一的非零元素的位置表示被激活的发射天线的序号[5].
Figure 1
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-1.jpg)
在平坦慢衰落情况下,假设Nr×Nt维信道矩阵H中的每个元素相互独立,即各子信道相互独立,且服从均值为零与方差为1的复高斯分布,包络服从瑞利分布.假设每根接收天线上的噪声n为理想加性复高斯白噪声,噪声功率谱密度是已知的,符号能量为1,Nt维发射向量xlt, st=[01×(lt-1), st, 01×(Nt-lt)]T,Nr维的接收向量y为
$\mathit{\boldsymbol{y = H}}{\mathit{\boldsymbol{x}}_{{l_{{\rm{t,}}}}{s_{\rm{t}}}}} + \mathit{\boldsymbol{n = }}{\mathit{\boldsymbol{h}}_{{l_{\rm{t}}}}}{\mathit{\boldsymbol{s}}_{\rm{t}}} + \mathit{\boldsymbol{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)SM-SD算法根据{‖ y-Hxl, s‖2≤R2}这一思想,仅通过搜索球内的可能发射向量来计算出激活发射天线的序号和发射的调制符号.本文将NtM种发射信号向量组成的集合称为“发射搜索空间”,而“接收搜索空间”是接收向量的维数Nr.初始搜索半径与噪声方差σn2,Nr和系数α的乘积有关[8],即R2=αNrσn2.限定误比特率ε=10-6,由
2.1 Rx-SD算法Rx-SD遍历搜索“发射搜索空间”中所有的NtM条路径,对每条路径从最高维开始不断地累加各维的层距,只要其仍然在球体之内,就继续在此路径上搜索,否则舍弃该条路径.每当发现一条球内的完整路径,就更新半径为此路径的欧氏距离.
Rx-SD中一条路径{l, s}只需要计算
$\left[ {l_{\rm{t}}^{\left( {{\rm{Rx}} - {\rm{SD}}} \right)},s_{\rm{t}}^{\left( {{\rm{Rx}} - {\rm{SD}}} \right)}} \right] = \mathop {\arg \min }\limits_{\begin{array}{*{20}{c}}{l \in \left\{ {1,2, \cdots ,{N_{\rm{t}}}} \right\}}\\{s \in \left\{ {{s_1},{s_2}, \cdots ,{s_M}} \right\}}\\{{{\tilde N}_{\rm{r}}}\left( {l,s} \right) = {N_{\rm{r}}}}\end{array}} \left\{ {\sum\limits_{r = 1}^{{{\tilde N}_{\rm{r}}}\left( {l,s} \right)} {{{\left| {{y_r} - {h_{l,r}}s} \right|}^2}} } \right\},$
式中yr和hl, r分别表示y和hl的第r维元素.根据文献[2],Rx-SD算法减小了“接收搜索空间”,非常适用于Nr非常大的情况.
2.2 C-SD算法接收信号、发送信号和噪声均为复向量,为了简化计算,首先需要对y, H, xlt, st进行实数化,转变为高维的实数向量y, H, xl, s.式 (1) 转化为
$\mathit{\boldsymbol{\bar y = \bar H}}{{\mathit{\boldsymbol{\bar x}}}_{{l_{{{t,}}}}{s_{{t}}}}} + \mathit{\boldsymbol{\bar n}}$
式中:
C-SD算法同时减小“发射搜索空间”和“接收搜索空间”,它只计算位于球体内的格点的欧氏距离,并不断更新搜索半径,节省了层距的计算次数.设ΘR是位于球体内部的发射向量的集合,C-SD可以写成
$\left[ {l_{\rm{t}}^{\left( {{\rm{C}} - {\rm{SD}}} \right)},s_{\rm{t}}^{\left( {{\rm{C}} - {\rm{SD}}} \right)}} \right] = \mathop {\arg \min }\limits_{\left( {l,s} \right) \in {\Theta _R}} \left\{ {{{\left\| {\bar y - \bar H{{\bar x}_{l,s}}} \right\|}^2}} \right\}.$ (2)
考虑Nt≤Nr的超定系统,
$\left[ {l_{\rm{t}}^{\left( {{\rm{C}} - {\rm{SD}}} \right)},s_{\rm{t}}^{\left( {{\rm{C}} - {\rm{SD}}} \right)}} \right] = \mathop {\arg \min }\limits_{\left( {l,s} \right) \in {\Theta _R}} \left\{ {{{\left\| {\bar z - \bar P{{\bar x}_{l,s}}} \right\|}^2}} \right\},$
式中z =PG-1 HTy.
由于发射端只激活了第l根发射天线,所以发射复向量中只有一个非零元素,实数化后的发射向量xl, s中有两个非零元素,即发射符号st的虚部
C-SD首先计算两个非零元素所在各自维度上的取值区间,然后从“发射搜索空间”中寻找满足取值区间的发射向量组成集合Θinterval,取值区间为
$\begin{array}{l}\frac{{ - R' + {{\bar z}_{l,{N_{\rm{t}}}}}}}{{{{\bar P}_{l + {N_{\rm{t}}},l + {N_{\rm{t}}}}}}} \le \Im \left( s \right) \le \frac{{R' + {{\bar z}_{l,{N_{\rm{t}}}}}}}{{{{\bar P}_{l + {N_{\rm{t}}},l + {N_{\rm{t}}}}}}},\\\frac{{ - R'' + {{\bar z}_{l\left| {l + {N_{\rm{t}}}} \right.}}}}{{{{\bar P}_{l,l}}}} \le \Re \left( s \right) \le \frac{{R'' + {{\bar z}_{l\left| {l + {N_{\rm{t}}}} \right.}}}}{{{{\bar P}_{l,l}}}}.\end{array}$ (3)
式中:
3 新SM-SD算法 3.1 新型实数化方式SD中H的结构限制了搜索必须从第一层开始逐层向下进行,并且在计算第k维 (k=l+Nt-1, …, 1) 的层距
$\begin{array}{l}\mathit{\boldsymbol{\tilde H = }}\\\left[ {\begin{array}{*{20}{c}}{\Re \left( {{H_{1,1}}} \right)} & { - \Im \left( {{H_{1,1}}} \right)} & \cdots & {\Re \left( {{H_{1,{N_{\rm{t}}}}}} \right)} & { - \Im \left( {{H_{1,{N_{\rm{t}}}}}} \right)}\\{\Im \left( {{H_{1,1}}} \right)} & {\Re \left( {{H_{1,1}}} \right)} & \cdots & {\Im \left( {{H_{1,{N_{\rm{t}}}}}} \right)} & {\Re \left( {{H_{1,{N_{\rm{t}}}}}} \right)}\\ \vdots & \vdots & \ddots & \vdots & \vdots \\{\Re \left( {{H_{{N_{\rm{r}}},1}}} \right)} & { - \Im \left( {{H_{{N_{\rm{r}}},1}}} \right)} & \cdots & {\Re \left( {{H_{{N_{\rm{r}}},{N_{\rm{t}}}}}} \right)} & { - \Im \left( {{H_{{N_{\rm{r}}},{N_{\rm{t}}}}}} \right)}\\{\Im \left( {{H_{{N_{\rm{r}}},1}}} \right)} & {\Re \left( {{H_{{N_{\rm{r}}},1}}} \right)} & \cdots & {\Im \left( {{H_{{N_{\rm{r}}},{N_{\rm{t}}}}}} \right)} & {\Re \left( {{H_{{N_{\rm{r}}},{N_{\rm{t}}}}}} \right)}\end{array}} \right].\end{array}$ (4)
式中: Hm, n是从第n根发射天线到第m根接收天线间的增益[10],n∈{1, 2, …, Nt},m∈{1, 2, …, Nr}.相应的,SM的实数发射向量xlt, st中元素的检测顺序发生改变,两个非零元素的位置相邻,分别位于第2l-1维和第2l维. xlt, st的形式为
${{\mathit{\boldsymbol{\bar x}}}_{{l_{\rm{t}}},{s_{\rm{t}}}}} = \left[ \begin{array}{l}0\\ \vdots \\\Re \left( s \right)\\\Im \left( s \right)\\ \vdots \\0\end{array} \right]\begin{array}{*{20}{c}}1\\ \vdots \\{2l - 1}\\{2l}\\ \vdots \\{第2{N_{\rm{t}}}维}\end{array}$
对
$\mathit{\boldsymbol{\tilde D = }}\left[ {\begin{array}{*{20}{c}}{{{\bar D}_{1,1}}} & 0 & {{{\bar D}_{1,3}}} & \cdots & {{{\bar D}_{1,2{N_{\rm{t}}}}}}\\0 & {{{\bar D}_{2,2}}} & {{{\bar D}_{2,3}}} & \cdots & {{{\bar D}_{2,2{N_{\rm{t}}}}}}\\ \vdots & \vdots & \ddots & \cdots & \vdots \\0 & 0 & 0 & {{{\bar D}_{2{N_{\rm{t}}} - 1,2{N_{\rm{t}}} - 1}}} & 0\\0 & 0 & 0 & 0 & {{{\bar D}_{2{N_{\rm{t}}},2{N_{\rm{t}}}}}}\end{array}} \right].$
这种稀疏性使搜索树的相邻两层相互独立,在计算层距时互不影响,减少了乘法运算次数.搜索树共有2Nt层,由前面可知,搜索树的第一层对应实数发射向量的第2Nt维,第二层对应着发射向量的第2Nt-1维,以此类推.例如,第2层的层距|z2Nt-1-D2Nt-1, 2Nt-1 x2Nt-1| 2不受第1层中x2Nt影响,实乘的运算次数比C-SD减少1次.
3.2 新SM-SD算法原理式 (3) 中的各向量已经分别转化为实向量
$\begin{array}{l}{{\mathit{\boldsymbol{\bar x}}}_{l,s}} = {\left[ {0 \cdots \Re \left( s_{\rm{t}} \right),\Im \left( s_{\rm{t}} \right) \cdots 0} \right]^{\rm{T}}},\\\mathit{\boldsymbol{\bar y = }}{\left[ {\Re \left( {{y_1}} \right),\Im \left( {{y_2}} \right) \cdots \Re \left( {{y_{{N_{\rm{r}}}}}} \right),\Im \left( {{y_{{N_{\rm{r}}}}}} \right)} \right]^{\rm{T}}},\\\mathit{\boldsymbol{\bar n = }}{\left[ {\Re \left( {{n_1}} \right),\Im \left( {{n_1}} \right) \cdots \Re \left( {{n_{{N_{\rm{r}}}}}} \right),\Im \left( {{n_{{N_{\rm{r}}}}}} \right)} \right]^{\rm{T}}}.\end{array}$
式 (4) 中的
${\left\| {\left[ {\begin{array}{*{20}{c}}{\mathit{\boldsymbol{Q}}_1^H}\\{\mathit{\boldsymbol{Q}}_2^H}\end{array}} \right]\mathit{\boldsymbol{\bar y}} - \left[ {\begin{array}{*{20}{c}}{\mathit{\boldsymbol{\bar D}}}\\{\bf{0}}\end{array}} \right]{{\mathit{\boldsymbol{\bar x}}}_{l,s}}} \right\|^2} \le {R^2}.$
忽略
$\sum\limits_{i = 1}^{2{N_{\rm{t}}}} {{{\left[ {{{\bar z}_i} - \sum\limits_{j = i}^{2{N_{\rm{t}}}} {{{\bar D}_{i,j}}{{\bar x}_{l,s}}\left( j \right)} } \right]}^2}} \le {R^2}.$ (5)
式中xl, s(j) 表示向量xl, s的第j维元素.
定义z,xl, s的第2Nt维分量对应着码搜索树的第1层,第2Nt-1维分量为第2层,依次类推,所以搜索树的第i层对应向量z,xl, s的第k=2Nt-i+1维分量. 图 2为4×4且采用4QAM的SM系统的码搜索树结构.
Figure 2
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-2.jpg)
在新SM-SD算法中,当i≥3时,能进行到第i层 (第k=2Nt-i+1维) 的点必然满足在第i-1层和第i-2层中有xl, s(2Nt-i+2)=0和xl, s(2Nt-i+3)=0;当i=1, 2时,并不存在xl, s(2Nt-i+2) 和xl, s(2Nt-i+3),所以直接计算第1层和第2层,如果有xl, s(2Nt)=0和xl, s(2Nt-1)=0,则计算第3层.
3.3 新SM-SD算法的步骤此算法从搜索树第1层 (i=1) 开始执行以下步骤.初始条件下,假设所有发射向量构成一个集合?1,再定义一个?2为空集,将来用于保存与接收向量之间具有最小欧式距离的发射向量.
Step 1?根据式 (5),在第i层计算xl, s(2Nt-i+1) 的可取值.
xl, s(2Nt-i+1) 的取值范围为
$\frac{{ - R' + {{\bar z}_{2{N_{\rm{t}}} - i + 1}}}}{{{{\bar D}_{2{N_{\rm{t}}} - i + 1,2{N_{\rm{t}}} - i + 1}}}} \le {{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i + 1} \right) \le \frac{{R' + {{\bar z}_{2{N_{\rm{t}}} - i + 1}}}}{{{{\bar D}_{2{N_{\rm{t}}} - i + 1,2{N_{\rm{t}}} - i + 1}}}},$ (6)
式中
遍历集合?1中的发射向量之后:
① 如果?1中任何一个发射向量的xl, s(2Nt-i+1) 都不满足式 (6):
a) 如果集合?2为空集,则增大半径R,令i=1,?1存入全部发射向量,重新回到Step 1;
b) 如果集合?2为非空集,则算法结束,?2中唯一发射向量即是发射信号.
② 如果集合?1中存在发射向量的xl, s(2Nt-i+1) 满足式 (6),则去掉?1中不满足式 (6) 的发射向量,执行Step 2.
Step 2?对集合?1中每个发射向量的xl, s(2Nt-i+1) 的取值情况进行判断.
① 如果?1中全部发射向量满足xl, s(2Nt-i+1)≠0,则对每个向量执行Step 3,执行完毕后,?1为空,使用与Step 1中① 相同的方法对?2进行判断.
② 如果?1中一部分发射向量满足xl, s(2Nt-i+1)≠0,另一部分发射向量不满足xl, s(2Nt-i+1)≠0,则对于满足xl, s(2Nt-i+1)≠0的每一个发射向量,都执行Step 3,对于xl, s(2Nt-i+1)=0的向量不做处理;?1中全部向量判断完毕后,令i=i+2.
a) 若i≤2Nt,说明还没有搜索到搜索树最后两层,则返回到Step 1.
b) 若i>2Nt,所有情况均已考虑完毕,集合?1显然已为空,对集合?2进行判断.若?2非空,则算法结束,若?2仍为空,则增大半径R,令i=1,?1装入全部发射向量.
Step 3?若某个发射向量满足xl, s(2Nt-i+1)≠0,根据式 (5),则该发射向量中xl, s(2Nt-i) 的取值范围为
$\frac{{ - R'' + {{\bar z}_{2{N_{\rm{t}}} - i}}}}{{{{\bar D}_{2{N_{\rm{t}}} - i,2{N_{\rm{t}}} - i}}}} \le {{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i} \right) \le \frac{{R'' + {{\bar z}_{2{N_{\rm{t}}} - i}}}}{{{{\bar D}_{2{N_{\rm{t}}} - i,2{N_{\rm{t}}} - i}}}}.$ (7)
式中
${R^{''2}} = {R^{'2}} - {\left| {{{\bar z}_{2{N_{\rm{t}}} - i + 1}} - {{\bar D}_{2{N_{\rm{t}}} - i + 1,2{N_{\rm{t}}} - i + 1}}{{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i + 1} \right)} \right|^2}.$
① 如果这个发射向量的xl, s(2Nt-i) 不满足式 (7),则从集合?1中去除这个发射向量,然后返回到Step 2.
② 如果这个发射向量的xl, s(2Nt-i) 满足式 (7),说明找到一个满足取值区间条件的发射向量,保存在集合Θinterval中.需要以R来检验此发射向量的欧几里得总距离,计算第i+1层的部分欧氏距离:
$\begin{array}{l}{w_{i + 1}} = \sum\limits_{m = 2{N_{\rm{t}}} - i + 2}^{2{N_{\rm{t}}}} {{{\left| {{{\bar z}_m}} \right|}^2} + \left| {{{\bar z}_{2{N_{\rm{t}}} - i + 1}} - } \right.} \\\;\;\;\;\;\;\;\;\;\;\;\;{\left. {{{\bar D}_{2{N_{\rm{t}}} - i + 1,2{N_{\rm{t}}} - i + 1}}{{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i + 1} \right)} \right|^2} + \\\;\;\;\;\;\;\;\;\;\;\;\;{\left| {{{\bar z}_{2{N_{\rm{t}}} - i}} - {{\bar D}_{2{N_{\rm{t}}} - i,2{N_{\rm{t}}} - i}}{{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i} \right)} \right|^2}.\end{array}$ (8)
如果此时集合?2为空,则令检验门限M=R2.如果wi+1>M,则从集合?1中去除此发射向量,返回Step 2;如果wi+1<M,检验欧几里得总距离.
$\begin{array}{l}{w_{i + 1}} + \sum\limits_{m = 1}^{2{N_{\rm{t}}} - i - 1} {\left| {{{\bar z}_m} - {{\bar D}_{m,2{N_{\rm{t}}} - i}}{{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i} \right) - } \right.} \\\;\;\;\;\;\;\;{\left. {{{\bar D}_{m,2{N_{\rm{t}}} - i + 1}}{{\bar x}_{l,s}}\left( {2{N_{\rm{t}}} - i + 1} \right)} \right|^2} \le M.\end{array}$ (9)
在累加计算过程中,一旦发现累加和不满足式 (9),则将之从?1中删去,返回Step 2.若总距离<M,则得到一个球内的点,对应的发射向量为xl, s=(0, …0, xl, s(2Nt-i+1), xl, s(2Nt-i), 0, …, 0)T,用它替换集合?2中原来的发射向量.更新判决门限M为此向量的欧几里得总距离,并将此向量从?1中删去.返回Step2.
新SM-SD算法执行过程可以由图 3和图 4中的流程图来表示.
Figure 3
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-3.jpg)
Figure 4
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-4.jpg)
4 SM-SD算法运算复杂度分析运算复杂度可以用算法过程中实数乘法运算的数量来衡量 (本文中,除法也看作乘法),下面对各算法 (SM-ML、Rx-SD、C-SD、新SM-SD算法) 的实乘运算次数进行分析.
4.1 SM-ML算法可能发射向量的总数是NtM,
4.2 Rx-SD算法Rx-SD算法对一条路径{l, s}需要进行
4.3 C-SD算法C-SD的运算复杂度就是计算球内点集ΘR的复杂度,运算复杂度为CC-SD=Cpre-com+Cinterval+Ccheck.
1) C-SD需要预先复杂度,包括Cholesky分解以及计算G,z,ρ的运算复杂度,即
${C_{{\rm{pre - com}}}} = {C_{CH}} + {C_{\mathit{\boldsymbol{\bar G}}}} + {C_\rho } + {C_{\bar z}}.$
式中:CCH=4Nt3/3,Cρ=4Nt2(2Nt+2Nr)+((2Nt)3+ 3(2Nt)2+2(2Nt))/3,Cz=4NtNr,CG =2Nt(4NrNt+1).
2) C-SD的计算取值区间以及检验过程的运算复杂度为
$\begin{array}{l}{C_{{\rm{interval}}}} + {C_{{\rm{check}}}} = \sum\limits_{l = 1}^{{N_{\rm{t}}}} {\left[ {\left( {{N_{\rm{t}}} - l + 2} \right) + \left( {2{N_{\rm{t}}} + 3} \right) \times } \right.} \\\;\;\;\;\;\;\left. {{N_{\left( 1 \right)}}} \right] + 3\sum\limits_{\left( {l,s} \right) \in {\mathit{\Theta }_{{\rm{interval}}}}} {\tilde L\left( {l,s} \right)} .\end{array}$
其中,N(1)为C-SD算法中计算式 (3) 的次数,
4.4 新SM-SD算法新SM-SD算法的运算复杂度包括:预先复杂度Cpre-com,求取值区间的复杂度Cinterval和检验Θinterval内格点的欧几里得总距离的运算复杂度Ccheck.
1) 预先复杂度为Cpre-com=CQR+Cz +C‖Q2Hy‖2,QR分解的复杂度为
${C_{{\rm{QR}}}} = \sum\limits_{k = 1}^N {\left[ {2f\left( k \right) + {f^2}\left( k \right) + 2{f^3}\left( k \right) + 1} \right] - N_{\rm{r}}^3} .$
式中:f(k)=Nr+1-k,N=min{Nr-1, Nt}[13],C‖QzHy‖2=(2Nr-2Nt)(2Nr+1),Cz =4NtNr.
2) 计算取值区间和检验Θinterval内格点欧几里得总距离的运算复杂度为
$\begin{array}{l}{C_{{\rm{interval}}}} + {C_{{\rm{check}}}} = \sum\limits_{i \in \left( {1,3, \cdots 2{N_{\rm{t}}} - 1} \right)} {{M_{\left( i \right)}}\left[ {4 + 4{N_{\left( i \right)}} + } \right.} \\\;\;\;\;\;\left. {\sum\limits_{\left( {l,s} \right) \in {\mathit{\Theta }_{{\rm{interval}}}}} {\left( {3\tilde L\left( {l,s} \right) + 2} \right)} } \right] - 2.\end{array}$
其中,N(i)是码搜索树第i层区间内非零可取值的个数,Θinterval为满足两层取值区间条件的格点构成的点集,0≤
解释:
1) 假设在搜索过程中,在码搜索树的第i∈(1, 3, …2Nt-1) 层,具有N(i) 个非零可取值.
当i=1时,计算式 (6) 中取值区间需要2次实除;对于N(1)个非零的xl, s(2Nt),计算式 (7) 中的取值区间需要2次实乘 (计算R′),2次实除.
当i=3,5…,2Nt-1时,计算式 (6) 中取值区间需要2次实除,2次实乘 (计算R′).对于N(i)个非零的xl, s(2Nt-i+1),计算式 (7) 中的取值区间时需要2次实除,2次实乘 (计算R″).所以有
${C_{{\rm{interval}}}} = \sum\limits_{i \in \left( {1,3, \cdots 2{N_{\rm{t}}} - 1} \right)} {\left[ {4 + 4{N_{\left( i \right)}}} \right]} - 2.$
2) 在检验Θinterval中的格点{l, s}的欧几里得总距离时,第2Nt维到第 (2Nt-i+1) 维的层欧氏距离已经计算过,计算第 (2Nt-i) 维的层欧氏距离需要2次实乘,从第 (2Nt-i-1) 维到第1维需要计算
${C_{{\rm{check}}}} = \sum\limits_{i \in \left( {1,3, \cdots 2{N_{\rm{t}}} - 1} \right)} {\sum\limits_{\left( {l,s} \right) \in {\mathit{\Theta }_{{\rm{interval}}}}} {\left[ {3\tilde L\left( {l,s} \right) + 2} \right]} } .$
3) 只有当第 (i-2) 层中xl, s(2Nt-i+3) 的可取值含有零时,新SM-SD算法才会执行到第i层,所以用M(i)表示在码搜索树的第 (i-2) 层中的可取值是否含有零,M(i)取值为0或者1.
5 仿真结果分析 5.1 仿真设置及说明在仿真实验中,选取了多个发射天线数Nt、接收天线数Nr和调制尺寸M不同的SM系统,接收端采用新SM-SD、Rx-SD、C-SD和SM-ML算法,信道矩阵元素服从 (0,1) 复高斯分布,噪声为加性高斯白噪声,符号能量为1,通过改变噪声的功率谱密度来设置信噪比在0至20 dB的范围内. 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约1 dB.
Figure 5
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-5.jpg)
5.3 运算复杂度仿真在比较运算复杂度时,将新SM-SD、Rx-SD和C-SD算法的运算复杂度用相对于SM-ML算法的减少量Crel来表示,Crel越大表示运算复杂度越低.
${C_{{\rm{rel}}}}\left( \% \right) = 100 \times \frac{{{C_{{\rm{SM - ML}}}} - {C_{{\rm{SM - SD}}}}}}{{{C_{{\rm{SM - ML}}}}}}.$
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也可以是最优的.
Figure 6
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-6.jpg)
Figure 7
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-7.jpg)
5.3.2 发射天线数与接收天线数不相等的情况 (Nt≠Nr)这里只考虑超定系统 (Nr>Nt) 的情况. 图 8和图 9是在Nt≠Nr时几种算法的运算复杂度仿真结果,从两个方面来分析新SM-SD的运算复杂度,图 8和图 9表明:
Figure 8
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-8.jpg)
Figure 9
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/5/PIC/hebgydxxb-49-5-22-9.jpg)
1) 若“发射搜索空间”不变,当Nr=6和Nr=8时,新SM-SD均优于C-SD,随着Nr增大,Rx-SD的优势逐渐显现,而新SM-SD相对于C-SD的优势减小,这是由于新SM-SD中QR分解的运算复杂度受Nr的影响大.
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.
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.