A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> K-best detector for sphere decoding <s> Sphere decoding has been suggested by a number of authors as an efficient algorithm to solve various detection problems in digital communications. In some cases, the algorithm is referred to as an algorithm of polynomial complexity without clearly specifying what assumptions are made about the problem structure. Another claim is that although worst-case complexity is exponential, the expected complexity of the algorithm is polynomial. Herein, we study the expected complexity where the problem size is defined to be the number of symbols jointly detected, and our main result is that the expected complexity is exponential for fixed signal-to-noise ratio (SNR), contrary to previous claims. The sphere radius, which is a parameter of the algorithm, must be chosen to ensure a nonvanishing probability of solving the detection problem. This causes the exponential complexity since the squared radius must grow linearly with problem size. The rate of linear increase is, however, dependent on the noise variance, and thus, the rate of the exponential function is strongly dependent on the SNR. Therefore sphere decoding can be efficient for some SNR and problems of moderate size, even though the number of operations required by the algorithm strictly speaking always grows as an exponential function of the problem size. <s> BIB001 </s> A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> K-best detector for sphere decoding <s> Multiple-input multiple-output (MIMO) techniques are a key enabling technology for high-rate wireless communications. This paper discusses two ASIC implementations of MIMO sphere decoders. The first ASIC attains maximum-likelihood performance with an average throughput of 73 Mb/s at a signal-to-noise ratio (SNR) of 20 dB; the second ASIC shows only a negligible bit-error-rate degradation and achieves a throughput of 170 Mb/s at the same SNR. The three key contributing factors to high throughput and low complexity are: depth-first tree traversal with radius reduction, implemented in a one-node-per-cycle architecture, the use of the /spl lscr//sup /spl infin//-instead of /spl lscr//sup 2/-norm, and, finally, the efficient implementation of the enumeration approach recently proposed in . The resulting ASICs currently rank among the fastest reported MIMO detector implementations. <s> BIB002 </s> A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> K-best detector for sphere decoding <s> The number of active users in code-division multiple access (CDMA) systems is often much lower than the spreading gain. The present paper exploits fruitfully this a priori information to improve performance of multiuser detectors. A low-activity factor manifests itself in a sparse symbol vector with entries drawn from a finite alphabet that is augmented by the zero symbol to capture user inactivity. The non-equiprobable symbols of the augmented alphabet motivate a sparsity-exploiting maximum a posteriori probability (S-MAP) criterion, which is shown to yield a cost comprising the l2 least-squares error penalized by the p-th norm of the wanted symbol vector (p = 0, 1, 2). Related optimization problems appear in variable selection (shrinkage) schemes developed for linear regression, as well as in the emerging field of compressive sampling (CS). The contribution of this work to such sparse CDMA systems is a gamut of sparsity-exploiting multiuser detectors trading off performance for complexity requirements. From the vantage point of CS and the least-absolute shrinkage selection operator (Lasso) spectrum of applications, the contribution amounts to sparsity-exploiting algorithms when the entries of the wanted signal vector adhere to finite-alphabet constraints. <s> BIB003 </s> A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> K-best detector for sphere decoding <s> Machine-type communications are quite often of very low data rate and of sporadic nature and therefore not well-suited for nowadays high data rate cellular communication systems. Since signaling overhead must be reasonable in relation to message size, research towards joint activity and data estimation was initiated. When the detection of sporadic multiuser signals is modeled as a sparse vector recovery problem, signaling concerning node activity can be avoided as it was demonstrated in previous works. In this paper we show how well-known K-Best detection can be modified to approximately solve this finite alphabet Compressed Sensing problem. We also demonstrate that this approach is robust against parameter variations and even works in cases where fewer measurements than unknown sources are available. <s> BIB004
The sphere decoder based MUDs are considered to achieve the maximum a posteriori probability (MAP) performance in terms of BER BIB003 . However, there are two main disadvantages of sphere decoding, i.e., it has an exponential complexity BIB001 and it is not possible to parallelize the computations BIB002 . In BIB004 to address these issues, a K-best detection approach is followed. The proposed algorithm reduces the search paths by performing iteratively a breadth-first tree search, which selects only K paths depending on the least metric. Note that in K-best detection, K denotes the number of selected paths and does not represent the number of nodes. The K-best detection reduces the complexity by reducing the number of search paths and facilitates the parallelization of computation by fixing the number of search paths. However, the limited coverage of the search tree results in an error floor and increases the BER. Moreover, for incorporating higher overloading, the number of paths needs to be increased which results in higher complexity.