C o m m u n i C a t i o n s y s t e m s Input message sequence m Encoded output c c(0) c(1) t(1) c(2) t(2) π RSC encoder 1 RSC encoder 2 n Noisy channel output r Estimate of message vector m Decoder 1 Extrinsic information 1 π π–1 π La,1 Lp(r(0)) r(0) Lp(z(1)) z(1) Lp(r(1)) r(1) Decoder 2 Extrinsic information 2 La,2 Lp(z(2)) z(2) Lp(c(2)) r(2) (a) (b) simon Haykin d i g i t a l Haykin_preface.fm Page iv Friday, January 11, 2013 6:01 PM Haykin_preface.fm Page i Friday, January 11, 2013 6:01 PM ASSOCIATE PUBLISHER Daniel Sayre EDITORIAL ASSISTANT Jessica Knecht MARKETING MANAGER Christopher Ruel PRODUCTION MANAGEMENT SERVICES Publishing Services CREATIVE DIRECTOR Harry Nolan COVER DESIGNER Kristine Carney Cover Image: The figure on the cover, depicting the UMTS-turbo code, is adapted from the doctoral thesis of Dr. Liang Li, Department of Electronics and Computer Science, University of Southampton, United Kingdom, with the permission of Dr. Li, his Supervisor Dr. Robert Maunder, and Professor Lajos Hanzo; the figure also appears on page 654 of the book. This book was set in Times by Publishing Services and printed and bound by RRD Von Hoffmann. The cover was printed by RRD Von Hoffmann. This book is printed on acid free paper.  Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/ citizenship. Copyright  2014 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax (201) 748-6008, website www.wiley.com/go/permissions. Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative. ISBN: 978-0-471-64735-5 Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 Haykin_preface.fm Page ii Friday, January 11, 2013 6:01 PM In loving memory of Vera Haykin_preface.fm Page iii Friday, January 11, 2013 6:01 PM Haykin_preface.fm Page iv Friday, January 11, 2013 6:01 PM v Preface The study of digital communications is an essential element of the undergraduate and postgraduate levels of present-day electrical and computer engineering programs. This book is appropriate for both levels. A Tour of the Book The introductory chapter is motivational, beginning with a brief history of digital communications, and continuing with sections on the communication process, digital communications, multiple-access and multiplexing techniques, and the Internet. Four themes organize the remaining nine chapters of the book. Theme 1 Mathematics of Digital Communications The first theme of the book provides a detailed exposé of the mathematical underpinnings of digital communications, with continuous mathematics aimed at the communication channel and interfering signals, and discrete mathematics aimed at the transmitter and receiver: • Chapter 2, Fourier Analysis of Signals and Systems, lays down the fundamentals for the representation of signals and linear time-invariant systems, as well as analog modulation theory. • Chapter 3, Probability Theory and Bayesian Inference, presents the underlying mathematics for dealing with uncertainty and the Bayesian paradigm for probabilistic reasoning. • Chapter 4, Stochastic Processes, focuses on weakly or wide-sense stationary processes, their statistical properties, and their roles in formulating models for Poisson, Gaussian, Rayleigh, and Rician distributions. • Chapter 5, Information Theory, presents the notions of entropy and mutual information for discrete as well continuous random variables, leading to Shannon’s celebrated theorems on source coding, channel coding, and information capacity, as well as rate-distortion theory. Theme 2 From Analog to Digital Communications The second theme of the book, covered in Chapter 6, describes how analog waveforms are transformed into coded pulses. It addresses the challenge of performing the transformation with robustness, bandwidth preservation, or minimal computational complexity. Theme 3 Signaling Techniques Three chapters address the third theme, each focusing on a specific form of channel impairment: • In Chapter 7, Signaling over Additive White Gaussian Noise (AWGN) Channels, the impairment is the unavoidable presence of channel noise, which is modeled as Haykin_preface.fm Page v Friday, January 11, 2013 6:01 PM vi Preface additive white Gaussian noise (AWGN). This model is well-suited for the signal- space diagram, which brings insight into the study of phase-shift keying (PSK), quadrature-amplitude modulation (QAM), and frequency-shift keying (FSK) as different ways of accommodating the transmission and reception of binary data. • In Chapter 8, Signaling over Band-Limited Channels, bandwidth limitation assumes center stage, with intersymbol interference (ISI) as the source of channel impairment. • Chapter 9, Signaling over Fading Channels, focuses on fading channels in wireless communications and the practical challenges they present. The channel impairment here is attributed to the multipath phenomenon, so called because the transmitted signal reaches the receiver via a multiplicity of paths. Theme 4 Error-control Coding Chapter 10 addresses the practical issue of reliable communications. To this end, various techniques of the feedforward variety are derived therein, so as to satisfy Shannon’s celebrated coding theorem. Two families of error-correcting codes are studied in the chapter: • Legacy (classic) codes, which embody linear block codes, cyclic codes, and convolutional codes. Although different in their structural compositions, they look to algebraic mathematics as the procedure for approaching the Shannon limit. • Probabilistic compound codes, which embody turbo codes and low-density parity- check (LDPC) codes. What is remarkable about these two codes is that they both approach the Shannon limit with doable computational complexity in a way that was not feasible until 1993. The trick behind this powerful information-processing capability is the adoption of random codes, the origin of which could be traced to Shannon’s 1948 classic paper. Features of the Book Feature 1 Analog in Digital Communication When we think of digital communications, we must not overlook the fact that such a system is of a hybrid nature. The channel across which data are transmitted is analog, exemplified by traditional telephone and wireless channels, and many of the sources responsible for the generation of data (e.g., speech and video) are of an analog kind. Moreover, certain principles of analog modulation theory, namely double sideband- suppressed carrier (DSB-SC) and vestigial sideband (VSB) modulation schemes, include binary phase-shift keying (PSK) and offset QPSK as special cases, respectively. It is with these points in mind that Chapter 2 includes • detailed discussion of communication channels as examples of linear systems, • analog modulation theory, and • phase and group delays. Feature 2 Hilbert Transform The Hilbert transform, discussed in Chapter 2, plays a key role in the complex representation of signals and systems, whereby • a band-pass signal, formulated around a sinusoidal carrier, is transformed into an equivalent complex low-pass signal; Haykin_preface.fm Page vi Friday, January 11, 2013 6:01 PM Preface vii • a band-pass system, be it a linear channel or filter with a midband frequency, is transformed into an equivalent complex low-pass system. Both transformations are performed without loss of information, and their use changes a difficult task into a much simpler one in mathematical terms, suitable for simulation on a computer. However, one must accommodate the use of complex variables. The Hilbert transform also plays a key role in Chapter 7. In formulating the method of orthogonal modulation, we show that one can derive the well-known formulas for the noncoherent detection of binary frequency-shift keying (FSK) and differential phase-shift keying (DPSK) signals, given unknown phase, in a much simpler manner than following traditional approaches that involve the use of Rician distribution. Feature 3 Discrete-time Signal Processing In Chapter 2, we briefly review finite-direction impulse response (FIR) or tapped-delay line (TDL) filters, followed by the discrete Fourier transform (DFT) and a well-known fast Fourier transform (FFT) algorithm for its computational implementations. FIR filters and FFT algorithms feature prominently in: • Modeling of the raised-cosine spectrum (RCS) and its square-root version (SQRCS), which are used in Chapter 8 to mitigate the ISI in band-limited channels; • Implementing the Jakes model for fast fading channels, demonstrated in Chapter 9; • Using FIR filtering to simplify the mathematical exposition of the most difficult form of channel fading, namely, the doubly spread channel (in Chapter 9). Another topic of importance in discrete-time signal processing is linear adaptive filtering, which appears: • In Chapter 6, dealing with differential pulse-code modulation (DPCM), where an adaptive predictor constitutes a key functional block in both the transmitter and receiver. The motivation here is to preserve channel bandwidth at the expense of increased computational complexity. The algorithm described therein is the widely used least mean-square (LMS) algorithm. • In Chapter 7, dealing with the need for synchronizing the receiver to the transmitter, where two algorithms are described, one for recursive estimation of the group delay (essential for timing recovery) and the other for recursive estimation of the unknown carrier phase (essential for carrier recovery). Both algorithms build on the LMS principle so as to maintain linear computational complexity. Feature 4 Digital Subscriber Lines Digital subscriber lines (DSLs), covered in Chapter 8, have established themselves as an essential tool for transforming a linear wideband channel, exemplified by the twisted-wire pair, into a discrete multitone (DMT) channel that is capable of accommodating data transmission at multiple megabits per second. Moreover, the transformation is afforded practical reality by exploiting the FFT algorithm, with the inverse FFT used in the transmitter and the FFT used in the receiver. Feature 5 Diversity Techniques As already mentioned, the wireless channel is one of the most challenging media for digital communications. The difficulty of reliable data transmission over a wireless Haykin_preface.fm Page vii Friday, January 11, 2013 6:01 PM viii Preface channel is attributed to the multipath phenomenon. Three diversity techniques developed to get around this practical difficulty are covered in Chapter 9: • Diversity on receive, the traditional approach, whereby an array of multiple antennas operating independently is deployed at the receiving end of a wireless channel. • Diversity on transmit, which operates by deploying two or more independent antennas at the transmit end of the wireless channel. • Multiple-input multiple-output (MIMO) channels, where multiple antennas (again operating independently) are deployed at both ends of the wireless channel. Among these three forms of diversity, the MIMO channel is naturally the most powerful in information-theoretic terms: an advantage gained at the expense of increased computational complexity. Feature 6 Turbo Codes Error-control coding has established itself as the most commonly used technique for reliable data transmission over a noisy channel. Among the challenging legacies bestowed by Claude Shannon was how to design a code that would closely approach the so-called Shannon limit. For over four decades, increasingly more powerful coding algorithms were described in the literature; however it was the turbo code that had the honor of closely approaching the Shannon limit, and doing so in a computationally feasible manner. Turbo codes, together with the associated maximum a posteriori (MAP) decoding algorithm, occupy a large portion of Chapter 10, which also includes: • Detailed derivation of the MAP algorithm and an illustrative example of how it operates; • The extrinsic information transfer (EXIT) chart, which provides an experimental tool for the design of turbo codes; • Turbo equalization, for demonstrating applicability of the turbo principle beyond error-control coding. Feature 7 Placement of Information Theory Typically, information theory is placed just before the chapter on error-control coding. In this book, it is introduced early because: Information theory is not only of basic importance to error-control coding but also other topics in digital communications. To elaborate: • Chapter 6 presents the relevance of source coding to pulse-code modulation (PCM), differential pulse-code modulation (DPCM), and delta modulation. • Comparative evaluation of M-ary PSK versus M-ary FSK, done in Chapter 7, requires knowledge of Shannon’s information capacity law. • Analysis and design of DSL, presented in Chapter 8, also builds on Shannon’s information capacity law. • Channel capacity in Shannon’s coding theorem is important to diversity techniques, particularly of the MIMO kind, discussed in Chapter 9. Haykin_preface.fm Page viii Friday, January 11, 2013 6:01 PM Preface ix Examples, Computer Experiments, and Problems Except for Chapter 1, each of the remaining nine chapters offers the following: • Illustrative examples are included to strengthen the understanding of a theorem or topic in as much detail as possible. Some of the examples are in the form of computer experiments. • An extensive list of end-of-chapter problems are grouped by section to fit the material covered in each chapter. The problems range from relatively easy ones all the way to more challenging ones. • In addition to the computer-oriented examples, nine computer-oriented experiments are included in the end-of-chapter problems. The Matlab codes for all of the computer-oriented examples in the text, as well as other calculations performed on the computer, are available at www.wiley.com/college/haykin. Appendices Eleven appendices broaden the scope of the theoretical as well as practical material covered in the book: • Appendix A, Advanced Probabilistic Models, covers the chi-square distribution, log-normal distribution, and Nakagami distribution that includes the Rayleigh distribution as a special case and is somewhat similar to the Rician distribution. Moreover, an experiment is included therein that demonstrates, in a step-by-step manner, how the Nakagami distribution evolves into the log-normal distribution in an approximate manner, demonstrating its adaptive capability. • Appendix B develops tight bounds on the Q-function. • Appendix C discussed the ordinary Bessel function and its modified form. • Appendix D describes the method of Lagrange multipliers for solving constrained optimization problems. • Appendix E derives the formula for the channel capacity of the MIMO channel under two scenarios: one that assumes no knowledge of the channel by the transmitter, and the other that assumes this knowledge is available to the transmitter via a narrowband feedback link. • Appendix F discusses the idea of interleaving, which is needed for dealing with bursts of interfering signals experienced in wireless communications. • Appendix G addresses the peak-to-average power reduction (PAPR) problem, which arises in the use of orthogonal frequency-division multiplexing (OFDM) for both wireless and DSL applications. • Appendix H discusses solid-state nonlinear power amplifiers, which play a critical role in the limited life of batteries in wireless communications. • Appendix I presents a short exposé of Monte Carlo integration: a theorem that deals with mathematically intractable problems. • Appendix J studies maximal-length sequences, also called m-sequences, which are used for implementing linear feedback shift registers (LFSRs). An important application of maximal-length sequences (viewed as pseudo-random noise) is in Haykin_preface.fm Page ix Friday, January 11, 2013 6:01 PM x Preface designing direct-sequence spread-spectrum communications for code-division multiple access (CDMA). • Finally, Appendix K provides a useful list of mathematical formulas and functions. Two Noteworthy Symbols Typically, the square-root of minus one is denoted by the italic symbol j, and the differential operator (used in differentiation as well as integration) is denoted by the italic symbol d. In reality, however, both of these terms are operators, each one in its own way: it is therefore incorrect to use italic symbols for their notations. Furthermore, italic j and italic d are also frequently used as indices or to represent other matters, thereby raising the potential for confusion. According, throughout the book, roman j and roman d are used to denote the square root of minus one and the differential operator, respectively. Concluding Remarks In writing this book every effort has been made to present the material in the manner easiest to read so as to enhance understanding of the topics covered. Moreover, cross- references within a chapter as well as from chapter to chapter have been included wherever the need calls for it. Finally, every effort has been made by the author as well as compositor of the book to make it as error-free as humanly possible. In this context, the author would welcome receiving notice of any errors discovered after publication of the book. Acknowledgements In writing this book I have benefited enormously from technical input, persistent support, and permissions provided by many. I am grateful to colleagues around the world for technical inputs that have made a significant difference in the book; in alphabetical order, they are: • Dr. Daniel Costello, Jr., University of Notre Dame, for reading and providing useful comments on the maximum likelihood decoding and maximum a posteriori decoding materials in Chapter 10. • Dr. Dimitri Bertsekas, MIT, for permission to use Table 3.1 on the Q-function in Chapter 3, taken from his co-authored book on the theory of probability. • Dr. Lajos Hanzo, University of Southampton, UK, for many useful comments on turbo codes as well as low-density parity-check codes in Chapter 10. I am also indebted to him for putting me in touch with his colleagues at the University of Southampton, Dr. R. G. Maunder and Dr. L. Li, who were extremely helpfully in performing the insightful computer experiments on UMTS-turbo codes and EXIT charts in Chapter 10. • Dr. Phillip Regalia, Catholic University, Washington DC, for contributing a section on serial-concatenated turbo codes in Chapter 10. This section has been edited by myself to follow the book’s writing style, and for its inclusion I take full responsibility. • Dr. Sam Shanmugan, University of Kansas, for his insightful inputs on the use of FIR filters and FFT algorithms for modeling the raised-cosine spectrum (RCS) and Haykin_preface.fm Page x Friday, January 11, 2013 6:01 PM Preface xi its square-root version (SQRCS) in Chapter 8, implementing the Jakes model in Chapter 9, as well as other simulation-oriented issues. • Dr. Yanbo Xue, University of Alberta, Canada, for performing computer-oriented experiments and many other graphical computations throughout the book, using well-developed Matlab codes. • Dr. Q. T. Zhang, The City University of Hong Kong, for reading through an early version of the manuscript and offering many valuable suggestions for improving it. I am also grateful to his student, Jiayi Chen, for performing the graphical computations on the Nakagami distribution in Appendix A. I’d also like to thank the reviewers who read drafts of the manuscript and provided valuable commentary: • Ender Ayanoglu, University of California, Irvine • Tolga M. Duman, Arizona State University • Bruce A. Harvey, Florida State University • Bing W. Kwan, FAMU-FSU College of Engineering • Chung-Chieh Lee, Northwestern University • Heung-No Lee, University of Pittsburgh • Michael Rice, Brigham Young University • James Ritcey, University of Washington • Lei Wei, University of Central Florida Production of the book would not have been possible without the following: • Daniel Sayre, Associate Publisher at John Wiley & Sons, who maintained not only his faith in this book but also provided sustained support for it over the past few years. In am deeply indebted to Dan for what he has done to make this book a reality. • Cindy Johnson, Publishing Services, Newburyport, MA, for her dedicated commitment to the beautiful layout and composition of the book. I am grateful for her tireless efforts to print the book in as errorless manner as humanly possible. I salute everyone, and others too many to list, for their individual and collective contributions, without which this book would not have been a reality. Simon Haykin Ancaster, Ontario Canada December, 2012 Haykin_preface.fm Page xi Friday, January 11, 2013 6:01 PM Haykin_preface.fm Page xii Friday, January 11, 2013 6:01 PM xiii Contents 1 Introduction 1 1.1 Historical Background 1 1.2 The Communication Process 2 1.3 Multiple-Access Techniques 4 1.4 Networks 6 1.5 Digital Communications 9 1.6 Organization of the Book 11 2 Fourier Analysis of Signals and Systems 13 2.1 Introduction 13 2.2 The Fourier Series 13 2.3 The Fourier Transform 16 2.4 The Inverse Relationship between Time-Domain and Frequency-Domain Representations 25 2.5 The Dirac Delta Function 28 2.6 Fourier Transforms of Periodic Signals 34 2.7 Transmission of Signals through Linear Time-Invariant Systems 37 2.8 Hilbert Transform 42 2.9 Pre-envelopes 45 2.10 Complex Envelopes of Band-Pass Signals 47 2.11 Canonical Representation of Band-Pass Signals 49 2.12 Complex Low-Pass Representations of Band-Pass Systems 52 2.13 Putting the Complex Representations of Band-Pass Signals and Systems All Together 54 2.14 Linear Modulation Theory 58 2.15 Phase and Group Delays 66 2.16 Numerical Computation of the Fourier Transform 69 2.17 Summary and Discussion 78 3 Probability Theory and Bayesian Inference 87 3.1 Introduction 87 3.2 Set Theory 88 3.3 Probability Theory 90 3.4 Random Variables 97 3.5 Distribution Functions 98 3.6 The Concept of Expectation 105 Haykin_preface.fm Page xiii Friday, January 11, 2013 6:01 PM