# A New Efficient Ordering Scheme for Sphere Detection

Authors: Cao Haiyan; Li Jun
Journal: Journal of Electrical and Computer Engineering
 (2011)

---

## Abstract

The decoding order has a deep impact in the complexity of sphere detection. A new ordering scheme for sphere detection is presented in this paper, which is based on SIC (serial interference canceling) and the gradient defined by the accumulated probability of the absolute difference between symbol element and the zero-forcing solution. The simulation results show that the proposed ordering scheme can achieve a significant complexity reduction, especially for high numbers of antennas and large constellation sizes in the low SNR region. Compared with sphere detection complexity under BSQR (balanced sorted QR) decomposition and GB (gradient-based) orderings atSNR=5dB, the average number of visited nodes under our proposed ordering is reduced by almost 30% and 33% in 4×4 16QAM system and by almost 30% and 50% reduction in 6×6 16QAM system, respectively. For 4×4 64QAM system, almost 75% and 80% reduction at SNR=0dB and more than 40% and 50% reduction at SNR=5dB can be achieved, respectively.


---

## Body

## 1. Introduction

Multiple-input multiple-output (MIMO) technology can linearly increase the channel capacity without requiring additional spectral resources. The maximum-likelihood (ML) detection is optimal for achieving the minimum error probability. However, it has an exponential complexity with respect to the order of the modulation and the number of transmit antennas. A few of suboptimal detection algorithms, such as zero forcing (ZF), minimum mean-squared (MMSE), and SIC (serial interference canceling) used in the vertical Bell Laboratories layered space-time (V-BLAST) [1], and so forth, have been proposed. Although these algorithms have low complexity, the achievable performance is bounded away from the performance of the optimum receiver.Sphere detection (SD) algorithm is a tree search strategy that can achieve the exact ML performance while offering a polynomial computational complexity in the average case and is widely considered to be the most promising approach for MIMO detection. In fact, the sphere detector finds the closest lattice point to the received vector but limits the search only in those lattice points that fall within a hyper-sphere centered at the received vector, which results in a considerable reduction in complexity. However, for low SNR or high-order modulations, the complexity of the SD is still high. It has been shown that the computation complexity is highly sensitive to the order of the columns of channel matrix, which is dependent on both the channel matrix and the received signal, even when the efficient SE enumeration strategy [2] is used. Motivated by this observation, some channel matrix preprocessing approaches, such as V-BLAST ordering [1, 3], BSQRD (balanced sorted QR decomposition) ordering [4, 5], and GB (gradient-based) ordering [6], have been proposed to improve the SD efficiency.In this paper, we modify GB ordering and combine it with SIC to propose a new efficient ordering scheme. The simulation results show that the proposed ordering scheme can achieve a significant complexity reduction, especially for high numbers of antennas and large constellation sizes in the low SNR regime.The rest of the paper is organized as follows. Section2 presents the system model and briefly reviews the SD algorithm. Section 3 describes our ordering scheme. Simulation results and discussions are provided in Section 4. Section 5 gives the conclusions.


## 2. System Model and Sphere Detection

Consider an uncoded MIMO system withM transmit and N receive antennas where M≥N. Under the assumption of flat-fading channel, the received vector can be expressed as
(1)y=Hs+w,
where s=[s1,s2,…,sM]T denotes the transmitted vector of dimension M×1, and we suppose that the entries of s are selected from a complex-valued constellation, y=[y1,y2,…,yN]T denotes the received vector of dimension N×1, H is the channel matrix, the elements of H are assumed to be independent and identically distributed (i.i.d.) complex Gaussian variables with zero mean and 0.5 variance, and w is the additive white Gaussian noise (AWGN) with zero mean and σ2 variance.For simplicity, the complex-valued model (1) usually is transformed into a real-valued model, where the dimension is doubled such that  m=2M, n=2N,(2)s=[Re(s)TIm⁡(s)T]T,y=[Re(y)TIm⁡(y)T]T,w=[Re(w)TIm⁡(w)T]T,H=[Re(H)-Im⁡(H)Im⁡(H)Re(H)],
where Re(•) and Im(•) denote the real and imaginary parts of complex numbers, respectively. Assume that perfect channel knowledge is given at the receiver, so the ML detection problem can be formulated as(3)sML=argmin⁡s∈D‖y-Hs‖2,
where D=Am and A is real-valued signal constellation set, for example, A={-3,-1,1,3} for 16-QAM. SD only searches the lattice points inside the hypersphere centered at the received vector with radius d0 instead of searching all lattice points, which can be written as(4)sML=argmin⁡s∈D‖y-Hs‖2≤d02.
Performing QR decomposition upon  H, we can get(5)‖y-Q[R0(n-m)×m]s‖2=‖Q1*y-Rs‖2+‖Q2*y‖2≤d02,
where R is an m×m upper triangular matrix, (•)* denotes Hermitian matrix transposition, and Q=[Q1Q2] is an n×n orthogonal matrix. Q1 and Q2 represent the first m and last n-m orthonormal columns of Q. Here we let d2=d02-∥Q2*y∥2 and  z=Q1*y; thus (4) is equivalent to a new inequality:
(6)sML=argmin⁡s∈D‖z-Rs‖2≤d2;
owing to the upper triangular property of  R, the left-hand side of (6) can be expanded as(7)(zm-rm,msm)2+(zm-1-rm-1,m-1sm-1-rm-1,msm)2+⋯≤d2.
We can get an interval of sm from the first term of (7) and also the intervals of sm-1, sm-2 till s1 by iteration. Therefore, sML can be solved recursively by SD algorithm, using a constrained tree search through n levels, starting from sn down to  s1, as shown in Figure 1.Figure 1
Tree search example for 16QAM system.The SD search process can be described as follows: (1) apply QR decomposition toH such that H=QR, where Q is an m×n orthogonal matrix and R is n×n upper triangular matrix; (2) perform a depth-first constrained tree search through n levels starting from the last component sn of s  down to s1; (3) update the radius d when a point closer to the center is found inside the hypersphere; (4) continue to search with the new radius constraint until the closest point to the center is found. The detection efficiency can be improved by changing the order of columns of channel matrix instead of the original random order from sn down to s1.


## 3. Ordering Schemes

The random decoding order is not the best decoding order, especially for low SNR or high-order modulation. Usually, rearranging the columns of the matrix properly to change the detection order can overcome it. The BSQR and V-BLAST orderings were devised to maximize the minimum of the diagonal elements of upper matrixR, hoping that the width of the intervals will be reduced, and the search tree will be reduced as well. GB ordering is a simple but efficient scheme, in which the soft ZF solutions are taken as the references. However, the noises amplified by the pseudoinverse of channel matrix H make the ZF solutions away from the correct one, especially at low SNR, and thus degrade the efficiency of ordering scheme. Since SD works in a similar way to the successive interference cancelation technique, we modify GB ordering and combine it with SIC to propose a new more efficient ordering scheme, which is described as follows for i=0,2,…,n-1.(1)
SetH0=H,y0=y, and idx=[1,2,…,n].(2)
Calculate the ZF solutionsizf=[(sizf)1,(sizf)2,…,(sizf)n-i]T=Hi†yi, where Hi†=(HiTHi)-1HiT is the pseudoinverse of the ith iteration channel matrix Hi, and, for each element of the solution (sizf)j,j=1,…,n-i, find the ordered set {sj(1),sj(2),…,sj(Q)} such that ∥sj(1)-(sizf)j∥≤∥sj(2)-(sizf)j∥≤⋯≤∥sj(Q)-(sizf)j∥ holds, where sj(q)∈A, q=1,2,…,Q, and Q is the size of real constellation set A.(3)
For each element of the solution(sizf)j, define and compute the gradient g=FX(∥sj(2)-(sizf)j∥), where FX(•) is the accumulated distribution function (CDF) of X which is a Gaussian random variable with zero mean and ∥(Hi†)j∥2σ2 variance, in which (Hi†)j is the jth row of  Hi†.(4)
Computek̂i=argmaxj=1,…,N-iFX(∥sj(2)-(sizf)j∥), and ki=idx(k̂i) is the corresponding column index of channel matrix H. Then circularly shift idx(k̂i:n-i) to the left by 1 for the next iteration.(5)
LetHi+1=Hi(:,idx(1:n-i-1)),yi+1=yi-hkiski(1) to cancel the interference, i=i+1, and repeat (2)–(4) computation steps until i=n-1.(6)
The columns of channel matrix are reordered asH=[hkn-1,hkn-2,…,hk1,hk0].


## 4. Simulation and Complexity Comparisons

In this section, we show the simulated comparisons of average number of visited nodes for4×4, 6×6 16QAM, and 4×4 64QAM systems under five ordering schemes: no ordering (random ordering), V-BLAST ordering, BSQR decomposition ordering, GB ordering, and our proposed ordering. SE enumeration strategy is used in the course of sphere detection under all the ordering schemes. Figure 2 shows the comparison for 4×4 16QAM system; the average number of visited nodes under our proposed ordering is reduced by more than 35% and 38% at SNR = 0 dB and by almost 30% and 33% at SNR = 5 dB, respectively, compared with that under BSQR decomposition and GB orderings. In addition, the more reduction can be observed for 6×6 16QAM, almost 60% and 70% reduction at SNR = 0 dB and 30% and 50% reduction at SNR = 5 dB, respectively, as shown in Figure 3. Moreover, it is shown in Figure 4 that, more complexity reduction can be achieved for 4×4 64QAM system, almost 75% and 80% reduction at SNR = 0 dB and more than 40% and 50% reduction at SNR = 5 dB, respectively.Figure 2
Complexity comparison under five ordering schemes for4×4 16QAM system.Figure 3
Complexity comparison under five ordering schemes for6×6 16QAM system.Figure 4
Complexity comparison under five ordering schemes for4×4 64QAM system.The simulation results clearly show that, under our ordering scheme, an extraordinary detection complexity reduction is realized especially at low and moderate SNRs and high modulation orders.


## 5. Conclusions

A novel ordering scheme combining SIC with GB ordering is proposed to substantially improve the sphere detection efficiency. The proposed ordering is very effective in reducing the SD complexity, especially at low and moderate SNRs and high modulation orders. The simulation results show that our proposed ordering offers extraordinary advantage over V-BLAST ordering, GB ordering, and BSQR decomposition ordering schemes.



---

*Source: 821407-2011-10-19.xml*