# Improved QRD-M Detection Algorithm for Generalized Spatial Modulation Scheme

Authors: Xiaorong Jing; Mingyue Wang; Wei Zhou; Hongqing Liu
Journal: International Journal of Antennas and Propagation
 (2017)

---

## Abstract

Generalized spatial modulation (GSM) is a spectral and energy efficient multiple-input multiple-output (MIMO) transmission scheme. It will lead to imperfect detection performance with relatively high computational complexity by directly applying the original QR-decomposition with M algorithm (QRD-M) to the GSM scheme. In this paper an improved QRD-M algorithm is proposed for GSM signal detection, which achieves near-optimal performance but with relatively low complexity. Based on the QRD, the improved algorithm firstly transforms the maximum likelihood (ML) detection of the GSM signals into searching an inverted tree structure. Then, in the searching process of theM branches, the branches corresponding to the illegitimate transmit antenna combinations (TACs) and related to invalid number of active antennas are cut in order to improve the validity of the resultant branches at each level by taking advantage of characteristics of GSM signals. Simulation results show that the improved QRD-M detection algorithm provides similar performance to maximum likelihood (ML) with the reduced computational complexity compared to the original QRD-M algorithm, and the optimal value of parameter M of the improved QRD-M algorithm for detection of the GSM scheme is equal to modulation order plus one.


---

## Body

## 1. Introduction

Multiple-input multiple-output (MIMO) technique has been shown to be an effective way to improve capacity and reliability comparing with single antenna wireless system. For this reason, a great variety of MIMO transmission schemes has been proposed and thoroughly analyzed in the literatures within the past few years, among which the vertical Bell Labs Layered Space-Time (V-BLAST) architecture [1] and the space-time code (STC) [2] are two general schemes achieving multiplexing and diversity gains and now have become an important part of modern wireless communication standards, such as IEEE 802.11n and 3GPP Long Term Evolution Advanced (LTE-A). However, regardless of variety of MIMO schemes, an increase of the complexity and cost is encountered in the development of multiple antenna transmission schemes caused by the interchannel interference (ICI), the interantenna synchronization (IAS), and the multiple radio frequency (RF) chains required [3].The spatial modulation (SM) [4], as an attractive modulation scheme for multiple antennas communications, employs only one active transmit antenna with single RF transmitter structure at one given channel use and one symbol is sent on this active antenna with the remaining antenna elements silent. Therefore, the IAS and RF requirement are relaxed and the IAI is avoided. However, the SM is of lower spectral efficiency compared to conventional MIMO counterparts since only one transmit antenna is activated and one symbol is sent on the activated antenna at one given channel use.Generalized spatial modulation (GSM), as an extension of SM scheme, is developed in [5] and offers a tradeoff between SM and V-BLAST. In GSM, parts of the transmit antennas (TAs) are activated simultaneously as an additional means to convey information. As a result, an increased capacity can be achieved by the GSM compared to SM. In [6], the lower and upper bounds on the capacity of the GSM scheme are derived. However, this operation introduces ICI among active antennas, and hence an efficient detection method is required at the receiver to eliminate it.Signal detection for GSM scheme is much more complicated than conventional MIMO, since the active transmit antenna combination (TAC) must be estimated first in order to detect the transmitted symbol vector. The maximum likelihood (ML) detector is the optimal detection algorithm, where an exhaustive search is performed to jointly detect the TACs and modulated symbol vectors [7]. However the intractable computational complexity renders the ML detector impractical for GSM scheme. For this, some low complexity and suboptimal detectors were proposed for GSM scheme. Based on Gaussian approximation and QR projection, the authors in [8] split the GSM signal detection into two stages to reduce the computational complexity, one for the TACs index and the other for the symbol vector. In [9], a group maximum likelihood (GML) scheme was proposed to detect GSM signal, which exhibits good performance, especially for the configuration of four transmit and two active antennas. Further, a suboptimal nested maximum likelihood group detection algorithm, which greatly reduces the complexity of the optimal ML detector, was proposed for GSM scheme [10]. In [11], a projection-based list detector was proposed for GSM scheme, which was shown to significantly reduce the gap to the optimal ML detector with dramatically reduced computational complexity. Although these detectors have low complexity, a significant detection performance gap to the optimal detector still is observed.Recently, several near-optimal detectors were also proposed for GSM scheme. An optimal detector based on improved sphere decoding (SD) has been proposed in [12], but the high computational cost in low SNR regimes makes its implementation prohibitive. To achieve a more balanced tradeoff between complexity and performance, Xiao et al. presented an order block minimum mean squared error (OB-MMSE) detector [13] for GSM scheme in which an ordering algorithm is proposed to sort the potential TACs, and the possible symbol vector for each ordered TAC is detected by block MMSE method. Furthermore, based on a computationally efficient concentrated ML (CECML) algorithm proposed for efficient computation of ordering metric for the OB-MMSE detector, an improved (OB-MMSE) detector for GSM was presented in [14], which can achieve substantial complexity reduction but with almost the same performance as OB-MMSE detector in [13]. In [15], a low complexity near-ML detection scheme for GSM aided single carrier systems was proposed, which provided a parameter to balance a tradeoff between complexity and performance.Furthermore, some compressive sensing (CS) based detectors were proposed for GSM detection by taking the inherent scarcity in GSM signals. In [16], a basis pursuit (BP) aided denoising detector was proposed for GSM scheme, which is robust to noise variation compared to conventional CS detectors. An extension of the normalized CS detector based on the orthogonal matching pursuit algorithm was proposed for GSM scheme in [17], which is shown to be suitable for large-scale GSM implementation due to its low complexity. Recently, Wang et al. proposed an enhanced Bayesian compressive sensing (EBCS) detector for GSM system [18]. The problem is that these detectors may fail to acquire the transmit vector when the transmitted vectors have poor sparse property.Among the existing MIMO detection algorithms, QR-decomposition with M algorithm (QRD-M) is one of the promising algorithms, which can achieve near-ML detection performance while requiring comparatively low complexity [19]. The QRD-M algorithm, as a breadth-first tree search algorithm, retains only M reliable candidate branches at each level with the smallest accumulated metrics, which is very convenient for parallel implementation. The QRD-M algorithm can be directly applied to GSM scheme by adding a zero as a constellation point. This, however, does not consider the basic and fundamental principle of GSM; namely, at any giving time, not all the antennas are activated. Thus, the complexity of such a system increases exponentially with the number of transmit antennas. In addition, the minimum Euclidean distance of the transmit vectors is decreased by considering the zero as a constellation point, which significantly degrades system performance. Therefore, in this work, an improved QRD-M algorithm is proposed for GSM signal detection by exploiting the structure of GSM; the improved QRD-M algorithm avoids a blind search by cutting the branches corresponding to the illegitimate TACs and related to invalid number of active antennas, which directly leads to increased minimum Euclidean distances of the transmit vectors. Simulation results show that the improved QRD-M algorithm can not only reduce computational complexity, but also achieve near-ML detection performance compared to original QRD-M algorithm.The remainder of this paper is organized as follows. The system model is presented in Section2. In Section 3, we briefly introduce the original QRD-M algorithm, and then based on it, the improved QRD-M algorithm for GSM signal detection is presented and computational complexity is also analyzed. Section 4 provides the simulation results. Finally, the conclusion is made in Section 5.


## 2. System Model

Consider a GSM scheme communicating over aNr×Nt MIMO channel where Nt and Nr denote the number of transmit and receive antennas, respectively. In a GSM transmission, only a subset containing NA transmit antennas is activated to the emission of independent symbols from each antenna at a channel use. Consequently, there are total CNtNA TACs, where CNtNA denotes the binomial coefficient. Among these TACs, only Nc=2log2⁡CNtNA of them are permitted and the other combinations are considered illegitimate, where ⌊·⌋ denotes the floor operator.At each channel use,log2⁡Nc bits are mapped into the TAC indices I∈Υ, where Υ denotes the TAC set, while NAlog⁡(Ω) bits are mapped into QAM symbols that are transmitted by NA activated antennas, where Ω denotes the cardinality of the constellation set Ω of QAM. The transmit symbol vector can be represented as(1)s=…,0,sa1,0,…,0,sa2,0,…,0,saNA,0,…T∈CNt×1,where {a1,a2,…,aNA}∈Υ represents the TAC indices with a1,a2,…,aNA∈1,2,…,Nt.LetH∈CNr×Nt be the MIMO channel matrix, whose elements are mutually independent and assumed to obey complex Gaussian distribution with zero mean and a variance of one. The received signal vector y∈CNr×1 is given by(2)y=Hs+n=∑i=a1aNAhisi+n=HIsI+n,where i∈I={a1,a2,…,aNA}, hi is the ith column of the channel matrix, HI=[ha1ha2⋯haNA] is the submatrix with NA columns of H, sI=sa1sa2⋯saNA, and n is complex additive white Gaussian noise vector with zero mean and variance of σ2INr.It follows from (2) that the ML detector for GSM signals can be formulated as(3)s^ML=arg⁡mins∈Υ×ΩNA⁡y-Hs,where Υ×ΩNA denotes the set of all possible transmit vectors in both the spatial and signal domains. Obviously, the ML detector can achieve the optimal performance by exhaustively searching all the possible transmitted signal vectors and thus may have a prohibitive complexity, especially for large values of Nc and NA with high order modulation constellation.


## 3. Improved QRD-M Detection Algorithm for GSM Scheme

In this section, to reduce the complexity while keeping near-ML performance, we propose an improved QRD-M detection algorithm by exploiting the structure of GSM signal.In what follows, a brief introduction of the original QRD-M algorithm is first provided and the problem caused by directly applying the original QRD-M algorithm for GSM signal detection is analyzed. Then an improved QRD-M algorithm is proposed by cutting the branches corresponding to the illegitimate TACs and related to invalid number of active antennas, which provides similar detection performance to maximum likelihood (ML) with dramatically reduced computational complexity compared to the original QRD-M algorithm.


### 3.1. The QRD-M Algorithm for GSM Detection

The QRD-M algorithm [19–21] can be directly applied to GSM systems by adding a zero as a constellation point in constellation set Ω to form the constellation set Ω0=Ω∪{0}. Based on QRD of channel matrix H=QR with Q and R denoting Nr×Nt unitary matrix and Nt×Nt upper triangular matrix, respectively, the QRD-M detector for GSM signals is formulated by(4)s^=arg⁡mins∈Ω0Nty¯-Rs2=arg⁡minsj∈Ω0∑n=1Nty¯n-∑j=nNtrn,jsj2,where y¯=QHy=y¯1,y¯1,…,y¯NtT and rn,j is the n,jth element in matrix R.From (4), since R is an upper triangular matrix, the detection of the GSM signals based on the original QRD-M algorithm is equivalent to searching an inverted tree structure with Nt+1 levels, and only M branches with the least accumulated metrics at each tree searching level are kept. However, the process of tree searching at each level is based on constellation set Ω0 instead of Ω.Lets~=s~1,s~2,…,s~i,…,s~NtT represent the possible transmit vector, where s~i∈Ω0, i=1,2,…,Nt. If the current searching level is n for n=1,2,…,Nt, let the ordered set ρn+1m=s~n+1m,s~n+2m,…,s~Ntm represent the mth survival branch at the search level n+1 with the corresponding accumulated metric Γρn+1m, where m=1,2,…,M¯n+1 with M¯n+1≤M denoting the number of the survival branches at search level n+1. For the search level n, the kth candidate branch ρnk=ρnq,m=s~nq∪ρn+1m=s~nq,s~n+1m,…,s~Ntm is obtained by expanding the survival branch ρn+1m at search level n+1, where s~nq∈Ω0, k=1,2,…,M¯n+1Ω0, and the corresponding accumulated metric is Γρnk=Γρn+1m→ρnq,m=Γρn+1m+μnq,m, where μρnq,m=y¯n-rn,ns~nq-∑j=n+1Ntrn,js~jm2. The accumulated metrics Γρnk for k=1,2,…,M¯n+1Ω0 are then ordered, and only M¯n≤M (namely, at most M) branches survive and the rest of the list is deleted. The same procedure is applied to the next level, and this process continues to the search level 1. At last, the branch with the minimum accumulated metric is chosen as the solution of the original QRD-M algorithm.From the procedure of the original QRD-M algorithm above, the direct application of the QRD-M algorithm to GSM scheme does not consider the basic and fundamental principle of GSM; namely, for any channel use onlyNA antennas out of Nt transmit antenna are active, which causes the relatively high complexity of QRD-M detector. In addition, the Euclidean distances of the possible transmit signal vectors decrease by considering the zero as a constellation point in Ω0, which significantly degrades the performance of QRD-M detector for GSM signals. Hence, in next subsection, an improved QRD-M algorithm for detection of GSM signals is proposed.


### 3.2. Improved QRD-M Algorithm for GSM Scheme

According to the procedure of the original QRD-M algorithm above, the search space isΩ0 at each search level in spite of the fact that at most M branches are retained. That is to say, the number of paths (corresponding to the possible transmit vectors) in the inverted searching tree with the Nt search levels for the QRD-M algorithm is Ω0Nt. However, in fact there exist only NcΩNA permitted transmit vectors in GSM signal, which means that Ω0Nt-NcΩNA paths in the inverted searching tree are illegitimate. Hence, the direct application of QRD-M algorithm to GSM signal detection will not only lead to the increased complexity, but also make the detection performance inferior to ML detection obviously due to decreasing the minimum Euclidean distances of the branches in the inverted searching tree.TheΩ0Nt-NcΩNA illegitimate paths in the inverted searching tree come from two parts. The first part includes NReΩNA paths with NRe=CNtNA-Nc, which represent the illegitimate transmit vectors s~ generated by unpermitted TACs while s~0=NA with ·0 denoting the 0-norm operation. The second part includes the Ω0Nt-CNtNAΩNA paths, which represent the illegitimate transmit vectors s~ with s~0≠NA.Take a GSM scheme withNt=4 and NA=2 as an illustrative example and define an “TAC pattern” to be a 4×1 vector consisting of 1s and 0s, where one in a coordinate indicates that the antennas corresponding to that coordinate are active and zero indicates that the corresponding antennas are silent. There exist six TAC patterns corresponding to six TACs for such system, given by(5)Call=a1,a2,a3,a4,a5,a6=1100,1010,1001,0110,0101,0011,where ai represents one possible TAC pattern for 1≤i≤6. In this case, out of the CNtNA=6 possible TACs, only Nc=2log2⁡CNtNA=4 are needed for signaling, and the corresponding TAC patterns form the set CGSM. If the TAC patterns a1,a2,a3,a4 are permitted, CGSM is(6)CGSM=a1,a2,a3,a4=1100,1010,1001,0110.Correspondingly, the unpermitted TAC patterns form the set CRe. That is,(7)CRe=a5,a6=0101,0011.It is obvious that Call=CGSM∪CRe.When BPSK modulation is considered in the GSM transmission, the inverted searching tree for the QRD-M algorithm is shown in Figure1, where the possible transmit vector is denoted by s~=s~1,s~2,s~3,s~4T and Ω0=1,-1,0. In Figure 1, the 16 permitted paths, which are matched with the permitted TAC patterns, are represented by the black solid lines. The 8 paths, matched with the unpermitted TAC patterns, are denoted by blue solid lines. The 57 paths, corresponding to the illegitimate transmit vectors, are represented by the red solid lines. The total number of the illegitimate paths is 65. It is concluded in Figure 1 that the illegitimate paths are decidedly in the majority in this inverted searching tree for the QRD-M algorithm. The similar conclusion can be drawn from other GSM schemes. The large number of the illegitimate paths in inverted searching tree for the QRD-M algorithm not only leads to the relatively high complexity of QRD-M detector, but also degrades the detection performance due to the deceased Euclidean distances of the possible paths (i.e., transmit vectors). Hence, in what follows, we propose an improved QRD-M detector, which is more suitable for GSM scheme.Figure 1
An example of the inverted tree for the original QRD-M algorithm withNt=4, NA=2, and BPSK modulation.For the improved QRD-M algorithm, if the current searching level isn for n=1,2,…,Nt and M¯n+1≤M survival branches are retained at the upper level n+1, M⌢n=M¯n+1Ω0 candidate branches can be obtained by extending these M¯n+1 survival branches. Different from the original QRD-M algorithm, the improved QRD-M algorithm only retains M^n≤M⌢n instead of M⌢n=M¯n+1Ω0 candidate branches by pruning the unpermitted branches, which are related to the illegitimate paths analyzed above. On the basis of this, the M-branch searching is then performed to form the resultant survival branches corresponding to the current search level. To summarize, the steps of the improved QRD-M detection algorithm for GSM scheme are presented in Algorithm 1. InStep3 of the improved QRD-M algorithm for GSM scheme, the branches corresponding to the illegitimate TACs and related to invalid number of active antennas are cut in each searching level. InStep4, the number of the retained branches in each searching level is calculated. The pseudocode of the proposed is provided in Pseudocode 1 in Appendix as well.Pseudocode 1:The pseudocode of the improved QRD-M algorithm for GSM detection.
Input: y-,R,CRe,M,  n=Nt,  Γ(ρNt+11)=0,  ρNt+11=∅,  M-Nt+1=1 (1)  while flag_done=0 do (2) k=0 (3) for m=1:1:M-n+1 (4)    for q=1:1:|Ω0| (5)    k=k+1 (6)    ρnk=ρnq,m={s^nq}∪ρn+1m (7)    end for (8) end for (9) M⌢n=M^n←k (10) if n≤Nt-NA+1 (11) if n≤Nt-NA (12)   for l=1 to M⌢n (13)     if ρnl0>NA+1 (14)    remove branch of ρnl, M^n←M^n-1 (15)     else (16)    keep branch of ρnl (17)    end if (18)  end for (19) end if (20) M⌢n←M^n (21) for l=1 to M⌢n (22)    if {ρnl≠0}∩CGSM=∅ (23)   remove branch of ρnl, M^n←M^n-1 (24)    else (25)   keep branch ofρnl (26)  end if (27) end for (28) end if (29) M⌢n←M^n (30) if n≤NA (31) for l=1 to M⌢n (32)  if Nt-ρnl0>Nt-NA+1 (33)   remove branch of ρnl, M^n←M^n-1 (34)  else (35)   keep branch of ρnl (36)  end if (37) end for (38) end if (39) for l=1 to M^n (40) Γ(ρnl)=Γ(ρn+1m→ρnq,m)=Γ(ρn+1m)+μnq,m (41) end for (42) if M^n≤Mn (43) M-n=M^n, keep ρnm={s^nm,s^n+1m,…,s^Ntm} and the corresponding Γ(ρnm), m=1,2,…,M-n (44) else (45) M-n=M, keep ρnm={s^nm,s^n+1m,…,s^Ntm} and the corresponding Γ(ρnm) so that Γ(ρnk) is minimized, m=1,2,…,M-n. (46) end if (47) n=n-1 (48) if n=0 (49) flag_done=1 (50) end if (51) end while (52) ki=arg⁡min⁡m=1,…,M-nΓρ1m Output: s^=[s^1ki,s^2ki,…,s^Ntki]TAlgorithm 1:Improved QRD-M algorithm for GSM detection.
Initialization: Set Γ(ρNt+11)=0, ρNt+11=∅ and M-Nt+1=1; Step  1. Let n=Nt; Step  2. Extend M-n+1 survival branches of level n+1 and form M⌢n=M-n+1Ω0 possible branch, ρnk=ρnq,m={s~nq}∪ρn+1m denoting one of branches at leveln, where s~nq∈Ω0, m=1,2,…,M-n+1 and q=1,2,…,Ω0; Step  3. Form the candidate branches of level n by pruning the unpermitted branches in the tree structure. Case1. If n≤Nt-NA, find the branches who are related with more than NA+1 active antennas and count the number of these branches, denoted bydn1, then delete these branches from the inverted tree structure. Case2. If n≤Nt-NA+1, find the branches who are related with the unpermitted TAC patterns and count the number of these branches, denoted bydn2, then delete them from the inverted tree structure. Case3. If n≤NA, find the branches who are related with more than Nt-NA+1 silent antennas and count the number of these branches, denoted bydn3, then delete them from the inverted tree structure. Step  4. Let M^n=M⌢n-dn1-dn2-dn3; Step  5. Compute Γ(ρnk)=Γ(ρn+1m→ρnq,m)=Γ(ρn+1m)+μnq,m, where μ(ρnq,m)=y-n-rn,ns~nq-∑j=n+1Nt‍rn,js~jm2 denoting the branch metric associated with the permitted path andk=1,2,…,M^n; Step  6. Sort Γ(ρnk) of the retained M^n branches in ascending order. If n=0, choose the path with smallest accumulated metricΓ(ρ1m) as the solution of the proposed algorithm; else let M-n=min⁡{M,M^n}, store M-n best branchesρnm={s~nm,s~n+1m,…,s~Ntm} with the associated path metric Γ(ρnm), where m=1,2,…,M-n, setn=n-1 and goto Step  2;Remark 1.
InStep3 of the improved QRD-M algorithm, the three cases are not mutually independent but complemented in order to prune the unpermitted branches in the tree structure. Note that also if one of cases inStep4 is not satisfied, the corresponding number of the deleted branches is zero; namely, dn1=0, dn2=0, or dn3=0.


### 3.3. Complexity Analysis

In this subsection, the computational complexity of the improved QRD-M is analyzed in terms of the floating-point operations required in the process of the GSM signal detection.For the QRD-M algorithm, the computational complexity includes two parts, namely, the QRD operation and theM-branch searching process. For original QRD-M algorithm and the improved QRD-M algorithm, the part of the QRD operation has the same computational complexity, given by(8)8Nt2Nr+8NtNr-Nt2-2Nt.For the original QRD-M algorithm,M¯n survival branches are retained at level n and further extended to form M¯nΩ0 candidate branches at the next level for n=1,2,…,Nt. Consequently, the complexity of the M-branch searching process is computed as(9)10Ω0+M¯NtΩ02×3+6×2+M¯Nt-1Ω02×4+6×3+⋯+M¯2Ω02×Nt+1+6×Nt.However, for the improved QRD-M algorithm, onlyM^n survival branches are retained at level n by pruning the unpermitted branches before performing M-branch searching, which is much smaller than M⌢n. Hence the complexity of the M-branch searching for the improved QRD-M algorithm is calculated as(10)10Ω0+M^Nt2×3+6×2+M^Nt-12×4+6×3+⋯+M^22×Nt+1+6×Nt.Based on the analysis above, the computational complexity of the original QRD-M and the improved QRD-M algorithm can be, respectively, represented by(11)CQRD-M=8Nt2Nr+8NtNr-Nt2-2Nt+10Ω0+M¯NtΩ02×3+6×2+M¯Nt-1Ω02×4+6×3+⋯+M¯2Ω02×Nt+1+6×Nt,CIQRD-M=8Nt2Nr+8NtNr-Nt2-2Nt+10Ω0+M^Nt2×3+6×2+M^Nt-12×4+6×3+⋯+M^22×Nt+1+6×Nt,where M¯n and M^n are the parameters to be determined, and the values of them are associated with the modulation order and the choice of the parameter M.For comparison purpose, the computational complexity of ML detector for GSM systems is denoted byCML, and it is [18](12)CML=NcΩNANr6NA+3.


## 3.1. The QRD-M Algorithm for GSM Detection

The QRD-M algorithm [19–21] can be directly applied to GSM systems by adding a zero as a constellation point in constellation set Ω to form the constellation set Ω0=Ω∪{0}. Based on QRD of channel matrix H=QR with Q and R denoting Nr×Nt unitary matrix and Nt×Nt upper triangular matrix, respectively, the QRD-M detector for GSM signals is formulated by(4)s^=arg⁡mins∈Ω0Nty¯-Rs2=arg⁡minsj∈Ω0∑n=1Nty¯n-∑j=nNtrn,jsj2,where y¯=QHy=y¯1,y¯1,…,y¯NtT and rn,j is the n,jth element in matrix R.From (4), since R is an upper triangular matrix, the detection of the GSM signals based on the original QRD-M algorithm is equivalent to searching an inverted tree structure with Nt+1 levels, and only M branches with the least accumulated metrics at each tree searching level are kept. However, the process of tree searching at each level is based on constellation set Ω0 instead of Ω.Lets~=s~1,s~2,…,s~i,…,s~NtT represent the possible transmit vector, where s~i∈Ω0, i=1,2,…,Nt. If the current searching level is n for n=1,2,…,Nt, let the ordered set ρn+1m=s~n+1m,s~n+2m,…,s~Ntm represent the mth survival branch at the search level n+1 with the corresponding accumulated metric Γρn+1m, where m=1,2,…,M¯n+1 with M¯n+1≤M denoting the number of the survival branches at search level n+1. For the search level n, the kth candidate branch ρnk=ρnq,m=s~nq∪ρn+1m=s~nq,s~n+1m,…,s~Ntm is obtained by expanding the survival branch ρn+1m at search level n+1, where s~nq∈Ω0, k=1,2,…,M¯n+1Ω0, and the corresponding accumulated metric is Γρnk=Γρn+1m→ρnq,m=Γρn+1m+μnq,m, where μρnq,m=y¯n-rn,ns~nq-∑j=n+1Ntrn,js~jm2. The accumulated metrics Γρnk for k=1,2,…,M¯n+1Ω0 are then ordered, and only M¯n≤M (namely, at most M) branches survive and the rest of the list is deleted. The same procedure is applied to the next level, and this process continues to the search level 1. At last, the branch with the minimum accumulated metric is chosen as the solution of the original QRD-M algorithm.From the procedure of the original QRD-M algorithm above, the direct application of the QRD-M algorithm to GSM scheme does not consider the basic and fundamental principle of GSM; namely, for any channel use onlyNA antennas out of Nt transmit antenna are active, which causes the relatively high complexity of QRD-M detector. In addition, the Euclidean distances of the possible transmit signal vectors decrease by considering the zero as a constellation point in Ω0, which significantly degrades the performance of QRD-M detector for GSM signals. Hence, in next subsection, an improved QRD-M algorithm for detection of GSM signals is proposed.


## 3.2. Improved QRD-M Algorithm for GSM Scheme

According to the procedure of the original QRD-M algorithm above, the search space isΩ0 at each search level in spite of the fact that at most M branches are retained. That is to say, the number of paths (corresponding to the possible transmit vectors) in the inverted searching tree with the Nt search levels for the QRD-M algorithm is Ω0Nt. However, in fact there exist only NcΩNA permitted transmit vectors in GSM signal, which means that Ω0Nt-NcΩNA paths in the inverted searching tree are illegitimate. Hence, the direct application of QRD-M algorithm to GSM signal detection will not only lead to the increased complexity, but also make the detection performance inferior to ML detection obviously due to decreasing the minimum Euclidean distances of the branches in the inverted searching tree.TheΩ0Nt-NcΩNA illegitimate paths in the inverted searching tree come from two parts. The first part includes NReΩNA paths with NRe=CNtNA-Nc, which represent the illegitimate transmit vectors s~ generated by unpermitted TACs while s~0=NA with ·0 denoting the 0-norm operation. The second part includes the Ω0Nt-CNtNAΩNA paths, which represent the illegitimate transmit vectors s~ with s~0≠NA.Take a GSM scheme withNt=4 and NA=2 as an illustrative example and define an “TAC pattern” to be a 4×1 vector consisting of 1s and 0s, where one in a coordinate indicates that the antennas corresponding to that coordinate are active and zero indicates that the corresponding antennas are silent. There exist six TAC patterns corresponding to six TACs for such system, given by(5)Call=a1,a2,a3,a4,a5,a6=1100,1010,1001,0110,0101,0011,where ai represents one possible TAC pattern for 1≤i≤6. In this case, out of the CNtNA=6 possible TACs, only Nc=2log2⁡CNtNA=4 are needed for signaling, and the corresponding TAC patterns form the set CGSM. If the TAC patterns a1,a2,a3,a4 are permitted, CGSM is(6)CGSM=a1,a2,a3,a4=1100,1010,1001,0110.Correspondingly, the unpermitted TAC patterns form the set CRe. That is,(7)CRe=a5,a6=0101,0011.It is obvious that Call=CGSM∪CRe.When BPSK modulation is considered in the GSM transmission, the inverted searching tree for the QRD-M algorithm is shown in Figure1, where the possible transmit vector is denoted by s~=s~1,s~2,s~3,s~4T and Ω0=1,-1,0. In Figure 1, the 16 permitted paths, which are matched with the permitted TAC patterns, are represented by the black solid lines. The 8 paths, matched with the unpermitted TAC patterns, are denoted by blue solid lines. The 57 paths, corresponding to the illegitimate transmit vectors, are represented by the red solid lines. The total number of the illegitimate paths is 65. It is concluded in Figure 1 that the illegitimate paths are decidedly in the majority in this inverted searching tree for the QRD-M algorithm. The similar conclusion can be drawn from other GSM schemes. The large number of the illegitimate paths in inverted searching tree for the QRD-M algorithm not only leads to the relatively high complexity of QRD-M detector, but also degrades the detection performance due to the deceased Euclidean distances of the possible paths (i.e., transmit vectors). Hence, in what follows, we propose an improved QRD-M detector, which is more suitable for GSM scheme.Figure 1
An example of the inverted tree for the original QRD-M algorithm withNt=4, NA=2, and BPSK modulation.For the improved QRD-M algorithm, if the current searching level isn for n=1,2,…,Nt and M¯n+1≤M survival branches are retained at the upper level n+1, M⌢n=M¯n+1Ω0 candidate branches can be obtained by extending these M¯n+1 survival branches. Different from the original QRD-M algorithm, the improved QRD-M algorithm only retains M^n≤M⌢n instead of M⌢n=M¯n+1Ω0 candidate branches by pruning the unpermitted branches, which are related to the illegitimate paths analyzed above. On the basis of this, the M-branch searching is then performed to form the resultant survival branches corresponding to the current search level. To summarize, the steps of the improved QRD-M detection algorithm for GSM scheme are presented in Algorithm 1. InStep3 of the improved QRD-M algorithm for GSM scheme, the branches corresponding to the illegitimate TACs and related to invalid number of active antennas are cut in each searching level. InStep4, the number of the retained branches in each searching level is calculated. The pseudocode of the proposed is provided in Pseudocode 1 in Appendix as well.Pseudocode 1:The pseudocode of the improved QRD-M algorithm for GSM detection.
Input: y-,R,CRe,M,  n=Nt,  Γ(ρNt+11)=0,  ρNt+11=∅,  M-Nt+1=1 (1)  while flag_done=0 do (2) k=0 (3) for m=1:1:M-n+1 (4)    for q=1:1:|Ω0| (5)    k=k+1 (6)    ρnk=ρnq,m={s^nq}∪ρn+1m (7)    end for (8) end for (9) M⌢n=M^n←k (10) if n≤Nt-NA+1 (11) if n≤Nt-NA (12)   for l=1 to M⌢n (13)     if ρnl0>NA+1 (14)    remove branch of ρnl, M^n←M^n-1 (15)     else (16)    keep branch of ρnl (17)    end if (18)  end for (19) end if (20) M⌢n←M^n (21) for l=1 to M⌢n (22)    if {ρnl≠0}∩CGSM=∅ (23)   remove branch of ρnl, M^n←M^n-1 (24)    else (25)   keep branch ofρnl (26)  end if (27) end for (28) end if (29) M⌢n←M^n (30) if n≤NA (31) for l=1 to M⌢n (32)  if Nt-ρnl0>Nt-NA+1 (33)   remove branch of ρnl, M^n←M^n-1 (34)  else (35)   keep branch of ρnl (36)  end if (37) end for (38) end if (39) for l=1 to M^n (40) Γ(ρnl)=Γ(ρn+1m→ρnq,m)=Γ(ρn+1m)+μnq,m (41) end for (42) if M^n≤Mn (43) M-n=M^n, keep ρnm={s^nm,s^n+1m,…,s^Ntm} and the corresponding Γ(ρnm), m=1,2,…,M-n (44) else (45) M-n=M, keep ρnm={s^nm,s^n+1m,…,s^Ntm} and the corresponding Γ(ρnm) so that Γ(ρnk) is minimized, m=1,2,…,M-n. (46) end if (47) n=n-1 (48) if n=0 (49) flag_done=1 (50) end if (51) end while (52) ki=arg⁡min⁡m=1,…,M-nΓρ1m Output: s^=[s^1ki,s^2ki,…,s^Ntki]TAlgorithm 1:Improved QRD-M algorithm for GSM detection.
Initialization: Set Γ(ρNt+11)=0, ρNt+11=∅ and M-Nt+1=1; Step  1. Let n=Nt; Step  2. Extend M-n+1 survival branches of level n+1 and form M⌢n=M-n+1Ω0 possible branch, ρnk=ρnq,m={s~nq}∪ρn+1m denoting one of branches at leveln, where s~nq∈Ω0, m=1,2,…,M-n+1 and q=1,2,…,Ω0; Step  3. Form the candidate branches of level n by pruning the unpermitted branches in the tree structure. Case1. If n≤Nt-NA, find the branches who are related with more than NA+1 active antennas and count the number of these branches, denoted bydn1, then delete these branches from the inverted tree structure. Case2. If n≤Nt-NA+1, find the branches who are related with the unpermitted TAC patterns and count the number of these branches, denoted bydn2, then delete them from the inverted tree structure. Case3. If n≤NA, find the branches who are related with more than Nt-NA+1 silent antennas and count the number of these branches, denoted bydn3, then delete them from the inverted tree structure. Step  4. Let M^n=M⌢n-dn1-dn2-dn3; Step  5. Compute Γ(ρnk)=Γ(ρn+1m→ρnq,m)=Γ(ρn+1m)+μnq,m, where μ(ρnq,m)=y-n-rn,ns~nq-∑j=n+1Nt‍rn,js~jm2 denoting the branch metric associated with the permitted path andk=1,2,…,M^n; Step  6. Sort Γ(ρnk) of the retained M^n branches in ascending order. If n=0, choose the path with smallest accumulated metricΓ(ρ1m) as the solution of the proposed algorithm; else let M-n=min⁡{M,M^n}, store M-n best branchesρnm={s~nm,s~n+1m,…,s~Ntm} with the associated path metric Γ(ρnm), where m=1,2,…,M-n, setn=n-1 and goto Step  2;Remark 1.
InStep3 of the improved QRD-M algorithm, the three cases are not mutually independent but complemented in order to prune the unpermitted branches in the tree structure. Note that also if one of cases inStep4 is not satisfied, the corresponding number of the deleted branches is zero; namely, dn1=0, dn2=0, or dn3=0.


## 3.3. Complexity Analysis

In this subsection, the computational complexity of the improved QRD-M is analyzed in terms of the floating-point operations required in the process of the GSM signal detection.For the QRD-M algorithm, the computational complexity includes two parts, namely, the QRD operation and theM-branch searching process. For original QRD-M algorithm and the improved QRD-M algorithm, the part of the QRD operation has the same computational complexity, given by(8)8Nt2Nr+8NtNr-Nt2-2Nt.For the original QRD-M algorithm,M¯n survival branches are retained at level n and further extended to form M¯nΩ0 candidate branches at the next level for n=1,2,…,Nt. Consequently, the complexity of the M-branch searching process is computed as(9)10Ω0+M¯NtΩ02×3+6×2+M¯Nt-1Ω02×4+6×3+⋯+M¯2Ω02×Nt+1+6×Nt.However, for the improved QRD-M algorithm, onlyM^n survival branches are retained at level n by pruning the unpermitted branches before performing M-branch searching, which is much smaller than M⌢n. Hence the complexity of the M-branch searching for the improved QRD-M algorithm is calculated as(10)10Ω0+M^Nt2×3+6×2+M^Nt-12×4+6×3+⋯+M^22×Nt+1+6×Nt.Based on the analysis above, the computational complexity of the original QRD-M and the improved QRD-M algorithm can be, respectively, represented by(11)CQRD-M=8Nt2Nr+8NtNr-Nt2-2Nt+10Ω0+M¯NtΩ02×3+6×2+M¯Nt-1Ω02×4+6×3+⋯+M¯2Ω02×Nt+1+6×Nt,CIQRD-M=8Nt2Nr+8NtNr-Nt2-2Nt+10Ω0+M^Nt2×3+6×2+M^Nt-12×4+6×3+⋯+M^22×Nt+1+6×Nt,where M¯n and M^n are the parameters to be determined, and the values of them are associated with the modulation order and the choice of the parameter M.For comparison purpose, the computational complexity of ML detector for GSM systems is denoted byCML, and it is [18](12)CML=NcΩNANr6NA+3.


## 4. Numerical Results

In this section we provide the simulation results of the improved QRD-M algorithm (denoted by I-QRD-M in the simulation figures) applied to the GSM signal detection in comparison with the original QRD-M algorithm (denoted by QRD-M in the simulation figures) and the ML algorithm. The number of transmit antennas, receiver antennas, and active antennas isNt=4, Nr=4, and NA=2,3, respectively. The ideal channel state information is assumed available at the receiver.First, the bit error rate (BER) performance comparison of the improved QRD-M algorithm with original QRD-M algorithm and the ML algorithm is provided in Figures2 and 3 over 4×4 MIMO channel with NA=2 for 16-QAM modulation and with NA=3 for 4-QAM modulation, respectively. It is seen from Figure 2 that, with increase of the parameter M, the GSM signal detection performance of the original QRD-M algorithm and the improved QRD-M algorithm improves correspondingly, especially for relatively high SNR region. However, the improved QRD-M algorithm for M=17 achieves the detection performance extremely close to ML algorithm and no more performance gain can be obtained by increasing M. But for the original QRD-M algorithm, there exist great performance gaps compared to the ML algorithm, even for M=22. Although the original QRD-M algorithm can achieve the near-ML detection performance with relatively low complexity for MIMO systems by selecting M candidates in each layer, the degraded performance is observed due to the decreased minimum Euclidean distances of the transmit vectors by directly applying to GSM scheme with zero as an additional constellation point. The improved QRD-M algorithm cuts the branches corresponding to the illegitimate TACs and related to invalid number of active antennas, which directly lead to the increased minimum Euclidean distances of the transmit vectors and then near-ML detection performance for GSM schemes. The similar results can also been seen from Figure 3. Furthermore, from Figures 2 and 3, the optimal M is equal to modulation order Ω plus 1 to achieve near-ML performance. However, from [21], the original QRD-M accomplishes the near-ML performance when M is equal to modulation order in the conventional MIMO systems.Figure 2
BER comparison for GSM scheme withNt=4, Nr=4, and NA=2 for 16-QAM.Figure 3
BER comparison for GSM scheme withNt=4, Nr=4, and NA=3 for 4-QAM.The computational complexity comparisons of the improved QRD-M algorithm, original QRD-M algorithm, OB-MMSE algorithm, SD algorithm, and the ML algorithm are provided in Figure4 over 4×4 MIMO channel with NA=3 for 4-QAM modulation. The computational complexity is evaluated in terms of average floating-point operations (flops) to detect one transmit symbol vector required by these algorithms. From Figure 4, the improved QRD-M algorithm is capable of achieving around 90% and 18% complexity reductions over the ML algorithm and the original QRD-M algorithm with the optimal value of M=5, respectively. The complexity superiority over SD algorithm is also very obvious. However, compared with OB-MMSE algorithm in [13], our proposed I-QRD-M algorithm for the optimal value of M=5 has a certain computational complexity increase. In [13], the set of the valid TACs is assumed to be known at the transmitter and receiver and hence the OB-MMSE algorithm does not involve the computation arising from the lots of the illegitimate transmit symbol vectors, which results in much computational complexity reduction in OB-MMSE algorithm. In fact, this assumption is not reasonable in real communication systems. In our proposed I-QRD-M algorithm, the valid TACs are unknown to transmitter and receiver, and some computational complexity is paid to remove the illegitimate transmit symbol vectors. Also from Figures 3 and 4, no performance improvement can be achieved by further increasing M, which only adds computational complexity in vain. The similar conclusion can be drawn from other system configurations as well.Figure 4
Computational complexity comparison for GSM scheme withNt=4, Nr=4, and NA=3 for 4-QAM.In addition, Figure5 illustrates the BER performance of the improved QRD-M algorithm for different antenna configurations at the transmitter and receiver over the Nt × Nr channel. For simplicity, we take Nt=Nr with a fixed number of active antennas NA=3 for 4-QAM modulation. From the conclusion drawn above, the optimal value of M for the improved QRD-M algorithm is 5 for GSM detection. From Figure 5, with the increase of the number of the antennas Nt=Nr, both the improved QRD-M and the traditional QRD-M algorithm can improve the detection performance, but the improved QRD-M algorithm can achieve near-ML GSM detection performance for the same antenna configuration.Figure 5
BER comparison for GSM scheme versus SNR for different antenna configurations withNA=3 and M=5 for 4-QAM.Finally, we show in Figure6 the BER performance of the improved QRD-M algorithm for different number of the active antennas NA over 4 × 4 channel for 4-QAM modulation. For 4×4 MIMO system, it is not reasonable to set NA to be 4 for the GSM scheme. Hence in the simulation, we set NA as 1, 2, and 3, respectively. The optimal value of M for the improved QRD-M algorithm is 5 for GSM detection. From Figure 6, we can observe that the performance of all these three algorithms, including the ML algorithm, the improved QRD-M algorithm, and the traditional QRD-M algorithm, improves due to the reduced interantenna interference when the number of active antennas NA decreases. Also the performance of the improve QRD-M algorithm is close to that of the optimal ML algorithm for different number of active antennas.Figure 6
BER comparison for GSM scheme versus SNR for different number of active antennasNA with Nt=4, Nr=4, and M=5 for 4-QAM.


## 5. Conclusion

The paper proposed an improved QRD-M detection algorithm for GSM scheme. By exploiting the special structure of GSM signal, the improved QRD-M algorithm avoids the blind search by cutting the branches corresponding to the illegitimate TACs and related to invalid number of active antennas before performing theM-branches searching and retaining the tree branches corresponding to the permitted TACs. Simulation results demonstrate that the improved QRD-M algorithm achieves near-ML performance with a relatively low complexity compared to the original QRD-M algorithm, SD algorithm, and ML algorithm.



---

*Source: 3581592-2017-01-16.xml*