SERGIO_VERDU So _— — Lu a Oe LUG Y) —) a —_l =MULTIUSER DETECTION Multiuser Detection provides the first comprehensive treatment of the sub- ject of multiuser digital communi demodulation of the mutually interfering digital streams of information that occur in areas such as wireless communications, high-speed data trans- ions. Multiuser detection deals with mission, satellite communication, digital television, and magnetic record- ing. The development of multiuser detection techniques is one of the most important recent advances in communications technology, and this self- contained book gives a comprehensive coverage of the design and analysis of receivers for multiaccess channels, while focusing on fundamental mod- els and algorithms. ‘The author begins with a review of multiaccess communications, dealing in particular with code-division multiple-access (CDMA) channels. Back- ground material on hypothesis testing and the effect of multiuser interfer- ence on single-user receivers are discussed next. This is followed by the design and analysis of optimum and linear multiuser detectors. Also cov- ered in detail are topics such as decision-driven multiuser detection and noncoherent multiuser detection. The elements of multiuser detection are clearly and systematically pre- sented along with more advanced recent results, some of which are published here for the first time. The extensive set of references and bibliographical notes offer a comprehensive account of the state of the art in the subject. ‘The only prerequisites assumed are undergraduate-level probability, lin- ear algebra, and introductory digital communications. The book contains over 300 exercises and is a suitable textbook for electrical engineering stu- dents, It is also an ideal self-study guide for practicing engineers, as well as a valuable reference volume for researchers in communications and signal processing. Sergio Verdi is Professor of Electrical Engineering at Princeton University. His contributions to the technology of multiuser detection span his pioneer- ing work in the early 1980s to recent results included in this text. Professor Verdi is also well known for his work on information theory, in which he explores the fundamental limits of data transmission and compression systems. Recipient of a number of awards, he is a Fellow of the TEEE and served as President of the IEEE Information Theory Society in 1997.PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE The Pitt Building, Trumpington Street, Cambridge, CB2 [RP United Kingdom CAMBRIDGE UNIVERSITY PRESS The Edinburgh Building, Cambridge CB2 2RU, UK —_heep:/hyww.cup.cam.ae.uk 40 West 20th Street, New York, NY 10011-4211, USA http:/Awww.cup.org 10 Stamford Road, Oakleigh, Melbourne 3166, Australia © Sergio Verdi 1998 This book is in copyright. Subject to statutory exception, and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1998 Printed in the United States of America Typeset in Times Roman 10,5/14 pt. and Futura in DTpX 2¢ [78] A catalog recont for this book is available from the British Library Library of Congress Cataloging-in-Publication Data Verdi, Sergio, 1958- Multiuser detection / Sergio Verdd. pcm, Includes bibliographical references. ISBN 0-521-59373-5 (hardbound) 1, Code division multiple access. 2, Demodulation (Electronics) 3. Spread spectrum communications, {, Title. TKS103.45.V47 1998 98-16453 621.3845—e2 IP ISBN 0521 59373 5 hardbackCONTENTS List of Figures Preface 1 MULTIACCESS COMMUNICATIONS 1.1 The Multiaccess Channel 1.2 FDMA and TDMA 1.3. Random Multiaccess 1.4. CDMA 1.5 Problems CODE-DIVISION MULTIPLE-ACCESS CHANNEL 2.1. Basie Synchronous CDMA Model 2.2 Basie Asynchronous CDMA Model 2.3. Signature Waveforms 2.3.1 Direct-Sequence Spread Spectrum 2.3.2. Spreading Factor 2.3.3 Signature Sequences 2.3.4 Long Sequences 2.3.5 Random Sequences 2.3.6 Other Spread-Spectrum Formats 2.4 Data Streams 2.5 Modulation 2.5.1 Carrier Modulation 2.5.2 Nonantipodal Modulation 2.6 Fading 2.6.1. Frequency-Flat Fading 2.6.2 Frequency-Selective Fading 2.6.3 Homogencous Fading page xi xix BRM 38 40 a 42 45 50 0) of waveforms in Figure 1.4 Synchronous antipodal modulation of orthogonal signals Signature waveforms in TDMA Successive decoding ‘Two-user asynchronous CDMA. Walsh functions of length 16 On-off signature waveform Raised cosine pulse with o = 0.5 Ofisets modeling asynchronism Bit epochs for K = 3, M = 1 Intersymbol interference as an asynchronous CDMA channel Definition of asynchronous crosscorrelations (k < /) Direct-sequence spread-spectrum signature waveform with N = 63 in the time and frequency domains (rectangular chip waveform) xi 7UST OF FIGURES 2.6 27 28 29 2.10 21 2.16 217 2.18 Direct-sequence spread-spectrum signature waveform with V = 63 in the time and frequency domains (sine chip waveform) Noiseless sum of six modutated direct-sequence waveforms with N = 63 Generation of pseudonoise sequence with a feedback shift register Direct-sequence spread-spectrum system with No = 63 and N =7 Locus of crosscorrelations (p12, 21) for N = 128 (left) and N = $12 (right) with rectangular chips Frequency-hopping spread-spectrum signature waveform, N = 7 Probability density functions: (a) Rayleigh; (b) Rice (d = 2); (c) Nakagami (d = 3); (d) log-normal (op = 10) Two-element array ‘Two-element array radiation patterns with equal gains and phase offsets of p = m (left) and y = 1/2 (right) Discrete-time K-dimensional vector of matched filter outputs K-dimensional channel of matched filter outputs for asynchronous CDMA channel Direct-sequence signature waveforms with V = TDMA signals subject to multipath. K = 2, a, = —0.5, ay = 2/3, y = 3/8 Six-element antenna array Cauchy vs, Gaussian binary hypothesis test Conditional distributions of ¥ given b = —I and b= +1 Linear plot of Q(x) for x > 0 Log-inear plot of Q(x) and its bounds: (a) (3.34), (b) (3.35), (c) (3.37), and (3.38) Bank of single-user matched filters, 36 43 52 56 63 67 74 78 8&7 95 98 103 104,LIST OF FIGURES 3.6 37 38 3.9 31 a 3.14 3.16 3.17 41 43 44 Bank of single-user matched filters (K = 2) Output of matched filter for user 1 with one interfering user Bit-error-rate of single-user matched filter with two synchronous users and p = 0.2 Signal-to-noise ratios necessary to achieve bit-error-rate not higher than 3 x 10° for both users, parametrized by p Decision regions in the two-dimensional space of matched filter outputs Decision regions in the one-dimensional space of matched filter output Decision regions of matched filter detector (orthogonal space); Ay = Az Decision regions of matched filter detector (orthogonal space); Ar = 6A2 Bit-error-rate of the single-user matched filter with ten equal-energy users and identical crosscorrelations 1 = 0.08; (a) exact, (b) Gaussian approximation Bit-error-rate of the single-user matched filter with fourteen equal-energy users and identical crosscorrelations x = 0.08; (a) exact, (b) Gaussian approximation Asymptotic multiuser efficiency of conventional detector as a function of the amplitude of the interferer; p = 0.2 (linear plot) Asymptotic multiuser efficiency of conventional detector as a function of the amplitude of the interferer; p = 0.2 (log-log plot) Decision regions of jointly optimum detector for Ay = Ax, p =0.2. Decision regions of jointly optimum detector for Ay = 6Az, p = 0.2 Maximum-likelihood detection for user 1 with one synchronous interferer Minimum bit-error-rate detector for user 1 with one synchronous interferer 106 107 109 i ut 112 113 115 1s 123 124, 1ST 1S7 159 160LIST OF FIGURES 45 46 47 48 49 4.10 4.11 4.12 4.)3 4.16 4.17 418 4.19 Decision regions of minimum bit-error-rate detector for 2 user 1. Ay = Az, p = Directed graph for maximum+-likelihood detection in the special case of four users with unit amplitudes Suboptimality of one-shot approach in asynchronous, channels Trellis diagram for two asynchronous users; M = | Trellis diagram for three-user asynchronous channel Optimum multiuser detector for asynchronous CDMA Bit-error-rate in a two-user channel with p =04, Ay = Ap: (a) single-user matched filter, (b) maximum-likelihood upper bound to minimum bit-error-rate, (c) genie lower bound to minimum bit-error-rate Optimum and single-user asymptotic multiuser efficiencies for two synchronous users Optimum asymptotic multiuser efficiency as a function of |p| and relative amplitude of interferer Signal-to-noise ratios necessary to achieve optimum bit-error-rate not higher than 3 x 10-° for both users If ¢ is decomposable into e’ and €", and b — 2e is the most likely vector, then both b — 2¢” and b — 2¢” are more likely than b Bit-error-rate in a fifteen-user channel with equal-power users and py = 0.09; (a) conventional, (b) maximum-likelihood upper bound to minimum bit-error-rate, (c) lower bound to minimum bit-error-rate Optimum and single-user matched-filter asymptotic multiuser efficiencies as functions of the amplitude of the interferer Computation of the a posteriori probability P[b; = +1|y] from the a priori probability my = Plb) = +1) Trellis for a 4-user channel using the decomposition in Problem 4.15 xiv 161 166 169 172 173 182 184 185 192 194LST OF FIGURES 4.20 SA 5.2, 5.3 SA 5.5 5.6 5.7 5.8 5.9 5.10 v 5.12 5.13 5.14 6.1 63 64 Markov chain modeling data stream in Problem 4.53 Decorrelating detector for the synchronous channel Modified matched filter bank for decorrelation Decorrelating receiver for two synchronous users Decision regions of the two-user decorrelating detector; Ay = Aa Asynchronous decorrelating detector One-shot approach to demodulation in asynchronous two-user channel Bit-error-rate comparison of decorrelator and single-user matched filter with two users and p = 0.75 Asymptotic multiuser efficiencies for two synchronous users, Signal-to-noise ratios necessary to achieve bit-error-rate not higher than 3 x 10° for both users. Shown for {pl = 0, 0.3, 0.5, and compared with the single-user matched filter detector regions (dashed) Signal-to-noise ratios necessary to achieve bit-error-rate not higher than 3 x 10~* for both users. Shown for || = 0.8, 0.9, and compared with the optimal regions (dashed) Optimality of decorrelating detector near-far resistance Bit-error-rate of decorrelating detector and single-user matched filter detector. Five equal-energy interferers Signature waveforms for Problem 5.20 Signature waveforms for Problem 5.22 Linear detector that maximizes asymptotic efficiency for the two-user synchronous channel Asymptotic multiuser efficiencies for two synchronous users MMSE linear detector for the synchronous channel MMSE linear receiver for two synchronous users. xv 230 235 237 238 238 244 247 251 252 253 290 290 295LIST OF FIGURES 65 6.6 67 68 69 6.10 6.11 7 72 7.3 74 75 716 Vd 78 7.9 7.10 7 Bit-error-rate with two users and crosscorrelation p = 0.8: (a) single-user matched filter; (b) decorrelator; (c) MMSE; (d) minimum (upper bound); (¢) minimum (lower bound) Bit-error-rate with eight equal-power users and identical crosscortelations py: = 0.1 Bit-error-rate with 100 equal-power users and random direct sequence signatures with N = 1,000 Decorrelating detector in canonical form Blind adaptive multiuser detector Complete desired-signal cancellation with mismatch Multiple-input multiple-output channel Successive cancellation for two synchronous users Equivalent implementation of successive cancellation for Wo synchronous users Decision regions of successive cancellation with A; = and A, =1 Decision regions of successive cancellation with A, =0.Sand A; =1 Decision regions of successive cancellation with A; = 2.5 and Ap =1 Decision regions of maximum-likelihood detection with Ay=Ar=1 Sliding window of decisions for demodulation of user 1 H(b, b’) is the shaded £-square normal to d(b, b’) and closest to $(b) in Dob’) Asymptotic multiuser efficiencies for two synchronous users; |p| = 0.6 Modified successive cancellation for two synchronous users Near-far resi function of crosscorrelation lance for two synchronous users as a xvi 300 306 316 320 322 335 346, 346 347 347 347 348 349 353LIST OF FIGURES 7.12, Signal-to-noise ratios necessary for successive cancellation to achieve bit-error-rate not higher than 3 x 10° for both users. Shown for |p| = 0.1, 0.3, 0.5 = 3. Signal-to-noise ratios necessary for successive cancellation to achieve bit-error-rate not higher than 3 x 107) for both users. Shown for |p| = 0.8, 0.9, and compared with the optimal regions (dashed) 7.14. Two-stage detector for two synchronous users 7.15 Decision regions of two-stage detector with Ay = I, A,=1 7.16 Three-stage detector for two synchronous users 7.17 Decision regions of m-stage detector with shaded regions Teading to limit-cycle decisions 7.18 Two-stage detector with decorrelating first stage 7.19 Decision regions of multistage detector with decorrelating first stage 7.20 Decision regions of m-stage detector (decorrelating first stage) with shaded regions leading to limit-cycle decisions 72 Asymptotic multiuser efficiencies for two synchronous users; |p| = 0.6 7.22 Near-far resistance of two-stage detector with conventional and decorrelating first stage for two synchronous users ignal-to-noise 1: necessary for two-stage detector with decorrelating first stage to achieve bit-error-rate not higher than 3 x 105 for both users 7.24 Average per-user power penalty for random signature sequences 7.25 ‘Two-user synchronous decision-feedback detector 7.26 Asynchronous decision-feedback multiuser detector 7.27 Comparison of requirements for multiuser detectors 7.28 Direct-sequence signature waveforms with N = 3 xvii 359 359 361 364 365 367 368 369 377 381 383 384 389PREFACE He that will not opply new remedies must expect new evils: for time is the greatest innovator. Francis Bacon (1561-1626) Research and development of digital communications systems is undergo- ing a revolution fueled by rapid advances in technology. With the ever- growing sophistication of signal processing and computation, advances in communication theory have an increasing potential to bridge the gap be- tween practically feasible channel utilization and the fundamental informa- tion theoretic limits on channel capacity. If conquering channel capacity is the manifest destiny of communications technology, the need for efficient use of channel bandwidth and transmission power is felt most acutely in wireless communication, where the exponentially growing demand for data rate must be accommodated in a finite segment of the radio spectrum. To add to the challenge, information is transmitted not by a single source but by several uncoordinated, bursty, and geographically separated sources, Multiuser Detection deals with the demodulation of mutually interfering digital streams of information. Cellular telephony, satellite communication, high-speed data transmission lines, digital radio/television broadcasting, fixed wireless local loops, and multitrack magnetic recording are some of the communication systems subject to multiaccess interference. The super- position of transmitted signals may originate from nonideal characteristics of the transmission medium, or it may be an integral part of the multi- plexing method as in the case of Code-Division Multiple-Access (CDMA). Multiuser detection (also known as cochannel interference suppression, multiuser demodulation, interference cancellation, etc.) exploits the con- siderable structure of the multiuser interference in order to increase the efficiency with which channel resources are employed. xixPREFACE Although isolated generalizations of digital communication models to multi-input multi-output channels had taken place as early as the 1960s, it was not until the mid 1980s that multiuser detection started developing as a cohesive body of analytical results that took into account the specific features of multiuser channels. Since then, the number of researchers working within this discipline has rapidly multiplied, to the point where it is now one of the most active and vibrant branches of digital communications. The extensive set of references collected in this book, although not pretending to be comprehensive in any way, gives evidence of the level of activity in multiuser detection in the past few years. The bibliographical notes at the end of each chapter provide an account of the development of the main results as well as a snapshot of the current state of the art. I can only hope that that part of the book will become quickly obsolete in view of the speed at which the field is currently evolving. While aiming for a fairly comprehensive coverage of the design and analy: elements of multiuser detection in the simplest setting that brings out the key concepts. A fertile ground for geometrical intuition, the linearly modulated synchronous multiuser channel proves to be a garden of Euclidean delights. Borrowing from the tradition in multiuser information theory, most of the main ideas are first introduced in the two-user channel, which emerges as a powerful pedagogical tool. Chapter 1 gives a brief introduction to the main approaches in multiac- cess communications. Chapter 2 introduces the basic channel models used throughout the book. The main paradigm is the Code-Division Multiple- Access channel, in which each user modulates its own signature wave- form. This channel is general enough to encompass orthogonal and non- orthogonal multiplexing methods, with or without spread-spectrum sig- naling, Chapter 3 covers background material on hypothesis testing and single-user detection and analyzes the effects of multiaccess interference on the single-user receiver. Chapter 4 is devoted to the design and analy- sis of optimum multiuser detectors. Linear signal processing for multiuser detection is studied in Chapters 5 and 6, with and without the constraint of complete multiuser interference suppression, respectively. Adaptive linear multiuser detection is covered in Chapter 6. Chapter 7 deals with nonlinear multiuser detectors that use decisions on the interfering digital streams to mitigate their effect. Whether it is used as a textbook, self-study tool, or research reference, the set of over 300 problems comprises an essential component of this book. They range from simple drill exercises to research results that complement is of receivers for multiaccess channels, my goal has been to distill the xxPREFACE the theory expounded in the text. T hope the reader will draw some sense of accomplishment from solving them. No prerequisites are assumed beyond undergraduate-level probability, linear algebra, and an introductory course on communications. At Prince- ton, I have used this text to teach a one-semester course on Multiuser Detec- tion to first- and second-year graduate students with diverse backgrounds. Although previous or concurrent exposure to a conventional detection and estimation course may be beneficial, Chapter 3 gives a self-contained pre- sentation of the required material. A typical “single-user” digital commu- nications course covering the fundamentals of equalization is not required either, In fact, it is my contention that (synchronous) multiaccess chan- nels provide an easier setting for learning many of the fundamentals of equalization in digital communications than the conventional single-user intersymbol interference channel. The text contains substantial material that can be tailored to serve as the core of various master’s and doctoral courses on multiuser communication. In addition, the book can be used as a self-study guide for practicing engi- neers and as a reference volume for academic and industrial researchers in communications and signal processing. SPECIAL THANKS Ezio Biciisrt + Giuseper. Caire + Brap Dickinson + Patt MEYLER Jim FREEBERSYSER * Mike HonrG + Vist Lucas + NARAYAN MANDAYAM Anpy McKezurs + U.Mapuow + Taracay Oskiper + Jay PLETT Laurie NELSON * Cart NuzMan * Mercupes Paratie + Vince Poor Craic RusurortH * SHLoMo SHamar * Joun SMeE + XiaopoNG WANG Rages SUNDARESAN * MINERVA YEUNG * MicHette Younc + BIN Yu A companion web site for this book can be found at rg/Titles/59/0521593735.html xxiCHAPTER ONE MULTIACCESS COMMUNICATIONS 1.1 THE MULTIACCESS CHANNEL The idea of using a communication channel to enable several transmitters to send information simultaneously dates back to Thomas A. Edison's 1873 invention of the diplex.' This revolutionary system enabled the simultaneous transmission of two telegraphic messages in the same di- tection through the same wire. One message was encoded by changes of polarity; the other by changing absolute values. Nowadays, there are numerous examples of multiaccess communication in which several transmitters share a common channel: mobile telephones transmitting to a base station, ground stations communicating with a satel- lite, a bus with multiple taps, multidrop telephone lines, local area networks, packet-radio networks, and interactive cable television networks, to name a few. A common feature of those communication channels is that the receiver obtains (anaisy version of) the superposition of the signals sent by the active transmitters (Figure 1.1). Oftentimes, the superposition of signals sent by different transmitters occurs unintentionally owing to nonideal effects; for example, crosstalk in telephony and in multitrack magnetic recording or any time the same radio frequency band is used simultaneously by distant trans- mitters, as in cellular telephony, radio/television broadcasting, and wireless local loops. Although occasionally the terms multiplexing and multiaccess are used interchangeably, multiaccess usually refers to situations where the message sources are not collocated and/or operate autonomously. The message sources ina multiaccess channel are referred to as users. The multiaccess communication scenario depicted in Figure 1.1 encom- passes not only the case of a common receiver for all users, but the case of several receivers, each of which is interested in the information sent by one * See Conot [60).CHAPTER 1. MULTIACCESS COMMUNICATIONS User 3 Receiver -—~ Usrk Noise user (or a subset of users) only, Multiaccess communication is sometimes referred to as multipoint-to-point communication. The engineering issues in the dual point-to-mudlripoint? clrannel depend on the commonality of the information transmitted to each destination. At one extreme, the same in- formation is delivered to all recipients, for example, in radio and television broadcasting or in cable television; at the other extreme, the messages trans- mitted to different recipients are independent, for example, a base station transmitting to mobile units. The latter scenario falls conceptually within the multiaccess channel model; in that case, the receiver (say one of the mo- bile units) is interested in only one of the information sources transmitted by the base station, 1.2. FDMA AND TDMA The advent of radio-frequency modulation in the early twentieth century enabled several radio transmissions to coexist in time and space without mutual interference by using different carrier frequencies. The same idea was used in long-distance wire telephony. Frequency-Division Multi plexing or Frequency-Division Multiple Access (FDMA) assigns a different carrier frequency to each user so that the resulting spectra do not overlap (Figure 1.2). Band-pass filtering (or heterodyning) enables separate demod- ulation of each channel. In Time-Division Multiplexing, time is partitioned into slots assigned to each incoming digital stream in round-robin fashion (Figure 1.3). Demul- tiplexing is carried out by simply switching on to the received signal at the appropriate epochs. Time division can be used not only to multiplex collocated message sources but also by geographically separated users who * Point-to-multipoint and multipoint-to-point channels are sometimes distinguished either as downlink and uplink channels, respectively, or as forward and reverse chan- nels, respectively. FIGURE 1.1. Multiaccess communicationFIGURE 1.2. Frequency- Division Multiple Access. FIGURE 1.3. TimeDivision Multiple Access showing guard limes between slots. 1.2 FOMA AND TDMA have the ability to maintain time-synchronism, in what is commonly re- ferred to as Time-Division Multiple Access (TDMA). Note that FODMA allows completely uncoordinated transmissions in the time domain: no time-synchronization among the users is required. This advantage is not shared by TDMA where all transmitters and receivers must have access to acommon clock, ‘The important feature of frequency-division and time-division multiac- cess techniques is that, for all conceptual purposes, the various users are operating in separate noninterfering channels. To put it in the signal-space language of digital communications, those multiaccess techniques operate by ensuring that the signals transmitted by the various users are mutually orthogonal. Channel or receiver nonideal effects may require the insertion of guard times in TDMA (Figure 1.3) and spectral guard bands in FOMA (Figure 1.2) to avoid cochannel interference. Why would it make sense to consider multiaccess techniques that do not adhere to the principle of dividing the channel into independent noninterfer- ing subchannels? One reason is that noninterfering multiaccess strategies may waste channel resources when the number of potential users is much greater than the number of simultaneously active users at any given time. Think for example of wireless telephony; if each subscriber were assigned a fixed radio frequency channel, only a tiny fraction of the spectrum would be utilized at any given time. Analogously, in TDMA most of the time slots would be empty, at any given time. How is it possible to assign the channel resources to the users in dynamic (in other words, on demand) rather than static fashion as above? At the expense of some increase in complexity, one possibility is to setup a separate reservation channel, where the users who want to use the channel notify the receiver, which, then, partitions the original channel using TDMA or FDMA. among the active users only. This presupposes a separate feedback channel that notifies every user of the time or frequency slot where it is allowed to transmit, However, note that the reservation channel is a multiaccess channel and we still have to cope with the same issue as before, namely, how to partition the resources of that channel dynamically. USER ] | USER USER] [USER | ] USER] ] USER 2 3 1 1 2 3 1CHAPTER 1, MULTIACCESS COMMUNICATIONS 1.3. RANDOM MULTIACCESS Random multiaccess communication is one of the approaches to dynamic channel sharing. When a user has a message (usually referred :0 as a packet in this context) to transmit it goes ahead and transmits it as if it were the sole user of the channel. If indeed nobody else is transmitting simultaneously, then the message is received successfully. However, the users are uncoordinated and the possibility always exists that the message will interfere (in time and frequency) with another transmission. In such case, itis typically assumed in random multiaccess communication that the receiver cannot demodulate reliably several simultaneous messages. The only alternative left is to notify the transmitters that a collision has hap- pened and, thus, their messages have to be retransmitted. Collisions would reoccur forever if upon notification of a collision, the transmitters involved ‘were to retransmit immediately (or after a similar delay). To overcome this, users wait a random period of time before retransmitting. The main distin- guishing feature among the existing random access communication systems is the algorithm used by the transmitters to determine the retransmission delay for each colliding packet. The first random multiaccess communication system was the ALo#ta sys- tem proposed for a radio channel in 1969 (Abramson [9]). Some coaxial- cable local area networks, typified by the widely used Eruerner, employ a “polite” version of ALona, called Carrier-Sense Multiple Access (CSMA), where users listen to the channel before transmitting so as not to collide with an ongoing transmission (Kleinrock and Tobagi [211]. In general, random multiaccess communications are best suited for very bursty chan- nels, in which it is not likely that more than one user will be transmitting simultancously. The main theoretical advances in this area occurred in the 1970s through the mid 1980s.’ Polling (Hayes and Sherman [139]) is an- other multiaccess strategy where simultaneous transmissions are avoided. ‘The receiver asks every transmitter that shares a common channel (say, in round-robin fashion) whether it has anything to transmit, 1.4 CDMA The channel-sharing approaches discussed so far are based on the philosophy of letting no more than one transmitter occupy a given time-frequency slot. Whenever this condition is violated in random-access ? See Bertsekas and Gallager [29] and Abramson [10].FIGURE 1.4, Orthogonal signals assigned fo wo users. FIGURE 1.5. Fourier transforms (magnitude, f > 0) of waveforms in Figure 1.4. 1.4 CDMA su at) communication, the receiver is unable to recover any of the colliding transmissions. As we remarked before, reception free from interchannel interference is a consequence of the use of orthogonal signaling, It is im- portant to realize that this can be accomplished by signals that overlap both in time and in frequency. For example, consider the time-limited signals s1 and s2 in Figure 1.4, Those signals overlap both in the time and frequency domains (Figure 1.5), yet their crosscorrelation or inner product is zero: r (si, 82) =| 51(f)82() dt = 0. dd) ‘0 A simple two-user multiaccess communication system could be designed by letting users | and 2 modulate antipodally signals s; and 52, respectively. ‘This means that user transmits s;(¢) in order to send | and —s;(r) in order to send 0 (Figure 1.6) in successive time epochs of duration 7. Let us assume that the system is synchronous in the sense that the transmission rate is the same for both users (equal to 1/7 bits per second) and their bit epochs are perfectly aligned (Figure 1.6). How can the information transmitted by both users be demodulated now that they overlap in both frequency and time? As we see in Figure 1.6, a hypothetical receiver that observed the sum of both signals (with identi- cal amplitude) can easily demodulate the transmitted bit streams. The bit transmitted by user 1 is equal to | or 0 depending on whether the ramp received in the corresponding bit period has positive or negative absolute value; the bit transmitted by user 2 is equal to 1 or 0 depending on whether the ramp received in the corresponding bit period is increasing or decreas- ing. However, any receiver will actually observe the sum of both signals (sip If) \ [\~.