e
`fee ee
`Ronald E.Crochiere
`
`eeehag =m =f)6)gf
`
`Petitioner Apple Inc.
`Ex. 1009, Cover
`
`iT
`
`

`

`PRENTICE-HALL SIGNAL PROCESSING SERIES
`
`Alan V. Oppenheim, Editor
`
`ANDREWS and HUNT Digital Image Restoration
`BRIGHAM The Fast Fourier Transform
`CASTLEMAN Digital Image Processing
`CROCHIERE and RABINER Multirate Digital Signal Processing
`DUDGEON and MERSEREAU Multi-Dimensional Signal Processing
`HAMMING Digital Filters, 2nd edition
`LEA (editor) Trends in Speech Recognition
`LIM (editor) Speech Enhancement
`McCLELLAN and RADER Number Theory in Digital Signal Processing
`OPPENHEIM (editor) Applications of Digital Signal Processing
`OPPENHEIM and SCHAFER Digital Signal Processing
`OPPENHEIM, WILLSKY with YOUNG Signals and Systems
`RABINER and GOLD Theory and Applications of Digital Signal Processing
`RABINER and SCHAFER Digital Processing of Speech Signals
`ROBINSON and TREITEL Geophysical Signal Analysis
`TRIBOLET Seismac Applications of Homomorphic Signal Processing
`
`Petitioner Apple Inc.
`Ex. 1009, p. ii
`
`

`

`MULTIRATE DIGITAL
`SIGNAL PROCESSING
`
`RONALD E. CROCHIERE
`
`LAWRENCE R. RABINER
`
`Acoustics Research Department
`Bell Laboratories
`Murray Hill, New Jersey
`
`Prentice-Hall. Inc., Englewood Cliffs, New Jersey 07632
`
`Petitioner Apple Inc.
`Ex. 1009, p. iii
`
`

`

`Library of Congress Cataloging in Publication Data
`
`Crochiere, Ronald E.
`Multirate digital signal processing.
`
`(Prentice-Hall signal processing series)
`Includes index.
`I. Signal processing-Digital techniques.
`I. Rabiner, Lawrence R.
`II. Title.
`III. Series.
`TK5102.5.C76
`1983 621.38'043
`ISBN 0-13-605162-6
`
`82-23.113
`
`Text processing: Donna Manganelli
`Editorial/production and supervision by Barbara Cassel and Mary Carnis
`Cover design: Mario Piazza
`Manufacturing buyer: Anthony Caruso
`
`© 1983 by Prentice-Hall, Inc., 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
`
`10 9 8 7 6 5 4 3 2
`
`I
`
`ISBN 0-13-605162-6
`
`Prentice-Hall International, Inc., London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Prentice-Hall of Southeast Asia Pte. Ltd., Singapore
`Whitehall Books Limited, Wellington, New Zealand
`
`Petitioner Apple Inc.
`Ex. 1009, p. iv
`
`

`

`To our families,
`Gail and Ryan
`and
`Suzanne, Sheri, Wendi, and Joni
`for their love, encouragement, and support.
`
`Petitioner Apple Inc.
`Ex. 1009, p. v
`
`

`

`Petitioner Apple Inc.
`Petitioner Apple Inc.
`Ex. 1009, p. vi
`Ex. 1009,p. vi
`
`

`

`Contents
`
`PREFACE
`
`ACKNOWLEDGMENTS
`
`. 1 INTRODUCTION
`
`1.0 Basic Considerations
`1.1 Sampling Rate Conversion 3
`1.2 Examples of Multirate Digital Systems 4
`1.2.1 Sampling Rate Conversion in Digital
`Audio Systems 4
`1.2.2 Conversion Between Delta Modulation
`and PCM Signal Coding Formats 5
`1.2.3 Digital Time Division Multiplexing (TDM) to
`Frequency Division Multiplexing (FDM) Translation 5
`1.2.4 Sub-Band Coding of Speech Signals 6
`1.2.5 Short-Time Spectral Analysis· and Synthesis 8
`1.3 Scope of the Book 9
`References 10
`
`2 BASIC PRINCIPLES OF SAMPLING AND SAMPLING RATE
`· - CONVERSION
`
`2.0 Introduction 13
`
`XV
`
`xix
`
`13
`
`vii
`
`Petitioner Apple Inc.
`Ex. 1009, p. vii
`
`

`

`viii
`
`Contents
`
`'2.1 Uniform Sampling and the Sampling Theorem 13
`2.1.1 Uniform Sampling Viewed as a Modulation Process 13
`2.1.2 Spectral Interpretations of Sampling 15
`2.1.3 The Sampling Theorem 18
`2.1.4 Reconstruction of an Analog Signal from Its Samples 20
`2.1.5 Summary of the Implications of the Sampling Theorem 21
`2.2 Sampling Rate Conversion - An Analog Interpretation 22
`2.3 Sampling Rate Conversion - A Direct Digital Approach 29
`2.3.1 Relationship to Time-Varying Systems 29
`2.3.2 Sampling Rate Reduction - Decimation by an
`Integer Factor M
`31
`2.3.3 Sampling Rate Increase - Interpolation by an
`Integer Factor L 35
`2.3.4 Sampling Rate Conversion by a Rational
`Factor M /L 39
`2.4 Decimation and Interpolation of Bandpass Signals 42
`2.4.1 The Sampling Theorem Applied to Bandpass Signals 42
`Integer-Band Decimation and Interpolation 43
`2.4.2
`2.4.3 Quadrature Modulation of Bandpass Signals 48
`2.4.4 Single-Sideband Modulation 52
`2.4.5 Discussion 56
`2.5 Summary 57
`References 57
`
`3) STRUCTURES AND NETWORK THEORY FOR MULTIRATE
`DIGITAL SYSTEMS
`
`59
`
`3.0 Introduction 59
`1 3.1 Signal-Flow Graph Representation of Digital Systems 60
`3.1.1 Signal-Flow Graphs: Basic Principles 61
`3.1.2 Commutation of Branch Operations and Circuit
`Identities 63
`3.1.3 Transposition and Duality for Multirate Systems 68
`3.2 A Review of Structures for Linear Time-Invariant Filters 70
`3.2.1 FIR Direct-Form Structure 71
`3.2.2 Transposed Direct-Form Structure for FIR Filters 72
`3.2.3 Structures for IIR Digital Filters 72
`3.3 Structures for FIR Decimators and Interpolators
`76
`3.3.1 Direct and Transposed Direct-Form FIR Structures for
`Decimators and Interpolators with Integer Changes in
`Sampling Rate 76
`3.3.2 Polyphase FIR Structures for Decimators and
`Interpolators with Integer Changes in Sampling
`Rate 79
`
`Petitioner Apple Inc.
`Ex. 1009, p. viii
`
`

`

`Contents
`
`ix
`
`3.3.3 Polyphase Structures Based on Clockwise Commutator
`Models 86
`3.3.4 FIR Structures with Time-Varying Coefficients for
`Interpolation/Decimation by a Factor of LIM 88
`3.4 IIR Structures for Decimators and Interpolators with
`Integer Changes in Sampling Rate 91
`3.4.1 Polyphase Structures for IIR Decimators and
`Interpolators 93
`3.4.2 Direct-Form Structures and Structures with
`Time-Varying Coefficients for IIR Decima tors
`and Interpolators 98
`3.4.3 Comparison of Structures for Decimation and
`Interpolation 99
`3.5 Advanced Network Concepts of Linear Multirate and
`Time-Varying Structures 1 00
`3.5.1 System Representation of Linear Time-Varying
`and Multirate Networks 101
`3.5.2 Cascading Networks and Commutation of
`Network Elements 108
`3.5.3 Network Duality 112
`3.5.4 Network Transposition and Tellegen's Theorem 116
`3.5.5 Transposition of Complex Networks 121
`3.6 Summary 124
`References 124
`
`4 DESIGN OF DIGITAL FILTERS FOR DECIMATION
`AND INTERPOLATION
`
`127
`
`4.0 Introduction 127
`4.1 Digital Filter Design Fundamentals 128
`4.1.1 Basic Considerations and Properties 128
`4.1.2 Advantages and Disadvantages of FIR and IIR
`Filters for Interpolation and Decimation 130
`4.2 Filter Specifications for Sampling Rate Changing System 132
`4.2.1 The Prototype Filter and Its Polyphase Representation 132
`4.2.2
`Ideal Frequency Domain Characteristics for
`Interpolation Filters 136
`Ideal Frequency Domain Characteristics for
`Decimation Filters 139
`4.2.4 Time Domain Properties of Ideal Interpolation
`Filters 140
`4.2.5 Time Domain Properties of Ideal Decimation
`Filters 142
`4.3 Filter Design Procedures for FIR Decimators and Interpolators 143
`
`4.2.3
`
`Petitioner Apple Inc.
`Ex. 1009, p. ix
`
`

`

`X
`
`Contents
`
`4.3.1 FIR Filters Based on Window Designs 143
`4.3.2 Equiripple (Optimal) FIR Designs 146
`4.3.3 The Effects of the cjJ Bands for Equiripple
`Designs 150
`4.3.4 Equiripple FIR Filters for Interpolation with
`Time Domain Constraints 154
`4.3.5 Half-Band FIR Filters- A Special Case of FIR
`Designs for Conversion by Factors of 2 155
`4.3.6 Minimum Mean-Square-Error Design of FIR
`Interpolators - Deterministic Signals 157
`4.3.7 Solution of the Matrix Equation 163
`4.3.8 Properties of the Minimum Mean-Square-Error
`Interpolators 165
`4.3.9 Design of FIR Interpolators with Minimax Error
`in the Frequency Domain 167
`4.3.10 Design of FIR Interpolators with Minimax Error
`in the Time Domain 172
`4.3.11 Linear Interpolation 175
`4.3.12 Lagrange Interpolators 177
`4.3.13 Discussion 180
`4.4 Filter Design Procedures for IIR Decimators and Interpolators 181
`4.4.1
`Ideal Characteristics and Practical Realizations
`of IIR Decimators and Interpolators 181
`4.4.2 Conventional IIR Filter Designs 183
`4.4.3 Special IIR Designs Based on the Transformation of
`Conventional Designs 185
`4.4.4 A Direct Design Procedure for Equiripple IIR Filters
`for Decimation and Interpolation 186
`4.5 Comparisons of IIR and FIR Designs of Interpolators and
`Decimators 188
`References 190
`
`5 MULTISTAGE IMPLEMENTATIONS
`OF SAMPLING RATE CONVERSION
`
`193
`
`5.0 Introduction 193
`5.1 Computational Efficiency of a 2-Stage Structure -A Design
`Example 196
`5.2 Terminology and Filter Requirements for Multistage Designs 199
`5.2.1 Overall Filter Requirements 199
`5.2.2 Lowpass Filter Requirements for Individual Stages 202
`5.2.3 Filter Specifications for Individual Stages which
`Include "Don't-Care" Bands 204
`5.2.4 Passband and Stopband Tolerance Requirements 205
`
`Petitioner Apple Inc.
`Ex. 1009, p. x
`
`

`

`Contents
`
`xi
`
`5.2.5 Design Considerations 206
`5.3 Multistage FIR Designs Based on an Optimization Procedure 207
`5.3.1 Analytic Expressions for the Required Filter Order
`for Each Stage of a Multistage Design 208
`5.3.2 Design Criteria Based on Multiplication Rate 209
`5.3.3 Design Criteria Based on Storage Requirements 210
`5.3.4 Design Curves Based on Computer-Aided Optimization 211
`5.3.5 Application of the Design Curves and Practical
`Considerations 216
`5.4 Multistage Structures Based on Half-Band FIR Filters 218
`5.4.1 Half-Band Designs with No Aliasing in the Final
`Transition Band 220
`5.4.2 Half-Band Designs for Power-of-2 Conversion Ratios
`and Aliasing in the Final Transition Band 222
`5.5 Multistage FIR Designs Based on a Specific Family of Half-Band
`Filter Designs and Comb Filters 227
`5.5.1 Comb Filter Characteristics 227
`5.5.2 A Design Procedure Using a Specific Class of
`Filters 231
`5.6 Multistage Decimators and Interpolators Based on IIR
`Filter Designs 235
`5.7 Considerations in the Implementation of Multistage Decimators
`and Interpolators 244
`5.8 Summary 249
`References 249
`
`6 MULTIRATE IMPLEMENTATIONS
`OF BASIC SIGNAL PROCESSING OPERATIONS
`
`251
`
`6.0 Introduction 251
`6.1 Multira~ Implementation of Lowpass Filters 252
`6.1.1 Design Characteristics of the Lowpass Filters 256
`6.1.2 Multistage Implementations of the Lowpass Filter
`Structure 258
`6.1.3 Some Comments on the Resulting Lowpass Filters 260
`6.1.4 Design Example Comparing Direct and Multistage
`Implementations of a Lowpass Filter 261
`6.2 Multirate Implementation of a Bandpass Filter 263
`6.2.1 Pseudo Integer-Band, Multirate Bandpass Filter
`Implementations 265
`6.2.2 Alternative Multirate Implementations of Bandpass
`Filters 267
`6.2.3 Multirate Implementation of Narrow-Band Highpass
`and Bandstop Filters 270
`
`Petitioner Apple Inc.
`Ex. 1009, p. xi
`
`

`

`xil
`
`Contents
`
`6.3 Design of Fractional Sample Phase Shifters Based
`on Multirate Concepts 271
`6.3.1 Design of Phase Shifter Networks
`with Fixed Phase Offsets 274
`6.4 Multirate Implementation of a Hilbert Transformer 275
`6.5 Narrow-Band, High-Resolution Spectral Analysis Using
`Multirate Techniques 280
`6.6 Sampling Rate Conversion Between Systems
`with Incommensurate Sampling Rates 283
`6.7 Summary 286
`References 287
`
`7 MULTIRATE TECHNIQUES IN FILTER BANKS
`AND SPECTRUM ANALYZERS AND SYNTHESIZERS
`
`289
`
`7.0 Introduction 289
`7.1 General Issues and Definitions 290
`7.2 Uniform DFT Filter Banks and Short-Time Fourier
`Analyzers and Synthesizers 296
`7.2.1 Filter Bank Interpretation Based on the
`Complex Modulator 297
`7.2.2 Complex Bandpass Filter Interpretation 300
`7.2.3 Polyphase Structures for Efficient Realization
`of Critically Sampled DFT Filter Banks 303
`7.2.4 Polyphase Filter Bank Structures for K=Ml 311
`7.2.5 Weighted Overlap-Add Structures for Efficient
`Realization of DFT Filter Banks 313
`7.2.6 A Simplified Weighted Overlap-Add Structure
`for Windows Shorter than the Transform Size 324
`7.2.7 Comparison of the Polyphase Structure and the
`Weighted Overlap-Add Structure 325
`7.3 Filter Design Criteria for DFT Filter Banks 326
`7.3.1 Aliasing and Imaging in the Frequency Domain 327
`7.3.2 Filter-Bank-Design by Frequency Domain Specification
`The Filter-Bank-Sum Method 332
`7.3.3 Aliasing and Imaging in the Time Domain 335
`7.3.4 Filter Bank Design by Time Domain Specification
`The Overlap-Add Method
`339
`7.3.5 Relationship of Time and Frequency Domain Specifications 341
`7.4 Effects of Multiplicative Modifications in the DFT Filter Bank
`and Methods of Fast Convolution 346
`7.4.1 The General Model for Multiplicative Modifications 346
`7.4.2 Modifications in the Filter-Bank-Sum Method 351
`7.4.3 Modifications in the Overlap-Add Method 352
`
`Petitioner Apple Inc.
`Ex. 1009, p. xii
`
`

`

`Contents
`
`xiil
`
`7.4.4 Time-Invariant Modifications and Methods of
`Fast Convolution 352
`7.4.5 Other Forms of Filter Bank Modifications and
`Systems 355
`7.5 Generalized Forms of the DFT Filter Bank 356
`7.5.1 The Generalized DFT (GDFT) 356
`7.5.2 The GDFT Filter Bank 358
`7.5.3 Polyphase Structure for the GDFT Filter Bank 360
`7.5.4 Weighted Overlap-Add Structure for the GDFT
`Filter Bank 362
`7.5.5 Filter Design Criteria for the GDFT Filter Bank 365
`7.6 Uniform Single-Sideband (SSB) Filter Banks 366
`7.6.1 Realization of SSB Filter Banks from Quadrature
`Modulation Designs 367
`7 .6.2 Critically Sampled SSB Filter Banks with
`k 0 - 1/4 371
`7.6.3 SSB Filter Banks Based on k 0 = 1/2 Designs 373
`7.7 Filter Banks Based on Cascaded Realizations and Tree
`Structures 376
`7.7.1 Quadrature Mirror Filter (QMF) Bank Design 378
`7.7.2 Finite Impulse Response (FIR) Designs for QMF
`Filter Banks 382
`7.7.3 Polyf>hase Realization of Quadrature Mirror Filter
`Banks 387
`7.7.4 Equivalent Parallel Realizations of Cascaded
`Tree Structures 392
`7.8 Summary 395
`References 396
`Appendix 7.1 401
`
`INDEX
`
`405
`
`Petitioner Apple Inc.
`Ex. 1009, p. xiii
`
`

`

`Petitioner Apple Inc.
`Petitioner Apple Inc.
`Ex. 1009, p. xiv
`Ex. 1009, p. xiv
`
`

`

`Preface
`
`The idea for a monograph on multirate digital signal processing arose out of an
`IEEE Workshop held at Arden House in 1975. At that time it became clear that
`the field of multirate signal processing was a burgeoning area of digital signal
`processing with a specialized set of problems. Several schools of thought had arisen
`as to how to solve the problems of multirate systems, and a wide variety of
`applications were being discussed. At that time, however, the theoretical basis for
`multirate processing was just emerging. Thus no serious thought was given to
`writing a monograph in this area at that time.
`A steady stream of theoretical and practical papers on multirate signal
`processing followed the Arden House Workshop and by 1979 it became clear to the
`authors that the time was ripe for a careful and thorough exposition of the theory
`and implementation of multirate digital systems. Our initial estimate was that a
`moderate size monograph would be adequate to explain the basic theory and to
`illustrate principles of implementation and application of the theory. However once
`the writing started it became clear that a: full and rich field had developed, and that
`a full sized text was required to do justice to all aspects of the field. Thus the
`current text has emerged.
`The area of multirate digital signal processing is basically concerned with
`problems in which more than one sampling rate is required in a digital system. It
`is an especially important part of modern (digital) telecommunications theory in
`which digital transmission systems are required to handle data at several rates (e.g.
`teletype, Fascimile, low bit-rate speech, video etc.). The main problem is the
`design of an efficient system for either raising or lowering the sampling rate of a
`
`XV
`
`Petitioner Apple Inc.
`Ex. 1009, p. xv
`
`

`

`xvi
`
`Preface
`
`signal by an arbitrary factor. The process of lowering the sampling rate of a signal
`has been called decimation; similarly the process of raising the sampling rate of a
`signal has been called interpolation. Both processes have been studied for a long
`time, especially by numerical analysts who were interested in efficient methods for
`tabulating functions and providing accurate procedures for interpolating the table
`entries. Although the numerical analysts learned a great deal about temporal
`aspects of multirate systems it was not until recently that more modern techniques
`were applied that enabled people to understand both temporal and spectral aspects
`of these systems.
`The goal of this book is to provide a theoretical exposition of all aspects of
`multirate digital signal processing. The basis for the theory is the Nyquist
`sampling theorem and the general theory of lowpass and bandpass sampling. Thus
`in Chapter 2 we present a general discussion of the sampling theorem and show
`how it leads to a straightforward digital system for changing the sampling rate of a
`signal. The canonic form of the system is a realization of a linear, periodically
`time-varying digital system. However for most cases of interest considerable
`simplifications in the form of the digital system are realized. Thus in the special
`cases of integer reductions in sampling rate, integer increases in sampling rate, and
`rational fraction changes in sampling rate, significant reductions in complexity of
`the digital system are achieved. In such cases the digital system basically involves
`filtering and combinations of subsampling (taking 1 of M samples and throwing
`away the rest) and sampling rate expansion (inserting L-1 zero valued samples
`between each current sample).
`It is also shown in Chapter 2 how to efficiently change the sampling rate of
`bandpass (rather than lowpass) signals. Several modulation
`techniques are
`discussed
`including bandpass
`translation
`(via quadrature or single-sideband
`techniques) and integer-band sampling.
`In Chapter 3 we show how to apply standard digital network theory concepts
`to the structures for multirate signal processing. After a brief review of some
`simple signal-flow graph principles, we show in what ways these same general
`principles can (or often cannot) be used in multirate structures. We then review
`the canonic structures for linear time-invariant filters, such as the FIR direct form
`and IIR cascade form, and show how efficient multirate structures can be realized
`by combining the signal-flow graph principles with the filtering implementations.
`We also introduce, in this chapter, the ideas of polyphase structures in which sub(cid:173)
`sampled versions of the filter impulse response are combined in a parallel structure
`with a commutator switch at either the input or output. We conclude this chapter
`with a discussion of advanced network concepts which provide additional insights
`and interpretations into the properties of multirate digital systems.
`In Chapter 4 we discuss the basic filter design techniques used for linear
`digital filters in multirate systems. We first describe the canonic lowpass filter
`characteristics of decimators and interpolators and discuss the characteristics of
`ideal (but nonrealizable) filters. We then review several practical lowpass filter
`design procedures
`including
`the window method and
`the equiripple design
`
`Petitioner Apple Inc.
`Ex. 1009, p. xvi
`
`

`

`Preface
`
`xvii
`
`It is shown that in some special cases ·the lowpass filter becomes a
`method.
`multistopband filter with "don't care" bands between each stopband. In such cases
`improved efficiency in filter designs can be achieved.
`Two special classes of digital filters for multirate systems are also introduced
`in Chapter 4, namely half-band designs, and minimum mean-square error designs.
`Such filters provide improved efficiency in some fairly general applications. A brief
`discussion of IIR filter design techniques is also given in this chapter and the design
`methods are compared with respect to their efficiency in multirate systems.
`In Chapter 5 we show that by breaking up a multirate system so that the
`processing occurs in a series of stages, increased efficiency results when large
`changes in sampling rate occur within the system. This increased efficiency results
`primarily from the relaxed filter design requirements in all stages. It is shown that
`there are three possible ways of realizing a multistage structure, namely by using a
`small number of stages (typically 2 or 3) and optimizing the eftl.ciency for each
`stage; by using a series of power of 2 stages with a generalized final stage; or by
`using one of several predesigned comb filter stages (systems) and choosing which
`one is most appropriate at each stage of the processing. The advantages and
`disadvantages of each of these methods is discussed in this chapter.
`The last two chapters of the book illustrate how the techniques discussed in
`the previous chapters can be applied to basic signal processing operations (Chapter
`6) and filter bank structures (Chapter 7). In particular, in Chapter 6 we show how
`to efficiently implement multirate, multistage structures for lowpass and bandpass
`filters, for fractional sample phase shifters and Hilbert transformers, and for narrow
`band, high resolution spectrum analyzers. In Chapter 7 we first define the basic
`properties of uniformly spaced filter banks and show how combinations of polyphase
`and DFT structures can be used to provide efficient implementations of these filter
`banks. An alternative structure, the weighted overlap-add method, is introduced
`next and
`it
`is shown
`to yield efficiencies comparable
`to
`the polyphase
`implementations. An extensive discussion of design methods for the filter bank is
`given in this chapter, along with a derivation of how aliasing and imaging can occur
`in both the time and frequency domains. Specific design rules are given which
`enable the designer to minimize (and often eliminate) aliasing and imaging by
`careful selection of filter bank parameters. An important result shown in this
`chapter is how the well-known methods of fast digital convolution (namely overlap(cid:173)
`add and overlap-save) can be derived from the general filter bank analysis-synthesis
`methodology. The remainder of Chapter 7 gives a thorough discussion of several
`generalizations of the DFT filter bank structure which allow arbitrary frequency
`stacking of the filters. Finally the chapter concludes with a brief discussion of some
`nonuniform filter bank structures. In particular we discuss filter banks based on
`tree like structures including the well-known quadrature mirror filter banks.
`The material in this book is intended as a one-semester advanced graduate
`course in digital signal processing or as a reference for practicing engineers and
`researchers. It is anticipated that all students taking such a course would have
`completed one or two semesters of courses in basic digital signal processing. The
`
`Petitioner Apple Inc.
`Ex. 1009, p. xvii
`
`

`

`xviii
`
`Preface
`
`material presented here is, as much as possible, self-contained. Each chapter builds
`up basic concepts so the student can follow the ideas from basic theory to applied
`designs. Although the chapters are closely tied to each other, the material was
`written so that the reader can study, almost independently, any of Chapters 3-7
`once he has successfully learned the material in Chapters 1 and 2. In this manner
`the book can also serve as a worthwhile reference text for graduate engineers.
`Our goal in writing this book was to make the vast area of multirate digital
`signal processing theory and application available in a complete, self-contained text.
`We hope we have succeeded in reaching this goal.
`
`Ronald E. Crochiere
`Lawrence R. Rabiner
`
`Petitioner Apple Inc.
`Ex. 1009, p. xviii
`
`

`

`Acknowledgments
`
`As with any book of this size, a number of individuals have had a significant
`impact on the material presented. We first would like to acknowledge the
`contributions of Dr. James L. Flanagan who has served as our supervisor, our
`colleague, and our friend. His appreciation of the importance of the area of this
`book along with his encouragement and support while working on the writing have
`lessened the difficulty of writing this book.
`Although a great deal of the material presented in this book came out of
`original research done at Bell Laboratories by the authors and their colleagues, a
`number of people have contributed significantly to our understanding of the theory
`and application of multirate digital signal processing. Perhaps the biggest
`contribution has come from Dr. Maurice Bellanger who first proposed the
`polyphase filter structure and showed how it could be used in a wide variety of
`applications related to telecommunications. Major contributions to the field are
`also due to Professor Ronald Schafer, Dr. Wolfgang Mecklenbrauker, Dr. Theo
`Claasen, Professor Hans Schuessler, Dr. Geerd Oetken, Dr. Peter Vary, Dr. David
`Goodman, Dr. Michael Portnoff, Dr. Jont Allen, Dr. Daniel Esteb;m, Dr. Claude
`Galand, Professor David Malah, Professor Vijay Jain, and Professor Thomas Parks.
`To each of these people and many others we owe a debt of thanks for what they
`have taught us about this field.
`We . would like to thank Professor Alan Oppenheim, as series editor for
`Prentice-Hall books on Digital Signal Processing, for inviting us to write this book
`and for his encouragement and counsel throughout the period in which the book
`was written.
`
`xix
`
`Petitioner Apple Inc.
`Ex. 1009, p. xix
`
`

`

`XX
`
`Acknowledgments
`
`Finally, we would like to acknowledge the contributions of Mrs. Donna (Dos
`Santos) Manganelli who has worked with us since the inception of the book and
`typed the many revisions through which this manuscript has undergone. Donna's
`pleasant personality and warmth have made working with her a most rewarding
`experience.
`
`Petitioner Apple Inc.
`Ex. 1009, p. xx
`
`

`

`2
`
`Basic Principles of Sampling
`
`and Sampling Rate
`
`Conversion
`
`2.0 INTRODUCTION
`
`The purpose of this chapter is to provide the basic theoretical framework for
`uniform sampling and for the signal processing operations involved in sampling rate
`conversion. As such we begin with a discussion of the sampling theorem and
`consider its interpretations in both the time and frequency domains. We then
`consider sampling rate conversion systems (for decimation and interpolation) in
`terms of both analog and digital operations on the signals for integer changes in the
`sampling rate. By combining concepts of integer decimation and interpolation, we
`generalize the results to the case of rational fraction changes of sampling rates for
`which a general input-output relationship can be obtained. These operations are
`also interpreted in terms of concepts of periodically time-varying digital systems.
`Next we consider more complicated sampling techniques and modulation
`techniques for dealing with bandpass signals instead of lowpass signals (which are
`assumed in the first part of the chapter). We show that sampling rate conversion
`techniques can be extended to bandpass signals as well as lowpass signals and can
`be used for purposes of modulation as well as sampling rate conversion.
`
`2.1 UNIFORM SAMPLING AND THE SAMPLING THEOREM
`
`2. 1.1 Uniform Sampling VIewed as a Modulation Process
`
`Let xc (t) be a continuous function of the continuous variable t. We are interested
`in sampling Xc (t) at the uniform rate
`
`13
`
`Petitioner Apple Inc.
`Ex. 1009, p. 13
`
`

`

`14
`
`Basic Principles of Sampling and Sampling Rate Conversion
`
`Chap. 2
`
`t = nT, -co < n < oo
`
`(2.1)
`
`that is, once every interval of duration T} We denote the sampled signal as x(n).
`Figure 2.1 shows an example of a signal xc (t) and the associated sampled signal
`x(n) for two different values ofT.
`·
`
`x(nl
`
`x (nl
`
`Figure l.l Continuous signal and two sampled versions of it.
`
`One convenient way of inferpreting this sampling process is as a modulation
`or multiplication process, as shown in Fig. 2.2(a). The continuous signal xc(t) is
`multiplied (modulated) ·by the periodic impulse train (sampling function) s (t) to
`give the pulse amplitude modulated (PAM) signal xc(t)s(t). This PAM signal is
`then discretized in time to give x (n), that is,
`
`x(n) -lim J xc(t)s(t) dt
`
`nT+<
`
`<--o0 t-nT-<
`
`where
`
`s (t) ... l; u0 (t -IT)
`1-oo
`
`(2.2)
`
`(2.3)
`
`In the context of this
`and where u0(t) denotes an ideal unit impulse function.
`interpretation, x (n) denotes the area under the impulse at time nT. Since this
`area is equal to the area under the unit impulse (area ... 1), at time nT, weighted
`
`1 A more general derivation of the sampling theorem would sample at t - nT + ll, where ll is an
`arbitrary constant. The results to be presented are independent of ll for stationary signals x (t). Later
`we consider cases where li is nonzero.
`
`Petitioner Apple Inc.
`Ex. 1009, p. 14
`
`

`

`Sec. 2.1
`
`Uniform Sampling and the Sampling Theorem
`
`15
`
`S( I)
`
`(a)
`
`t =nT
`Xc ( t ) - - - - -0 - - - ' f - - - - - x (n)
`
`1
`
`(C) I I
`
`-2T
`
`-T
`
`T
`
`2T
`
`I I I I l
`
`3T
`
`4T
`
`5T t
`
`(d)
`
`Figure 2.2 Periodic sampling of xc<t) via modulation to obtain x (n).
`
`by xc (nT), it is easy to see that
`
`x (n) - xc(nT)
`
`(2.4)
`
`Figure 2.2 (b), (c), and (d) show xc (t), s (t), and x (n) for a sampling period of T
`seconds.
`
`2.1.2 Spectral Interpretations of Sampling
`
`We assume that xc(t) has a Fourier transformXc(jO) defined as
`Xc(j 0) - f xc(t)e-jOt dt
`
`-00
`
`(2.5)
`
`where 0 denotes the analog frequency On radians/sec). Similarly, the Fourier
`transform of the sampling function s (t) can be defined as
`S(jO) ... f s(t)e-jot dt
`
`(2.6)
`
`00
`
`-00
`
`Petitioner Apple Inc.
`Ex. 1009, p. 15
`
`

`

`16
`
`Basic Principles of Sampling and Sampling Rate Conversion
`
`Chap. 2
`
`and it can be shown that by applying Eq. (2.3) to Eq. (2.6), S (j 0) has the form
`S(jO) = 211" ~ uo(o- 211"1)
`T 1--oo
`T
`
`(2.7)
`
`By defining
`
`and
`
`1 F=(cid:173)
`T
`
`S (j 0) also has the form
`
`00
`
`S(jO)- OF ~ uo(O -/OF)
`1--oo
`
`(2.8)
`
`(2.9a)
`
`(2.9b)
`
`(2.10)
`
`That is, a uniformly spaced impulse train in time, s (t), transforms to a uniformly
`spaced impulse train in frequency, s (j 0).
`Since multiplication in the time domain is equivalent to convolution in the
`frequency domain, we have the relation
`
`00
`
`(2.11)
`
`Xc(jO) * S(jO) == J [xc(t)s(t)]e-i 0 ' dt
`where * denotes a linear convolution of Xc(j O) and S (j O) in frequency. Figure
`2.3 shows typical plots of Xc<i 0), S (j 0), and the convolution Xc(j O) * S (j 0),
`where it is assumed that Xc<i 0) is bandlimited and its highest-frequency
`component 21rFc is less than one-half of the sampling frequency, OF ... 21rF.
`From this figure it is seen that the process of pulse amplitude modulation
`periodically repeats the spectrum Xc(j 0) at harmonics of the sampling frequency
`due to the convolution of Xc(jO) and S(jO).
`Because of the direct correspondence between the sequence x (n) and the
`pulse amplitude modulated signal xc (t) s (t), as seen by Eqs. (2.2) and (2.4) it is
`clear that the information content and the spectral interpretations of the two signals
`are synonymous. This correspondence can be shown more formally by considering
`the (discrete) Fourier transform of the sequence x (n), which is defined as
`
`Petitioner Apple Inc.
`Ex. 1009, p. 16
`
`

`

`Sec. 2.1
`
`Uniform Sampling and the Sampling Theorem
`
`17
`
`(O)
`
`(b)
`
`Xc<jm
`
`I I, \
`
`0
`
`.n
`
`.n
`
`(C)
`
`-~-,\L l~ ., ~j_
`-.n.
`-.n.l
`21
`
`·3.rlF
`2
`
`Xc(j.rll* S(j.[l)
`11/T
`
`0
`
`>~o ~ 1 L
`R~ 1 ~I/.
`1-.n;
`
`n.
`
`3S1F
`2
`
`n
`
`Figure 2.3 Spectra of signals obtained from periodic sampling via modulation.
`
`·217"Fc
`
`217"Fc
`
`00
`
`X(ei"') - ~ x (n)e-jwn
`n--oo
`
`(2.12)
`
`where w denotes the frequency (in radians relative to the sampling rate F), defined
`as
`
`0
`w- or-(cid:173)
`F
`
`(2.13)
`
`Since xc(t) and x(n) are related by Eq. (2.4), a relation can be derived between
`Xc(j 0) and X(ei"') .with the aid of Eqs. (2.5) and (2.12) as follows. The inverse
`Fourier transform of Xc (j 0) gives xc (t) as
`
`Xc(t) ... -:}- j Xc(jO)eiOt dO
`
`1f' -oo
`
`Evaluating Eq. (2.14) fort ... nT, we get
`
`x(n) =xc(nT) == - 1-
`21f' -oo
`
`j Xc(jO)eiOnT dO
`
`(2.14)
`
`(2.15)
`
`The sequence x (n) may also be obtained as the (discrete) inverse Fourier
`transform of X(ei"'),
`
`Petitioner Apple Inc.
`Ex. 1009, p. 17
`
`

`

`18
`
`Basic Principles of Sampling and Sampling Rate Conversion
`
`Chap. 2
`
`...
`x(n) = - 1- J X(ei"')eiwn dw
`
`211" -r
`
`Combining Eqs. (2.15) and (2.16), we get
`
`- 1- J X(ei"')eiwn dw""' - 1- J Xc(jO)eiOnT dO
`
`~
`
`211" -~
`
`...
`
`211" --...
`
`(2.16)
`
`(2.17)
`
`By expressing the right-hand side of Eq. (2.17) as a sum of integrals (each of width
`2?r/T), we get
`
`~
`
`2?r -~
`
`~ (2/+l)r/T
`
`211" 1--~ (2/-l)r/T
`
`_1_ J X