Algorithms for Communications Systems and their Applications

Preface 3

Acknowledgments 3

1 Elements of signal theory 7

1.1 Continuous-time linear systems 7

1.2 Discrete-time linear systems 10

Discrete Fourier transform 13

The DFT operator 14

Circular and linear convolution via DFT 15

Convolution by the overlap-save method 17

IIR and FIR filters 19

1.3 Signal bandwidth 22

The sampling theorem 24

Heaviside conditions for the absence of signal distortion 26

1.4 Passband signals and systems 26

Complex representation 26

Relation between a signal and its complex representation 28

Baseband equivalent of a transformation 36

Envelope and instantaneous phase and frequency 37

1.5 Second-order analysis of random processes 38

1.5.1 Correlation 39

Properties of the autocorrelation function 40

1.5.2 Power spectral density 40

Spectral lines in the PSD 40

Cross power spectral density 42

Properties of the PSD 42

PSD through filtering 43

1.5.3 PSD of discrete-time random processes 43

Spectral lines in the PSD 44

PSD through filtering 45

Minimum-phase spectral factorization 46

1.5.4 PSD of passband processes 47

PSD of in-phase and quadrature components 47

Cyclostationary processes 50

1.6 The autocorrelation matrix 56

Properties 56

Eigenvalues 56

Other properties 57

Eigenvalue analysis for Hermitian matrices 58

1.7 Examples of random processes 60

1.8 Matched filter 66

White noise case 68

1.9 Ergodic random processes 69

1.9.1 Mean value estimators 71

Rectangular window 74

Exponential filter 74

General window 75

1.9.2 Correlation estimators 75

Unbiased estimate 76

Biased estimate 76

1.9.3 Power spectral density estimators 77

Periodogram or instantaneous spectrum 77

Welch periodogram 78

Blackman and Tukey correlogram 79

Windowing and window closing 79

1.10 Parametric models of random processes 82

ARMA 82

MA 84

AR 84

Spectral factorization of AR models 87

Whitening filter 87

Relation between ARMA, MA, and AR models 87

1.10.1 Autocorrelation of AR processes 89

1.10.2 Spectral estimation of an AR process 91

Some useful relations 92

AR model of sinusoidal processes 94

1.11 Guide to the bibliography 95

Bibliography 95

Appendixes 97

1.A Multirate systems 98

1.A.1 Fundamentals 98

1.A.2 Decimation 100

1.A.3 Interpolation 102

1.A.4 Decimator filter 104

1.A.5 Interpolator filter 105

1.A.6 Rate conversion 108

1.A.7 Time interpolation 109

Linear interpolation 110

Quadratic interpolation 112

1.A.8 The noble identities 112

1.A.9 The polyphase representation 113

Efficient implementations 114

1.B Generation of a complex Gaussian noise 121

1.C Pseudo-noise sequences 122

Maximal-length 122

CAZAC 124

Gold 125

2 The Wiener filter 129

2.1 The Wiener filter 129

Matrix formulation 130

Optimum filter design 132

The principle of orthogonality 134

Expression of the minimum mean-square error 135

Characterization of the cost function surface 136

The Wiener filter in the z-domain 137

2.2 Linear prediction 140

Forward linear predictor 141

Optimum predictor coefficients 141

Forward prediction error filter 142

Relation between linear prediction and AR models 143

First and second order solutions 144

2.3 The least squares method 145

Data windowing 146

Matrix formulation 146

Correlation matrix 147

Determination of the optimum filter coefficients 147

2.3.1 The principle of orthogonality 148

Minimum cost function 149

The normal equation using the data matrix 149

Geometric interpretation: the projection operator 150

2.3.2 Solutions to the LS problem 151

Singular value decomposition 152

Minimum norm solution 154

2.4 The estimation problem 155

Estimation of a random variable 155

MMSE estimation 155

Extension to multiple observations 157

Linear MMSE estimation of a random variable 158

Linear MMSE estimation of a random vector 158

2.4.1 The Cramér-Rao lower bound 160

Extension to vector parameter 162

2.5 Examples of application 164

2.5.1 Identification of a linear discrete-time system 164

2.5.2 Identification of a continuous-time system 166

2.5.3 Cancellation of an interfering signal 169

2.5.4 Cancellation of a sinusoidal interferer with known frequency 170

2.5.5 Echo cancellation in digital subscriber loops 171

2.5.6 Cancellation of a periodic interferer 172

Bibliography 173

Appendixes 174

2.A The Levinson-Durbin algorithm 175

Lattice filters 176

The Delsarte-Genin algorithm 177

3 Adaptive transversal filters 179

3.1 The MSE design criterion 180

3.1.1 The steepest descent or gradient algorithm 181

Stability 181

Conditions for convergence 183

Adaptation gain 184

Transient behaviour of the MSE 185

3.1.2 The least mean square algorithm 186

Implementation 187

Computational complexity 188

Conditions for convergence 188

3.1.3 Convergence analysis of the LMS algorithm 190

Convergence of the mean 191

Convergence in the mean-square sense: real scalar case 192

Convergence in the mean-square sense: general case 193

Fundamental results 196

Observations 197

Final remarks 199

3.1.4 Other versions of the LMS algorithm 199

Leaky LMS 199

Sign algorithm 200

Normalized LMS 200

Variable adaptation gain 201

3.1.5 Example of application: the predictor 202

3.2 The recursive least squares algorithm 208

Normal equation 209

Derivation 210

Initialization 212

Recursive form of the minimum cost function 212

Convergence 214

Computational complexity 214

Example of application: the predictor 215

3.3 Fast recursive algorithms 215

3.3.1 Comparison of the various algorithms 216

3.4 Examples of application 216

3.4.1 Identification of a linear discrete-time system 217

Finite alphabet case 219

3.4.2 Cancellation of a sinusoidal interferer with known frequency 220

Bibliography 221

4 Transmission channels 223

4.1 Radio channel 223

4.1.1 Propagation and used frequencies in radio transmission 224

Basic propagation mechanisms 224

Frequency ranges 224

4.1.2 Analog front-end architectures 226

Radiation masks 226

Conventional superheterodyne receiver 227

Alternative architectures 227

Direct conversion receiver 228

Single conversion to low-IF 229

Double conversion and wideband IF 229

4.1.3 General channel model 230

High power amplifier 230

Transmission medium 233

Additive noise 234

Phase noise 234

4.1.4 Narrowband radio channel model 235

Equivalent circuit at the receiver 237

Multipath 238

Path loss as a function of distance 240

4.1.5 Fading effects in propagation models 243

Macroscopic fading or shadowing 243

Microscopic fading 245

4.1.6 Doppler shift 245

4.1.7 Wideband channel model 247

Multipath channel parameters 249

Statistical description of fading channels 250

4.1.8 Channel statistics 252

Power delay profile 252

Coherence bandwidth 253

Doppler spectrum 254

Coherence time 255

Doppler spectrum models 256

Power angular spectrum 256

Coherence distance 256

On fading 257

4.1.9 Discrete-time model for fading channels 258

Generation of a process with a preassigned spectrum 259

4.1.10 Discrete-space model of shadowing 261

4.1.11 Multiantenna systems 264

Discrete-time model 266

4.2 Telephone channel 268

Distortion 270

Noise sources 270

Echo 270

Appendixes 272

4.A Discrete-time NB model for mmWave channels 273

Angular domain representation 273

Bibliography 274

5 Vector quantization 277

5.1 Basic concept 277

5.2 Characterization of VQ 278

Parameters determining VQ performance 278

Comparison between VQ and scalar quantization 280

5.3 Optimum quantization 281

Generalized Lloyd algorithm 282

5.4 The Linde, Buzo, and Gray algorithm 284

Choice of the initial codebook 285

Splitting procedure 286

Selection of the training sequence 287

5.4.1 k-means clustering 288

5.5 Variants of VQ 288

Tree search VQ 288

Multistage VQ 289

Product code VQ 291

5.6 VQ of channel state information 292

MISO channel quantization 292

Channel feedback with feedforward information 294

5.7 Principal component analysis 295

5.7.1 PCA and k-means clustering 297

Bibliography 299

6 Digital transmission model and channel capacity 301

6.1 Digital transmission model 301

6.2 Detection 305

6.2.1 Optimum detection 306

ML 307

MAP 307

6.2.2 Soft detection 309

LLRs associated to bits of BMAP 309

Simplified expressions 312

6.2.3 Receiver strategies 314

6.3 Relevant parameters of the digital transmission model 314

Relations among parameters 315

6.4 Error probability 317

6.5 Capacity 320

6.5.1 Discrete-time AWGN channel 321

6.5.2 SISO narrowband AWGN channel 322

6.5.3 SISO dispersive AGN channel 322

6.5.4 MIMO discrete-time NB AWGN channel 325

6.6 Achievable rates of modulations in AWGN channels 326

6.6.1 Rate as a function of the SNR per dimension 327

6.6.2 Coding strategies depending on the signal-to-noise ratio 329

Coding gain 330

6.6.3 Achievable rate of an AWGN channel using PAM 331

Bibliography 333

Appendixes 334

6.A Gray labelling 335

6.B The Gaussian distribution and Marcum functions 336

6.B.1 The Q function 336

6.B.2 Marcum function 338

7 Single-carrier modulation 341

7.1 Signals and systems 341

7.1.1 Baseband digital transmission (PAM) 341

Modulator 342

Transmission channel 343

Receiver 343

Power spectral density 344

7.1.2 Passband digital transmission (QAM) 346

Modulator 346

Power spectral density 347

Three equivalent representations of the modulator 348

Coherent receiver 349

7.1.3 Baseband equivalent model of a QAM system 349

Signal analysis 349

7.1.4 Characterization of system elements 353

Transmitter 353

Transmission channel 354

Receiver 355

7.2 Intersymbol interference 356

Discrete-time equivalent system 356

Nyquist pulses 357

Eye diagram 361

7.3 Performance analysis 365

Signal-to-noise ratio 365

Symbol error probability in the absence of ISI 366

Matched filter receiver 367

7.4 Channel equalization 367

7.4.1 Zero-forcing equalizer 367

7.4.2 Linear equalizer 368

Optimum receiver in the presence of noise and ISI 369

Alternative derivation of the IIR equalizer 370

Signal-to-noise ratio at detector 374

7.4.3 LE with a finite number of coefficients 375

Adaptive LE 376

Fractionally spaced equalizer 378

7.4.4 Decision feedback equalizer 381

Design of a DFE with a finite number of coefficients 384

Design of a fractionally spaced DFE 387

Signal-to-noise ratio at the decision point 389

Remarks 390

7.4.5 Frequency domain equalization 390

DFE with data frame using a unique word 390

7.4.6 LE-ZF 394

7.4.7 DFE-ZF with IIR filters 394

DFE-ZF as noise predictor 400

DFE as ISI and noise predictor 400

7.4.8 Benchmark performance of LE-ZF and DFE-ZF 402

Comparison 402

Performance for two channel models 403

7.4.9 Passband equalizers 404

Passband receiver structure 405

Optimization of equalizer coefficients and carrier phase offset 407

Adaptive method 408

7.5 Optimum methods for data detection 410

7.5.1 Maximum-likelihood sequence detection 412

Lower bound to error probability using MLSD 413

The Viterbi algorithm 414

Computational complexity of the VA 419

7.5.2 Maximum a posteriori probability detector 419

Statistical description of a sequential machine 420

The forward-backward algorithm 421

Scaling 425

The log likelihood function and the Max-Log-MAP criterion 426

LLRs associated to bits of BMAP 427

Relation between Max-Log-MAP and Log-MAP 428

7.5.3 Optimum receivers 428

7.5.4 The Ungerboeck's formulation of MLSD 430

7.5.5 Error probability achieved by MLSD 433

Computation of the minimum distance 437

7.5.6 The reduced-state sequence detection 441

Trellis diagram 442

The RSSE algorithm 444

Further simplification: DFSE 446

7.6 Numerical results obtained by simulations 447

QPSK over a minimum-phase channel 447

QPSK over a non minimum phase channel 448

8-PSK over a minimum phase channel 449

8-PSK over a non minimum phase channel 449

7.7 Precoding for dispersive channels 451

7.7.1 Tomlinson-Harashima precoding 452

7.7.2 Flexible precoding 454

7.8 Channel estimation 456

7.8.1 The correlation method 456

7.8.2 The LS method 458

Formulation using the data matrix 459

7.8.3 Signal-to-estimation error ratio 460

7.8.4 Channel estimation for multirate systems 464

7.8.5 The LMMSE method 465

7.9 Faster-than-Nyquist Signalling 467

Bibliography 467

Appendixes 470

7.A Simulation of a QAM system 471

7.B Description of a finite-state machine 477

7.C Line codes for PAM systems 478

7.C.1 Line codes 478

Non-return-to-zero format 478

Return-to-zero format 479

Biphase format 480

Delay modulation or Miller code 481

Block line codes 481

Alternate mark inversion 481

7.C.2 Partial response systems 482

The choice of the PR polynomial 485

Symbol detection and error probability 489

Precoding 491

Error probability with precoding 492

Alternative interpretation of PR systems 493

7.D Implementation of a QAM transmitter 497

8 Multicarrier modulation 499

8.1 MC systems 499

8.2 Orthogonality conditions 500

Time domain 501

Frequency domain 501

z-transform domain 501

8.3 Efficient implementation of MC systems 502

MC implementation employing matched filters 502

Orthogonality conditions in terms of the polyphase components 505

MC implementation employing a prototype filter 505

8.4 Non-critically sampled filter banks 510

8.5 Examples of MC systems 515

OFDM or DMT 515

Filtered multitone 516

8.6 Analog signal processing requirements in MC systems 517

8.6.1 Analog filter requirements 517

Interpolator filter and virtual subchannels 517

Modulator filter 519

8.6.2 Power amplifier requirements 520

8.7 Equalization 521

8.7.1 OFDM equalization 521

8.7.2 FMT equalization 524

Per-subchannel fractionally-spaced equalization 524

Per-subchannel T -spaced equalization 524

Alternative per-subchannel T -spaced equalization 525

8.8 Orthogonal time frequency space modulation 526

OTFS equalization 527

8.9 Channel estimation in OFDM 527

Instantaneous estimate or LS method 528

LMMSE 530

The LS estimate with truncated impulse response 531

8.9.1 Channel estimate and pilot symbols 532

8.10 Multiuser access schemes 532

8.10.1 OFDMA 533

8.10.2 SC-FDMA or DFT-spread OFDM 534

8.11 Comparison between MC and SC systems 535

8.12 Other MC waveforms 536

Bibliography 537

9 Transmission over multiple input multiple output channels 539

9.1 The MIMO NB channel 539

Spatial multiplexing and spatial diversity 544

Interference in MIMO channels 544

9.2 CSI only at the receiver 545

9.2.1 SIMO combiner 545

Equalization and diversity 548

9.2.2 MIMO combiner 548

Zero-forcing 549

MMSE 550

9.2.3 MIMO nonlinear detection and decoding 550

V-BLAST system 550

Spatial modulation 552

9.2.4 Space-time coding 553

The Alamouti code 553

The Golden code 555

9.2.5 MIMO channel estimation 556

The least squares method 556

The LMMSE method 557

9.3 CSI only at the transmitter 558

9.3.1 MISO linear precoding 558

MISO antenna selection 559

9.3.2 MIMO linear precoding 560

ZF precoding 561

9.3.3 MIMO nonlinear precoding 562

Dirty paper coding 562

TH precoding 564

9.3.4 Channel estimation for CSIT 564

9.4 CSI at both the transmitter and the receiver 565

9.5 Hybrid beamforming 566

Hybrid beamforming and angular domain representation 567

9.6 Multiuser MIMO: broadcast channel 568

9.6.1 CSI at both the transmitter and the receivers 569

Block diagonalization 570

User selection 571

Joint spatial division and multiplexing 572

9.6.2 Broadcast channel estimation 573

9.7 Multiuser MIMO: multiple-access channel 573

9.7.1 CSI at both the transmitters and the receiver 574

Block diagonalization 575

9.7.2 Multiple-access channel estimation 575

9.8 Massive MIMO 575

9.8.1 Channel hardening 576

9.8.2 Multiuser channel orthogonality 576

Bibliography 576

10 Spread-spectrum systems 581

10.1 Spread-spectrum techniques 581

10.1.1 Direct sequence systems 581

Classification of CDMA systems 589

Synchronization 590

10.1.2 Frequency hopping systems 590

Classification of FH systems 592

10.2 Applications of spread-spectrum systems 593

10.2.1 Anti-jamming 594

10.2.2 Multiple access 596

10.2.3 Interference rejection 597

10.3 Chip matched filter and rake receiver 597

Number of resolvable rays in a multipath channel 597

Chip matched filter 598

10.4 Interference 601

Detection strategies for multiple-access systems 603

10.5 Single-user detection 603

Chip equalizer 603

Symbol equalizer 605

10.6 Multiuser detection 606

10.6.1 Block equalizer 606

10.6.2 Interference cancellation detector 608

Successive interference cancellation 608

Parallel interference cancellation 610

10.6.3 ML multiuser detector 610

Correlation matrix 611

Whitening filter 611

10.7 Multicarrier CDMA systems 612

Bibliography 613

Appendixes 615

10.A Walsh codes 616

11 Channel codes 619

11.1 System model 620

11.2 Block codes 622

11.2.1 Theory of binary codes with group structure 622

Properties 622

Parity check matrix 625

Code generator matrix 628

Decoding of binary parity check codes 628

Cosets 629

Two conceptually simple decoding methods 630

Syndrome decoding 631

11.2.2 Fundamentals of algebra 633

modulo-q arithmetic 634

Polynomials with coefficients from a field 637

Modular arithmetic for polynomials 638

Devices to sum and multiply elements in a finite field 640

Remarks on finite fields 642

Roots of a polynomial 646

Minimum function 648

Methods to determine the minimum function 650

Properties of the minimum function 652

11.2.3 Cyclic codes 653

The algebra of cyclic codes 653

Properties of cyclic codes 654

Encoding by a shift register of length r 658

Encoding by a shift register of length k 661

Hard decoding of cyclic codes 662

Hamming codes 663

Burst error detection 666

11.2.4 Simplex cyclic codes 666

Relation to PN sequences 668

11.2.5 BCH codes 669

An alternative method to specify the code polynomials 669

Bose-Chaudhuri-Hocquenhemcodes 671

Binary BCH codes 674

Reed-Solomon codes 675

Decoding of BCH codes 676

Efficient decoding of BCH codes 681

11.2.6 Performance of block codes 689

11.3 Convolutional codes 690

11.3.1 General description of convolutional codes 693

Parity check matrix 695

Generator matrix 696

Transfer function 696

Catastrophic error propagation 700

11.3.2 Decoding of convolutional codes 702

Interleaving 702

Two decoding models 703

Decoding by the Viterbi algorithm 704

Decoding by the forward-backward algorithm 705

Sequential decoding 706

11.3.3 Performance of convolutional codes 710

11.4 Puncturing 711

11.5 Concatenated codes 711

The soft-output Viterbi algorithm 711

11.6 Turbo codes 713

Encoding 713

The basic principle of iterative decoding 718

FBA revisited 719

Iterative decoding 728

Performance evaluation 730

11.7 Iterative detection and decoding 730

11.8 Low-density parity check codes 734

11.8.1 Representation of LDPC codes 735

Matrix representation 735

Graphical representation 736

11.8.2 Encoding 737

Encoding procedure 737

11.8.3 Decoding 738

Hard decision decoder 738

The sum-product algorithm decoder 741

The LR-SPA decoder 744

The LLR-SPA or log-domain SPA decoder 745

The min-sum decoder 747

Other decoding algorithms 748

11.8.4 Example of application 748

Performance and coding gain 748

11.8.5 Comparison with turbo codes 749

11.9 Polar codes 751

11.9.1 Encoding 752

Internal CRC 753

LLRs associated to code bits 754

11.9.2 Tanner graph 755

11.9.3 Decoding algorithms 757

Successive cancellation decoding - the principle 758

Successive cancellation decoding - the algorithm 760

Successive cancellation list decoding 763

Other decoding algorithms 765

11.9.4 Frozen set design 765

Genie-aided SC decoding 766

Design based on density evolution 767

Channel polarisation 770

11.9.5 Puncturing and shortening 770

Puncturing 771

Shortening 772

Frozen set design 774

11.9.6 Performance 774

11.10Milestones in channel coding 775

Bibliography 775

Appendixes 781

11.A Nonbinary parity check codes 782

Linear codes 783

Parity check matrix 784

Code generator matrix 785

Decoding of nonbinary parity check codes 786

Coset 786

Two conceptually simple decoding methods 787

Syndrome decoding 787

12 Trellis coded modulation 789

12.1 Linear TCM for one and two-dimensional signal sets 790

12.1.1 Fundamental elements 790

Basic TCM scheme 792

Example 792

12.1.2 Set partitioning 795

12.1.3 Lattices 797

12.1.4 Assignment of symbols to the transitions in the trellis 802

12.1.5 General structure of the encoder/bit-mapper 807

Computation of dfree 809

12.2 Multidimensional TCM 811

Encoding 812

Decoding 815

12.3 Rotationally invariant TCM schemes 817

Bibliography 817

13 Techniques to achieve capacity 819

13.1 Capacity achieving solutions for multicarrier systems 819

13.1.1 Achievable bit rate of OFDM 819

13.1.2 Waterfilling solution 820

Iterative solution 821

13.1.3 Achievable rate under practical constraints 821

Effective SNR and system margin in MC systems 822

Uniform power allocation and minimum rate per subchannel 823

13.1.4 The bit and power loading problem revisited 824

Transmission modes 824

Problem formulation 825

Some simplifying assumptions 826

On loading algorithms 826

The Hughes-Hartogs algorithm 827

The Krongold-Ramchandran Jones algorithm 827

The Chow-Cioffi Bingham algorithm 830

Comparison 832

13.2 Capacity achieving solutions for single carrier systems 833

Achieving capacity 837

Bibliography 838

14 Synchronization 839

14.1 The problem of synchronization for QAM systems 839

14.2 The phase-locked loop 841

14.2.1 PLL baseband model 843

Linear approximation 844

14.2.2 Analysis of the PLL in the presence of additive noise 846

Noise analysis using the linearity assumption 847

14.2.3 Analysis of a second order PLL 848

14.3 Costas loop 852

14.3.1 PAM signals 852

14.3.2 QAM signals 854

14.4 The optimum receiver 856

Timing recovery 858

Carrier phase recovery 862

14.5 Algorithms for timing and carrier phase recovery 863

14.5.1 ML criterion 863

Assumption of slow time varying channel 863

14.5.2 Taxonomy of algorithms using the ML criterion 863

Feedback estimators 865

Early-late estimators 866

14.5.3 Timing estimators 867

Non data aided 867

NDA synchronization via spectral estimation 869

Data aided and data directed 871

Data and phase directed with feedback: differentiator scheme 874

Data and phase directed with feedback: Mueller & Muller scheme 874

Non data aided with feedback 877

14.5.4 Phasor estimators 878

Data and timing directed 878

Non data aided forM-PSK signals 878

Data and timing directed with feedback 879

14.6 Algorithms for carrier frequency recovery 880

14.6.1 Frequency offset estimators 881

Non data aided 881

Non data aided and timing independent with feedback 882

Non data aided and timing directed with feedback 883

14.6.2 Estimators operating at the modulation rate 883

Data aided and data directed 884

Non data aided forM-PSK 885

14.7 Second-order digital PLL 885

14.8 Synchronization in spread-spectrum systems 885

14.8.1 The transmission system 885

Transmitter 885

Optimum receiver 886

14.8.2 Timing estimators with feedback 887

Non data aided: non coherent DLL 888

Non data aided modified code tracking loop 888

Data and phase directed: coherent DLL 891

14.9 Synchronization in OFDM 891

14.9.1 Frame synchronization 891

Effects of STO 891

Schmidl and Cox algorithm 893

14.9.2 Carrier frequency synchronization 894

Estimator performance 895

Other synchronization solutions 895

14.10Synchronization in SC-FDMA 896

Bibliography 899

15 Self-training equalization 901

15.1 Problem definition and fundamentals 901

Minimization of a special function 904

15.2 Three algorithms for PAM systems 908

The Sato algorithm 908

Benveniste-Goursat algorithm 909

Stop-and-go algorithm 909

Remar