Advances in Multiuser Detection

Preface xv

Contributors xvii

1 Overview of Multiuser Detection 1
Michael L. Honig

1.1 Introduction 1

1.1.1 Applications 2

1.1.2 Mobile Cellular Challenges 4

1.1.3 Chapter Outline 5

1.2 Matrix Channel Model 6

1.3 Optimal Multiuser Detection 8

1.3.1 Maximum Likelihood (ML) 8

1.3.2 Optimal (Maximum a Posteriori) Detection 9

1.3.3 Sphere Decoder 10

1.4 Linear Detectors 12

1.4.1 Comparison with Optimal Detection 13

1.4.2 Properties of Linear Multiuser Detection 15

1.5 Reduced-Rank Estimation 16

1.5.1 Subspaces from the Matched Filter 17

1.5.2 Eigen-Space Methods 18

1.5.2.1 Principal Components (PC) 18

1.5.2.2 Generalized Side-lobe Canceller (GSC) 18

1.5.2.3 Cross-Spectral Method 19

1.5.2.4 Comparison 19

1.5.3 Krylov Subspace Methods 20

1.5.3.1 Multi-Stage Wiener Filter (MSWF) 20

1.5.3.2 Rank-Recursive (Conjugate Gradient) Algorithm 22

1.5.3.3 Performance 22

1.5.3.4 Adaptive Rank Selection 24

1.5.4 Performance Comparison 25

1.6 Decision-Feedback Detection 26

1.6.1 Successive Decision Feedback 30

1.6.2 Parallel Decision Feedback 30

1.6.3 Filter Adaptation 31

1.6.4 Error Propagation and Iterative Decision Feedback 31

1.6.5 Application to MIMO Channels 32

1.7 Interference Mitigation at the Transmitter 33

1.7.1 Precoding for Coordinated Data Streams 33

1.7.1.1 Precoding for Equalizing SNR Performance 35

1.7.2 Signature Optimization with Uncoordinated Data Streams 36

1.7.3 Network Configurations 37

1.8 Overview of Remaining Chapters 38

References 39

2 Iterative Techniques 47
Alex Grant and Lars K. Rasmussen

2.1 Introduction 47

2.1.1 System Model 48

2.1.2 Multiuser Detectors 50

2.1.2.1 Optimal Multiuser Detectors 51

2.1.2.2 Decorrelator Detector 52

2.1.2.3 Linear Minimum Mean-Squared Error Detectors 52

2.1.2.4 Per-User Linear Minimum Mean-Squared Error Detectors 53

2.1.2.5 Per-User Approximate Nonlinear MMSE Detector 54

2.2 Iterative Joint Detection for Uncoded Data 56

2.2.1 Interference Cancellation 56

2.2.1.1 Schedules for Iterative Cancellation 58

2.2.1.2 Implementation via Residual Error Update 59

2.2.1.3 Tentative Decision Functions 63

2.2.2 Linear Methods 64

2.2.2.1 Solutions to Linear Systems 66

2.2.2.2 Direct Solution 66

2.2.2.3 Series Expansions 67

2.2.2.4 Iterative Solution Methods 70

2.2.2.5 Jacobi Iteration 72

2.2.2.6 Gauss-Seidel Iteration 74

2.2.2.7 Descent Algorithms 75

2.2.3 Non-Linear Methods 80

2.2.3.1 Constrained Optimization 80

2.2.3.2 Clipped Soft Decision 84

2.2.3.3 Hyperbolic Tangent 86

2.2.3.4 Hard Decision 86

2.2.4 Numerical Results 88

2.2.4.1 Parallel Cancellation 88

2.2.4.2 Serial Cancellation 89

2.2.4.3 Gradient Methods 93

2.3 Iterative Joint Decoding for Coded Data 95

2.3.1 Joint Optimal Multiuser and Separate Single-User Decoders 96

2.3.2 The Canonical Iterative Joint Multiuser Decoder 97

2.3.3 Linear Detection in Iterative Joint Multiuser Decoding 100

2.3.4 Parallel Interference Cancellation 102

2.3.5 Per-User LMMSE Filters with Priors 103

2.3.6 Transfer Function Convergence Analysis 105

2.3.7 Numerical Examples 107

2.3.7.1 Separate Multiuser Detection and Single-User Decoding 107

2.3.7.2 Single-User Matched Filter Parallel Interference Cancellation 107

2.3.7.3 Per-User LMMSE Filtering 111

2.3.7.4 Comparison of Single-User Matched-Filter PIC and LMMSE Decoders 115

2.4 Concluding Remarks 118

References 119

3 Blind Multiuser Detection in Fading Channels 127
Daryl Reynolds, H. Vincent Poor, and Xiaodong Wang

3.1 Introduction 127

3.2 Signal Models and Blind Multiuser Detectors for Fading Channels 129

3.2.1 Asynchronous Multi-Antenna Multipath CDMA 129

3.2.2 Synchronous Multipath CDMA 134

3.2.3 Synchronous Multi-Antenna CDMA 136

3.2.4 Remarks 137

3.3 Performance of Blind Multiuser Detectors 138

3.3.1 Complex Gaussian Distribution 138

3.3.2 Performance of Blind Multiuser Detectors with Known Channels 139

3.3.3 Performance of Blind Multiuser Detector with Blind Channel Estimation 142

3.3.4 Numerical Results 143

3.3.5 Adaptive Implementation 144

3.3.6 Algorithm Summary 146

3.4 Bayesian Multiuser Detection for Long-Code CDMA 148

3.4.1 System Descriptions 148

3.4.1.1 Signal and Channel Model 148

3.4.1.2 Noise Model 149

3.4.1.3 Blind Bayesian Multiuser Detection 150

3.4.1.4 The Gibbs Sampler 151

3.4.2 Bayesian MCMC Multiuser Detectors 152

3.4.2.1 White Gaussian Noise 152

3.4.2.2 Colored Gaussian Noise 155

3.4.3 Simulation Examples 157

3.5 Multiuser Detection for Long-Code CDMA in Fast-Fading Channels 161

3.5.1 Channel Model and Sequential EM Algorithm 161

3.5.2 Sequential Blind Multiuser Detector 163

3.5.3 Simulation Results 163

3.6 Transmitter-Based Multiuser Precoding for Fading Channels 165

3.6.1 Basic Approach and Adaptation 166

3.6.1.1 Uplink Signal Model and Blind Channel Estimation 166

3.6.1.2 Downlink Signal Model and Matched Filter Detection 166

3.6.1.3 Transmitter Precoding for a Synchronous Multipath Downlink 167

3.6.1.4 Adaptive Implementation 169

3.6.1.5 Algorithm Summary 170

3.6.2 Precoding with Multiple Transmit Antennas 171

3.6.2.1 Downlink Signal Model 171

3.6.2.2 Precoder Design for Orthogonal Spreading Codes 171

3.6.2.3 Precoder Design for Non-Orthogonal Spreading Codes 172

3.6.3 Precoding for Multipath ISI Channels 174

3.6.3.1 Prerake-Diversity Combining 174

3.6.3.2 Precoder Design 175

3.6.4 Performance Analyses 178

3.6.4.1 Performance of Transmitter Precoding with Blind Channel Estimation 178

3.6.4.2 Performance and Achievable Diversity for Multi-Antenna Precoding 180

3.7 Conclusion 183

References 184

4 Performance with Random Signatures 189
Matthew J. M. Peacock, Iain B. Collings, and Michael L. Honig

4.1 Random Signatures and Large System Analysis 189

4.2 System Models 192

4.2.1 Uplink CDMAWithout Multipath 193

4.2.2 Downlink CDMA 194

4.2.3 Multi-Cell Downlink or Multi-Signature Uplink 196

4.2.4 Model Limitations 197

4.3 Large System Limit 198

4.3.1 SINR of Linear Filters 198

4.4 Random Matrix Terminology 201

4.4.1 Eigen-Value Distributions 201

4.4.2 Stieltjes Transform 201

4.4.3 Examples 202

4.4.4 Asymptotic Equivalence 203

4.5 Incremental Matrix Expansion 204

4.6 Analysis of Downlink Model 206

4.6.1 MMSE Receiver and SINR 206

4.6.2 Large-System SINR 207

4.6.3 Two Important Preliminary Results 208

4.6.3.1 Rotational Invariance of SINR 208

4.6.3.2 Covariance Matrix Expansion Along Transmit Dimensions 209

4.6.4 Large System SINR 210

4.6.5 Numerical Example 213

4.7 Spectral Efficiency 215

4.7.1 Sum Capacity 215

4.7.2 Capacity Regions 219

4.8 Adaptive Linear Receivers 221

4.8.1 ALS Receiver 221

4.8.2 ALS Convergence: Numerical Example 223

4.8.3 Large System Limit 224

4.8.4 Analysis and Results 225

4.8.4.1 ALS Transient Behavior 226

4.8.4.2 Steady-State SINR 228

4.8.5 Numerical Examples 228

4.8.6 Optimization of Training Overhead 230

4.9 Other Models and Extensions 236

4.10 Bibliographical Notes 237

Appendix: Proof Sketch of Theorem 1 238

Appendix: Free Probability Transforms 241

4.B.1 Free Probability Transforms 242

4.B.2 Sums of Unitarily Invariant Matrices 243

4.B.3 Products of Unitarily Invariant Matrices 245

References 246

5 Generic Multiuser Detection and Statistical Physics 251
Dongning Guo and Toshiyuki Tanaka

5.1 Introduction 251

5.1.1 Generic Multiuser Detection 251

5.1.2 Single-User Characterization of Multiuser Systems 252

5.1.3 On the Replica Method 254

5.1.4 Statistical Inference Using Practical Algorithms 254

5.1.5 Statistical Physics and Related Problems 255

5.2 Generic Multiuser Detection 256

5.2.1 CDMA/MIMO Channel Model 256

5.2.2 Generic Posterior Mean Estimation 256

5.2.3 Specific Detectors as Posterior Mean Estimators 259

5.2.3.1 Linear Detectors 260

5.2.3.2 Optimal Detectors 260

5.2.3.3 Interference Cancelers 260

5.3 Main Results: Single-User Characterization 261

5.3.1 Is the Decision Statistic Gaussian? 261

5.3.2 The Decoupling Principle: Individually Optimal Detection 262

5.3.3 Decoupling Principle: Generic Multiuser Detection 269

5.3.3.1 A Companion Channel 269

5.3.3.2 Main Results 271

5.3.4 Justification of Results: Sparse Spreading 272

5.3.5 Well-Known Detectors as Special Cases 273

5.3.5.1 Linear Detectors 273

5.3.5.2 Optimal Detectors 275

5.4 The Replica Analysis of Generic Multiuser Detection 276

5.4.1 The Replica Method 276

5.4.1.1 Spectral Efficiency and Detection Performance 276

5.4.1.2 The Replica Method 277

5.4.1.3 A Simple Example 278

5.4.2 Free Energy 281

5.4.2.1 Large Deviations and Saddle Point 283

5.4.2.2 Replica Symmetry Solution 285

5.4.2.3 Single-User Channel Interpretation 286

5.4.2.4 Spectral Efficiency and Multiuser Efficiency 288

5.4.3 Joint Moments 289

5.5 Further Discussion 291

5.5.1 On Replica Symmetry 291

5.5.2 On Metastable Solutions 292

5.6 Statistical Physics and the Replica Method 294

5.6.1 A Note on Statistical Physics 294

5.6.2 Multiuser Communications and Statistical Physics 296

5.6.2.1 Equivalence of Multiuser Systems and Spin Glasses 296

5.7 Interference Cancellation 297

5.7.1 Conventional Parallel Interference Cancellation 297

5.7.2 Belief Propagation 298

5.7.2.1 Application of Belief Propagation to Multiuser Detection 298

5.7.2.2 Conventional Parallel Interference Cancellation as Approximate BP 300

5.7.2.3 BP-Based Parallel Interference Cancellation Algorithm 301

5.8 Concluding Remarks 303

5.9 Acknowledgments 304

References 304

6 Joint Detection for Multi-Antenna Channels 311
Antonia Tulino, Matthew R. McKay, Jeffrey G. Andrews, Iain B. Collings, and Robert W. Heath, Jr.

6.1 Introduction 311

6.2 Wireless Channels: The Multi-Antenna Realm 312

6.3 Definitions and Preliminaries 314

6.4 Multi-Antenna Capacity: Ergodic Regime 315

6.4.1 Input Optimization and Capacity-Achieving Transceiver Architectures 316

6.4.2 Random Matrix Theory 320

6.4.2.1 Eigen-Value Distributions 320

6.4.2.2 Transforms 320

6.4.3 Canonical Model (IID Channel) 321

6.4.3.1 Separable Correlation Model 323

6.5 Multi-Antenna Capacity: Non-Ergodic Regime 327

6.6 Receiver Architectures and Performance 330

6.6.1 Linear Receivers 330

6.6.1.1 Zero-Forcing Receiver 331

6.6.1.2 Minimum Mean-Square Error Receiver 337

6.7 Multiuser Multi-Antenna Systems 345

6.7.1 Same-Cell Interference and Cooperation 346

6.7.1.1 Downlink: Precoding 347

6.7.1.2 Uplink: Interference Cancellation 349

6.7.2 Other-Cell Interference and Cooperation 349

6.7.2.1 Joint Encoding 350

6.7.2.2 Base Station Cooperative Scheduling 350

6.8 Diversity-Multiplexing Tradeoffs and Spatial Adaptation 351

6.8.1 Diversity-Multiplexing Tradeoff 352

6.8.2 Mode Adaptation: Switching Between Diversity and Multiplexing 353

6.9 Conclusions 355

References 355

7 Interference Avoidance for CDMA Systems 365
Dimitrie C. Popescu, Sennur Ulukus, Christopher Rose, and Roy Yates

7.1 Introduction 365

7.2 Interference Avoidance Basics 367

7.2.1 Greedy Interference Avoidance: The Eigen-Algorithm 370

7.2.2 MMSE Interference Avoidance 372

7.2.3 Other Algorithms for Interference Avoidance 376

7.3 Interference Avoidance over Time-Invariant Channels 377

7.3.1 Interference Avoidance with Diagonal Channel Matrices 379

7.3.2 Interference Avoidance with General Channel Matrices 380

7.4 Interference Avoidance in Fading Channels 384

7.4.1 Iterative Power and Sequence Optimization in Fading 388

7.5 Interference Avoidance in Asynchronous Systems 389

7.5.1 Interference Avoidance for User Capacity Maximization 390

7.5.2 Interference Avoidance for Sum Capacity Maximization 396

7.5.3 TSAC Reduction: Iterative Algorithms 399

7.6 Feedback Requirements for Interference Avoidance 401

7.6.1 Codeword Tracking for Interference Avoidance 401

7.6.2 Reduced-Rank Signatures 402

7.7 Recent Results on Interference Avoidance 403

7.7.1 Interference Avoidance and Power Control 403

7.7.2 Adaptive Interference Avoidance Algorithms 405

7.8 Summary and Conclusions 410

References 411

8 Capacity-Approaching Multiuser Communications Over Multiple Input/Multiple Output Broadcast Channels 417
Uri Erez and Stephan ten Brink

8.1 Introduction 417

8.2 Many-to-One Multiple Access versus One-to-Many Scalar Broadcast Channels 418

8.3 Alternative Approach: Dirty Paper Coding 420

8.3.1 The Dirty Paper Coding Result 420

8.3.2 DPC vs. SSD Approach for a Coded Interference Signal 421

8.3.3 Scalar Broadcast Using the DPC Approach 421

8.4 A Simple 2 × 2 Example 423

8.5 General Gaussian MIMO Broadcast Channels 428

8.5.1 Vector Dirty Paper Coding: Reduction to Scalar Case 428

8.5.2 DPC Rate Region 430

8.6 Coding with Side Information at the Transmitter 431

8.6.1 A Naive Attempt 432

8.6.2 Scalar Quantization: Tomlinson-Harashima Precoding 432

8.6.2.1 Dither Signal 434

8.6.2.2 Losses of Tomlinson-Harashima Precoding 434

8.6.2.3 MMSE Scaling 436

8.6.2.4 One-Dimensional Soft-Symbol Metric 437

8.6.3 Vector Quantization: Sign-Bit Shaping 440

8.6.3.1 Lattices 440

8.6.3.2 Shaping Gain 440

8.6.3.3 Communication Using Lattices 441

8.6.3.4 Lattice Precoding at the Transmitter 442

8.6.3.5 High-Dimensional Lattices from Linear Codes 443

8.6.3.6 Sign-Bit Shaping 447

8.6.3.7 Coset Decoding at the Receiver 448

8.6.3.8 Mutual Information Limits 450

8.6.4 The Role of Channel Knowledge 451

8.6.4.1 Single User vs. Multiuser MIMO 451

8.6.4.2 Obtaining Channel Knowledge 452

8.7 Summary 452

References 453

Index 455