`
`_ - _._
`
`From other
`sources
`--------- ---------------
`Channel
`Source
`bits
`bits
`~ j
`
`~
`
`~
`
`i I
`~ Source
`~ bits
`L ---- --- -- — -----
`
`1
`Channel
`bits _ _ _
`
`i
`~
`----J
`
`Optional
`
`Essential
`
`To other
`destinations
`
`Petitioner's Exhibit 1003
`Page 001
`
`
`
`-'
`
`♦.
`
`, ,`
`
`;,
`
` ;'
`
`The Aerospace Corporation, El Segundo, California
`and
`University of California, Los Angeles
`
`P T R Prentice Hall
`Englewood Cliffs, New Jersey 07632
`
`Petitioner's Exhibit 1003
`Page 002
`
`
`
`~:'',
`
`; ,
`
`'~`~
`
`Library of Congress Cataloging-in-Publication Data
`
`SKLAR~ BERNARD ~d8Y0~
`Digital communications.
`Bibliography: p.
`Includes index.
`1. Digital communications. I. Tide.
`TK5103.7.355 1988
`621.38'0413
`ISBN 0-13-211939-0
`
`87-1316
`
`EditoriaUproduction supervision and
`interior design: Reynold Rieger
`Cover design: Wanda Lubelska Design
`Manufacturing buyers: Gordon Osbourne and Paula Benevento
`
`O 1988 by P T K Prentice Hall
`Prentice-Hall, Inc.
`A Paramount Communications Company
`Englewood Cliffs, New Jersey 07632
`
`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
`
`20 19 18 17 16
`
`ISBN 0-13-211939-0
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronto
`j Prentice-Hall Hispanoamericana, S.A., Mezico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japam, Inc., Tokyo
`Simon &Schuster Asia.Pte. Ltd., Singapore
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`Petitioner's Exhibit 1003
`Page 003
`
`
`
`Contents
`
`~~E~~C~
`
`Z SIGNALS AND SPECTRA
`L 1 Digital Communication Signal Processing, 3
`1.1.1 Why Digital?, 3
`11.2
`Typical Block Diagrarrc and Transformations, 4
`1.1.3 Basic Digital Communication Nomenclature, 9
`1.1.4 Digital versus Analog Pcrforrnance Criteria, 11
`1.2 Classification of Signals, ` 11
`1.2.1 Deterministic and Random. Signals, 11
`1.2.2 Periodic and Nonperiodic Signals, 12
`1.2.3
`Analog and Discrete Signals, 12
`1.2.4 Energy and Power Signals,. 12
`The Unit Impulse Function, 13
`1.2.5
`Spectral Density, 14
`1.3.1 Energy Spectral Density, 14
`1.3.2 Power Spectral Density,
`IS
`Autocorrelation, 17
`1.4.1 Autocorrelation of an L'nergy Signal, 17
`1.4.2 Autocorrelation of a Periodic (Power) Signal, 17
`1.5 Random Signals, 18a
`1.5.1 Random Variables, 18
`1.5.2 Random Processes, 20
`
`1.4
`
`1.3
`
`~~a
`
`1
`
`vii
`
`Petitioner's Exhibit 1003
`Page 004
`
`
`
`~..9
`
`' ' ~
`
`''
`
`j
`3
`
`',
`', r
`
`j
`
`~ ~,
`
`Time Averaging and Ergodicity, 22
`1.5.3
`~'ower 5'pectral Ucnsity of a Random Process, 23
`1.5.4
`1.5.5 Noire in Communication Systems, 27
`Signal Transmission through Linear Systems, 30
`Impulse Response, 31
`1.6.1
`1.6.2 Frequency Transfer Function, 31
`1.6.3 Distortionless Transmission, 32
`1.6.4 Signals, Circuits, and Spectra, 38
`Bandwidth of Digital Data, 41
`1.7.1 Baseband versus Bandpass, 41
`1.7.2
`The Bandwidth Dilemma, 43
`Conclusion, 46
`References, 46
`Problems, 47
`
`1.6
`
`1.7
`
`1.8
`
`Z FOR1VI1iTTYNG ANI) BASEBAND TRANSMISSION
`
`51
`
`2.4
`
`2.5
`
`2.1
`Baseband Systems, 54
`2.2
`Formatting Textual Data (Character Coding), 55
`2.3 Messages, Characters, and Symbols, 55
`2.3.1 `Example of Messages, Characters, and
`Symbols, SS
`Formatting Analog Information, 59
`2.4.1
`The Sarrepling Theorem, 59
`2.4.2 Aliasing, 66
`2.4.3 Signal Interface for a Digital System, 69
`Sources of Corruption, 70
`2.5.1 Sa»~pling and Quantizing Effects, 70
`2.5.2 Channel Effects, 71
`2.5.3 Signal-to-Noise Ratio for Quantized Pulses, 72
`Pulse Code Modulation, 73
`2.6
`2.7 Uniform and Nonuniform Quantization, 74
`2.7.1 Statistics of Speech Amplitudes, 74
`2.7.2 Nonuniform Quantization, 76
`2.7.3 Companding Characteristics, 77
`Baseband Transmission, 78
`2.8.1 Waveform Representation of Binary Digits, 78
`2.8.2 PCM Waveform Types, 78
`2.8.3 Spectrnl Attributes of PCM Waveforms, 82
`2.9 Detection of Binary Signals in Gaussian Noise,- 83
`2.9.1 Maximum Likelihood Receiver Structure, 85
`2.9.2
`The Matched Filter, 88
`2.9.3 Correlation Realization of the Matched Filter, 90
`2.9.4 Application ~of the Matched Filter, 91
`2.9.5 Error Probability Performance of Binary
`Signaling, 92
`
`2.8
`
`~~~~
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 005
`
`
`
`2.10
`
`iVlultilevel Bascband Transmission, 95
`2.10.1 YCM Word SiZc, 97
`2.11 IntersymbolInterference, 98
`2.11.1 Pulse Shaping to Reduce ISI, 100
`2.11.2 Equalization, 104
`2.12 Partial Response Signaling, 106
`2.12.1 Duobinary Signaling, 106
`2.12.2 Duobinary Decoding, 107.
`2.12.3 Precoding, 108
`2.12.4 Duobinary Equivalent Transfer Function, 109
`2.12.5 Comparison of Binary with Duobinary
`Signaling, 111
`2.12.6 Polybinary Signaling, 112
`2.13 Conclusion, 112
`References, 113
`Problems, 1.13
`
`51
`
`3 BAIiiDPASS MODULATION AND DEll~IODULA'TION
`
`217
`
`3.1 Why Modulate?, 118
`3.2 Signals and Noise, 119
`3.2.1 Noise in Radio Communication Systems, 119
`3.2.2 A Geometric View of Signals and Noise, 120
`3.3 Digital Bandpass Modulation Techniques, 127
`3.3.1 Phase Shift Keying, 130
`x.3.2 Frequency Shift Keying, 130
`3.3.3 Amplitude Shift Keying, 131
`3.3.4 Amplitude Phase Keying, 131
`3.3.5 Waveform Amplitude Coefficient, 132
`3.4 Detection of Signals in Gaussian Noise, 132
`3.4.1 Decision Regions, 132
`3.4.2 Correlation Receiver, 133
`3.5 Coherent Detection, 138
`3.5.1 Coherent Detection of PSK, 138
`3.5.2 Sampled Matched Filter, 139
`3.5.3 Coherent Detection of Multiple Phase Shift
`Keying, 142
`3.5.4 Coherent Detection of FSK, 145
`3.6 Noncoherent Detection, 146
`3.6.1 Detection of Differential PSK, 146
`3.6.2 Binary Differential PSK Example, 148
`ISO -
`3.6.3 Noncoherent Detection of FSK,
`3.6.4 Minimum Required Tone Spacing for Noncoherent
`Orthogonal FSK Signaling, 152
`
`tents
`
`Contents
`
`I
`
`ix
`
`Petitioner's Exhibit 1003
`Page 006
`
`
`
`{
`~
`
`~~`~'~
`~ '
`
``
`~~
`~' ~~
`~'~
`~
`'
`~~
`'
`5 ~ "'
`fir,;
`
`:,;
`~~;.
`I!, _
`its
`~
`~~'_, _
`~~;:s~
`~
`~~
`
`I
`
`'~
`
`~i
`
`~
`
`~
`
`3.7 Error Performance for Binary Systems, 155
`3J.I Probability of Bit Error for Coherently Detected
`BPSK, 155
`3.72 Probability of Bit Error for Coherently Detected
`Differentially Encoded PSK, 160
`3.7.3 Probability of Bit Error for Coherently Detected
`FSK, 161
`3.7.4 Probability of Bit Error for• Noncoherently Detected
`FSK, 162
`3.7.5 Probability of Bit Error for DPSK, 764
`3.7.6 Comparison of Bit F,rror Performance for Various
`Modulation Types, 166
`3.8 M-ary Signaling and Performance, 167
`3.8.1
`Ideal Probability of Bit Error Performance, 167
`3.8.2 M-ary Signaling, 167
`3.8.3 Vectorial Vier of MPSK Signaling, 170
`3.8.4 BPSK and QPSK Have the Sume Bit F_rror
`Probability, 171
`3.8.5 Vectorial View of MFSK Signaling, 172
`Symbol Error Performance for M-ary Systems (M > 2), 176
`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
`3.9.4 Bit Error Probability versus Symbol Error Probability
`for Multiple Phase Signaling, 181
`3.9.5 Effects of Intersymbol Interference, 182
`3.10 Conclusion, 182
`References, 182
`Problems, 183
`
`3.9
`
`~ COMMUNICATI0111S LINK ANALYSIS
`
`187
`
`~
`
`t
`
`~'
`
`4.1 What the System Link Budget Tells the System
`Engineer, 188
`42 The Channel, 189
`4.2.1 The Concept of Free Space, 189
`4.2.2 Signal-to-Noise Ratio Degradation, 190
`4.2.3 Sources of Signal Loss and Noise,
`I90
`Received Signal Power .and Noise Power, 195
`4.3.1 The Range Equation, 195
`4.3.2 Received Signal Power as a Function of
`Frequency, 199
`4.3.3 Path Loss Is Frequency Dependent, 204
`4.3.4 Thermal Noise Power, 202
`
`4.3
`
`x
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 007
`
`
`
`4.4 Link Budget Analysis, 204
`4.41 Two F,blNo Values of Interest, 205
`4.4.2 Link Budgets Are Typically Calculated i~a
`llccibels, 206
`4.4.3 How Much Link Margin Is Enough?, 207
`4.4.4 Link Availability, 209
`4.5 Noise Figure, Noise Temperature, and System
`Temperature, 213
`4.5.1 Noise Figure, 213
`4.5.2 Noise Temperature, 215
`4.5.3 Linc Loss, 216
`4.5.4 Composite Noise Figure and Composite Noise
`Temperature, 218
`4.5.5 System Effective Temperature, 220
`4.5.6 Sky Noise Temperature, 224
`4.6 Sample Link Analysis, 228
`4.6.1 Link Budget Details, 228
`4.6.2 Receiver Figure-of-Merit, 230
`4.6.3 Received Isotropic Power, 231
`4.7 Satellite Repeaters, 232
`4.7.1 Nonrege~zerative Repeaters, 232
`4.7.2 Nonlinear Repeater Amplifiers, 236
`4.8 System Trade-Offs, 238
`4.9 Conclusion, 239
`References, 239
`Problems, 240
`
`5 CHI~NNEL CODIRTG: PART 1
`
`245
`
`187 5.1 Waveform Coding, 246 '
`5.1.1 Antipodal and Orthogonal Signals, 247
`5.1.2 M-ary Signaling, 249
`5.1.3 Waveform Coding with Correlation Detection, 249
`5.1.4 Orthogonal Codes, 251
`5.1.5 Biorthogonal Codes, 255
`Transorthogonal (Simplex) Codes, 257
`5.1.6
`5.2 Types of Error Control, 258
`Terminal Connectivity, 258
`5.2.1
`5.2.2
`Automatic Repeat Request, 259
`5.3 Structured Sequences,. 260
`5.3.1 Channel Models, 261
`5.3.2
`Code Rate anc~-Redundancy, 263
`5.3.3 Parity-Check Codes, 263
`5.3.4 Coding Gain, 266
`
`rtents
`
`Contents
`
`~o
`
`Petitioner's Exhibit 1003
`Page 008
`
`
`
`'~.:~~:
`3
`1
`. :
`
`f. ',
`~ s.. .
`
`S.5
`
`5.4 Linear Block Codes, 269
`Vector .Spaces, 269
`5.4.1
`Vector Subspaces, 270
`5.4.2
`A (6, 3) Linear Block Code Example, 271
`5.4.3
`5.4.4 Generator Matrix, 272
`Systematic Linear Black Codes, 273
`5.4.5
`5.4.6 Parity-Check Matf-ix, 275
`Syndrome Testing, 276
`5.4.7
`5.4.8 Error Correction, 277
`Coding Strength, 280
`5.5.1 Weight and Distance of Binary Vectors, 280
`5.5.2 Minimum Distance of a Linear Code, 281
`5.5.3 Error Detection and Correction, 281
`Visualization of a 6-Tuple Space, 285
`5.5.4
`5.5.5 Erasure Correction, 287
`5.6 Cyclic Codes, 288
`5.6.1 Algebraic Structure of Cyclic Cndes, 288
`5.6.2 Binary Cyclic Code Properties, 290
`5.6.3 Encoding in Systematic Form, 290
`5.6.4 Circuit for Dividing Polynomials, 292
`Systematic Encoding with an (n — k)-Stage Shift
`5.6.5
`Register, 294
`5.6.6 Error Detection with an (n — k)-Stage Shift
`Register, 296
`5.7 Well-Known Block Codes, 298
`5.7.1 Hamming Codes, 298
`5.7.2 Extended Golay Code, 301
`5.73 BCH Codes, 301
`5.7.4 Reed—Solomon Codes, 304
`5.8 Conclusion, 308
`References, 308
`309
`Problems,
`
`G CHANNEL CODING: PART 2
`
`314
`
`6.l Convolutional Encoding, 315
`(.2 Convolutional Encoder Representation, 317
`6.2.1 Connection Representation, 318
`State Representation and the State Diagram, 322
`6.2.2
`The Tree Diagram, 324
`6.2.3
`The Trellis Diagram, 326
`6.2.4
`6.3 Formulation of the Convolutional Decoding Problem, 327
`6.3.1 Maximum Likelihood Decoding, 327
`Channel Models: Hard versus Soft Decisions, 329
`6.3.2
`The Viterbi Convolutional Decoding Algorithm, 333
`6.3.3
`
`xii
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 009
`
`
`
`6.3.4 An Example of Viterbi Convolutional
`Decoding, 333
`6.3.5 Path Memory and SyncJaronization, 337
`6.4 Properties of Convolutional Codes, 338
`6.4.1 Distance Properties of Convolutional Codes, 338
`6.4.2 Systematic and Nonsystematic Convolutional
`Codes, 342
`6.4.3 Catastrop{aic Error Propagation in Convolutional
`Codes, 342
`6.4.4 Performance Bounds for Convolutional Codes, 344
`6.4.5 Coding Gain, 345
`6.4.6 Best Known Convolutional Codes, 347
`6.4.7 Convolutional Code Rate Trade-Off, 348
`6.5 Other Convolutional Decoding Algorithms, 350
`6.5.1 Sequential Decoding, 350
`6.5.2 Comparisons artd Limitations of Viterbi and
`Sequential Decoding, 354
`6.5.3 Feedback Decoding, 355
`Interleaving and Concatenated Codes, 357
`6.6.1 Block Interleaving, 360
`6.6.2 Convolutional interleaving, 362
`6.6.3 Concatenated Codes, 365
`6.7 Coding and Interleaving Applied to the Compact Disc Digital
`Audio System, 366
`6.7.1 CLRC Encoding, 367
`6.7.2 CIRC Decoding, 369
`6.7.3
`Interpolation and Muting, 371
`6.8 Conclusion, 374
`References., 374
`Problems, 376
`
`6.6
`
`7 16~ODLTLATION AND CODING TRADE-OFFS
`
`3~1
`
`314
`
`~• 1 Goals of the Communications System Designer, 382
`7.2 Error Probability Plane, 383
`7.3 Nyquist Minimum Bandwidth, 385
`7.4
`Shannon—Hartley Capacity Theorem, 385
`7.4.1 Shannon Limit, 387
`7.4.2 Entropy, 389
`7.4.3 Equivocation and Effective Transmission Rate, 391
`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
`
`7.6
`
`7.5
`
`ntents
`
`Contents
`
`~~~~
`
`Petitioner's Exhibit 1003
`Page 010
`
`
`
`7.7 Bandwidth-Limited Systems, 397
`7.8 Modulation and Coding Trade-Offs, 397
`7.9 Bandwidth-Efficient Modulations, 399
`7.9.1 QPSK and Offset QPSK Signaling, 399
`7.92 Minimum Shift Keying, 403
`7.9.3 Quadratatre Amplitude Modulation, 407
`7.10 Modulation and Coding for Bandlimited Channels, 410
`7.10.1 Commercial Telephone Moderns, 411
`7.10.2 Signal Constellation Boundaries, 412
`7.10.3 Higher-Dimensional Signal Constellations, 412
`7.10.4 Higher-Density Lattice Structures, 415
`7.10.5 Combined-Gain: N-Sphcrc Mapping and Dense
`Lattice, 416
`7.10.6 Trellis-Coded Modulation, 417
`7.10.7 Trellis-Coding Example, 420
`7.11 Conclusion, 424
`References, 425
`Problems, 426
`
`l~£~k
`
`~: ~=~~1
`
`~~
`
`fI
`
`~
`~ :
`
`~ SYNCHRONIZATION
`Maurice A. King, Jr.
`
`~~9
`
`8.1 Synchronization in the Context of Digital
`Communications, 430
`8.1.1 What It Means to Be Synchronized, 430
`8.1.2 Costs versus Benefits of Synchronization
`Levels, 432
`8.2 Receiver Synchronization, 434
`8.2.1 Coherent Systems: Phase-Locked Loops, 434
`8.2.2 Symbol Synchronization, 453
`8.2.3 Frame Synchronization, 460
`8.3 - Network Synchronization; 464
`8.3.1 Open-Loop Transmitter Synchronization, 465
`8.3.2 Closed-Loop Transmitter Synchronization, 468
`8.4 Conclusion, 470
`References, 471
`Problems, 472
`
`~ lO~ULTIPLEXING AND MULTIPLE ACCESS
`
`475
`
`'~~
`
`9.1 Allocation of the Communications Resource, 476 i
`9.1.1 Frequency-Division Multiplexing/Multiple
`Access, 478
`
`xiv
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 011
`
`
`
`Tirrte-Division MultiplexingJMultiple Access, 484
`9.1.2
`9.1.3 Cornrnunicatiorts Resource Chan~aelization, 487
`9.1.4 Perfor•marzce Corrcparison of~FDMA and
`"PUMA, '488
`9.1.5 Code-Division Multiple Access, 491
`9.1.6 Space-Division and Polarization-Division Multiple
`Access, 493
`9.2 Multiple Access Communications System and
`Architecture, 495
`9.2.1 Multiple Access Information Flow, 496
`9.2.2 Demand-Assignment Multiple Access, 497
`9.3 Access Algorithms, 498
`9.3.1 ALOHA, 498
`9.3.2 Slotted ALOHA, 500
`9.3.3 Reservation-ALOHA, 502
`9.3.4 Performance Comparison of S-ALOHA
`and R-ALOHA, 503
`9.3.5 Polling Techniques, 505
`9.4 Multiple Access Techniques Employed with
`INTELSAT, 507
`9.4.1 Pr~eassignecl FDM/FM/FDMA or MCPC
`Operation, 508
`9.4.2 MCPC Modes of Accessing an INTELSAT
`Satellite, SIO
`9.4.3 SPADE Operation, 511
`9.4.4 TDMA in INTELSAT, 516
`9.4.5 Satellite-Switched TDMA irc INTELSAT, 523
`9.5 Multiple Access .Techniques for Local Area Networks,
`9.5.1 Carrier-Sense Multiple Access Networks, 526
`Token-Ring Networks, 528
`9.5.2
`9.5.3 Performance Comparison of CSMAICD
`and Token-Ring Networks, 530
`9.6 Conclusion, 531
`References, 532
`Problems, 533
`
`526
`
`SPREAD-SPECTIZLTM TECHIlTIQUES
`
`10.1 Spread-Spectrum Overview, 537
`The Beneficial Attrifiutes of Spread-Spectrum
`1 D.1.1
`Systems, 538
`10.1.2 Model for Spread-Spectrum Interference
`Rejection, 5~2
`10.1.3 A Catalog of Spreading Techniques, 543
`10.1.4 Historical Background, 544
`
`429
`
`475
`
`itents
`
`Contents
`
`536
`
`~~
`
`Petitioner's Exhibit 1003
`Page 012
`
`
`
`' ';
`
`'`-
`
``;
`~....,
`
`',
`
`10.2
`
`10.4
`
`Pseudonoise Sequences, 546
`10.2.1 Randomness Properties, 546
`10.2.2 Shift Register Sequences, 547
`10.2.3 PN Autocorrelation Function, 548
`10.3 Direct-Sequence Spread-Spectrum Systems, 549
`10.3.1 Example of Direct Segr~encing, 550
`10.3.2 Processing Gain and Performance, 552
`Frequency Hopping Systems, 555
`10.4.1 Frequency Hopping Example, 557
`10.4.2 Robustness, 558
`10.4.3 Frequency Hopping with Diversity, SS9
`10.4.4 Fust Hopping versus Slow Hopping, 560
`10.4.5 FFH/MFSK Demodulator, 562
`Synchronization, 562
`10.51 Acquisition, 563
`10.5.2
`Trucking, 568
`Spread-Spectrum Applications, 571
`10.6.1 Code-Division Multiple Access, 571
`10.6.2 Multipath Chararaels, 573
`The Jainnzing Came, 574
`10.6.3
`Further Jamming Considerations, 579
`10.7.1 Broadband Noise Jamming, 579
`10.7.2 Partial-Band Noise Jamming, 581
`10.7.3 M~~Itiple-Tone Jamming,
`.583
`10.7.4 Pulse Jamming, 584
`10.7.5 Repeat-Back Jamming, 386
`IDJ.6 BLADES System, 588
`10.8 Conclusion, 589
`References, 589
`Problems, 591
`
`10.5
`
`10.6
`
`10.7
`
`',
`
`',
`
`',
`
`,
`
`595
`
`11 SOURCE CODING
`Fredric J. Harris
`
`11.1 Sources, 596
`11.1.1 Discrete Sources, 596
`11.1.2 Waveform Sources, 601
`11.2 Amplitude Quantizing, 603
`11.2.1 Quantizing Noise, 605
`~ 11.2.2
`Uniform Qatarctizing, 608
`11.2.3
`Saturation, 611
`11.2.4
`llithering, 614
`11.2.5 Nonuniform Quantizing, 617
`11.3 Differential Pulse (erode Modulation, 627
`11.3.1 One-Tup Prediction, 630
`11.3.2 N-Tap Prediction, 631
`
`~
`
`xvi
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 013
`
`
`
`11.3.3 Delta Modulation, 633
`11.3.4 Adaptive Prediction, 639
`11.4 Block Coding, 643
`11.4.1 Vector Quantizing, 643
`11.4.2
`Transform Coding, 645
`11.4.3 Quatatization for Transfoj•~~i Coding, 647
`11.4.4 Subband Coding, 647
`11.5 SynthesisiAnalysis Coding, 649
`11.51 Vncoders, 650
`11.5.2 Linear Predictive Coding, 653
`7 1.6 Redundancy-Reducing Coding, 653
`11.6.1 Properties of Codes, 655
`11.6.2 Huffman 'Code, 657
`11.6.3 Run-Length Codes, 660
`11.7 Conclusion, 663
`References, 663
`Problems, 664
`
`12 ENCRYPTION AND DECRYPTION
`
`668
`
`595
`
`12.1 Models, Goals, and Early Cipher Systems, 669
`12.1.1
`A Model of the Encryption acrd Decryption
`Process, 669
`12.1.2
`System Goals, 671
`12.1.3
`Classic Threats, 671
`12.1.4
`Classic Ciphers, 672
`12.2 The Secrecy of a Cipher System, 675
`12.2.1 Perfect Secrecy, 675
`12.2.2
`Entropy and Equivocation, 678
`12.2.3 Rate of a Language and Redundancy, 680
`12.2.4 Uriiciry Distance and Ideal Secrecy, 680
`12.3 Practical Security, 683
`12.3.1 Confusion and Diffusion, 683
`12.3.2
`Substitution, 683
`12.3.3 Permutation, 685
`12.3.4 Product Cipher System, 686
`12.3.5
`The Data Encryption Standard, 687
`12.4 Stream Encryption, 694
`12.4.1 Example of Key Generation Using a Linear
`Feedback Shift Register, 694
`Vulnerabilities of Linear Feedback Shift
`Registers, 693`
`Synchronous and Self-Synchron~~us Stream
`Encryption Systems, 697
`
`12.4.3
`
`12.4.2
`
`ntents
`
`Contents
`
`xvii
`
`Petitioner's Exhibit 1003
`Page 014
`
`
`
`12.5 Public Key Cryptosystems, 698
`12.5.1 Signature Authevztication Using a Public Key
`Cryptosystem, 699
`12.5.2 A Trapdoor One-Way Function, 700
`The Rivest—Shamir—Adelrraan Scheme, 701
`12.5.3
`T1ee Knapsack Problem, 703
`12.5.4
`12.5.5 A Public Key Cryptosystem Based on a Trapdoor
`Knapsack, 705
`12.6 Conclusion, 707
`References, 707
`Problems, 708
`
`~ A RE~JIEW OF FOURIER TECHNI(ZUES
`
`710
`
`A.1
`A.2
`
`A.3
`
`A.4
`
`A.5
`
`A.6
`
`Signals, Spectra, and Linear Systems, 710
`Fourier Techniques for Linear System Analysis, 711
`A.2,1 Fourier Series Transform, 713
`Spectrum of a Pulse Train, 716
`A.2.2
`Fourier• Integral Transform, 719
`A.2.3
`Fourier Transform Properties, 720
`Time Shifting Property, 720
`A.31
`Frequency Shifting Property, 720
`A.3.2
`Useful Functions, 721
`A.4.1 Unit Impulse Function, 721
`A.4.2 Spectrum of a Sinusoid, 721
`Convolution, 722
`A.5.1 Graphical Illustration of Convolution, 726
`Time Convolution Property, 726
`A.5.2
`Frequency Convolution Property, 726
`A.5.3
`A.5.4 Convolution of a Function with a Unit
`Impulse, 728
`A.5.5 Demodulation Application of Convolution, 729
`Tables of Fourier Transforms and Operations, 731
`References, 732
`
`~.
`<~:
`
`1 ''
`• '`
`
`~
`
`1
`
`~
`
`~
`
`~
`
`B.1 Bayes' Theorem, %33
`B.1.1 Discrete Form of Bayes' Theorem, 734
`B..1.2 Mixed Form of Bayes' Theorem, 736
`
`[~Z~?
`
`Contents
`
`Petitioner's Exhibit 1003
`Page 015
`
`
`
`B.2 Decision Theory, 738
`8.21 Components of the Declision Theory Problem, 738
`8.2.2
`The Likelihood Ratio Test and tJze Maximum
`A Posteraori Cr~iter~ion, 739
`82.3
`The Maximum Likelihood Criterion, 739
`B.3 Signal Detection Example, 740
`B.31
`The Maximum Likelihood Binary Decision, 740
`B.3.2 Probability of Bit Error, 741
`References, 743
`
`C RESPONSE OF CORR~LATORS TO WHITE NOISE
`
`OFTElii USED IDEIiT'I'ITI~S
`
`E A CONVOLUTIONAL ENCODER/DECODER
`COMPUTER PROGRAM
`
`LIST OF SYMBOLS
`
`II~TDEX
`
`" 744
`
`746
`
`X48
`
`759
`
`7f5
`
`r7~Ii:
`
`733
`
`ntents
`
`Contents
`
`xix
`
`Petitioner's Exhibit 1003
`Page 016
`
`
`
`Pref ac e
`
`This book is intended to provide a comprehensive coverage of digital commu-
`nication systems for senior-level undergraduates,first-year graduate students, and
`practicing engineers. Even though the emphasis of the book is on digital com-
`munications, necessary analog fundamentals are included, since analog wave-
`forms are used for the radio transmission of digital signals.
`The key feature of a digital communication system is that it deals with a
`finite set of discrete messages, in contrast to an analog communication system in
`which messages are defined on a continuum. The objective at the receiver of the
`digital system is not to reproduce a waveform with precision; it is, instead, to
`determine from anoise-perturbed signal which of the finite set of waveforms had
`been sent by the transmitter. In fulfillment of this objective, an impressive as-
`sortment of signal processing techniques has arisen over the past two decades.
`The book develops these important techniques in the context of a unified
`structure. The structure, in block diagram form, appears at the beginning of each
`chapter; blocks in the diagram are emphasized, as appropriate, to correspond to
`the subject of that chapter. Major purposes of the book are (1) to add organization
`and structure to a field that has grown rapidly in the last two decades, and (2) to
`ensure awareness of the "big picture" even while delving into the details. The
`signals and key processing steps are traced from the information source through
`the transmitter, channel, receiver, and ultimately to the information sink. Signal
`transformations are organized according to functional classes: formatting and
`source coding, modulation, channel coding, multiplexing and multiple access,
`spreading, encryption, and synchronization. Throughout the book, emphasis is
`
`xxi
`
`Petitioner's Exhibit 1003
`Page 017
`
`
`
`placed on system goals and the need to trade off basic system parameters such
`as signal-to-noise ratio, probability of error, and bandwidth (spectral) expenditure.
`
`ORGANIZATION OF THE BOOK
`It is assumed that the reader is familiar with Fourier methods and convolution.
`Appendix A reviews these techniques, emphasizing those properties that are par-
`ticularly useful in the study of communication theory. It is also assumed that the
`reader has a knowledge of basic probability and has some familiarity with random
`variables. Appendix B builds on these disciplines for a short treatment on statis-
`tical decision theory with emphasis on hypothesis testing—so important in the
`understanding of detection theory. Chapter 1 introduces the overall digital com-
`munication system and the basic signal transformations that are highlighted in
`subsequent chapters. Some basic ideas of random variables and the additive white
`Gaussian noise (AWGN) model are reviewed. Also, the relationship between
`power spectral density and autocorrelation, and the basics of signal transmission
`through linear systems, are established. Chapter 2 covers the signal processing
`step, known as formatting, the step that renders an information signal compatible
`with a digital system. Chapter 2 also emphasizes the transmission of baseband
`signals. Chapter 3 deals with bandpass modulation and demodulation techniques.
`The detection of digital signals in Gaussian noise is stressed, and receiver optim-
`ization is examined. Chapter 4 deals with link analysis, an important subject for
`providing overall system insight; it considers some subtleties usually neglected
`at the college level. Chapters 5 and 6 deal with channel coding—a cost-effective
`way of providing improvement in system error performance. Chapter 5 empha-
`sizes linear block coding, and Chapter 6 emphasizes convolutional coding.
`Chapter 7 considers various modulation/coding system trade-offs dealing
`with probability of bit error performance, bandwidth efficiency, and signal-to-
`noise ratio. Chapter 8 deals with synchronization for digital systems. It covers
`phase-locked-loop implementation for achieving carrier synchronization; bit syn-
`chronization, frame synchronization, and network synchronization; and some fun-
`damentals of synchronization as applied to satellite links.
`Chapter 9 treats multiplexing and multiple access. It explores techniques
`that are available for utilizing the communication resource efficiently. Chapter
`10 introduces spread-spectrum techniques and their application in such areas as
`multiple access, ranging, and interference rejection. This technology is particu-
`larly important for most military communication systems. The subject of source
`coding in Chapter 11 deals with data formatting, as is done in Chapter 2; the main
`difference between formatting and source coding is that source coding additionally
`involves data redundancy reduction. Rather than considering source coding im-
`mediately after formatting, source coding has purposely been treated in a later
`chapter. It is felt that the reader should be involved with the fundamental pro-
`cessing steps, such as modulation and channel coding, early in the 'book, before
`examining some of the special considerations of source coding. Chapter 12 covers
`
`xzii
`
`Preface
`
`Petitioner's Exhibit 1003
`Page 018
`
`
`
`►
`
`some basic encryption/decryption ideas. It includes some classical encryption
`concepts, as well as some of the proposals for a class of encryption systems called
`public key cryptosystems.
`If the book is used for atwo-term course, a simple partitioning is suggested:
`the first six chapters to be taught in the first term, and the last six chapters in the
`second term. If the book is used for aone-term only course, it is suggested that
`the course material be selected from the following chapters: 1, 2, 3, 4, 5, 6, 8,
`- and lU.
`
`ACKNOWLEDGMENTS
`
`This book is an outgrowth of my teaching activities at the University of California,
`i Los Angeles, and my work in the Communications Division at The Aerospace
`Corporation. A number of people have contributed in many ways and it is a
`i pleasure to acknowledge them. Dr. Maurice King, my colleague at Aerospace,
`i carefully reviewed and made important contributions to each chapter. His con-
`tinual assistance has been invaluable. He also contributed Chapter 8, Synchro-
`riization. Professor Fred Harris of San Diego State University suggested many
`i improvements and contributed Chapter 11, Source Coding. I want to pay special
`thanks to Dr. Marvin Simon of the Jet Propulsion Laboratory for providing me
`- with much encouragement and many valuable suggestions.
`r I also want to thank Professor Jim Omura of UCLA for sharing with me his
`~ considerable knowledge of encryption and thereby helping me improve Chapter
`12. Professor Raymond Pickholtz of George Washington University gave me lots
`- of beneficial advice throughout the writing process. Professors William Lindsey
`and Andreas Polydoros of the University of Southern California suggested im-
`portant improvements. Professor James Modestino of Rensselaer Polytechnic In-
`-
`stitute, Dr. Adam Lender of Lockheed Palo Alto Research Laboratory, and Pro-
`s
`fessor Ron Iltis of the University of California, Santa Barbara, each provided
`- valuable reviews. Dr. Todd Citron of Hughes Aircraft, Dr. Joe Odenwalder of
`- MA/COM Linkabit, and Dr. Unjeng Cheng of Axiomatics were extremely helpful
`in the chapters on channel coding. Mr. Don Martin and Mr.-Ned Feldman of The
`s Aerospace Corporation made numerous suggestions and contributions. I also want
`r to pay special thanks to Professor Wayne Stark of the University of Michigan,
`s whose unique critical talents enhanced the manuscript's continuity.
`- The block diagrams in Figures 1.2 and 1.3, at each chapter opening, and on
`..
`the cover of the book, first appeared in the two part paper: OO 1983 IEEE; B.
`Sklar, "A Structured Overview of Digital Communications—A Tutorial Review,"
`y IEEE Communications Magazine, August and October, 1983. Permission from
`- IEEE to reprint these figures throughout the book is gratefully acknowledged.
`r My students at UCLA and those at Aerospace used early versions of chap-
`-
`tern of this book and made many helpful contributions. I am indebted. to all those
`students who have taken my courses and thus helped me with this project. I also
`s want to express my appreciation to my management at Aerospace, Mr. Hal
`
`e Acknowledgments
`
`X~~~s
`
`Petitioner's Exhibit 1003
`Page 019
`
`
`
`McDonnell and Mr. Fred Jones, for their indulgence and moral support. I want
`to acknowledge and thank Ms. Cynthia Dickson for her diligence and speed in
`typing the entire manuscript.
`Finally, I want to thank my wife, Gwen, for her very unselfish support, her
`understanding, and her endurance of the many months I had time for only one
`devotion—the writing of this book.
`
`BERNARD SKLAR
`Tarzana, California
`
`xxiv
`
`Preface
`
`Petitioner's Exhibit 1003
`Page 020
`
`
`
`~ t
`
`~
`
`1 ~
`•
`
`~ , • •
`
`~
`
`1t
`
`n ;r
`
`~e
`
`~-------
`Information
`Source
`~
`source
`~
`bits
`W I 1
`Source,
`encode
`
`Format
`
`Encrypt
`
`From other
`sources
`
`Channel
`bits
`1
`
`~
`
`Channel
`encode
`
`Multi-
`piex
`
`Mod-
`ulate
`
`Ffeq- Multiple
`uency
`access
`spread
`
`Digital
`input
`m~
`
`Digital
`output
`
`I
`~
`~
`~ Bit
`~ stream
`~
`I
`
`S;(i)
`
`Synch-
`Digital
`ronization waveform
`
`Format
`
`Source
`decode
`„~.~..~
`
`Decrypt
`////////
`
`Channel
`decode
`...~~~~~~
`
`Demulti-
`plex
`~~~~~~.~~
`
`Demod-
`ulate
`
`UengY
`clespread
`
`Information
`sink
`
`~,~ ~
`~
`Source
`~
`bits
`
`~
`Channel
`_ bits _ _ _ _ _ _ _
`
`Optional
`Essential
`
`To other
`destinations
`
`~
`I
`I
`
`i
`
`I
`I
`
`Multiple
`access
`iiiiiiii~
`T
`
`~
`
`~e
`
`X
`M
`T
`
`~
`h
`
`n
`~
`e
`~
`
`C
`V
`
`1
`
`Petitioner's Exhibit 1003
`Page 021
`
`
`
`This book presents the ideas and techniques fiindamental to digital communication
`systems. Emphasis is placed on system design goa15 and on the need for trade-
`offs among basic system parameters _such as signal-to-noise ratio (SNR), proba-
`., .
`y.,.
`.
`is-a~f lnl to
`bility~~.~rror, and bandwidth expenditure~ Transmission ban~wic~'ht
`~esource~ there is a ~rowingrawareness that bandwidth must be conserved, shared,
`..~__
`. ~.~~ r ~~.., m_~ ,n~e...~,..., _
`._. .~s ~.~ ,_~..,
`~.
`~.,~.~
`and used efficiently. In general, we shall see that system performance can often
`;~be improved through the use of increased transmission bandwidth. However, such
`an increase is not always possible, because of physical limitations or- the constraint
`of government regulations concerning the allocation and conservation of the us-
`able electromagnetic spectrum.
`We shall deal with the transmission of information (voice, video, or data)
`over a path (channel) that may consist of wires, waveguides, or free space. Fre-
`quently, the treatment will be in the context of a satellite communications link.
`Communication via satellites has two unique characteristics: (1) the ability to
`cover the globe with a flexibility that cannot be duplicated with terrestrial links,
`and (2) the availability of bandwidth exceeding anything previously available for
`intercontinental communications. Until recently, most satellite communication
`systems have been analog in nature. However, digital communication is becoming
`increasingly attractive because of the ever-growing demand for data communi-
`cation and because digital transmission offers data processing options and flex-
`ibilities not available with analog transmission.
`The principal feature of a digital communication system (DCS) is that during
`a~f n to interval of time, it sends a ~vave~orm_.from~~a~ ~nite~ set'~of possible
`-
`e~~,.
`o,..~ ,
`_
`.~. ~~ m _... _.,
`~`~orin"s, to contrast to an analog communication system, which sends a waveform
`q__~ ~, ~.~~. ~.~
`~.._~..~,_ ~. ~_~ r.._ ~~_.~. ~_ ~, ~o_-.~-...--~
`Signals and Spectra
`Chap. 1
`
`Petitioner's Exhibit 1003
`Page 022
`
`
`
`from az~.nin.~inite ~ety.Fof~waue~orria,..s~apes_w th theoret~ca~.y,.~,t~fi~ite resolution.
`In a DCS, the objective at the receiver is not to reproduce a transmitteci~waveform
`wit precision; it si , instead; to~erinirie from _a noise-perturbed signal which~l
`wave-ec~"orm._from t_I%e-mite_ set._~f waveforms had.been sent by the transmitter, An
`important measure of system performance in a DCS is the probability ofy error
`_.__~.-
`,~_~..,
`~,~_.v......,..~~ ---~
`
`F
`
`a
`
`1.1 DIGITAL COMMUNICATION SIGNAL PROCESSING
`1.1.1 Why Digital?
`Why are communication systems, military and commercial alike, "going digital"?
`There are many reasons. The primary advantage is the ease with which digital
`signals, compared to analog signals, are regenerated. Figure 1.1 illustrates an ideal
`binary digital pulse propagating along a transmission line. The shape of the wave-
`form is affected by two basic mechanisms: (1) as all transmission lines and circuits
`have some nonideal tran