I Introduction
The multiple-input multiple-output (MIMO) detection problem is a fundamental problem in modern digital communications and plays a pivotal role in various applications [1, 2]. In general, the goal is to recover a vector of transmitted symbols from the output of a linear channel corrupted by the additive Gaussian noise. In this paper, we will focus on the multi-user MIMO setting, where the inputs consist of the symbols transmitted by multiple user terminals (UTs) and the outputs consist of the received signals from the multiple antennas at the base station (BS).
Over the decades, many detection algorithms have been proposed in the literature. The classic sphere decoding algorithm [3] offers an efficient implementation of the maximum-likelihood (ML) detector, which achieves the theoretically optimal vector error probability (VEP) under some mild conditions. However, its expected complexity grows exponentially as the number of UTs increases [4]. There also exist a large branch of suboptimal algorithms that trade performance for complexity. The incomplete list includes the linear detectors, the semidefinite relaxation detectors, and the lattice-reduction aided detectors: we refer the readers to the survey [5] and the references therein. Conventionally, the error performances of these detectors are analyzed in terms of the diversity order [2, 6, 7, 8], which specifies how fast the VEP decays to zero as the signal-to-noise ratio (SNR) tends to infinity.
Recent years have seen revived interest in the signal detection of a large-scale multi-user MIMO system, thanks to the great advances in the massive MIMO technology. In this emerging scenario, the BS is equipped with hundreds of or even thousands of antennas to serve a large number of power-limited UTs simultaneously. The traditional error analysis via the diversity order is not directly applicable here since it usually employs high-SNR approximations. Hence, we propose to study the error performance in the large system regime, where the SNR per UT is kept fixed but the number of receive antennas at the BS grows unbounded [9, 10]. Specifically, we propose a new performance metric termed antenna efficiency that measures how much reduction in the VEP can be expected with an additional receive antenna asymptotically. We analyze the antenna efficiency of the optimal ML detector and the simple zero-forcing (ZF) detector and show that they admit a simple closed form depending on the UT-to-antenna ratio, the SNR, and the constellation set.
We adopt the following standard notations in this paper. We use to denote the -th entry of a vector and to denote the -th entry of a matrix . We use to denote the modulus of a complex number, to denote the conjugate transpose, and to denote the Euclidean norm of a vector. The symbol denotes the identity matrix. denotes the expectation operator, and sometimes
is used to stress that the expectation is taken with respect to the random variable
. The moment-generating function (MGF) of a random variable
is defined as . We use and to denote the unconditional and conditional probability, respectively. We use to denote the distribution of a circular symmetric complex Gaussian random vector with zero mean and covariance matrix .Ii System Model and Problem Formulation
Ii-a System Model
Consider a multi-user MIMO system consisting of UTs with a single antenna and a BS with antennas. Throughout the paper, we assume that . The received signal vector at the BS is given by
(1) |
where is a complex channel matrix, is the vector of transmitted symbols, and is the vector of additive white Gaussian noises. The -th column of , denoted by , represents the channel from UT to the BS. We further assume that all entries of are independent and identically distributed (i.i.d.) following , and all entries of are i.i.d. following . We define the SNR as the received SNR per UT:
(2) |
The transmitted symbols are drawn from a constellation set of size . Our results apply to an arbitrary constellation set, including the -PSK constellation and the -QAM constellation. In particular, the key quantity that plays a crucial role in our analysis is the minimum distance of defined as
Intuitively, the minimum distance affects the “hardness” of the detection problem: a larger implies that the symbols are separated further from each other and hence easier to distinguish and detect.
Ii-B Two MIMO Detectors
Given the received signal vector and the channel realization , a MIMO detection algorithm outputs
as an estimate of
. The goal is to minimize the VEP defined as . In this paper, we will focus on two well-studied detectors: the ML detector and the ZF detector.The ML detector is given by
(3) |
Under the assumption that the UTs choose their transmitted symbols from
uniformly and independently, the ML detector is known to be optimal in terms of achieving the minimum possible VEP. However, the combinatorial optimization problem in (
3) is strongly NP-hard [11] and hence the computational cost of globally solving it can be prohibitively high especially when the number of UTs is large. Still, it can serve as a benchmark for other detection algorithms.The ZF detector belongs to the family of linear detectors and is computationally cheap. It first multiplies the received symbol vector by the pseudoinverse of to get
(4) |
and then maps each entry of the decorrelated signals to the nearest constellation symbol in :
(5) |
Due to its simplicity, the ZF detector often allows closed-form theoretical results and is thoroughly investigated in the literature [2].
Ii-C Antenna Efficiency
In general, the exact VEP of a MIMO detector is intractable and hence it is common to rely on asymptotic analysis. A classic performance metric is the diversity order
[2] defined by(6) |
and it characterizes the rate at which the VEP tends to zero in the high SNR regime. Specifically, the diversity analysis implies that the VEP of the detector should scale as at high SNR. It is known that the ML detector enjoys diversity order of [12, 13], while the ZF detector only achieves diversity order of [6].
In this paper, we take an alternative view and study how the VEP behaves in the large system limit, where the number of antennas grows infinitely large while the ratio tends to . This includes the special case where the number of UTs remains fixed by letting . Analogous to the definition of diversity order in (6), we define
(7) |
Roughly speaking, with (7) we shall have , which means that each additional antenna at the BS will bring dB decrease in the VEP. In this sense, characterizes how efficiently we can reduce the VEP by increasing the number of antennas, and hence we name it as antenna efficiency. As it will become more clear, the antenna efficiency in (7) is a function of the ratio
, the noise variance
, and the constellation set . In the following, we will quantify such dependence and give the antenna efficiency of the ML and ZF detectors in simple closed form.It is worth mentioning that some researchers have also considered MIMO detection in the large system limit [14, 15, 16], but with different channel models from ours. More specifically, they assumed that the entries of are i.i.d. real/complex zero-mean Gaussian random variables with variance either (i.e., the total transmitted power is fixed) or (i.e., the received power per UT is fixed). This difference leads to a very different asymptotic behavior: instead of tending to zero at an exponential rate, the VEP is shown to converge to a nonzero limit when goes to infinity. We justify our system model in twofold. First, for a multi-user MIMO system, it is reasonable to assume that the UTs have individual power supplies and the captured energy at the BS increases linearly with the number of antennas . Such assumptions are also widely adopted in the literature [9, 10]. Second, our analysis appears more elementary, whereas the existing works involve more sophisticated tools such as the replica method [14] and the Gaussian comparison inequalities [16]. This simplicity also enables us to generalize our results to the spatially correlated channel as in [9] and possibly other problems in the massive MIMO system such as symbol-level precoding [17], which we will put as future works.
Iii Antenna Efficiency of ML Detector
In this section, we characterize and prove the antenna efficiency of the ML detector.
Theorem 1.
Consider the MIMO system in (1). Assume that the entries of are i.i.d. following , the entries of are i.i.d. following , and the entries of are drawn uniformly and independently from the constellation set with minimum distance . Then for the ML detector in (3), its antenna efficiency is given by
(8) |
Theorem 1 offers a simple formula for and shows that it is determined by the quantity , which can be regarded as the effective detection SNR. Also, note that is independent of the UT-to-antenna ratio . Since a larger means more UTs in the system and hence higher interference, we deduce that the ML detector is able to suppress the multi-user interference effectively.
To prove Theorem 1, we first derive a lower bound on the VEP by assuming no multi-user interference, and then provide a matching upper bound by using the union bound.
Iii-a No-Interference Lower Bound
Note that for all . Hence, in the following we will lower bound , which in turn results in a lower bound on the VEP.
Without loss of generality, let . To derive a lower bound, imagine that all the transmitted symbols except are known. Equivalently, this can be interpreted as the idealistic assumption that the interference caused by transmissions from other UTs is perfectly cancelled out. In this case, the detection of reduces to a single-input multiple-output detection problem
(9) |
where . Furthermore, it can be shown that the vector detection in (9) is equivalent to a scalar detection problem [2, Sec. A.2.3]:
where the variance of the equivalent noise is given by . It follows from standard results on scalar detection [18, Sec. 4.2] that
(10) |
where the -function is .
It remains to take the expectation over . Note that is a chi-square random variable with degrees of freedom, i.e., . Hence, its MGF can be computed as . Using the Craig’s representation of [19], i.e.,
and exchanging the order of expectation and integration, from (10) we get
Combining this with Wallis’ formula [20]
yields
It follows immediately from the definition in (7) that
Iii-B Union Upper Bound
From (3), we can see that the ML detector fails to recover the true transmitted signal vector only if there exists different from such that . Therefore, we define the pairwise error probability as
and the union bound leads to
(11) |
Now we take a closer look at the pairwise error probability. Conditioned on , it corresponds to a detection problem with a binary symbol set . Hence, we have
(12) |
where we used the standard inequality
(13) |
To average over the randomness of , we write
where by our assumption are i.i.d. following . Hence, is a complex Gaussian random vector with zero mean and covariance matrix being , which implies that . By this and using its MGF, we get from (12) that
(14) |
Now we distinguish two cases: remains bounded as tends to infinity, or also grows unbounded. In the first case, since is different from in at least one entry, we have . Then (11) and (14) lead to
Since both and are upper bounded by some absolute constant independent of , we arrive at
(15) |
The second case requires more refined analysis. If is different from in entries, then . By grouping according to the number of incorrect entries, the union bound (11) and (14) result in
(16) |
Recall that we always assume . Hence, when is large enough, we can expect that the first summand (i.e., the term corresponding to ) in the right-hand side of (16) will dominate. The following lemma formalizes this observation.
Lemma 2.
Let . If is larger than
then we have
Iv Antenna Efficiency of ZF Detector
In this section, we will characterize and prove the antenna efficiency of the ZF detector.
Theorem 3.
Compared with (8), the suboptimality of the ZF detector is reflected in the coefficient . On the one hand, when the number of antennas is much larger than the number of UTs , the ratio is close to 0 and the ZF detector should achieve near-optimal antenna efficiency as the ML detector. On the other hand, when scales linearly with , the performance of the ZF detector deteriorates due to the multi-user interference.
Similar to Section III, we prove Theorem 3 by deriving matching lower and upper bounds on the VEP. We first write the decorrelated signal vector in (4) as
(18) |
where . We can see from (5) and (18) that the ZF detector transforms the MIMO channel into parallel scalar channels and decides the transmitted symbol of each UT separately. Hence, it is easier to analyze the symbol error probability , which is related to the VEP by
(19) |
Moreover, since the UTs’ channels are statistically equivalent, we have for all and (19) further reduces to
(20) |
Conditioned on , the equivalent noise vector
follows a complex Gaussian distribution with zero mean and covariance matrix being
Hence, the first UT sees a scalar channel with the equivalent noise variance . Following standard results on scalar detection [18], we have
(21) | ||||
(22) |
where .
V Numerical Results
In this section, we present some numerical results to validate our analysis. In our simulations, the constellation set is normalized such that for all and hence (cf. (2)). We test the impacts of the UT-to-antenna ratio , the SNR, and the constellation set on the VEP. The results are shown in Figs. 1–3 respectively, where each data point is the average of 10,000 random instances.
By the definition in (7), we can view the antenna efficiency as the negative slope of the VEP (in the log scale) versus the number of receive antennas in the large system limit. Fig. 1 shows that while a smaller ratio leads to a steeper slope for the ZF detector, it does not affect the ML detector in terms of the asymptotic performance. Also, when the number of UTs is fixed, which corresponds to , the ZF detector can achieve the optimal antenna efficiency as predicted by our analysis. On the other hand, from Fig. 2 and Fig. 3, we can see that both the ZF and ML detectors can benefit from a higher SNR or a constellation set with a larger minimum distance.
To compare our theoretical analysis with the empirical results, in Figs. 1–3 we also plot the dotted lines with the slopes given by (8) or (17) alongside the corresponding VEP curves. From the figures, we can observe that the empirical VEP agrees well with our analysis across various settings. Despite the asymptotic nature of our analysis, the VEP exhibits an exponential decay with a moderate number of antennas.
References
- [1] S. Verdú, Multiuser Detection. New York: Cambridge University Press, 1998.
- [2] D. Tse and P. Viswanath, Fundamentals of Wireless Communication. New York: Cambridge University Press, 2005.
- [3] O. Damen, A. Chkeif, and J.-C. Belfiore, “Lattice code decoder for space-time codes,” IEEE Commun. Lett., vol. 4, no. 5, pp. 161–163, 2000.
- [4] J. Jaldén and B. Ottersten, “On the complexity of sphere decoding in digital communications,” IEEE Trans. Signal Process., vol. 53, no. 4, pp. 1474–1484, 2005.
- [5] S. Yang and L. Hanzo, “Fifty years of MIMO detection: The road to large-scale MIMOs,” IEEE Commun. Surveys Tuts., vol. 17, no. 4, pp. 1941–1988, 2015.
- [6] J. Winters, J. Salz, and R. Gitlin, “The impact of antenna diversity on the capacity of wireless communication systems,” IEEE Trans. Commun., vol. 42, no. 2/3/4, pp. 1740–1751, 1994.
- [7] J. Jalden and B. Ottersten, “The diversity order of the semidefinite relaxation detector,” IEEE Trans. Inf. Theory, vol. 54, no. 4, pp. 1406–1422, 2008.
- [8] Y. H. Gan, C. Ling, and W. H. Mow, “Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection,” IEEE Trans. Signal Process., vol. 57, no. 7, pp. 2701–2710, 2009.
- [9] S. Wagner, R. Couillet, M. Debbah, and D. T. M. Slock, “Large system analysis of linear precoding in correlated MISO broadcast channels under limited feedback,” IEEE Trans. Inf. Theory, vol. 58, no. 7, pp. 4509–4537, 2012.
- [10] J. Hoydis, S. ten Brink, and M. Debbah, “Massive MIMO in the UL/DL of cellular networks: How many antennas do we need?” IEEE J. Sel. Areas Commun., vol. 31, no. 2, pp. 160–171, 2013.
- [11] S. Verdú, “Computational complexity of optimum multiuser detection,” Algorithmica, vol. 4, no. 1, pp. 303–312, 1989.
- [12] R. van Nee, A. van Zelst, and G. Awater, “Maximum likelihood decoding in a space division multiplexing system,” in Proc. IEEE Veh. Technol. Conf., vol. 1, Tokyo, Japan, May 2000, pp. 6–10.
- [13] X. Zhu and R. Murch, “Performance analysis of maximum likelihood detection in a MIMO antenna system,” IEEE Trans. Commun., vol. 50, no. 2, pp. 187–191, 2002.
- [14] T. Tanaka, “A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors,” IEEE Trans. Inf. Theory, vol. 48, no. 11, pp. 2888–2910, 2002.
- [15] C. Jeon, R. Ghods, A. Maleki, and C. Studer, “Optimality of large MIMO detection via approximate message passing,” in Proc. IEEE Int. Symp. on Inf. Theory, Hong Kong, China, Jun. 2015, pp. 1227–1231.
- [16] C. Thrampoulidis, W. Xu, and B. Hassibi, “Symbol error rate performance of box-relaxation decoders in massive MIMO,” IEEE Trans. Signal Process., vol. 66, no. 13, pp. 3377–3392, 2018.
- [17] M. Alodeh, D. Spano, A. Kalantari, C. G. Tsinos, D. Christopoulos, S. Chatzinotas, and B. Ottersten, “Symbol-level and multicast precoding for multiuser multiantenna downlink: A state-of-the-art, classification, and challenges,” IEEE Commun. Surveys Tuts., vol. 20, no. 3, pp. 1733–1757, 2018.
- [18] J. Proakis and M. Salehi, Digital Communications. New York, NY: McGraw-Hill, 2008.
- [19] J. Craig, “A new, simple and exact result for calculating the probability of error for two-dimensional signal constellations,” in Proc. MILCOM Conf., McLean, VA, USA, Nov. 1991, pp. 571–575.
- [20] D. K. Kazarinoff, “On Wallis’ formula,” Edinburgh Math. Notes, vol. 40, pp. 19–21, 1956.
- [21] Y. Jiang, M. K. Varanasi, and J. Li, “Performance analysis of ZF and MMSE equalizers for MIMO systems: An in-depth study of the high SNR regime,” IEEE Trans. Inf. Theory, vol. 57, no. 4, pp. 2008–2026, 2011.
Comments
There are no comments yet.