`
`destinations <<.
`
`I |||
`
`|||||
`
`Digital
`input
`mj
`
`Digital
`
`Information
`source
`
`Information
`sink
`
`From other
`sources
`
`Channel
`bits
`
`Bit
`
`stream
`
`Digital
`waveform
`
`w
`Multiple
`access
`a
`
`EZ Optional
`To other
`fia3] Essential
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 1 of 64
`
`
`
` DIGITAL
`
`
`COMMUNICATIONS
`Fundamentals and Applications
`
`BERNARD SKLAR
`The Aerospace Corporation, El Segundo, California
`an
`University of California, Los Angeles
`
`P TR Prentice Hall
`
`
`
`
`
`Englewood Cliffs, New Jersey 07632
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 2 of 64
`
`
`
`Library of Congress Cataloging-in-Publication Data
`Star, Bernarp (date)
`Digital communications,
`
`Bibliography: p.
`Includes index.
`I. Title.
`1. Digital communications.
`TKS5103.7.855
`1988
`621,.38'0413
`ISBN 0-13-211939-0
`}
`
`87-1316
`
`Editorial/production supervision and
`interior design: Reynold Rieger
`Cover design: Wanda Lubelska Design
`Manufacturing buyers: Gordon Osbourne and Paula Benevento
`
`=5© 1988 by P T R Prentice-Hall, Inc.
`= A Simon & Schuster Company
`Englewood Cliffs, New Jersey 07632
`
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`Prentice-Hall International (UK).Limited, London
`Prentice-Hall of Australia Pty, Limited, Sydney
`Prentice-Hall Canada Inc., Teronto
`Prentice-Hall Hispanoamericana, §.A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokye
`Simon & Schuster Asia Pte. Ltd., Singapore
`
`All rights reserved. No part of this book may be
`reproduced, in any form or by any means,
`without permission in writing from the publisher.
`
`Printed in the United States of America
`
`10
`
`ISBN 0-13-211939-0 O25
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 3 of 64
`
`
`
`
`
`
`
`Contents
`
`.
`j
`
`;
`|
`
`i
`
`|
`
`|
`
`|
`
`PREFACE
`
`1 SIGNALS AND SPECTRA
`
`1.1
`
`1.2
`
`1.3.
`
`1.5
`
`Digital Communication Signal Processing,
`3
`Id.) Why Digital?,
`3
`1.J.2
`Typical Block Diagram'and Transformations,
`1.4.3
`Basie Digital Communication Nomenclature,
`1.1.4 Digital versus Analog Performance Criteria,
`Classification of Signals,
`11
`1.2.1 Deterministic and Random Signals,
`1.2.2
`Periodic and Nonperiodic Signals,
`1.23 Analog and Discrete Signals,
`12
`1.2.4
`Energy and Power Signals,
`1.2.5
`The Unit Impulse Function,
`Spectral Density,
`14
`13.1
`Energy Spectral Density,
`1.3.2
`Power Spectral Density,
`1.4 Autocorrelation,
`17
`17
`1.4.1 Autocorrelation of an Energy Signal,
`1.4.2 Autocorrelation of a Periodic (Power) Signal,
`Random Signals,
`18
`L351
`Random Variables,
`1.5.2
`Random Processes,
`
`11
`12
`
`12
`13
`
`14
`15
`
`18
`20
`
`xxi
`
`1
`
`vil
`
`4
`9
`11
`
`17
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 4 of 64
`
`
`
`23
`
`30
`
`22
`Time Averaging and Ergodicity,
`15.3
`Power Spectral Density of a Random Process,
`154
`Noise in Communication Systems,
`27
`15.5
`Signal Transmission through Linear Systems,
`1.6.1
`Impulse Response,
`31
`1.6.2)
`Frequency Transfer Function,
`1.6.3 Distortionless Transmission,
`1.6.4
`Signals, Circuits, and Spectra,
`Bandwidth of Digital Data,
`41
`1.7.1
`Baseband versus Bandpass,
`1.7.2.
`The Bandwidth Dilemma,
`Conclusion,
`46
`References,
`46
`Problems,
`47
`
`31
`32
`
`38
`
`41
`
`43
`
`Contents
`
`54
`Baseband Systems,
`Formatting Textual Data (Character Coding),
`Messages, Characters, and Symbols,
`55
`2.3.1
`Example of Messages, Characters, and
`Symbols,
`55
`Formatting Analog Information,
`2.4.1
`The Sampling Theorem,
`59
`2.4.2 Aliasing,
`66
`2.4.3
`Signal Interface for a Digital System,
`Sources of Corruption,
`70
`2.5.1
`Sampling and Quantizing Effects,
`2.5.2
`Channel Effects,
`71
`2.5.3
`Signal-to-Noise Ratio for Quantized Pulses,
`Pulse Code Modulation,
`73
`Uniform and Nonuniform Quantization,
`2.7.1
`Statistics of Speech Amplitudes,
`74
`2.7.2. Nonuniform Quantization,
`76
`2.7.3
`Companding Characteristics,
`Baseband Transmission,
`78
`2.8.1 Waveform Representation of Binary Digits,
`2.8.2
`PCM Waveform Types,
`78
`82
`2.8.3
`Spectral Attributes of PCM Waveforms,
`Detection of Binary Signals in Gaussian Noise,
`2.9.1 Maximum Likelihood Receiver Structure,
`2.9.2
`The Matched Filter,
`88
`2.9.3
`Correlation Realization of the Matched Filter,
`2.9.4 Application of the Matched Filter,
`91
`2.9.5
`Error Probability Performance of Binary
`Signaling,
`92
`
`2 FORMATTING AND BASEBAND TRANSMISSION
`
`59
`
`69
`
`70
`
`74
`
`77
`
`55
`
`72
`
`78
`
`83
`
`85
`
`90
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 5 of 64
`
`
`
` Multilevel Baseband Transmission,
`
`95
`
`
`
`97
`
`2.10.1 PCM Word Size,
`98
`Intersymbol Interference,
`211.1 Pulse Shaping to Reduce ISI,
`2.41.2 Equalization,
`104
`Partial Response Signaling,
`2.12.1 Duobinary Signaling,
`2.42.2 Duobinary Decoding,
`y
`2.12.3 Precoding,
`108
`2.12.4 Duobinary Equivalent Transfer Function,
`2.12.53 Comparison of Binary with Duobinary
`Signaling,
`[11
`2.12.6 Polybinary Signaling,
`Conclusion,
`112
`References,
`113
`Problems,
`113
`
`
`
`2.11
`
`2.12
`
`2.13
`
`Nn—
`
`3.3
`
`3.4
`
`3.5
`
`3.6
`
`i100
`
`106
`106
`107
`
`112
`
`109
`
`3 BANDPASS MODULATION AND DEMODULATION
`
`117
`
`119
`120
`
`132
`132
`
`118
`Why Modulate?,
`119
`Signals and Noise,
`3.2.1 Noise in Radio Communication Systems,
`3.2.2
`A Geometric View of Signals and Noise,
`Digital Bandpass Modulation Techniques,
`127
`3.3.1
`Phase Shift Keying,
`130
`130
`3.3.2
`Frequency Shift Keying,
`131
`3.3.3 Amplitude Shift Keying,
`131
`3.3.4 Amplitude Phase Keying,
`3.3.5 Waveform Amplitude Coefficient,
`Detection of Signals in Gaussian Noise,
`3.4.]
`Decision Regions,
`132
`3.4.2
`Correlation Receiver,
`Coherent Detection,
`138
`3.5.1
`Coherent Detection af PSK,
`3.5.2.
`Sampled Matched Filter,
`139
`3.5.3
`Coherent Detection af Multiple Phase Shift
`Keying,
`142
`Coherent Detection of FSK,
`3.5.4
`Noncoherent Detection,
`146
`146
`3.6.1
`Detection of Differential PSK,
`148
`3.6.2
`Binary Differential PSK Example,
`150
`3.6.3 Noncoherent Detection of FSK,
`3.6.4 Minimum Required Tone Spacing for Noncoherent
`Orthogonal FSK Signaling,
`152
`
`133
`
`138
`
`145
`
`Contents
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 6 of 64
`
`
`
`3.7.2
`
`3.7.3
`
`3.74
`
`3.7.5
`3.7.6
`
`4. COMMUNICATIONS LINK ANALYSIS
`
`167
`
`176
`
`182
`
`155
`Error Performance for Binary Systems,
`3.7.1
`Probability ofBit Error for Coherenily Detected
`BPSK,
`155
`Prebability ofBit Error for Coherently Detected
`Differentially Encoded PSK,
`160
`Probability of Bit Error for Coherently Detected
`FSK,
`161
`Probability ofBit Error forNoncoherently Detected
`FSK,
`162
`164
`Probability of Bit Error for DPSK,
`Comparison of Bit Error Performance for Various
`Modulation Types,
`166
`167
`M-ary Signaling and Performance,
`3.8.1
`Ideal Probability of Bit Error Performance,
`3.8.2 M-ary Signaling,
`167
`170
`3.8.3
` Vectorial View ofMPSK Signaling,
`3.8.4
`BPSK and QPSK Have the Same Bit Error
`Probability,
`171
`172
`Vectorial View af MFSK Signaling,
`3.8.5
`Symbol Error Performance for M-ary Systems (M > 2),
`3.9.1
`Probability of Symbol Error for MPSK,
`176
`3.9.2
`Probability of Symbol Error for MFSK,
`177
`3.9.3 Bit Error Probability versus Symbol Error Probability
`for Orthogonal Signals,
`180
`Bit Error Probability versus Symbol Error Probability
`3.94
`for Multiple Phase Signaling,
`181
`/
`Effects of Intersymbol Interference,
`3.9.5
`Conclusion,
`182
`References,
`182
`Problems,
`183
`
`Contents
`
`4.1 What the System Link Budget Tells the System
`Engineer,
`188
`189
`The Channel,
`189
`4.2.1
`The Concept of Free Space,
`4.2.2
`Signal-to-Noise Ratio Degradation,
`4.2.3
`Sources of Signal Loss and Noise,
`Received Signal Power and Noise Power,
`4.3.1
`The Range Equation,
`195
`4.3.2 Received Signal Power as a Function of
`Frequency,
`199
`Path Loss Is Frequency Dependent,
`Thermal Noise Power,
`202
`
`4.2.
`
`4.3.3
`4.3.4
`
`190
`190
`195
`
`200
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 7 of 64
`
`
`
`|
`
`y
`
`187)
`
`
`
`4.4
`
`4.6
`
`4.7
`
`4.8
`4.9
`
`204
`Link Budget Analysis,
`205
`4.4.1
`Two E,/No Values of Interest,
`4.4.2
`Link Budgets Are Typically Calculated in
`Decibels,
`206
`4.4.3 How Much Link Margin Is Enough?,
`4.44
`Link Availability,
`209
`4.5 Noise Figure, Noise Temperature, and System
`Temperature,
`213
`213
`4.5.1 Noise Figure,
`4.5.2 Noise Temperature,
`4.5.3
`Line Loss,
`216
`4.5.4
`Composite Noise Figure and Composite Noise
`Temperature,
`218
`System Effective Temperature,
`4.5.5
`Sky Noise Temperature,
`224
`4.5.6
`Sample Link Analysis,
`228
`228
`4.6.1
`Link Budget Details,
`4.6.2
`Receiver Figure-of-Merit,
`4.6.3
`Received Isotropic Power,
`Satellite Repeaters,
`232
`232
`4.7.1 Nonregenerative Repeaters,
`4.7.2 Nonlinear Repeater Amplifiers,
`System Trade-Offs,
`238
`Conclusion,
`239
`References,
`239
`Problems,
`240
`
`207
`
`215
`
`220
`
`236
`
`230
`231
`
`5 CHANNEL CODING: PART 1
`
`245
`
`246
`5.1 Waveform Coding,
`5.1.1
`Antipodal and Orthogonal Signals,
`5.1.2 M-ary Signaling,
`249
`5.1.3 Waveform Coding with Correlation Detection,
`5.14 Orthogonal Codes,
`251
`5.1.5
`Biorthogonal Codes,
`255
`5.1.6
`Transorthogonal (Simplex) Codes,
`Types of Error Control,
`258
`258
`5.2.1
`Terminal Connectivity,
`5.2.2 Automatic Repeat Request,
`Structured Sequences,
`260
`5.3.1
`Channel Models,
`261
`5.3.2
`Code Rate and Redundancy,
`5.3.3
`Parity-Check Codes,
`263
`5.3.4
`Coding Gain,
`266
`
`5
`
`247
`
`257
`
`249
`
`259
`
`263
`
`5.2
`
`5.3.
`
`Contents
`
`
`Contents
`
`xi
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 8 of 64
`
`
`
`271
`
`273
`
`280
`281
`
`288
`
`298
`
`301
`
`304
`
`5.6.6
`
`CHANNEL CODING: PART 2
`
`269
`Linear Block Codes,
`54d
`269
`Vector Spaces,
`24.2
`270
`Vector Subspaces,
`54.3
`A (6, 3) Linear Block Code Example,
`544
`Generator Matrix,
`272
`34.5
`Systematic Linear Block Cades,
`5.4.6
`Parity-Check Matrix,
`275
`5.4.7
`Syndrome Testing,
`276
`5.4.8
`Error Correction,
`277
`Coding Strength,
`280
`Jul
`Weight and Distance of Binary Vectors,
`5.5.2
`Minimum Distance of a Linear Code,
`awd
`Error Detection and Correction,
`281
`3.5.4
`Visualization of a 6-Tuple Space,
`285
`5.5.5
`Erasure Correction,
`287
`Cyclic Codes,
`288
`5.6.1
`Algebraic Structure of Cyclic Cedes,
`2.0.2
`Binary Cyclic Code Properties,
`290
`3.6.3
`Encoding in Systematic Form, 290
`5.6.4
`Circuit for Dividing Polynomials,
`292
`3.6.5
`Systematic Encoding with an (n — k)-Stage Shift
`Register,
`294
`Error Detection with an (n — k)-Stage Shift
`Register,
`296
`Well-Known Block Codes,
`3.7.1
`Hamming Codes,
`298
`572
`Extended Golay Cade,
`ars
`BCH Codes,
`301
`5.7.4
`Reed-Solomon Codes,
`Conclusion,
`308
`References,
`308
`Problems,
`309
`
`Contents
`
`317
`
`315
`Convolutional Encoding,
`Convolutional Encoder Representation,
`6.21
`Connection Representation,
`318
`6.2.2
`State Representation and the State Diagram,
`6.2.3
`The Tree Diagram,
`324
`6.2.4
`The Trellis Diagram,
`326
`Formulation of the Convolutional Decoding Problem,
`6.3.1
`Maximum Likelihood Decoding,
`327
`6.3.2
`Channel Models: Hard versus Soft Decisions,
`6.3.3
`The Viterbi Convolutional Decoding Algorithm,
`
`322
`
`327
`
`329
`333
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 9 of 64
`
`
`
`
`
`6.4.3
`
`6.4
`
`6.5
`
`6.6
`
`6.7.
`
`6.8
`
`6.3.4 An Example ofViterbi Convolutional
`Decoding,
`333
`Path Memory and Synchronization,
`6.3.5
`Properties of Convolutional Codes,
`338
`6.4.1 Distance Properties of Convolutional Codes, 338
`6.4.2
`Systematic and Nonsystematic Convolutional
`Codes,
`342
`Catastrophic Errer Propagation in Convolutional
`Codes,
`342
`Performance Bounds for Convolutional Codes,
`6.4.4
`Coding Gain,
`345
`64.5
`Best Known Convolutional Codes,
`6.4.6
`Convolutional Code Rate Trade-Off,
`6.4.7
`Other Convolutional Decoding Algorithms,
`6.5.1
`Sequential Decoding,
`350
`6.5.2.
`Comparisons and Limitations of Viterbi and
`Sequential Decoding,
`354
`Feedback Decoding,
`355
`65.3
`Interleaving and Concatenated Codes,
`6.6.1
`Block Interleaving,
`360
`6.6.2
`Convolutional Interleaving,
`6.6.3
` Concatenated Codes,
`365
`Coding and Interleaving Applied to the Compact Disc Digital
`Audio System,
`366
`367
`6.7.1
`CIRC Encoding,
`369
`6.7.2
`CIRC Decoding,
`6.7.3
`Interpolation and Muting,
`Conclusion,
`374
`References,
`374
`Problems,
`376
`
`337
`
`344
`
`347
`348
`350
`
`357
`
`362
`
`371
`
`7 MODULATION AND CODING TRADE-OFFS
`
`381
`
`\
`
`.
`
`|
`
`| )
`
`|
`
`Goals of the Communications System Designer,
`
`Error Probability Plane,
`
`383
`
`7.1.
`
`7.2
`
`7.5
`
`7.6
`
`385
`
`382
`
`391
`
`385
`7.3. Nyquist Minimum Bandwidth,
`7.4
`Shannon—Hartley Capacity Theorem,
`741°
`Shannon Limit,
`387
`7.42
`Entropy,
`389
`74,3
`Equivocation and Effective Transmission Rate,
`Bandwidth-Efficiency Plane,
`393
`7.5.1
`Bandwidth Efficiency of MPSK and MFSK
`Modulation,
`395
`7.5.2 Analogies between Bandwidth-Efficiency and Error
`Probability Planes,
`396
`Power-Limited Systems,
`396
`
`Contents
`
`xiii
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 10 of 64
`
`
`
`399
`
`410
`
`397
`Bandwidth-Limited Systems,
`397
`Modulation and Coding Trade-Offs,
`399
`Bandwidth-Efficient Modulations,
`7.9.1
`QPSK and Offset QPSK Signaling,
`7.9.2 Minimum Shift Keying,
`403
`407
`7.9.3 Quadrature Amplitude Modulation,
`Modulation and Coding for Bandlimited Channels,
`7.10.1 Commercial Telephone Modems,
`411
`7.10.2 Signal Constellation Boundaries,
`412
`7.10.3 Higher-Dimensional Signal Constellations,
`7.10.4 Higher-Density Lattice Structures,
`415
`7.10.5 Combined-Gain: N-Sphere Mapping and Dense
`Lattice,
`416
`7.10.6 TrelliseCoded Modulation, 417
`7.10.7 Trellis-Coding Example,
`420
`Conclusion,
`424
`References,
`425
`Problems,
`426
`
`Contents
`
`412
`
`8 SYNCHRONIZATION
`Maurice A. King,Jr.
`
`8.1
`
`Synchronization in the Context of Digital
`Communications,
`430
`430
`8.1.1 What It Means to Be Synchronized,
`8.1.2
`Costs versus Benefits of Synchronization
`Levels,
`432
`434
`Receiver Synchronization,
`8.2.1
`Coherent Systems: Phase-Locked Loops,
`8.2.2
`Symbol Synchronization,
`453
`8.2.3
`Frame Synchronization,
`460
`Network Synchronization,
`464
`465
`8.3.1
`Open-Loop Transmitter Synchronization,
`8.3.2
`Closed-Loop Transmitter Synchronization, 468
`Conclusion,
`470
`References,
`471
`Problems,
`472
`
`434
`
`Q MULTIPLEXING AND MULTIPLE ACCESS
`
`9.1.
`
`Allocation of the Communications Resource,
`9.1]
`Frequency-Division Multiplexing/Multiple
`Access,
`478
`
`476)
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 11 of 64
`
`
`
`
`
`484
`487
`
`526
`
`9.1.2
`9.1.3
`9.14
`
`9.1.5
`9.1.6
`
`Time-Division Multiplexing/Multiple Access,
`Communications Resource Channelization,
`Performance Comparison of FDMA and
`TDMA,
`‘488
`491
`Code-Division Multiple Access,
` Space-Division and Polarization-Division Multiple
`Access,
`493
`Multiple Access Communications System and
`Architecture,
`495
`496
`9.2.1 Multiple Access Information Flow,
`9.2.2 Demand-Assignment Multiple Access,
`497
`Access Algorithms,
`498
`9.3.1
`ALOHA,
`498
`500
`9.3.2
`Slotted ALOHA,
`502
`9.3.3
`Reservation-ALOHA,
`9.3.4
`Performance Comparison of S-ALOHA
`and R-ALOHA,
`503
`505
`Polling Techniques,
`9.3.5
`Multiple Access Techniques Employed with
`INTELSAT,
`507
`9.4.1
`Preassigned FDM/FM/FDMA or MCPC
`Operation,
`508
`9.4.2 MCPC Modes of Accessing an INTELSAT
`Satellite,
`510
`511
`SPADE Operation,
`9.4.3
`TDMAin INTELSAT,
`516
`944
`523
` Satellite-Switched TDMA in INTELSAT,
`9.4.5
`Multiple Access Techniques for Local Area Networks,
`9.5.1
`Carrier-Sense Multiple Access Networks,
`526
`9.5.2.
`Token-Ring Networks,
`528
`9.5.3
`Performance Comparison of CSMA/CD
`and Token-Ring Networks,
`530
`Conclusion,
`531
`References,
`532
`Problems,
`533
`
`9.2
`
`9.3
`
`9.4
`
`9.5
`
`9.6
`
`10 SPREAD-SPECTRUM TECHNIQUES
`
`10.1
`
`537
`Spread-Spectrum Overview,
`M11
`The Beneficial Attributes of Spread-Spectrum
`Systems,
`538
`10.1.2 Model for Spread-Spectrum Interference
`Rejection,
`542
`A Catalog of Spreading Techniques,
`10.1.3
`10.1.4 Historical Background,
`544
`
`543
`
`Contents
`
`536
`
`xV
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 12 of 64
`
`
`
`549
`
`552
`
`559
`560
`
`571
`
`579
`579
`581
`
`546
`Pseudonoise Sequences,
`546
`10.2.1
`Randomness Properties,
`547
`10.2.2
`Shift Register Sequences,
`548
`10.2.3
`PN Autocorrelation Function,
`Direct-Sequence Spread-Spectrum Systems,
`10.3.1
`Example of Direct Sequencing,
`550
`10.3.2, Processing Gain and Performance,
`Frequency Hopping Systems,
`555
`10.4.1
`Frequency Hopping Example, 557
`10.4.2 Robustness,
`558
`10.4.3
`Frequency Hopping with Diversity,
`10.4.4
`Fast Hopping versus Slow Hopping,
`10.4.5
`FFH/IMFSK Demodulator,
`562
`Synchronization,
`562
`10.5.1 Acquisition,
`563
`10.5.2
`Tracking,
`568
`571
`Spread-Spectrum Applications,
`10.6.1
`Code-Division Multiple Access,
`10.6.2 Multipath Channels,
`573
`10.6.3
`The Jamming Game,
`574
`Further Jamming Considerations,
`10.7.1 Broadband Noise Jamming,
`10.7.2
`Partial-Band Noise Jamming,
`10.7.3 Multiple-Tone Jamming,
`583
`10.7.4
`Pulse Jamming,
`584
`10.7.5 Repeat-Back Jamming,
`10.7.6
`BLADES System,
`588
`Conclusion,
`589
`References,
`589
`Problems,
`591
`
`Contents
`
`586
`
`SOURCE CODING
`Fredric J. Harris
`
`11.1
`
`596
`Sources,
`Discrete Sources,
`Jil
`111.2 Waveform Sources,
`Amplitude Quantizing,
`603
`11.2.1
`Quantizing Noise,
`605
`11.2.2.
`Uniform Quantizing,
`608
`11.2.3
`Saturation,
`611
`11.2.4 Dithering,
`614
`11.2.5|Nonuniform Quantizing, 617
`
`Differential Pulse Code Modulation,
`627
`11.3.1
`One-Tap Prediction,
`630
`11.3.2.
`N-Tap Prediction,
`631
`
`596
`60]
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 13 of 64
`
`
`
`{14.3|Quantization for Transform Coding, 647
`
` 11.4.3
`Delta Modulation,
`Adaptive Prediction,
`11.3.4
`Block Coding,
`643
`643
`{14.1
`Vector Quantizing,
`645
`11.4.2
`Transform Coding,
`
`
`
`
`
`1144
` Subband Coding,
`647
`
`
` Synthesis/Analysis Coding,
`
`
`11.5.1
`Vocoders,
`650
`11.5.2
`Linear Predictive Coding,
`
`
`Redundancy-Reducing Coding,
`
`
`11.6.1
`Properties of Codes,
`655
`11.6.2
`Huffman Code,
`657
`
`
`11.6.3
`Run-Length Codes,
`
`
`Conclusion,
`663
`References,
`663
`
`Problems,
`
`
`
`
`
`633
`639
`
`11.4
`
`11.5
`
`11.6
`
`11.7.
`
`649
`
`653
`653
`
`660
`
`
`
`
`
`
`664
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`595
`
`ENCRYPTION AND DECRYPTION
`
`12.1 Models, Goals, and Early Cipher Systems,
`669
`12.1.1
`A Model of the Encryption and Decryption
`Process,
`669
`671
`System Goals,
`12.1.2
`671
`Classic Threats,
`12.1.3
`672
`Classic Ciphers,
`12.14
`The Secrecy of a Cipher System,
`12.2.1
`Perfect Secrecy,
`675
`678
`12.2.2
`Entropy and Equivocation,
`12.2.3
`Rate of a Language and Redundancy,
`12.2.4
`Unicity Distance and Ideal Secrecy,
`Practical Security,
`683
`12.3.1
`Confusion and Diffusion,
`12.3.2
`Substitution,
`683
`
`
`12.3.3
`Permutation,
`685
`
`
`686
`12.3.4
`Product Cipher System,
`
`
`12.3.5
`The Data Encryption Standard,
`
`
`
`
`Stream Encryption,
`694
`12.4.1
`Example of Key Generation Using a Linear
`Feedback Shift Register,
`694
`
`
`Vulnerabilities of Linear Feedback Shift
`Registers,
`695
`
`
`Synchronous and Self-Synchronous Stream
`12.4.3
`
`
`Encryption Systems,
`697
`
`
` Contents
`Contents
`
`
`
`
`
`
`
`
`
`
`
`
`
`12.2
`
`12.3.
`
`12.4
`
`12.4.2
`
`680
`680
`
`675
`
`683
`
`687
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 14 of 64
`
`
`
`12.5.2.
`12.5.3
`12.54
`12.5.5
`
`698
`Public Key Cryptosystems,
`12.5.1
`Signature Authentication Using a Public Key
`Cryptosystem,
`699
`700
`A Trapdoor One-Way Function,
`The Rivest-Shamir—Adelman Scheme,
`The Knapsack Problem,
`703
`A Public Key Cryptosystem Based on a Trapdoor
`Knapsack,
`705
`Conclusion,
`707
`References,
`707
`Problems,
`708
`
`701
`
`A. A REVIEW OF FOURIER TECHNIQUES
`
`Contents
`
`710
`Signals, Spectra, and Linear Systems,
`Fourier Techniques for Linear System Analysis,
`A.2.l
`Fourier Series Transform,
`713
`A.2.2
`Spectrum of a Pulse Train,
`716
`A.2.3_—
`Fourier Integral Transform,
`719
`Fourier Transform Properties,
`720
`A3.l
`Time Shifting Property,
`720
`A.3.2
`Frequency Shifting Property,
`Useful Functions,
`721
`Ad.
`Unit Impulse Function,
`A4.2.—
`Spectrum of a Sinusoid,
`Convolution,
`722
`A.5.1
`Graphical Illustration of Convelution,
`A.5.2
`Time Convolution Property,
`726
`726
`A353
`Frequency Convolution Property,
`A54
`Convolution of a Function with a Unit
`Impulse,
`728
` Demodulation Application of Convolution,
`A.3.5
`Tables of Fourier Transforms and Operations,
`References,
`732
`
`A.l
`A.2
`
`721
`721
`
`720
`
`711
`
`729
`731
`
`726
`
`FUNDAMENTALS OF STATISTICAL DECISION
`THEORY
`
`B.1
`
`733
`Bayes’ Theorem,
`Bild
`Discrete Form of Bayes’ Theorem,
`B12 Mixed Form of Bayes’ Theorem,
`
`734
`736
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 15 of 64
`
`
`
`B.3
`
`738
`
`739
`
`740
`
`738
`Decision Theory,
`B.2.1
`Components of the Decision Theory Problem,
`B.2.2
`The Likelihood Ratio Test and the Maximum
`A Posteriori Criterion,
`739
`The Maximum Likelihood Criterion,
`B2.3>
`Signal Detection Example,
`740
`B31
`The Maximum Likelihood Binary Decision,
`B3.2
`Probability of Bit Error,
`741
`References,
`743
`
`Contents
`
`RESPONSE OF CORRELATORS TO WHITE NOISE
`
`OFTEN USED IDENTITIES
`
`A CONVOLUTIONAL ENCODER/DECODER
`COMPUTER PROGRAM
`
`LIST OF SYMBOLS
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 16 of 64
`
`
`
`CHAPTER 7
`
`Information
`
`r
`
`From other
`sources
`
`Channel
`bits
`
`Ez req-
`uancy
`spread17
`
`Multiple
`“ag
`
`
`
`
`
`
`
`Modulation and Coding
`Trade-Ofts
`
`
`
`Digital
`Synch-
`stream ronization|waveform.
`
`
`
`Information
`sink
`
`Optional
`[] Essential
`
`To other
`destinations
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 17 of 64
`
`
`
`
`
`as ach
`will be
`plane; {
`
`7.2 ERROR PI
`
`7.1 GOALS OF THE COMMUNICATIONS SYSTEM DESIGNER
`:
`System trade-offs are fundamentaltoall digital communication designs. The goals
`of the designer are (1) to maximize transmissionbit rate, R; (2) to minimize prob-
`ability of bit error, Pg; (3) to minimize required power, or equivalently, to min-
`imize required bit energy to noise powerspectral density, £,/No; (4) to minimize
`required system bandwidth, W; (5) to maximize system utilization, that is, to
`providereliable service for a maximum numberofusers with minimum delay and
`with maximumresistance to interference; and (6) to minimize system complexity,
`computational load, and system cost. A good system designer seeks to achieve
`all these goals simultaneously. However, goals 1 and 2 are clearly in conflict with
`goals 3 and 4; they call for simultaneously maximizing R, while minimizing Pp,
`E,/No, and W. There are several constraints and theoretical limitations that ne-
`cessitate the trading off of any one system requirement with each of the others.
`Some of the constraints are:
`The Nyquist theoretical minimum bandwidth requirement
`The Shannon—Hartley capacity theorem (and the Shannonlimit)
`Governmentregulations(e.g., frequency allocations)
`Technologicallimitations (e.g., state-of-the art components)
`Other system requirements (e.g.,
`satellite orbits)
`eta
`eee
`Some ofthe realizable modulation and coding trade-offs can best be viewed
`
`382
`
`Modulation and Coding Trade-Offs
`
`Chap. 7
`
`|
`
`|
`
`|
`
`|
`
`Figure
`tection
`7.1b). I
`M-ary |
`represe
`illustrat
`
`M)is in
`
`modula
`Pz, or
`Figure ’
`as k (or
`keying
`bandwi:
`require)
`probabi
`error pr
`able for
`rate, ca
`requires
`CUPVES.
`mission
`requirec
`availab]
`point in
`in the o
`from on
`7.1a anc
`arrows.
`can be.
`movemi
`e and f.
`perform
`along li
`be achie
`trade-of
`tem isc
`3) invols
`need to
`
`Sec. 7.2
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 18 of 64
`
`
`
`
`
`
`as a changein operating point on one of two performanceplanes. These planes
`
`will be referred to as the error probability plane and the bandwidth efficiency
`
`plane; they are described in the following sections.
`
`
`
`
`
`7.2 ERROR PROBABILITY PLANE
`Figure 7.1 illustrates the family of Py versus E,/No curves for the coherent de-
`tection of orthogonal signaling (Figure 7.1a) and multiple phase signaling (Figure
`7.1b). Forsignaling schemes that process k bits at a time, the signaling is called
`
`M-ary (see Section 3.8). The modulator uses one of its M = 2" waveforms to
`representeach k-bit sequence, where M is the size of the symbolset. Figure 7.la
`
`
`illustrates the potential bit error improvement with orthogonal signaling as k (or
`
`M)is increased. For orthogonal signal sets, such as frequency shift keying (FSK)
`
`modulation, increasing the size of the symbol set can provide an improvementin
`
`Px, or a reduction in the E,/No required, at the cost of increased bandwidth.
`
`Figure 7.1b illustrates potential bit error degradation with nonorthogonal signaling
`
`as k (or M) increases. For nonorthogonal signal sets, such as multiple phase shift
`
`keying (MPSK) modulation, increasing the size of the symbol set can reduce the
`
`bandwidth requirement,but at the cost of a degraded Pz, or an increased E,/No
`
`requirement, We shall refer to these families of curves (Figure 7.1a or b) as error
`
`probability performance curves, ‘and to the plane on which they are plotted as an
`
`error probability plane. Such a plane describes the locus of operating points avail-
`
`able for a particular type ofmodulation and coding. For a given system information
`
`rate, each curve in the plane can be associated with a different fixed minimum
`
`required bandwidth; therefore, the set of curves can be termed equibandwidth
`
`curves. As the curves movein the direction of the ordinate, the required trans-
`
`mission bandwidth increases; as the curves move in the opposite direction, the
`
`required bandwidth decreases. Once a modulation and coding scheme and an
`available E;,/No are determined, system operation is characterized by a particular
`
`point in the error probability plane. Possible trade-offs can be viewed as changes
`
`in the operating point on one of the curves or as changesin the operating point
`
`from one curveto another curve of the family. These trade-offs are seen in Figure
`
`7.1a and b as changes in the system operating pointin the direction shown by the
`
`arrows. Movementof the operating point along line 1, between points a and b,
`can be viewed astrading off Ps for E,/No performance (withWfixed). Similarly,
`
`movement along line 2, between points c and d, is seen as trading Ps for W
`
`performance (with E,/No fixed), Finally, movementalongline 3, between points
`
`e and f,illustrates trading W for E,/No performance (with Py fixed), Movement
`along line 1 is effected by increasing or decreasingthe available E,/No. This can
`
`
`be achieved, for example, by increasing transmitter power, which means that the
`
`trade-off might be accomplished simply by “turning a knob,’* even after the sys-
`
`tem is configured. However, the other trade-offs (movementalong line 2 orline
`3) involve some change in the system modulation or coding scheme,and therefore
`
`need to be accomplished during the system design phase.
`
`
`
`
`
`
`
`
`
`
`Sec. 7.2
`
`Error Probability Plane
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 19 of 64
`
`
`
`
`
`(a)
`
`signaling.é
`
`23a ei Eo
`
`gz
`
`g3&aZ&a 55 5 &
`
`
`
`10 E,/No(dB)
`
`(b}
`
`
`
`Ey/Ng(dB)-
`
`(WW) 8g ‘Al qeqoud soa yg
`
`t
`S
`=
`
`I
`°
`=
`
`(IN) 8g “Auiqeqoud Joa Wg
`
`7.3 NYQI
`
`E b
`
`i
`ir
`
`tt
`Ir
`li
`bd
`
`ooPit
`
`tereooo
`
`
`
`
`
`forcoherentlydetectedM-arysignaling.(a)
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 20 of 64
`
`
`
`7.3 NYQUIST MINIMUM BANDWIDTH
`
`7.4 SHANNON-HARTLEY CAPACITY THEOREM
`
`Shannon [2] showed that the system capacity, C, of a channel perturbed by ad-
`ditive white Gaussian noise (AWGN)is a function of the average received signal
`power, S, the average noise power, N, and the bandwidth, W. The capacity re-
`lationship (Shannon—Hartley theorem) can be stated as
`S
`
`C = W logs (1 + x)
`
`(7.1)
`
`Everyrealizable system having some nonideal filtering will suffer from intersym-
`bol interference (ISI)—thetail of one pulse spilling over into adjacent symbol
`intervals so as to interfere with correct detection. Nyquist [1] showedthat, in
`theory, R, symbols per second could be detected without ISI in an R,/2 hertz
`minimum bandwidth (Nyquist bandwidth); this is a basic theoretical constraint,
`limiting the designer’s goal to expendaslittle bandwidth as possible (see Section
`2.11). In practice, R, hertz is typically required for the transmission ofR, symbols
`per second. In other words, typical digital communication throughput, without
`ISI, is limited to 1 symbol/s per hertz. The modulation or coding system assigns
`to each symbol, of its set of M symbols, a k-bit meaning, where M = 2*, Fora
`signaling scheme with a fixed bandwidth, such as MPSK, as & increases, the
`allowable data rate, R, increases, and hence the bandwidth efficiency, R/W, mea-
`sured in bits per secondperhertz, also increases. For example, movement along
`line 3, from point ¢ to point f in Figure7. 1b represents trading E,/No fora reduced
`bandwidth requirement. In other words, with the same system bandwidth one can
`transmit at an increased data rate, hence at an increased R/W.
`
`
`
`
`
`When W is in hertz and the logarithm is taken to the base 2, as shown, the capacity
`is givenin bits/s. It is theoretically possible to transmit information over such a
`channel at any rate, R, where R = C, with an arbitrarily small error probability
`by using a sufficiently complicated coding scheme. For an information rate
`R > C,it is not possible to find a code that can achieve an arbitrarily small error
`probability, Shannon’s work showed that the values of 5, N, and W set a limit
`on transmission rate, not on error probability. Shannon [3] used Equation (7.1)
`to graphically exhibit a bound for the achievable performance ofpractical systems.
`This plot, shown in Figure 7.2, gives the normalized channel capacity C/W in
`bits/s/Hz as a function of the channel signal-to-noise ratio (SNR). A related plot,
`shownin Figure 7.3, indicates the normalized channel bandwidth W/C in Hz/bits/s
`as a function of SNR in the channel. Figure 7.3 is sometimes used to illustrate
`the power—bandwidth trade-off inherent in the ideal channel. However, it is not
`a pure trade-off [4] becausethe detected noise power is proportional to bandwidth.
`N = NoW
`(7.2)
`
`Sec.7.4
`
`Shannon-Hartley Capacity Theorem
`
`385
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 21 of 64
`
`
`
`
`
`C/W (bits/s/Hz)
`
` Unattainable
`
`region
`systems 20
`
`Practical
`
`
`30
`SNR (dB)
`
`1/2
`
`Figure 7.2 Normalized channel
`capacity versus channel SNR.
`
`Unattainak
`region
`
`Substituting Equation (7,2) into Equation (7.1) and rearranging terms yields
`(7.3)
`W = logs (: i aw)
`Cc
`s
`For the case where transmission bit rate is equal to channel capacity, R = C
`we can usethe identity presented in Equation (3.94) to write
`Nod ~ Ne
`Hence we can modify Equation (7.3) as follows:
`
`os
`
`3
`
`© = 108, [! + (5)
`20W = 1 + ma (=)
`(7.6)
`7 = =o - 1)
`Figure 7.4 is a plot of W/C versus E,/Np in accordance with Equation (7.6).
`
`7.5)
`
`386
`
`Modulation and Coding Trade-Offs
`
`Chap. 7
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 22 of 64
`
`
`
` Shannon-Hartley Capacity Theorem
`
`There exists a limiting value of E,/No below which there can be no error-free
`communication at any information rate. Using the identity
`lim (1 + x)* =e
`a0
`
`Figure 7.3. Normalized channel
`bandwidth versus channel SNR.
`
`The asymptotic behavior of this curve as C/W — 0 (or. W/C > @)is discussed in
`the next section.
`
`7.4.1 Shannon Limit
`
`we can calculate the limiting value of E,,/No as follows. Let
`a (C
`~ No
`\W
`
`Then from Equation (7.5),
`
`= x log, (1 + x)!”
`
`=W
`
`Ep
`j= —
`No loge (1 + x)
`
`Ix
`
`Sec. 7.4
`
`W/C(Hz/bits/s)
`
`Practical
`systems
`
`30
`20
`SNR (dB)
`
`Unattainable
`region
`
`V4
`
`1/8
`
`
`
`
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 23 of 64
`
`
`
`W/C (Hz/bits/s)
`
`Asymptote
`log, 2 = — 1.59 dB
`
`Practical
`systems
`
`18
`
`24
`
`30
`
`E,/No (dB)
`
`1/8
`
`1/16
`
`Unattainable
`region
`
`Chap. 7
`
`This value of £,/No is called the Shannon limit. On Figure 7.1a the Shannonlimit
`is the Pp versus E,/No curve corresponding to k > ~. The curveis discontinuous,
`going from a value of Py = } to Py = Oat E,/Ny = —1.59 dB. It is not possible
`in practice to reach the Shannonlimit, because as k increases without bound,the
`bandwidth requirement and the implementation complexity increase without
`bound. Shannon’s work provided a theoretical proof for the existence of codes
`that could improve the Pg performance, or reduce the E,/No required, from the
`levels of the uncoded binary modulation schemesto levels approachingthelimiting
`curve. Fora bit error probability of 10~°, binary phase shift keying (BPSK) mod-
`ulation requires an E,/No of 9.6 dB (the optimum uncoded binary modulation),
`Therefore, Shannon’s work promised the existence ofa theoretical performance
`
`Figure 7.4 Normalized channel bandwidth versus channel E,/Np.
`
`In the limit, as C/W — 0, we get
`
`= 0.693
`
`or, in decibels = —1.59 dB
`
`(7.7)
`
`388
`
`Modulation and Coding Trade-Offs
`
`ERICSSON v. UNILOC
`Ex. 1022 / Page 24 of 64
`
`
`
`
`
`improvement of 11.2 dB over the performance of optimum uncoded binary mod-
`
`ulation, through the use of coding techniques. Today, most of that promised im-
`
`provement(approximately 7 dB) is realizable [5]. Optimum system design can
`
`best be described as a search for rational compromises or trade-offs among the
`various constraints and conflicting goals. The modulation and coding trade-off,
`that is, the: selection of modulation and coding techniques to make the best use
`of transmitter power and channel bandwidth, is important, since there are strong
`incentives to reduce the cost of generating power and to conserve the radio
`spectrum.
`
`
`
`|
`
`
`
`
`
`
`
`
`|
`
`
`
`
`
`
`|
`
`|
`
`H = — > p;logzp;_bits/source output (7.8) ))
`
`
`
`i=1
`|
`)
`;
`|
`
`wherep; is the probability of the ith output and >) p; = 1. In the case of a binary
`message or a source having only two possible outputs, with probabilities p and
`q = (1 — p), the entropyis written
`H = —(p log. p + q log: q)
`
`(7.9)
`
`|
`I
`ili
`\|
`ii
`|
`H}
`
`
`
`
`7.4.2 Entropy
`
`
`
`
`To design a communications system with a specified message handling capability,
`|
`we need a metric for measuring the information content to be transmitted. Shan-
`|
`non [2] developed such a metric, H, called the entropy of the message source
`|
`(having n possible outputs), Entropy is defined as the average amountof infor-
`|
`
`
`mation per source output and is expressed by
`}
`
`
`
`
`and is plotted versus p in Figure 7.5.
`including the
`The quantity H has a numberof interesting properties,
`
`
`following:
`
`1. Whenthe logarithm in Equation (7.8) is taken to th