Efficient Near-Optimal Detection with Generalized Sphere Decoder for Blind MU-MIMO Systems
Efficient Near-Optimal Detection with Generalized Sphere Decoder for Blind MU-MIMO Systems
ETRI Journal. 2014. Jun, 36(4): 682-685
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : October 23, 2013
  • Accepted : January 22, 2014
  • Published : June 01, 2014
Export by style
Cited by
About the Authors
Minjoon Kim
Jangyong Park
Hyunsub Kim
Jaeseok Kim

In this letter, we propose an efficient near-optimal detection scheme (that makes use of a generalized sphere decoder (GSD)) for blind multi-user multiple-input multiple-output (MU-MIMO) systems. In practical MU-MIMO systems, a receiver suffers from interference because the precoding matrix, the result of the precoding technique used, is quantized with limited feedback and is thus imperfect. The proposed scheme can achieve near-optimal performance with low complexity by using a GSD to detect several additional interference signals. In addition, the proposed scheme is suitable for use in blind systems.
I. Introduction
In multi-user multiple-input multiple-output (MU-MIMO) systems, such as those covered by the IEEE 802.11ac standard [1] , a base station (BS) communicates with multiple users. As this configuration causes each user to receive interference signals generated by other users, the BS must employ a channel information–based precoding technique [2] that nullifies these interference signals. Owing to limited feedback [3] , however, the precoding matrix is not perfect in practical situations and allows the reception of weakened interference signals. In systems with large numbers of users, the sum of these weakened interference signals can be large enough to degrade performance and induce an error floor. As such, each MU-MIMO system user must consider received interference signals to achieve sufficient performance.
Several types of interference-aware receiver systems have already been developed. Joint maximum-likelihood detection (JMLD) is a multi-user detection (MUD) scheme designed to achieve optimal performance [4] ; however, its complexity is high and increases exponentially with the number of users. Lower-complexity receivers based on linear techniques have also been proposed but are not considered here because they cannot achieve near-optimal performance.
In this letter, we propose a method for achieving near-optimal performance of blind MU-MIMO systems with low complexity through the use of sphere decoding (SD) [5] . Because rank-deficiency problems occur in MU-MIMO systems, we propose to apply a generalized sphere decoding (GSD) algorithm [6] to implement MUD. The proposed scheme can achieve near-optimal performance with much lower complexity in comparison to a JMLD scheme. This result is based on the fact that to attain low complexity it need only detect a few interference signals. To enable its use in blind systems (that is, those in which each user cannot know the modulation type of other users) it detects interference signals with a predefined modulation type.
II. System Model and Maximum Likelihood Detection (MLD)
- 1. MU-MIMO System
In this letter, we consider an MU-MIMO downlink channel consisting of a single BS with NT antennas and K users each having NR antennas. For this system, the NR × 1 vector, y i , of signals received by user i can be expressed as
y i = H i V ^ x+ n i
= H i V ^ i x i + j=1,ji K H i V ^ j x j + n i
= H i ( V i + E i ) x i Desired  signal + j=1,ji K H i E j x j Interference  signal + n i ,
where H i is the NR × NT channel matrix corresponding to user i ,
V ^
is the NT × NT practical precoding matrix, x is the NT × 1 data vector, and n i is an independent and identically distributed complex zero-mean Gaussian noise with variance σ 2 . In (3),
V ^
is represented as
V ^
= V+E , where V is the block diagonal precoding matrix given in [2] and E is the quantization error (QE) matrix from limited feedback. If V , E , and x are composed of K users, as in V = [ V 1 ... V K ], E = [ E 1 ... E K ], and x = [ x 1 T ... x K T ] T , then (1) can be rewritten as (2). Finally, because H i V j = 0 for i j as in [2] , (2) can be rewritten as (3). For simplicity, (3) can be represented as
y i = H D x i + H I x I + n i
where H D = H i ( V i + E i ), H I = [ H i E 1 H i E j ], and x = [ x 1 T ... x j T ] T for j = 1, …, K for j i .
- 2. MLD and JMLD
The MLD method used to perform single-user detection (SUD) is represented by
x ^ i,ML = argmin x i Ω N R y i H D x i 2 ,
where Ω N is the set of all possible candidates for the N -element transmitted data vector x . While (5) considers only desired signals, the JMLD proposed in [5] also considers interference signals and can be represented by
[ x ^ i,JML T x ^ I,JML T ] T = argmin x i Ω N R x I Ω N T N R y i H D x i H I x I 2 .
JMLD has optimal performance in MUD because it mitigates interference signals by detecting them simultaneously.
III. Proposed MUD Algorithm
- 1. SD Approach to MUD
SD is a low-complexity method for finding a maximum likelihood solution. In SUD systems, SD uses R , an upper triangular matrix for which R H R = H D H H D , which can be obtained by Cholesky decomposition. Using R , (5) can be rewritten as
x ^ i,SD = argmin x i Ω N R R( x ¯ i x i ) 2 ,
x ¯ i
= ( R H R ) –1 H D H y i . Although SD can help to reduce the number of nodes visited in tree searching, it causes rankdeficiency problems to occur in MUD. The reason these problems occur is that R cannot be constructed from
H ˜
= [ H D H I ], which is an NR × NT matrix and NR (representing the number of antennas per user) is usually less than NT . In other words, as
H ˜ H H ˜
is not of full rank, R has zero-values over NR rows. We can solve this problem by adapting the GSD method proposed by Cui [6] for rank-deficient MIMO systems. GSD forms
R ˜
by adding the product of the unit matrix and the noise variance to
H ˜ H H ˜
, allowing (7) to be rewritten as
[ x ^ i,GSD T x ^ I,GSD T ] T = argmin x i Ω N R x I Ω N T N R R ˜ ( x ¯ [ x i T x I T ] T ) 2 ,
R ˜ H R ˜  =  H ˜ H H ˜  +  σ 2 I
x ¯  =  ( R ˜ H R ˜ ) −1 H ˜ H y i .
Although a small degree of performance degradation is caused by the additive term, SD can be successfully conducted using (8). We previously introduced this concept in [7] and evaluated its performance under the IEEE 802.11ac standard but did not consider a blind system. However, as many MU-MIMO systems are blind systems, we propose the improved techniques in this letter.
- 2. Interference Detection
Although (8) has a much lower complexity than (6), we propose two further techniques — one to reduce complexity and the other for use in blind systems. For better understanding, we illustrate the concepts of the proposed techniques using single-symbol detection in Fig. 1 . As shown in Fig. 1(a) , the original signal point is affected by interference signals and causes detection errors.
First, we propose that sufficiently high performance can be achieved by detecting only several interference signals (see Fig. 1(b) ). Of course, detecting all interference signals is good for performance (error rate); however, this does lead to high complexity. So, we propose that detecting only some of the interference signals is enough to have good performance and at the same time achieve low complexity. Therefore, we can avoid detection errors in the desired signals if we manage to reduce the sum of these interference signals. For this purpose, we propose to select the N Intf most influential signals from the arranged channel matrix H I,ordered , which is ordered by the descending channel norm. We can reconstruct
H ˜
, consisting of the channel matrices for the desired signals and the N Intf selected interference signals, as
H ˜ =[ H D   [ H I,ordered ] 1 N Intf ],
[ H ] 1 M
contains the column entries of H from 1 to M . Obtaining
R ˜
and performing GSD are done as they were in (8), except that x I ∈ Ω NIntf .
The second proposed technique is detecting interference signals by assuming a predefined modulation type, regardless of the actual types used. Because many MU-MIMO systems are blind systems, such as the IEEE 802.11ac standard, they cannot detect interference signals using their own modulation types. However, we propose that rough detection is enough to mitigate interference because a user does not need to decode bit information for other users’ signals. Although rough interference detection still incurs errors, the sum of these errors can be reduced sufficiently to allow for accurate detection (as shown in Fig. 1(c) ). In the quadrature amplitude modulation (QAM) scheme, each modulation type has a similar square pattern. As such, each can be used for the rough detection of each other because the scale is normalized to approximately one. Thus, we can set a predefined modulation type for interference signals to conduct rough detection. As we explained, interference signals are much smaller than desired signals, and our detection goal is not to decode them but to reduce their sum. Therefore, interference detection using a predefined modulation type can achieve near-identical performance to that used in a non-blind system.
PPT Slide
Lager Image
MUD concept with one desired signal and three interference signals: (a) no detection of interference — that is, SUD; (b) ideal detection of two interference signals; and (c) rough detection of two interference signals.
To summarize, the proposed detection scheme uses two variables: N Intf , the number of interference signals to be detected; and QAM Intf , the number of constellation points used by the predefined modulation type. Figure 2 shows the proposed MUD scheme, which first detects desired signals at high levels and then detects N Intf interference signals with QAM Intf points at low levels.
PPT Slide
Lager Image
Proposed MUD scheme with QAMIntf = 4 for 16 QAM desired signals.
IV. Simulation Results
Computer simulations based on the IEEE 802.11ac standard in channel model D [1] were conducted to evaluate the proposed MUD scheme. The simulations considered an MUMIMO system: a 4 × [2, 2] system comprising a BS with four antennas and two users with two antennas each. The bandwidth and guard interval length were 160 MHz and 800 ns, respectively. Channel coding and decoding were used with convolution encoding (with 3/4 coding rates) and Viterbi decoding (with hard detection and 80 trace-back depth). We assumed that, in all cases, all users were located equidistantly from the BS. We consider two scenarios with 16 QAM and 64 QAM modulation types. For the sake of simplicity, we assumed that all users used the same modulation type (in real systems, other modulation types can be used in various combinations). To construct a practical environment, we created a QE by using a limited number of feedback quantization bits ( ψ = 4 and ϕ = 6), as indicated in the IEEE 802.11ac standard, and channel estimation error (CEE) by using a least square channel estimation method. However, our basic scenario is with QE and without CEE. The proposed MUD scheme was tested at various values of N Intf and QAM Intf . For SD pruning, we used the Schnorr–Euchner enumeration [5] . Here, we present the performance of the SD and JMLD methods together, as they have optimal SUD and MUD performance, respectively. We assumed a non-blind system for the JMLD method. However, the proposed scheme assumed a blind system and used QAM Intf .
Figure 3 shows a plot of the bit error rate (BER) performance versus the bit energy-to-noise ratio ( E b / N 0 ) of JMLD, SD, and the proposed scheme (in ( N Intf , QAM Intf ) format). We present 16 QAM and 64 QAM scenarios in the QE situation. In addition, for the 16 QAM scenario, we consider a “No QE & CEE” situation and a “QE & CEE” situation. From the QE situation in Fig. 3 , it is found that the proposed MUD scheme achieves near performance to JMLD and much better performance than SD for both the different modulation types. In addition, it is observed that the BER performance depends more on N Intf than on QAM Intf ; this reinforces the fact that the exact value of QAM Intf is not very important in MUD. For the same N Intf , the exact QAM Intf exhibits the best performance. We also can evaluate how the practical error (QE & CEE) affects BER performance by making comparisons with the “No QE & CEE” and the “QE & CEE” situations in Fig. 3 . For the “No QE & CEE” situation, SD is the same as JMLD and an error floor is not observed. The “QE & CEE” situation exhibits a lower, but similar, BER performance than the QE situation. In addition, the performance of the proposed method is close to the QE situation as E b / N 0 increases.
PPT Slide
Lager Image
BER performance for 4 × [2, 2] systems in the cases of 16 QAM and 64 QAM.
For tree searching–based algorithms, such as SD, there is no closed-form method for calculating complexity; instead, the number of nodes visited is often used. We list the number of nodes visited for the SD and proposed MUD schemes for E b / N 0 =20 dB in Table 1 . As N Intf and QAM Intf increase, the number of nodes visited (see Table 1 ) increases. The data in Table 1 suggests that the proposed MUD scheme has a little more complexity than SD. Although the numerical values in Table 1 are different for different simulation conditions, our proposed MUD scheme is assured of achieving optimal MUD performance with low complexity.
Average number of nodes visited.
Detection scheme Scenario
16 QAM 64 QAM
SD [5] 10.2 12.9
Proposed(NIntf, QAMIntf) (1, 4)/(2, 4) 19.2/30.4 20.6/31.3
(1, 16)/(2, 16) 20.1/34.5 21.9/34.9
(1, 64)/(2, 64) X 22.5/39.7
V. Conclusion
In this paper, we considered an efficient MUD scheme to achieve near-optimal performance for blind MU-MIMO systems. For the problem of rank deficiency, we applied the GSD scheme for MUD. Further, we propose to use two parameters — the number of interference signals detected and the modulation type used to detect the interference signals — to lower complexity and for use in blind systems, respectively. As a result, the proposed MUD scheme achieves near-optimal performance with much lower complexity than JMLD. Furthermore, the proposed scheme is suitable to use in blind systems.
This work was supported by IT R&D program of MOTIE/KIET [10035389, Research on high speed and low power wireless communication SoC for high resolution video information mining]. This work was also supported by System LSI Division in Samsung Electronics Co., LTD.
2012 IEEE Std. IEEE 802.11ac/D2.0 Draft Standard for Information Technology IEEE
Spencer Q.H. , Swindlehurst A.L. , Haardt M. 2004 “Zero-Forcing Methods for Downlink Spatial Multiplexing in Multiuser MIMO Channels,” IEEE Trans. Signal Process. 52 (2) 461 - 471    DOI : 10.1109/TSP.2003.821107
Love D.J. 2008 “An Overview of Limited Feedback in Wireless Communication Systems,” IEEE J. Sel. Areas Commun. 26 (8) 1341 - 1365    DOI : 10.1109/JSAC.2008.081002
Lee J. , Toumpakaris D. , Yu W. 2011 “Interference Mitigation via Joint Detection,” IEEE J. Sel. Areas Commun. 29 (6) 1172 - 1184    DOI : 10.1109/JSAC.2011.110606
Schnorr C.P. , Euchner M. 1994 “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problem,” Math. Programm. 66 (1-3) 181 - 199    DOI : 10.1007/BF01581144
Cui T. 2005 “An Efficient Generalized Sphere Decoder for Rank-Deficient MIMO Systems,” IEEE Commun. Lett. 9 (5) 423 - 425    DOI : 10.1109/LCOMM.2005.1431159
Park J. 2013 “A High Performance MIMO Detection Algorithm for DL MU-MIMO with Practical Errors in IEEE 802.11ac Systems,” IEEE PIMRC London, UK 78 - 82    DOI : 10.1109/PIMRC.2013.6666108