DIGITAL COMMUNICATIONS
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 1
`
`

`

`DIGITAL COMMUNICATIONS
`Third Edition
`
`John G. Proakis, Ph.D., P.E.
`Department of Electrical and Computer Engineering
`Northeastern University
`
`McGraw-Hill, Inc.
`New York St. Louis San Francisco Auckland Bogota Caracas Lisbon
`London Madrid Mexico City Milan Montreal New Delhi
`San Juan Singapore Sydney Tokyo Toronto
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 2
`
`

`

`This book was set in Times Roman.
`The editors were George T. Hoffman and John M. Morriss;
`the production supervisor was Leroy A. Young.
`The cover was designed by Tana Kamine.
`Project supervision was done by The Universities Press (Belfast) Ltd.
`R. R. Donnelley & Sons Company was printer and binder.
`
`DIGITAL COMMUNICATIONS
`
`Copyright © 1995, 1989, 1983 by McGraw-Hill, Inc. All rights reserved. Printed in the
`United States of America. Except as permitted under the United States Copyright Act
`of 1976, no part of this publication may be reproduced or distributed in any form or by
`any means, or stored in a data base or retrieval system, without the prior written
`permission of the publisher.
`
`This book is printed on recycled, acid-free paper containing 10%
`postconsumer waste.
`
`1 2 3 4 5 6 7 8 9 0 D O H D O H 9 0 9 8 7 6 5
`
`ISBN 0-07-051726-6
`
`Library of Congress Cataloging-in-Publication Data
`
`Proakis, John G.
`Digital communications / John G. Proakis.—3rd ed.
`p.
`cm.—(McGraw-Hill series in electrical and computer
`engineering. Communications and signal processing)
`Includes bibliographical references and index.
`ISBN 0-07-051726-6
`1. Digital communications.
`TK5103.7.P76
`1995
`621.382—dc20
`
`94-41620
`
`I. Title.
`
`II. Series.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 3
`
`

`

`CONTENTS
`
`Preface
`
`1 Introduction
`1-1 Elements of a Digital Communication System
`1-2 Communication Channels and Their Characteristics
`1-3 Mathematical Models for Communication Channels
`1-4 A Historical Perspective in the Development of Digital
`Communications
`1-5 Overview of the Book
`1-6 Bibliographical Notes and References
`
`2 Probability and Stochastic Processes
`2-1 Probability
`2-1-1 Random Variables, Probability Distributions,
`and Probability Densities
`2-1-2 Functions of Random Variables
`2-1-3 Statistical Averages of Random Variables
`2-1-4 Some Useful Probability Distributions
`2-1-5 Upper bounds on the Tail Probability
`2-1-6 Sums of Random Variables and the Central Limit
`Theorem
`2-2 Stochastic Processes
`2-2-1 Statistical Averages
`2-2-2 Power Density Spectrum
`2-2-3 Response of a Linear Time-Invariant System to a Random
`Input Signal
`2-2-4 Sampling Theorem for Band-Limited Stochastic Processes
`2-2-5 Discrete-Time Stochastic Signals and Systems
`2-2-6 Cyclostationary Processes
`2-3 Bibliographical Notes and References
`Problems
`
`xix
`
`l
`1
`3
`11
`
`13
`16
`16
`
`17
`17
`
`22
`28
`33
`37
`53
`
`58
`62
`64
`67
`
`68
`72
`74
`75
`77
`77
`
`xi
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 4
`
`

`

`Xii
`
`CONTENTS
`
`3 Source Coding
`3-1 Mathematical Models for Information
`3-2 A Logarithmic Measure of Information
`3-2-1 Average Mutual Information and Entropy
`3-2-2
`Information Measures for Continuous Random Variables
`3-3 Coding for Discrete Sources
`3-3-1 Coding for Discrete Memoryless Sources
`3-3-2 Discrete Stationary Sources
`3-3-3 The Lempel-Ziv Algorithm
`3-4 Coding for Analog Sources—Optimum Quantization
`3-4-1 Rate-Distortion Function
`3-4-2 Scalar Quantization
`3-4-3 Vector Quantization
`3-5 Coding Techniques for Analog Sources
`3-5-1 Temporal Waveform Coding
`3-5-2 Spectral Waveform Coding
`3-5-3 Model-Based Source Coding
`3-6 Bibliographical Notes and References
`Problems
`
`4 Characterization of Communication Signals
`a n d Systems
`4-1 Representation of Bandpass Signals and Systems
`4-1-1 Representation of Bandpass Signals
`4-1-2 Representation of Linear Bandpass Systems
`4-1-3 Response of a Bandpass System to a Bandpass Signal
`4-1-4 Representation of Bandpass Stationary Stochastic
`Processes
`4-2 Signal Space Representation
`4-2-1 Vector Space Concepts
`4-2-2 Signal Space Concepts
`4-2-3 Orthogonal Expansions of Signals
`4-3 Representation of Digitally Modulated Signals
`4-3-1 Memoryless Modulation Methods
`4-3-2 Linear Modulation with Memory
`4-3-3 Nonlinear Modulation Methods with Memory
`4-4 Spectral Characteristics of Digitally Modulated Signals
`4-4-1 Power Spectra of Linearly Modulated Signals
`4-4-2 Power Spectra of CPFSK and CPM Signals
`4-4-3 Power Spectra of Modulated Signals with Memory
`4-5 Bibliographical Notes and References
`Problems
`
`5 Optimum Receivers for the Additive White
`Gaussian Noise Channel
`5-1 Optimum Receiver for Signals Corrupted by AWGN
`5-1-1 Correlation Demodulator
`5-1-2 Matched-Filter Demodulator
`
`82
`82
`84
`87
`91
`93
`94
`103
`106
`108
`108
`113
`118
`125
`125
`136
`138
`144
`144
`
`152
`152
`153
`157
`157
`
`159
`163
`163
`165
`165
`173
`174
`186
`190
`203
`204
`209
`220
`223
`224
`
`233
`233
`234
`238
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 5
`
`

`

`82
`g2
`84
`g7
`91
`93
`94
`103
`106
`108
`108
`H3
`H8
`125
`125
`136
`138
`144
`144
`
`1 S?
`
`152
`153
`'57
`157
`
`159
`163
`1^3
`165
`165
`173
`174
`186
`190
`203
`204
`209
`220
`223
`224
`
`233
`233
`234
`238
`
`CONTENTS
`
`xiii
`
`5-1-3 The Optimum Detector
`5-1-4 The Maximum-Likelihood Sequence Detector
`5-1-5 A Symbol-by-Symbol MAP Detector for Signals
`with Memory
`5-2 Performance of the Optimum Receiver for Memoryless
`Modulation
`5-2-1 Probability of Error for Binary Modulation
`5-2-2 Probability of Error for M-ary Orthogonal Signals
`5-2-3 Probability of Error for M-ary Biorthogonal Signals
`5-2-4 Probability of Error for Simplex Signals
`5-2-5 Probability of Error for M-ary Binary-Coded Signals
`5-2-6 Probability of Error for M-ary PAM
`5-2-7 Probability of Error for M-ary PSK
`5-2-8 Differential PSK (DPSK) and its Performance
`5-2-9 Probability of Error for QAM
`5-2-10 Comparison of Digital Modulation Methods
`5-3 Optimum Receiver for CPM Signals
`5-3-1 Optimum Demodulation and Detection of CPM
`5-3-2 Performance of CPM Signals
`5-3-3 Symbol-by-Symbol Detection of CPM Signals
`5-4 Optimum Receiver for Signals with Random Phase in AWGN
`Channel
`.
`5-4-1 Optimum Receiver for Binary Signals
`5-4-2 Optimum Receiver for M-ary Orthogonal Signals
`5-4-3 Probability of Error for Envelope Detection of M-ary
`Orthogonal Signals
`5-4-4 Probability of Error for Envelope Detection of Correlated
`Binary Signals
`5_5 Regenerative Repeaters and Link Budget Analysis
`5-5-1 Regenerative Repeaters
`5-5-2 Communication Link Budget Analysis
`5-6 Bibliographical Notes and References
`Problems
`
`6 Carrier and Symbol Synchronization
`6-1 Signal Parameter Estimation
`6-1-1 The Likelihood Function
`6-1-2 Carrier Recovery and Symbol Synchronization
`in Signal Demodulation
`6-2 Carrier Phase Estimation
`6-2-1 Maximum-Likelihood Carrier Phase Estimation
`6-2-2 The Phase-Locked Loop
`6-2-3 Effect of Additive Noise on the Phase Estimate
`6-2-4 Decision-Directed Loops
`6-2-5 Non-Decision-Directed Loops
`6-3 Symbol Timing Estimation
`6-3-1 Maximum-Likelihood Timing Estimation
`6-3-2 Non-Decision-Directed Timing Estimation
`
`244
`249
`
`254
`
`257
`257
`260
`264
`266
`266
`267
`269
`274
`278
`282
`284
`285
`290
`296
`
`301
`302
`308
`
`308
`
`312
`313
`314
`316
`319
`320
`
`333
`333
`335
`
`336
`337
`339
`341
`343
`347
`350
`358
`359
`361
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 6
`
`

`

`CONTENTS
`
`6-4 Joint Estimation of Carrier Phase and Symbol Timing
`6-5 Performance Characteristics of ML Estimators
`6-6 Bibliographical Notes and References
`Problems
`
`Channel Capacity and Coding
`7-1 Channel Models and Channel Capacity
`7-1-1 Channel Models
`7-1-2 Channel Capacity
`7-1-3 Achieving Channel Capacity with Orthogonal Signals
`7-1-4 Channel Reliability Functions
`7-2 Random Selection of Codes
`7-2-1 Random Coding Based on M-ary Binary-Coded Signals
`7-2-2 Random Coding Based on M-ary Multiamplitude Signals
`7-2-3 Comparison of R$ with the Capacity of the AWGN
`Channel
`7-3 Communication System Design Based on the Cutoff Rate
`7-4 Bibliographical Notes and References
`Problems
`
`Block and Convolutional Channel Codes
`8-1 Linear Block Codes
`8-1-1 The Generator Matrix and the Parity Check Matrix
`8-1-2 Some Specific Linear Block Codes
`8-1-3 Cyclic Codes
`8-1-4 Optimum Soft-Decision Decoding of Linear Block Codes
`8-1-5 Hard-Decision Decoding
`8-1-6 Comparison of Performance between Hard-Decision and
`Soft-Decision Decoding
`8-1-7 Bounds on Minimum Distance of Linear Block Codes
`8-1-8 Nonbinary Block Codes and Concatenated Block Codes
`8-1-9
`Interleaving of Coded Data for Channels with Burst
`Errors
`8-2 Convolutional Codes
`8-2-1 The Transfer Function of a Convolutional Code
`8-2-2 Optimum Decoding of Convolutional Codes—
`The Viterbi Algorithm
`8-2-3 Probability of Error for Soft-Decision Decoding
`8-2-4 Probability of Error for Hard-Decision Decoding
`8-2-5 Distance Properties of Binary Convolutional Codes
`8-2-6 Nonbinary Dual-/c Codes and Concatenated Codes
`8-2-7 Other Decoding Algorithms for Convolutional Codes
`8-2-8 Practical Considerations in the Application of
`Convolutional Codes
`8-3 Coded Modulation for Bandwidth-Constrained Channels
`8-4 Bibliographical Notes and References
`Problems
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 7
`
`

`

`365
`367
`370
`371
`
`374
`375
`375
`380
`387
`389
`390
`390
`397
`
`399
`400
`406
`406
`
`413
`413
`417
`421
`423
`436
`445
`
`456
`461
`464
`
`468
`470
`477
`
`|
`
`|
`|
`
`i
`
`I
`:
`I
`
`483
`I
`486
`b
`489
`492 |
`492
`I
`I
`500
`
`506
`511
`526
`528
`
`I
`I
`I
`I
`
`CONTENTS
`
`XV
`
`9 Signal Design for Band-Limited Channels
`9-1 Characterization of Band-Limited Channels
`9-2 Signal Design for Band-Limited Channels
`9-2-1 Design of Band-Limited Signals for No Intersymbol
`Interference—The Nyquist Criterion
`9-2-2 Design of Band-Limited Signals with Controlled ISI—
`Partial-Response Signals
`9-2-3 Data Detection for Controlled ISI
`9-2-4 Signal Design for Channels with Distortion
`9-3 Probability of Error in Detection of PAM
`9-3-1 Probability of Error for Detection of PAM with Zero ISI
`9-3-2 Probability of Error for Detection of Partial-Response
`Signals
`9-3-3 Probability of Error for Optimum Signals in Channel
`with Distortion
`9-4 Modulation Codes for Spectrum Shaping
`9-5 Bibliographical Notes and References
`Problems
`
`_
`_
`10 Communication through Band-Limited Linear
`Filter Channels
`10-1 Optimum Receiver for Channels with ISI and AWGN
`10-1-1 Optimum Maximum-Likelihood Receiver
`10-1-2 A Discrete-Time Model for a Channel with ISI
`10-1-3 The Viterbi Algorithm for the Discrete-Time White
`Noise Filter Model
`10-1-4 Performance of MLSE for Channels with ISI
`10-2 Linear Equalization
`10-2-1 Peak Distortion Criterion
`10-2-2 Mean Square Error (MSE) Criterion
`10-2-3 Performance Characteristics of the MSE Equalizer
`10-2-4 Fractionally Spaced Equalizer
`10-3 Decision-Feedback Equalization
`10-3-1 Coefficient Optimization
`10-3-2 Performance Characteristics of DFE
`10-3-3 Predictive Decision-Feedback Equalizer
`10-4 Bibliographical Notes and References
`Problems
`
`11 Adaptive Equalization
`11-1 Adaptive Linear Equalizer
`11-1-1 The Zero-Forcing Algorithm
`11-1-2 The LMS algorithm
`11-1-3 Convergence Properties of the LMS Algorithm
`11-1-4 Excess MSE Due to Noisy Gradient Estimates
`11-1-5 Baseband and Passband Linear Equalizers
`11-2 Adaptive Decision-Feedback Equalizer
`11-2-1 Adaptive Equalization of Trellis-Coded Signals
`
`534
`534
`540
`
`542
`
`548
`551
`557
`561
`561
`
`562
`
`565
`566
`576
`576
`
`583
`584
`584
`586
`
`589
`593
`601
`602
`607
`612
`617
`621
`621
`622
`626
`628
`628
`
`636
`636
`637
`639
`642
`644
`648
`649
`650
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 8
`
`

`

`HL
`
`xvi
`
`11-3 An Adaptive Channel Estimator for ML Sequence Detection
`11-4 Recursive Least-Squares Algorithms for Adaptive Equalization
`11-4-1 Recursive Least-Squares (Kalman) Algorithm
`11-4-2 Linear Prediction and the Lattice Filter
`11-5 Self-Recovering (Blind) Equalization
`11-5-1 Blind Equalization Based on Maximum-Likelihood
`Criterion
`11-5-2 Stochastic Gradient Algorithms
`11-5-3 Blind Equalization Algorithms Based on Second-
`and Higher-Order Signal Statistics
`11-6 Bibliographical Notes and References
`Problems
`
`12 Multichannel and Multicarrier Systems
`12-1 Multichannel Digital Communication in AWGN Channels
`12-1-1 Binary Signals
`12-1-2 M-ary Orthogonal Signals
`12-2 Multicarrier Communications
`12-2-1 Capacity of a Non-Ideal Linear Filter Channel
`12-2-2 An FFT-Based Multicarrier System
`12-3 Bibiliographical Notes and References
`Problems
`
`13 Spread Spectrum Signals for Digital Communications
`13-1 Model of Spread Spectrum Digital Communication System
`13-2 Direct Sequence Spread Spectrum Signals
`13-2-1 Error Rate Performance of the Decoder
`13-2-2 Some Applications of DS Spread Spectrum Signals
`13-2-3 Effect of Pulsed Interference on DS Spread Spectrum
`Systems
`13-2-4 Generation of PN Sequences
`13-3 Frequency-Hoppped Spread Spectrum Signals
`13-3-1 Performance of FH Spread Spectrum Signals in AWGN
`Channel
`13-3-2 Performance of FH Spread Spectrum Signals in Partial-
`Band Interference
`13-3-3 A CDMA System Based on FH Spread Spectrum Signals
`13-4 Other Types of Spread Spectrum Signals
`13-5 Synchronization of Spread Spectrum Signals
`13-6 Bibliographical Notes and References
`Problems
`
`14 Digital Communication through Fading
`Multipath Channels
`14-1 Characterization of Fading Multipath Channels
`14-1-1 Channel Correlation Functions and Power Spectra
`14-1-2 Statistical Models for Fading Channels
`
`652
`654
`656
`660
`664
`
`664
`668
`
`673
`675
`676
`
`680
`680
`682
`684
`686
`687
`689
`692
`693
`
`695
`697
`698
`702
`712
`
`717
`724
`729
`
`732
`
`734
`741
`743
`744
`752
`753
`
`758
`759
`762
`767
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 9
`
`

`

`652
`654
`656
`660
`664
`
`664
`668
`
`673
`675
`676
`
`680
`680
`682
`684
`686
`687
`689
`692
`693
`
`695
`697
`698
`702
`712
`
`717
`724
`729
`
`732
`
`734
`741
`743
`744
`752
`753
`
`758
`759
`762
`767
`
`CONTENTS XVli
`
`14-2 The Effect of Characteristics on the Choice
`of a Channel Model
`14-3 Frequency-Nonselective, Slowly Fading Channel
`14-4 Diversity Techniques for Fading Multipath Channels
`14-4-1 Binary Signals
`14-4-2 Multiphase Signals
`14-4-3 M-ary Orthogonal Signals
`14-5 Digital Signaling over a Frequency-Selective, Slowly Fading
`Channel
`14-5-1 A Tapped-Delay-Line Channel Model
`14-5-2 The RAKE Demodulator
`14-5-3 Performance of RAKE Receiver
`14-6 Coded Waveforms for Fading Channels
`14-6-1 Probability of Error for Soft-Decision Decoding of Linear
`Binary Block Codes
`14-6-2 Probability of Error for Hard-Decision Decoding of
`Linear Binary Block Codes
`14-6-3 Upper Bounds on the Performance of Convolutional
`Codes for a Raleigh Fading Channel
`14-6-4 Use of Constant-Weight Codes and Concatenated Codes
`for a Fading Channel
`14-6-5 System Design Based on the Cutoff Rate
`14-6-6 Trellis-Coded Modulation
`14-7 Bibliographical Notes and References
`Problems
`
`15 Multiuser Communications
`15-1
`Introduction to Multiple Access Techniques
`15-2 Capacity of Multiple Access Methods
`15-3 Code-Division Multiple Access
`15-3-1 CDMA Signal and Channel Models
`15-3-2 The Optimum Receiver
`15-3-3 Suboptimum Detectors
`15-3-4 Performance Characteristics of Detectors
`15-4 Random Access Methods
`15-4-1 ALOHA System and Protocols
`15-4-2 Carrier Sense Systems and Protocols
`15-5 Bibliographical Notes and References
`Problems
`
`Appendix A The Levinson-Durbin Algorithm
`
`Appendix B Error Probability for Multichannel
`Binary Signals
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 10
`
`

`

`XV111
`
`CONTENTS
`
`Appendix C Error Probabilities for Adaptive Reception
`of M-phase Signals
`C-l Mathematical Model for an M-phase Signaling
`Communications System
`C-2 Characteristic Function and Probability Density
`Function of the Phase 6
`C-3 Error Probabilities for Slowly Rayleigh Fading
`Channels
`C-4 Error Probabilities for Time-Invariant and Ricean
`Fading Channels
`
`Appendix D Square-Root Factorization
`References and Bibliography
`Index
`
`887
`
`887
`
`889
`
`891
`
`893
`
`897
`
`899
`
`917
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 11
`
`

`

`492 DIGITAL COMMUNICATIONS
`
`simplicity. In comparing the performance between soft-decision and hard-
`decision decoding, note that the difference obtained from the upper bounds is
`approximately 2.5 dB for 1CT6 =s Ph =£ 10~2.
`Finally, we should mention that the ensemble average error rate perfor­
`mance of a convolutional code on a discrete memoryless channel, just as in the
`case of a block code, can be expressed in terms of the cutoff rate parameter R u
`as (for the derivation, see Viterbi and Omura, 1979).
`
`-
`p
`b
`
`(q - \)q- K R^ Rc
`L±
`J"} _ g-(Rcr-«c)/«c]2 '
`
`D < J?
`IXc
`
`~~
`
`where q is the number of channel input symbols, K is the constraint length of
`the code, Rc is the code rate, and R0 is the cutoff rate defined in Sections 7-2
`and 8-1. Therefore, conclusions reached by computing R() for various channel
`conditions apply to both block codes and convolutional codes.
`
`8-2-5 Distance Properties of Binary Convolutional Codes
`
`In this subsection, we shall tabulate the minimum free distance and the
`generators for several binary, short-constraint-length convolutional codes for
`several code rates. These binary codes are optimal in the sense that, for a given
`rate and a given constraint length, they have the largest possible d[rec. The
`generators and the corresponding values of dfree tabulated below have been
`obtained by Odenwalder (1970), Larsen (1973), Paaske (1974), and Daut et al.
`(1982) using computer search methods.
`Heller (1968) has derived a relatively simple upper bound on the minimum
`free distance of a rate 1/n convolutional code. It is given by
`
`= mm
`
`2
`
`(K + I — l)n
`• 2 — 1
`-
`
`(8-2-35)
`
`where bej denotes the largest integer contained in x. For purposes of
`comparison, this upper bound is also given in the tables for the rate 1/n codes.
`For rate k/n convolutional codes, Daut et al. (1982) has given a modification to
`Heller's bound. The values obtained from this upper bound for k/n codes are
`also tabulated.
`Tables 8-2-1 to 8-2-7 list the parameter of rate l/n convolutional codes foi
`n =2,3,... ,8. Tables 8-2-8 to 8-2-11 list the parameters of several rate k/n
`convolutional codes for k =£ 4 and n
`8.
`
`8-2-6 Nonbinary Dual-/c Codes and Concatenated Codes
`
`Our treatment of convolutional codes thus far has been focused primarily on
`binary codes. Binary codes are particularly suitable for channels in w
`binary or quaternary PSK modulation and coherent demodulation is possl
`
`'
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 12
`
`

`

`on and hard-
`iper bounds is
`
`r rate perfor-
`, just as in the
`parameter RQ
`
`raint length of
`in Sections 7-2
`arious channel
`
`tance and the
`ional codes for
`hat, for a given
`sible diree. The
`low have been
`and Daut et al.
`
`n the minimum
`
`(8-2-35)
`
`3i' purposes of
`• rate 1 In codes.
`modification to
`>r k/n codes are
`
`itional codes for
`several rate k/n
`
`sed primarily on
`annels in which
`ation is possible.
`
`CHAPTER 8: BLOCK AND CONVOLUTIONAL CHANNEL CODES 493
`
`TABLE 8-2-1 RATE 1/2 MAXIMUM FREE DISTANCE CODE
`
`Constraint
`
`length K
`
`Generators in octal
`
`^free
`
`Upper bound
`on d f r Q C
`
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`
`5
`15
`23
`53
`133
`247
`561
`1,167
`2,335
`4,335
`10,533
`21,675
`
`7
`17
`35 '
`75
`171
`371
`753
`1,545
`3,661
`5,723
`17,661
`27,123
`
`5
`6
`7
`8
`10
`10
`12
`12
`14
`15
`16
`16
`
`Source: Odenwalder (1970) and Larsen (1973).
`
`5
`6
`8
`8
`10
`11
`12
`13
`14
`15
`16
`17
`
`However, there are many applications in which PSK modulation and coherent
`demodulation is not suitable or possible. In such cases, other modulation
`techniques, e.g., M-ary FSK, are employed in conjunction with noncoherent
`demodulation. Nonbinary codes are particularly matched to M-ary signals that
`are demodulated noncoherently.
`In this subsection, we describe a class of nonbinary convolutional codes,
`called dual-k codes, that are easily decoded by means of the Viterbi algorithm
`using either soft-decision or hard-decision decoding. They are also suitable
`either as an outer code or as an inner code in a concatenated code, as will also
`be described below.
`
`TABLE 8-2-2 RATE 1/3 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length K
`
`Generators in octal
`
`'A M' 1
`
`on rffrcc
`
`Upper bound
`
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`
`5
`13
`25
`47
`133
`225
`557
`1,117
`2,353
`4,767
`10,533
`21,645
`
`7
`15
`33
`53
`145
`331
`663
`1,365
`2,671
`5,723
`10,675
`35,661
`
`7
`17
`37
`75
`175
`367
`711
`1,633
`3,175
`6,265
`17,661
`37,133
`
`8
`10
`12
`13
`15
`16
`18
`20
`22
`24
`24
`26
`
`Sources: Odenwalder (1970) and Larsen (1973).
`
`8
`10
`12
`13
`15
`16
`18
`20
`22
`24
`24
`26
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 13
`
`

`

`494 DIGITAL COMMUNICATIONS
`
`TABLE 8-2-3 RATE 1/4 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length K
`
`Generators in octal
`
`Upper bound
`on rffree
`
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`
`5
`13
`25
`53
`135
`235
`463
`1,117
`2,387
`4,767
`11,145
`21,113
`
`7
`15
`27
`67
`135
`275
`535
`1,365
`2,353
`5,723
`12,477
`23,175
`
`7
`15
`33
`71
`147
`313
`733
`1,633
`2,671
`6,265
`15,537
`35,527
`
`7
`17
`37
`75
`163
`357
`745
`1,653
`3,175
`7,455
`16,727
`35,537
`
`Source: Larsen (1973).
`
`TABLE 8-2-4 RATE 1/5 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length K
`
`Generators in octal
`
`3
`4
`5
`6
`7
`8
`
`7
`17
`37
`75
`175
`257
`
`7
`17
`27
`71
`131
`233
`
`7
`13
`33
`73
`135
`323
`
`5
`15
`25
`65
`135
`271
`
`5
`15
`35
`57
`147
`357
`
`Source: Daiit et al. (1982).
`
`TABLE 8-2-5 RATE 1/6 MAXIMUM FREE DISTANCE CODES
`
`10
`13
`16
`18
`20
`22
`24
`27
`29
`32
`33
`36
`
`"tree
`
`13
`16
`20
`22
`25
`28
`
`10
`15
`16
`18
`20
`22
`24
`27
`29
`32
`33
`36
`
`Upper bound
`on rffree
`
`13
`16
`20
`22
`25
`28
`
`Constraint
`length
`
`Generators in octal
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`7
`7
`
`17
`13
`
`37
`33
`
`73
`65
`
`173
`135
`
`253
`235
`
`7
`5
`
`17
`15
`
`35
`25
`
`75
`47
`
`151
`163
`
`375
`313
`
`7
`5
`
`13
`15
`
`27
`35
`
`55
`57
`
`135
`137
`
`331
`357
`
`Source: Daut et al. (1982).
`
`^free
`
`16
`
`20
`
`24
`
`27
`
`30
`
`34
`
`Upper bound
`on i/llLl.
`
`16
`
`20
`
`24
`
`27
`
`30
`
`34
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 14
`
`

`

`*
`
`CHAPTER 8: BLOCK AND CONVOLUTIONAL CHANNEL CODES 495
`
`TABLE 8-2-6 RATE 1/7 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length K
`
`Generators in octal
`
`dfree
`
`on dtrec
`
`Upper bound
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`7
`5
`
`17
`13
`
`35
`33
`
`53
`47
`
`165
`135
`
`275
`235
`
`7
`5
`
`17
`15
`
`27
`35
`
`75
`67
`
`145
`147
`
`253
`313
`
`7
`5
`
`13
`15
`
`25
`37
`
`65
`57
`
`173
`137
`
`375
`357
`
`7
`
`13
`
`27
`
`75
`
`135
`
`331
`
`18
`
`23
`
`28
`
`32
`
`36
`
`40
`
`Source: Daut et al. (1982).
`
`18
`
`23
`
`28
`
`32
`
`36
`
`40
`
`TABLE 8-2-7 RATE 1/8 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length K
`
`Generators in octal
`
`Upper bound
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`7
`5
`
`17
`13
`
`37
`35
`
`57
`75
`
`153
`135
`
`275
`331
`
`7
`7
`
`17
`15
`
`33
`33
`
`73
`47
`
`111
`135
`
`275
`235
`
`5
`7
`
`13
`15
`
`25
`27
`
`51
`67
`
`165
`147
`
`253
`313
`
`5
`7
`
`13
`17
`
`25
`37
`
`65
`57
`
`173
`137
`
`371
`357
`
`21
`
`26
`
`32
`
`36
`
`40
`
`45
`
`Source: Daut et al. (1982).
`
`on rffrce
`
`21
`
`26
`
`32
`
`36
`
`40
`
`45
`
`TABLE 8-2-8 RATE 2/3 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`length X
`
`Generators in octal
`
`^Aree
`
`Upper bound
`on rffrec
`
`2
`3
`4
`
`17
`27
`236
`
`06
`75
`155
`
`15
`72
`337
`
`3
`5
`7
`
`4
`6
`7
`
`Source: Duat et al. (1982).
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 15
`
`

`

`496
`
`DIGITAL COMMUNICATIONS
`
`TABLE 8-2-9 RATE k/5 MAXIMUM FREE DISTANCE CODES
`
`Rate
`
`2/5
`
`3/5
`
`4/5
`
`Constraint
`length K
`
`Generators in octal
`
`2
`3
`4
`
`2
`
`2
`
`17
`27
`247
`
`35
`
`07
`71
`366
`
`23
`
`11
`52
`171
`
`75
`
`12
`65
`266
`
`61
`
`04
`57
`373
`
`47
`
`237
`
`274
`
`156
`
`255
`
`337
`
`^A'ree
`
`6
`10
`12
`
`5
`
`3
`
`Upper bound
`on d[rce
`
`6
`10
`12
`
`5
`
`4
`
`Source: Daut et al. (1982).
`
`TABLE 8-2-10 RATE k / 1 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`Upper bound
`
`Rate
`
`length K
`
`Generators in octal
`
`^frce
`
`on
`
`2/7
`
`2
`
`05
`15
`
`06
`13
`
`12
`17
`
`15
`
`9
`
`14
`
`9
`
`14
`
`3
`
`4
`
`2
`
`2
`
`33
`25
`
`312
`171
`
`45
`57
`
`130
`156
`
`55
`53
`
`125
`266
`
`21
`43
`
`067
`255
`
`72
`75
`
`247
`373
`
`36
`71
`
`237
`337
`
`47
`
`366
`
`18
`
`18
`
`62
`
`274
`
`8
`
`6
`
`8
`
`7
`
`3/7
`
`4/7
`
`Source: Daut et al. (1982).
`
`TABLE 8-2-11 RATES 3/4 AND 3/8 MAXIMUM FREE DISTANCE CODES
`
`Constraint
`
`Rate
`
`length K
`
`Generators in octal
`
`3/4
`
`3/8
`
`2
`
`2
`
`13
`
`15
`51
`
`25
`
`42
`36
`
`61
`
`23
`75
`
`47
`
`61
`47
`
`^free
`
`4
`
`8
`
`Upper bound
`on rffre(.
`
`4
`
`8
`
`Source: Daut et al. (1982).
`
`A dual-/c rate 1/2 convolutional encoder may be represented as shown in
`Fig. 8-2-16. It consists of two (K = 2) A:-bit shift-register stages and n
`function generators. Its output is two fc-bit symbols. We note that the co
`considered in Example 8-2-3 is a dual-2 convolutional code.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 16
`
`