Advances in Multiuser Detection

MICHAEL L. HONIG is a Professor in the Electrical Engineering and Computer Science Department at Northwestern University.

• Preface xvContributors xvii1 Overview of Multiuser Detection 1Michael L. Honig1.1 Introduction 11.1.1 Applications 21.1.2 Mobile Cellular Challenges 41.1.3 Chapter Outline 51.2 Matrix Channel Model 61.3 Optimal Multiuser Detection 81.3.1 Maximum Likelihood (ML) 81.3.2 Optimal (Maximum a Posteriori) Detection 91.3.3 Sphere Decoder 101.4 Linear Detectors 121.4.1 Comparison with Optimal Detection 131.4.2 Properties of Linear Multiuser Detection 151.5 Reduced-Rank Estimation 161.5.1 Subspaces from the Matched Filter 171.5.2 Eigen-Space Methods 181.5.2.1 Principal Components (PC) 181.5.2.2 Generalized Side-lobe Canceller (GSC) 181.5.2.3 Cross-Spectral Method 191.5.2.4 Comparison 191.5.3 Krylov Subspace Methods 201.5.3.1 Multi-Stage Wiener Filter (MSWF) 201.5.3.2 Rank-Recursive (Conjugate Gradient) Algorithm 221.5.3.3 Performance 221.5.3.4 Adaptive Rank Selection 241.5.4 Performance Comparison 251.6 Decision-Feedback Detection 261.6.1 Successive Decision Feedback 301.6.2 Parallel Decision Feedback 301.6.3 Filter Adaptation 311.6.4 Error Propagation and Iterative Decision Feedback 311.6.5 Application to MIMO Channels 321.7 Interference Mitigation at the Transmitter 331.7.1 Precoding for Coordinated Data Streams 331.7.1.1 Precoding for Equalizing SNR Performance 351.7.2 Signature Optimization with Uncoordinated Data Streams 361.7.3 Network Configurations 371.8 Overview of Remaining Chapters 38References 392 Iterative Techniques 47Alex Grant and Lars K. Rasmussen2.1 Introduction 472.1.1 System Model 482.1.2 Multiuser Detectors 502.1.2.1 Optimal Multiuser Detectors 512.1.2.2 Decorrelator Detector 522.1.2.3 Linear Minimum Mean-Squared Error Detectors 522.1.2.4 Per-User Linear Minimum Mean-Squared Error Detectors 532.1.2.5 Per-User Approximate Nonlinear MMSE Detector 542.2 Iterative Joint Detection for Uncoded Data 562.2.1 Interference Cancellation 562.2.1.1 Schedules for Iterative Cancellation 582.2.1.2 Implementation via Residual Error Update 592.2.1.3 Tentative Decision Functions 632.2.2 Linear Methods 642.2.2.1 Solutions to Linear Systems 662.2.2.2 Direct Solution 662.2.2.3 Series Expansions 672.2.2.4 Iterative Solution Methods 702.2.2.5 Jacobi Iteration 722.2.2.6 Gauss-Seidel Iteration 742.2.2.7 Descent Algorithms 752.2.3 Non-Linear Methods 802.2.3.1 Constrained Optimization 802.2.3.2 Clipped Soft Decision 842.2.3.3 Hyperbolic Tangent 862.2.3.4 Hard Decision 862.2.4 Numerical Results 882.2.4.1 Parallel Cancellation 882.2.4.2 Serial Cancellation 892.2.4.3 Gradient Methods 932.3 Iterative Joint Decoding for Coded Data 952.3.1 Joint Optimal Multiuser and Separate Single-User Decoders 962.3.2 The Canonical Iterative Joint Multiuser Decoder 972.3.3 Linear Detection in Iterative Joint Multiuser Decoding 1002.3.4 Parallel Interference Cancellation 1022.3.5 Per-User LMMSE Filters with Priors 1032.3.6 Transfer Function Convergence Analysis 1052.3.7 Numerical Examples 1072.3.7.1 Separate Multiuser Detection and Single-User Decoding 1072.3.7.2 Single-User Matched Filter Parallel Interference Cancellation 1072.3.7.3 Per-User LMMSE Filtering 1112.3.7.4 Comparison of Single-User Matched-Filter PIC and LMMSE Decoders 1152.4 Concluding Remarks 118References 1193 Blind Multiuser Detection in Fading Channels 127Daryl Reynolds, H. Vincent Poor, and Xiaodong Wang3.1 Introduction 1273.2 Signal Models and Blind Multiuser Detectors for Fading Channels 1293.2.1 Asynchronous Multi-Antenna Multipath CDMA 1293.2.2 Synchronous Multipath CDMA 1343.2.3 Synchronous Multi-Antenna CDMA 1363.2.4 Remarks 1373.3 Performance of Blind Multiuser Detectors 1383.3.1 Complex Gaussian Distribution 1383.3.2 Performance of Blind Multiuser Detectors with Known Channels 1393.3.3 Performance of Blind Multiuser Detector with Blind Channel Estimation 1423.3.4 Numerical Results 1433.3.5 Adaptive Implementation 1443.3.6 Algorithm Summary 1463.4 Bayesian Multiuser Detection for Long-Code CDMA 1483.4.1 System Descriptions 1483.4.1.1 Signal and Channel Model 1483.4.1.2 Noise Model 1493.4.1.3 Blind Bayesian Multiuser Detection 1503.4.1.4 The Gibbs Sampler 1513.4.2 Bayesian MCMC Multiuser Detectors 1523.4.2.1 White Gaussian Noise 1523.4.2.2 Colored Gaussian Noise 1553.4.3 Simulation Examples 1573.5 Multiuser Detection for Long-Code CDMA in Fast-Fading Channels 1613.5.1 Channel Model and Sequential EM Algorithm 1613.5.2 Sequential Blind Multiuser Detector 1633.5.3 Simulation Results 1633.6 Transmitter-Based Multiuser Precoding for Fading Channels 1653.6.1 Basic Approach and Adaptation 1663.6.1.1 Uplink Signal Model and Blind Channel Estimation 1663.6.1.2 Downlink Signal Model and Matched Filter Detection 1663.6.1.3 Transmitter Precoding for a Synchronous Multipath Downlink 1673.6.1.4 Adaptive Implementation 1693.6.1.5 Algorithm Summary 1703.6.2 Precoding with Multiple Transmit Antennas 1713.6.2.1 Downlink Signal Model 1713.6.2.2 Precoder Design for Orthogonal Spreading Codes 1713.6.2.3 Precoder Design for Non-Orthogonal Spreading Codes 1723.6.3 Precoding for Multipath ISI Channels 1743.6.3.1 Prerake-Diversity Combining 1743.6.3.2 Precoder Design 1753.6.4 Performance Analyses 1783.6.4.1 Performance of Transmitter Precoding with Blind Channel Estimation 1783.6.4.2 Performance and Achievable Diversity for Multi-Antenna Precoding 1803.7 Conclusion 183References 1844 Performance with Random Signatures 189Matthew J. M. Peacock, Iain B. Collings, and Michael L. Honig4.1 Random Signatures and Large System Analysis 1894.2 System Models 1924.2.1 Uplink CDMAWithout Multipath 1934.2.2 Downlink CDMA 1944.2.3 Multi-Cell Downlink or Multi-Signature Uplink 1964.2.4 Model Limitations 1974.3 Large System Limit 1984.3.1 SINR of Linear Filters 1984.4 Random Matrix Terminology 2014.4.1 Eigen-Value Distributions 2014.4.2 Stieltjes Transform 2014.4.3 Examples 2024.4.4 Asymptotic Equivalence 2034.5 Incremental Matrix Expansion 2044.6 Analysis of Downlink Model 2064.6.1 MMSE Receiver and SINR 2064.6.2 Large-System SINR 2074.6.3 Two Important Preliminary Results 2084.6.3.1 Rotational Invariance of SINR 2084.6.3.2 Covariance Matrix Expansion Along Transmit Dimensions 2094.6.4 Large System SINR 2104.6.5 Numerical Example 2134.7 Spectral Efficiency 2154.7.1 Sum Capacity 2154.7.2 Capacity Regions 2194.8 Adaptive Linear Receivers 2214.8.1 ALS Receiver 2214.8.2 ALS Convergence: Numerical Example 2234.8.3 Large System Limit 2244.8.4 Analysis and Results 2254.8.4.1 ALS Transient Behavior 2264.8.4.2 Steady-State SINR 2284.8.5 Numerical Examples 2284.8.6 Optimization of Training Overhead 2304.9 Other Models and Extensions 2364.10 Bibliographical Notes 237Appendix: Proof Sketch of Theorem 1 238Appendix: Free Probability Transforms 2414.B.1 Free Probability Transforms 2424.B.2 Sums of Unitarily Invariant Matrices 2434.B.3 Products of Unitarily Invariant Matrices 245References 2465 Generic Multiuser Detection and Statistical Physics 251Dongning Guo and Toshiyuki Tanaka5.1 Introduction 2515.1.1 Generic Multiuser Detection 2515.1.2 Single-User Characterization of Multiuser Systems 2525.1.3 On the Replica Method 2545.1.4 Statistical Inference Using Practical Algorithms 2545.1.5 Statistical Physics and Related Problems 2555.2 Generic Multiuser Detection 2565.2.1 CDMA/MIMO Channel Model 2565.2.2 Generic Posterior Mean Estimation 2565.2.3 Specific Detectors as Posterior Mean Estimators 2595.2.3.1 Linear Detectors 2605.2.3.2 Optimal Detectors 2605.2.3.3 Interference Cancelers 2605.3 Main Results: Single-User Characterization 2615.3.1 Is the Decision Statistic Gaussian? 2615.3.2 The Decoupling Principle: Individually Optimal Detection 2625.3.3 Decoupling Principle: Generic Multiuser Detection 2695.3.3.1 A Companion Channel 2695.3.3.2 Main Results 2715.3.4 Justification of Results: Sparse Spreading 2725.3.5 Well-Known Detectors as Special Cases 2735.3.5.1 Linear Detectors 2735.3.5.2 Optimal Detectors 2755.4 The Replica Analysis of Generic Multiuser Detection 2765.4.1 The Replica Method 2765.4.1.1 Spectral Efficiency and Detection Performance 2765.4.1.2 The Replica Method 2775.4.1.3 A Simple Example 2785.4.2 Free Energy 2815.4.2.1 Large Deviations and Saddle Point 2835.4.2.2 Replica Symmetry Solution 2855.4.2.3 Single-User Channel Interpretation 2865.4.2.4 Spectral Efficiency and Multiuser Efficiency 2885.4.3 Joint Moments 2895.5 Further Discussion 2915.5.1 On Replica Symmetry 2915.5.2 On Metastable Solutions 2925.6 Statistical Physics and the Replica Method 2945.6.1 A Note on Statistical Physics 2945.6.2 Multiuser Communications and Statistical Physics 2965.6.2.1 Equivalence of Multiuser Systems and Spin Glasses 2965.7 Interference Cancellation 2975.7.1 Conventional Parallel Interference Cancellation 2975.7.2 Belief Propagation 2985.7.2.1 Application of Belief Propagation to Multiuser Detection 2985.7.2.2 Conventional Parallel Interference Cancellation as Approximate BP 3005.7.2.3 BP-Based Parallel Interference Cancellation Algorithm 3015.8 Concluding Remarks 3035.9 Acknowledgments 304References 3046 Joint Detection for Multi-Antenna Channels 311Antonia Tulino, Matthew R. McKay, Jeffrey G. Andrews, Iain B. Collings, and Robert W. Heath, Jr.6.1 Introduction 3116.2 Wireless Channels: The Multi-Antenna Realm 3126.3 Definitions and Preliminaries 3146.4 Multi-Antenna Capacity: Ergodic Regime 3156.4.1 Input Optimization and Capacity-Achieving Transceiver Architectures 3166.4.2 Random Matrix Theory 3206.4.2.1 Eigen-Value Distributions 3206.4.2.2 Transforms 3206.4.3 Canonical Model (IID Channel) 3216.4.3.1 Separable Correlation Model 3236.5 Multi-Antenna Capacity: Non-Ergodic Regime 3276.6 Receiver Architectures and Performance 3306.6.1 Linear Receivers 3306.6.1.1 Zero-Forcing Receiver 3316.6.1.2 Minimum Mean-Square Error Receiver 3376.7 Multiuser Multi-Antenna Systems 3456.7.1 Same-Cell Interference and Cooperation 3466.7.1.1 Downlink: Precoding 3476.7.1.2 Uplink: Interference Cancellation 3496.7.2 Other-Cell Interference and Cooperation 3496.7.2.1 Joint Encoding 3506.7.2.2 Base Station Cooperative Scheduling 3506.8 Diversity-Multiplexing Tradeoffs and Spatial Adaptation 3516.8.1 Diversity-Multiplexing Tradeoff 3526.8.2 Mode Adaptation: Switching Between Diversity and Multiplexing 3536.9 Conclusions 355References 3557 Interference Avoidance for CDMA Systems 365Dimitrie C. Popescu, Sennur Ulukus, Christopher Rose, and Roy Yates7.1 Introduction 3657.2 Interference Avoidance Basics 3677.2.1 Greedy Interference Avoidance: The Eigen-Algorithm 3707.2.2 MMSE Interference Avoidance 3727.2.3 Other Algorithms for Interference Avoidance 3767.3 Interference Avoidance over Time-Invariant Channels 3777.3.1 Interference Avoidance with Diagonal Channel Matrices 3797.3.2 Interference Avoidance with General Channel Matrices 3807.4 Interference Avoidance in Fading Channels 3847.4.1 Iterative Power and Sequence Optimization in Fading 3887.5 Interference Avoidance in Asynchronous Systems 3897.5.1 Interference Avoidance for User Capacity Maximization 3907.5.2 Interference Avoidance for Sum Capacity Maximization 3967.5.3 TSAC Reduction: Iterative Algorithms 3997.6 Feedback Requirements for Interference Avoidance 4017.6.1 Codeword Tracking for Interference Avoidance 4017.6.2 Reduced-Rank Signatures 4027.7 Recent Results on Interference Avoidance 4037.7.1 Interference Avoidance and Power Control 4037.7.2 Adaptive Interference Avoidance Algorithms 4057.8 Summary and Conclusions 410References 4118 Capacity-Approaching Multiuser Communications Over Multiple Input/Multiple Output Broadcast Channels 417Uri Erez and Stephan ten Brink8.1 Introduction 4178.2 Many-to-One Multiple Access versus One-to-Many Scalar Broadcast Channels 4188.3 Alternative Approach: Dirty Paper Coding 4208.3.1 The Dirty Paper Coding Result 4208.3.2 DPC vs. SSD Approach for a Coded Interference Signal 4218.3.3 Scalar Broadcast Using the DPC Approach 4218.4 A Simple 2 × 2 Example 4238.5 General Gaussian MIMO Broadcast Channels 4288.5.1 Vector Dirty Paper Coding: Reduction to Scalar Case 4288.5.2 DPC Rate Region 4308.6 Coding with Side Information at the Transmitter 4318.6.1 A Naive Attempt 4328.6.2 Scalar Quantization: Tomlinson-Harashima Precoding 4328.6.2.1 Dither Signal 4348.6.2.2 Losses of Tomlinson-Harashima Precoding 4348.6.2.3 MMSE Scaling 4368.6.2.4 One-Dimensional Soft-Symbol Metric 4378.6.3 Vector Quantization: Sign-Bit Shaping 4408.6.3.1 Lattices 4408.6.3.2 Shaping Gain 4408.6.3.3 Communication Using Lattices 4418.6.3.4 Lattice Precoding at the Transmitter 4428.6.3.5 High-Dimensional Lattices from Linear Codes 4438.6.3.6 Sign-Bit Shaping 4478.6.3.7 Coset Decoding at the Receiver 4488.6.3.8 Mutual Information Limits 4508.6.4 The Role of Channel Knowledge 4518.6.4.1 Single User vs. Multiuser MIMO 4518.6.4.2 Obtaining Channel Knowledge 4528.7 Summary 452References 453Index 455