Blind Equalization and System Identification: Batch Processing Algorithms, Performance and Applications (Paperback)

Description

Discrete-time signal processing has had a momentous impact on advances in engineering and science over recent decades. The rapid progress of digital and mixed-signal integrated circuits in processing speed, functionality and cost-effectiveness has led to their ubiquitous employment in signal processing and transmission in diverse milieux.

The absence of training or pilot signals from many kinds of transmission – in, for example, speech analysis, seismic exploration and texture image analysis – necessitates the widespread use of blind equalization and system identification. There have been a great many algorithms developed for these purposes, working with one- or two-dimensional (2-d) signals and with single-input single-output (SISO) or multiple-input multiple-output (MIMO), real or complex systems. It is now time for a unified treatment of this subject, pointing out the common characteristics and the sometimes close relations of these algorithms as well as learning from their different perspectives. Blind Equalization and System Identification provides such a unified treatment presenting theory, performance analysis, simulation, implementation and applications.

Topics covered include:

• SISO, MIMO and 2-d non-blind equalization (deconvolution) algorithms;

 

• SISO, MIMO and 2-d blind equalization (deconvolution) algorithms;

 

• SISO, MIMO and 2-d blind system identification algorithms;

 

• algorithm analyses and improvements;

 

• applications of SISO, MIMO and 2-d blind equalization/identification algorithms.

Each chapter is completed by exercises and computer assignments designed to further understanding and to give practical experience with the algorithms discussed.

This is a textbook for graduate-level courses in discrete-time random processes, statistical signal processing, and blind equalization and system identification. It contains material which will also interest researchers and practicing engineers working in digital communications, source separation, speech processing, image processing, seismic exploration, sonar, radar and other, similar applications.

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . . . 1
References . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Vectors and Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Matrix Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Mathematical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.3 Hilbert Spaces, Sequence Spaces and Function Spaces . . 33
2.2.4 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3 Optimization Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3.1 Vector Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.2 Necessary and Sufficient Conditions for Solutions . . . . . . 45
2.3.3 Gradient-Type Optimization Methods . . . . . . . . . . . . . . . . 48
2.4 Least-Squares Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4.1 Full-Rank Overdetermined Least-Squares Problem . . . . . 64
2.4.2 Generic Least-Squares Problem . . . . . . . . . . . . . . . . . . . . . 65
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 67
Appendix 2A Proof of Theorem 2.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Appendix 2B Some Terminologies of Functions . . . . . . . . . . . . . . . . . . 72
Appendix 2C Proof of Theorem 2.33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Appendix 2D Proof of Theorem 2.36 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Appendix 2E Proof of Theorem 2.38 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Appendix 2F Proof of Theorem 2.46 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 81
x Contents
3 Fundamentals of Statistical Signal Processing . . . . . . . . . . . . . . 83
3.1 Discrete-Time Signals and Systems . . . . . . . . . . . . . . . . . . . . . . . . 83
3.1.1 Time-Domain Characterization . . . . . . . . . . . . . . . . . . . . . . 83
3.1.2 Transformation Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.1.3 Transform-Domain Characterization . . . . . . . . . . . . . . . . . 91
3.2 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.1 Statistical Characterization . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.2 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.2.3 Cumulants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.2.4 Some Useful Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.3 Random Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.3.1 Statistical Characterization . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.3.2 Stationary Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.3.3 Cyclostationary Processes . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.4 Estimation Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.1 Estimation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.2 Properties of Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
3.4.3 Maximum-Likelihood Estimation . . . . . . . . . . . . . . . . . . . . 158
3.4.4 Method of Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
3.4.5 Minimum Mean-Square-Error Estimation . . . . . . . . . . . . . 164
3.4.6 Wiener Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
3.4.7 Least-Squares Estimation. . . . . . . . . . . . . . . . . . . . . . . . . . . 169
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . 172
Appendix 3A Relationship between Cumulants and Moments . . . . . . 172
Appendix 3B Proof of Theorem 3.47 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Appendix 3C Proof of Theorem 3.52 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 180
4 SISO Blind Equalization Algorithms . . . . . . . . . . . . . . . . . . . . . . . 183
4.1 Linear Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
4.1.1 Blind Equalization Problem . . . . . . . . . . . . . . . . . . . . . . . . 183
4.1.2 Peak Distortion and MMSE Equalization Criteria . . . . . 187
4.2 SOS Based Blind Equalization Approach: Linear Prediction . . . 190
4.2.1 Forward and Backward Linear Prediction . . . . . . . . . . . . . 191
4.2.2 Levinson–Durbin Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.2.3 Lattice Linear Prediction Error Filters . . . . . . . . . . . . . . . 202
4.2.4 Linear Predictive Deconvolution . . . . . . . . . . . . . . . . . . . . . 205
4.3 HOS Based Blind Equalization Approaches . . . . . . . . . . . . . . . . . 209
4.3.1 Maximum Normalized Cumulant Equalization
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
4.3.2 Super-Exponential Equalization Algorithm . . . . . . . . . . . 214
4.3.3 Algorithm Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
4.3.4 Algorithm Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Contents xi
4.4 Simulation Examples for Algorithm Tests . . . . . . . . . . . . . . . . . . . 231
4.5 Some Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
4.5.1 Seismic Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
4.5.2 Speech Signal Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
4.5.3 Baud-Spaced Equalization in Digital Communications . . 252
4.6 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Appendix 4A Proof of Property 4.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 268
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
References . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 270
5 MIMO Blind Equalization Algorithms . . . . . . . . . . . . . . . . . . . . . 275
5.1 MIMO Linear Time-Invariant Systems . . . . . . . . . . . . . . . . . . . . . 275
5.1.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 275
5.1.2 Smith–McMillan Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
5.2 Linear Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
5.2.1 Blind Equalization Problem . . . . . . . . . . . . . . . . . . . . . . . . 287
5.2.2 Peak Distortion and MMSE Equalization Criteria . . . . . 290
5.3 SOS Based Blind Equalization Approaches . . . . . . . . . . . . . . . . . 292
5.3.1 Blind SIMO Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
5.3.2 Blind MIMO Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . 300
5.4 HOS Based Blind Equalization Approaches . . . . . . . . . . . . . . . . . 304
5.4.1 Temporally IID Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
5.4.2 Temporally Colored Inputs . . . . . . . . . . . . . . . . . . . . . . . . . 314
5.5 Algorithm Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
5.6 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
Appendix 5A Proof of Property 5.34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
Appendix 5B Proof of Property 5.35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Appendix 5C A GCD Computation Algorithm . . . . . . . . . . . . . . . . . . . 329
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
References . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . . . . . 331
6 Applications of MIMO Blind Equalization Algorithms . . . . . 335
6.1 Fractionally Spaced Equalization in Digital Communications . . 335
6.2 Blind Maximum Ratio Combining . . . . . . . . . . . . . . . . . . . . . . . . . 340
6.3 SIMO Blind System Identification . . . . . . . . . . . . . . . . . . . . . . . . . 342
6.3.1 MIMO-MNC Equalizer–System Relation . . . . . . . . . . . . . 344
6.3.2 Analysis on System Identification Based on
MIMO-MNC Equalizer–System Relation . . . . . . . . . . . . . 345
6.3.3 SIMO Blind System Identification Algorithm . . . . . . . . . 346
6.4 Multiple Time Delay Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 351
6.4.1 Model Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
6.4.2 MTDE with Space Diversity Gain . . . . . . . . . . . . . . . . . . . 352
6.5 Blind Beamforming for Source Separation . . . . . . . . . . . . . . . . . . 357
xii Contents
6.5.1 Model Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
6.5.2 Blind Beamforming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
6.5.3 Multistage Source Separation . . . . . . . . . . . . . . . . . . . . . . . 359
6.6 Multiuser Detection in Wireless Communications . . . . . . . . . . . . 362
6.6.1 Model Assumptions and Problem Statement . . . . . . . . . . 363
6.6.2 Signature Waveform Matched Filtering Based
Multiuser Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
6.6.3 Chip Waveform Matched Filtering Based Multiuser
Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
6.6.4 Multiple Antennas Based Multiuser Detection . . . . . . . . . 375
6.7 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
Appendix 6A Proof of Theorem 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
Appendix 6B Proof of Fact 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
Appendix 6C Proof of Property 6.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
Appendix 6D Multichannel Levinson Recursion Algorithm. . . . . . . . . 383
Appendix 6E Integrated Bispectrum Based Time Delay Estimation . 385
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7 Two-Dimensional Blind Deconvolution Algorithms . . . . . . . . . 391
7.1 Two-Dimensional Discrete-Space Signals, Systems and
Random Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
7.1.1 2-D Deterministic Signals . . . . . . . . . . . . . . . . . . . . . . . . . . 391
7.1.2 2-D Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
7.1.3 2-D Linear Shift-Invariant Systems . . . . . . . . . . . . . . . . . . 395
7.1.4 2-D Stationary Random Processes . . . . . . . . . . . . . . . . . . . 400
7.2 2-D Deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
7.2.1 Blind Deconvolution Problem . . . . . . . . . . . . . . . . . . . . . . . 402
7.2.2 Peak Distortion and Minimum Mean-Square-Error
Deconvolution Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
7.3 SOS Based Blind Deconvolution Approach: Linear Prediction . 406
7.4 HOS Based Blind Deconvolution Approaches . . . . . . . . . . . . . . . . 409
7.4.1 2-D Maximum Normalized Cumulant Deconvolution
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
7.4.2 2-D Super-Exponential Deconvolution Algorithm . . . . . . 413
7.4.3 Improvements on 2-D MNC Deconvolution Algorithm . . 416
7.5 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
7.6 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
Computer Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
Contents xiii
8 Applications of Two-Dimensional Blind Deconvolution
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
8.1 Nonparametric Blind System Identification and Texture
Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
8.1.1 Nonparametric 2-D BSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
8.1.2 Texture Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
8.2 Parametric Blind System Identification and Texture Image
Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
8.2.1 Parametric 2-D BSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
8.2.2 Texture Image Classification . . . . . . . . . . . . . . . . . . . . . . . . 449
8.3 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
Appendix 8A Proof of Property 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
Appendix 8B Proof of Property 8.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
Appendix 8C Proof of Theorem 8.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
Appendix 8D Proof of Fact 8.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
Computer Assignments . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . . 460
References . . . . . . . . . . . . . . . . . . . . . . . .. . .  . . . . . . . . . . . . . . . . 461
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463