A low-complexity SISO multiuser detector for iterative decoding of asynchronous CDMA systems with convolutional codes

The optimal decoding scheme for asynchronous code-division multiple-access (CDMA) systems that employ convolutional codes results in a prohibitive computational complexity. To reduce the computational complexity, an iterative receiver structure was proposed for decoding multiuser data in a convolutional coded CDMA system. At each iteration, extrinsic information is exchanged between a soft-input soft-output (SISO) multiuser detector and a bank of single-user SISO channel decoders. A direct implementation of the optimal SISO multiuser detector, however, has exponential computational complexity in terms of the number of users which is still prohibitive for channels with a medium to large number of users. This paper presents a low-complexity SISO multiuser detector using the decision-feedback scheme, of which tentative hard decisions are made and fed back to the SISO multiuser from the previous decoding output. In the proposed scheme, the log-likelihood ratios (LLR) as well as the tentative hard decisions of code bits are fed back from the SISO decoders. The hard decisions are used to constrain the trellis of the SISO multiuser detector and the LLRs are used to provide a priori information on the code bits. The detector provides good performance/complexity tradeoffs. The computational complexity of the detector can be set to be as low as linear in the number of users. Simulations show that the performance of the low-complexity SISO multiuser detector approaches that of the single-user system for moderate to high signal-to-noise ratios even for a large number of users.     

Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints

Multiuser orthogonal frequency division multiplexing (MU-OFDM) is a promising technique for achieving high downlink capacities in future cellular and wireless local area network (LAN) systems. The sum capacity of MU-OFDM is maximized when each subchannel is assigned to the user with the best channel-to-noise ratio for that subchannel, with power subsequently distributed by water-filling. However, fairness among the users cannot generally be achieved with such a scheme. In this paper, a set of proportional fairness constraints is imposed to assure that each user can achieve a required data rate, as in a system with quality of service guarantees. Since the optimal solution to the constrained fairness problem is extremely computationally complex to obtain, a low-complexity suboptimal algorithm that separates subchannel allocation and power allocation is proposed. In the proposed algorithm, subchannel allocation is first performed by assuming an equal power distribution. An optimal power allocation algorithm then maximizes the sum capacity while maintaining proportional fairness. The proposed algorithm is shown to achieve about 95% of the optimal capacity in a two-user system, while reducing the complexity from exponential to linear in the number of subchannels. It is also shown that with the proposed resource allocation algorithm, the sum capacity is distributed more fairly and flexibly among users than the sum capacity maximization method.     

Near-ML multiuser detection with linear filters and reliability-based processing

The prohibitive - exponential in the number of users - computational complexity of the maximum-likelihood multiuser detector for direct-sequence code-division multiple-access communications has fueled an extensive research effort for the development of low-complexity multiuser detection alternatives. We show that we can efficiently and effectively approach the error rate performance of the optimum multiuser detector as follows. We utilize a multiuser zero-forcing or minimum mean-square error (MMSE) linear filter as a preprocessor and we establish that the output magnitudes, when properly scaled, provide a reliability measure for each user bit decision. Then, we prepare an ordered, reliability-based error search sequence of length linear in the number of users; it returns the most likely user bit vector among all visited options. Numerical and simulation studies for moderately loaded systems that permit exact implementation of the optimum detector indicate that the error rate performance of the optimum and the proposed detector are nearly indistinguishable over the whole predetection. signal-to-noise ratio range of practical interest. Similar studies for higher user loads (that prohibit comparisons with the optimum detector) demonstrate error rate performance gains of orders of magnitude in comparison with straight decorrelating or MMSE multiuser detection.     

A reduced-complexity maximum-likelihood method for multiuser detection

Multiuser or joint detection has recently been receiving significant research interest because of its potential for the significant increase in system capacity and performance. Among the conventional multiuser detection schemes such as the minimum mean-squared error and successive interference cancellation-based ones, maximum-likelihood multiuser detection has the best system performance. However, the complexity of maximum-likelihood detection (MLD) increases exponentially in the number of users and constellation size. In this paper, a low-complexity MLD scheme based on the use of a sensitive-bits algorithm is proposed. It is demonstrated that the proposed method can greatly reduce the computational complexity with a minimal penalty in performance compared with the exhaustive optimal MLD scheme.     

Blind multiuser detection in uplink CDMA with multipath fading: a sequential EM approach

We consider joint channel estimation and data detection in uplink asynchronous code-division multiple-access systems employing aperiodic (long) spreading sequences in the presence of unknown multipath fading. Since maximum-likelihood (ML) sequence estimation is too complex to perform, multiuser receivers are proposed based on the sequential expectation-maximization (EM) algorithm. With the prior knowledge of only the signature waveforms, the delays and the second-order statistics of the fading channel, the receivers sequentially estimate the channel using the sequential EM algorithm. Moreover, the snapshot estimates of each path are tracked by linear minimum mean-squared error filters. The user data are detected by a ML sequence detector, given the channel estimates. The proposed receivers that use the exact expressions have a computational complexity O(2/sup K/) per bit, where K is the number of users. Using the EM algorithm, we derive low-complexity approximations which have a computational complexity of O(K/sup 2/) per bit. Simulation results demonstrate that the proposed receivers offer substantial performance gains over conventional pilot-symbol-assisted techniques and achieve a performance close to the known channel bounds. Furthermore, the proposed receivers even outperform the single-user RAKE receiver with Nyquist pilot-insertion rate in a single-user environment.     

A soft decoding scheme for vector quantization over a CDMA channel

The optimal decoding of vector quantization (VQ) over a code-division multiple-access (CDMA) channel is too complicated for systems with a medium-to-large number of users. This paper presents a low-complexity, suboptimal decoder for VQ over a CDMA channel. The proposed decoder is built from a soft-output multiuser detector, a soft bit estimator, and the optimal soft VQ decoding of an individual user. Simulation results obtained over both additive white Gaussian noise and flat Rayleigh fading channels show that with a lower complexity and good performance, the proposed decoding scheme is an attractive alternative to the more complicated optimal decoder.     

空间相关信道下的交替多用户调度算法

针对多用户多输入多输出（MIMO）系统,研究了空间相关信道下的多用户调度问题。通过推导用户信道向量夹角的统计特征,分析了多用户调度算法对所调度用户间正交性的影响。分析结果表明在空间相关信道下现有基于串行搜索的调度方法在统计意义上降低了被调度用户之间的正交性,从而导致基于串行搜索的调度算法与最优的穷举搜索之间存在较大的性能差距。为了提高相关信道下多用户MIMO系统的性能,提出了一种基于交替搜索的多用户调度算法及其低复杂度实现方法。仿真结果表明,所提出的用户调度算法能够有效地弥补基于串行搜索的调度方法的性能损失,在空间独立信道和空间相关信道下以较低的计算复杂度获得接近穷举搜索的最优性能。      

A new construction of signature waveforms for synchronous CDMA systems

We consider synchronous code-division multiple access (CDMA) systems over an additive white Gaussian noise (AWGN) channel, where all users are divided into groups of small size. The signature waveforms for users in each group are constructed from the same signature sequence but with different chip waveforms. To minimize the multiple access interference (MAI) at the output of the correlators, Welch-bound-equality (WBE) sequences and chip waveforms having optimal correlation property are employed. The main idea behind the proposed construction is to suppress the inter-group interference from users in different groups as much as possible (even to remove it completely) at the expense of introducing the intra-group interference among the users in the same group. The intra-group interference, however, can be easily handled by a low-complexity, optimal (or suboptimal) multiuser detector(s) if the group size is kept small enough. As special cases, the proposed constructions correspond to the optimal design of the signature waveforms and the conventional system that uses a single chip waveform, respectively. Thus the proposed construction offers a flexibility to trade performance for complexity. In particular, it is demonstrated that, while the conventional system's error performance is very sensitive to even a small amount of overload, the proposed system with two users per group can have up to 100% overload with an excellent error performance.     

Structured multiuser channel estimation for block-synchronousDS/CDMA

Uplink channel estimation for a block-synchronous chip-asynchronous DS/CDMA system as proposed for the time-division duplex option of third-generation cellular systems is considered. Training midambles are employed for joint channel estimation of all users. The standard unstructured approach based on modeling the effective user channels as unknown FIR filters is compared with two structured methods that exploit a priori knowledge about the user channels such as the maximum delay-spread, the transmit chip-shaping pulse and the path delays. Since these are usually unknown, a low-complexity estimator for the path delays of all users is derived from a maximum-likelihood approach. For all channel estimators, optimal sets of training sequences based on perfect root-of-unity sequences are found. For these optimal sets, it is shown that the reduction in channel estimation mean-squared error of the structured estimator versus the unstructured estimator is exactly the ratio of the number of structured parameters to unstructured parameters. Simulation results show that structured channel estimation provide advantages up to 4 dB in terms of output signal-to-interference plus noise ratio with respect to unstructured estimation, for linear RINSE detection. In contrast, for conventional single-user matched filtering, unstructured estimation proves to be sufficiently good     

EDA-Based Scheduling of Users in the MIMO Multiple Access Channel

In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive search grows exponentially with the number of users. We present an iterative, low-complexity, sub-optimal algorithm for this problem. We apply an Estimation of Distribution Algorithm (EDA) for the user scheduling problem. An EDA is an evolutionary algorithm and updates its chosen population at each iteration on the basis of the probability distribution learned from the population of superior candidate solutions chosen at the previous iterations. The proposed EDA has a low computational complexity and can find a nearly optimal solution in real time for the user scheduling problem. Beyond applying the general EDA to user scheduling, we also present specific improvements that reduce computation for obtaining an acceptable solution. These improvements include the idea of generating an initial population by cyclically shifting a candidate solution. The simulation results show that our proposed algorithm performs better than other scheduling algorithms with comparable complexity.     

Iterative reduced-state multiuser detection for asynchronous coded CDMA

The conventional maximum a posteriori receiver for coded code-division multiple-access (CDMA) systems has exponential computational complexity in terms of the number of users and the memory of the channel code. In this letter, we propose a low-complexity soft-input soft-output (SISO) multiuser detector based on the reduced-state a posteriori probability algorithm. Per-survivor processing and soft interference cancellation are used to remove the residual past and future interference in the branch metric computation. The complexity of the proposed receiver is related to the reduced memory of the CDMA channel and can be adjusted according to the complexity/performance tradeoff. Simulation results show that for asynchronous convolutionally coded systems, the proposed receiver can achieve the near-single-user performance for moderate to high signal-to-noise ratios.     

低复杂度空间调制MPSK信号的最优检测

针对MQAM信号,已有低复杂度的最优检测算法,但是针对MPSK信号还没有类似的最优检测算法发表,因此从二维矢量量化的ML解调角度出发,利用MPSK星座图的特性,给出了与调制符号阶数无关的ML简化算法,避免了ML联合检测算法中对调制符号空间的搜索,极大地降低了算法复杂度。新算法不仅与ML最优检测算法具有完全相同的性能,而且具有较低的复杂度,有较好的理论和实际意义。该算法在天线技术和绿色通信技术中有较好的实际应用意义。     

基于随机集理论和多进制粒子群算法的多用户检测

在移动多址通信系统中,活跃用户个数及其参数随时间不断变化.多用户检测中常假定接收方已知活跃用户数,一般为系统所能容纳的最大用户个数.由于某些时刻某些用户处于休眠状态,此情况下传统方法性能很差.该文采用随机集合模型拟合DS-CDMA和MC-CDMA系统中活跃用户时变情况,为解决计算量随用户数指数上升的问题,提出多进制粒子群算法与随机集相结合的检测方法.仿真结果表明,该文提出的多用户检测方法性能优于常规多用户检测方法.     

On the macroscopic optimization of multicell wireless systems with multiuser detection and multiple antennas - uplink analysis

In this paper, we consider a system with K single-antenna client users, n/sub B/ base stations (each base station has n/sub R/ antennas), as well as a centralized controller. A client user could be associated with a single base station at any time. All the base stations operate at the same frequency and have optimal multiuser detection per base station which cancels intracell interference only. We consider a general problem of uplink macroscopic resource management where the centralized controller dynamically determines an appropriate association mapping of the K users with respect to the n/sub B/ base stations over a macroscopic time scale. We propose a novel analytical framework for the above macroscopic scheduling problems. A simple rule is to associate a user with the strongest base station (camp-on-the-strongest-cell), and this has been widely employed in conventional cellular systems. However, based on the optimization framework, we found that this conventional approach is in fact not optimal when multiuser detection is employed at the base station. We show that the optimal macroscopic scheduling algorithm is of exponential complexity, and we propose a simple greedy algorithm as a feasible solution.     

Decision-feedback soft-input/soft-output multiuser detector foriterative decoding of coded CDMA

The optimal decoding scheme for a code-division multiple-access (CDMA) system that employs convolutional codes results in a prohibitive computational complexity. To reduce the computational complexity, an iterative receiver structure was proposed for decoding multiuser data in a convolutional coded CDMA system. At each iteration, extrinsic information is exchanged between a soft-input/soft-output (SISO) multiuser detector and a bank of single-user SISO channel decoders. However, a direct implementation of the full-complexity SISO multiuser detector also has the exponential computational complexity in terms of the number of users. This paper proposes a low-complexity SISO multiuser detector based on tentative hard decisions that are made and fed back from the channel decoders in the previous iteration. The computational complexity of the proposed detector is linear in terms of the number of users and can be adjusted according to the complexity/performance tradeoff. Simulation results show that even with this simple feedback scheme, the performance of the coded multiuser system approaches that of the single-user system for moderate to high signal-to-noise ratios (SNRs)     

大规模MIMO系统中基于TFQMR的低复杂度信号检测算法

在大规模多输入多输出(Multiple-Input Multiple-Output,MIMO)系统上行链路检测算法中,最小均方误差(Minimum Mean Square Error,MMSE)算法可取得近似最优的性能,然而MMSE算法涉及高维矩阵求逆问题,其计算复杂度高达O(K 3),其中K表示用户数。为此,针对极化信道编码的大规模MIMO系统,基于无转置极小残差(Transpose-Free Quasi-Minimal Residual,TFQMR)方法,提出了一种低复杂度次优信号检测算法。该算法有效地避免了矩阵求逆运算,使其计算复杂度降至约O(K 2)。仿真结果表明,基于TFQMR的信号检测算法的误比特率性能与计算复杂度均优于基于Neumann级数展开的信号检测算法;同时,最多经5次迭代该方法可取得接近MMSE检测算法的性能。     

Low complexity MIMO scheduling with channel decomposition using capacity upperbound

In multiuser MIMO systems, the base station schedules transmissions to a group of users simultaneously. Since the data transmitted to each user are different, in order to avoid the inter-user interference, a transmit preprocessing technique which decomposes the multiuser MIMO downlink channel into multiple parallel independent single-user MIMO channels can be used. When the number of users is larger than the maximum that the system can support simultaneously, the base station selects a subset of users who have the best instantaneous channel quality to maximize the system throughput. Since the exhaustive search for the optimal user set is computationally prohibitive, a low complexity scheduling algorithm which aims to maximize the capacity upper bound is proposed. Simulation results show that the proposed scheduling algorithm achieves comparable total throughput as the optimal algorithm with much lower complexity.     

Novel decoding of square QAM modulated mimo systems based on turbo multiuser detection

By introducing the bit-level multi-stream coded Layered Space-Time （LST） transmitter along with a novel iterative MultiStage Decoding （MSD） at the receiver, the paper shows how to achieve the near-capacity performance of the Multiple-Input Multiple-Output （MIMO） systems with square Quadrature Amplitude Modulation （QAM）. In the proposed iterative MSD scheme, the detection at each stage is equivalent to multiuser detection of synchronous Code Division Multiple Access （CDMA） multiuser systems with the aid of the binary representation of the transmitted symbols. Therefore, the optimal Soft-Input Soft-Output （SISO） multiuser detection and low-complexity SISO multiuser detection can be utilized herein. And the proposed scheme with low-complexity SISO multiuser detection has polynomial complexity in the number of transmit antennas M, the number of receive antennas N, and the number of bits per constellation point Me. Simulation results demonstrate that the proposed scheme has similar Bit Error Rate （BER） performance to that of the known Iterative Tree Search （ITS） detection.     

On multicell cooperative transmission in backhaul-constrained cellular systems

Recent work has shown that multicell cooperative signal processing in cellular networks can significantly increase system capacity and fairness. For example, multicell joint transmission and joint detection can be performed to combat intercell interference, often mentioned in the context of distributed antenna systems. Most publications in this field assume that an infinite amount of information can be exchanged between the cooperating base stations, neglecting the main downside of such systems, namely, the need for an additional network backhaul. In recent publications, we have thus proposed an optimization framework and algorithm that applies multicell signal processing to only a carefully selected subset of users for cellular systems with a strongly constrained backhaul. In this paper, we consider the cellular downlink and provide a comprehensive summary and extension of our previous and current work. We compare the performance obtained through centralized or decentralized optimization approaches, or through optimal or suboptimal calculation of precoding matrices, and identify reasonable performance–complexity trade-offs. It is shown that even low-complexity optimization approaches for cellular systems with a strongly constrained backhaul can yield major performance improvements over conventional systems.     

A low-complexity iterative multiuser receiver for turbo-codedDS-CDMA systems

Optimal joint multiuser detection and decoding for direct-sequence code-division multiple-access (DS-CDMA) systems with forward error correction normally requires prohibitively high computational complexity. A suboptimal solution with low complexity is therefore appealing for use in practical applications. We propose a low-complexity iterative multiuser receiver for turbo-coded DS-CDMA systems. The proposed approach consists of a modified decorrelating decision-feedback detector (MDDFD) and K single-user turbo decoders, where K is the number of users in the DS-CDMA system. The MDDFD is derived on the basis of maximizing a likelihood probability and has a feature that it can use the reliability information from the turbo decoders' output. In addition, the MDDFD can deliver interference-cancelled soft outputs to the turbo decoders where the calculation of transition metrics is modified appropriately. Both performance analysis and computer simulation results have indicated that the reliability information from the turbo decoders' output can enhance the multiuser detection capability of the MDDFD. Computer simulations have also shown that the proposed iterative multiuser receiver outperforms the conventional DDFD-based multiuser receiver in terms of the bit-error probability