Multirate Systems and Filter Banks

Multirate Systems and Filter BanksMultirate Systemsand Filter BanksP.P. vaidyanathanDepartment of Electrical EngiCalifornia Institute of Technology, PasadenaPRENTICE HALL P T R. Englewood Cliffs, New Jerubrary of Congress Cataloging-in-Publicaton DMulbrate systems and fiter banks /PP. vaidyanathar. ChRIncudes bibliographical references(p. )and index1sBN013-80571日71. Signal processiong--Digital techniques I. TitleTK51025V24189392-65478213922-c20Editorial production supen isun: Endan M. StewartPrepress buyer: Afan Mfc cartneymmy parentsManufacturing buver: Susan BrunkeAcquIsitions editor: Karen Germanmy wife ushaC 1993 by Prentice HalIPTRPrentice-Hall. IncEnglewood Cliff, New Jersey 07632The publisher offers discounts on this hook when ordered in bulk quantities. For more information. write:Special Sales/Profcssionet Marketing PrenIice-Hall Professional Technical Reference DivisionEnglewood Cliffs. N吖763All nght reserved. No part of this book may beproduced. in any form or by any means,itout permision in writing from the publisherPrinted in the United States of AmericaIsBN-13-505718-7Prentice Hall Intrnational (l k) limted I ndowPrentice- Hall of Austr lia Pty Limited, sydneyPrentice Hall of Canada Inc, FutontoPrentice-Hull HIsPanoamcricands A. MextPrunuce-llall of India Pri\ Jle I imiled, Nrw DelhiPrenuce-llall of Japan, Inc, lol yUPearson Ducation Asia Fic. I td Singur arefeitosa Prt1 i l do Brst i tdd. kt, dc Jun irUContentsPrefacePART 1 INTRODUCTORY CHAPTERS1 ntroductionl.1Major Developments 32 Review of Discrete-Time System2202.1Discrete- Time Signals 1222Multi-Input Multi-Output Systems 2423282.4Discrete-Time Filters(Digital Filters) 31Proble3 Review of Digital Filters 423.0Introduction 42Filter Design Specifi3.2FIR Filter Desig45IIR Filter Design 603.4Allpass filLers 71.5 Special Types of Filters 83IR Filters Based on Two Allpass Filters 813.7Concluding re91Problems 9g4 Fundamentals of Multirate Systems 1004.0Introduction 100Basic Multirate Operations 10042Interconnection of Building Blocks 1184.3 The Polyphase Representation 120Multistage Imple4.5Soine Applications of Multirate Systems 1434.6Special Filters and Filter Banks 1511.7hods 168ProPART 2 MULTIRATE FILTER BANKS9394Noise Transmission in Multirate Systems 4055 Maximally Decimated Filter Banks 188Noise in Filter Banks 40895Filter Bank Output Noise 41250Introduction 1889.6Limit Cycles 4165.1Errors Created in the Q 1F Ban19197Coefficient Quantization 41852A Simple Alis- Free QMF System 196Problems 4245.3 Power Symmetric QMF Banks5.4M-channcl Fllter Banks 22310 Multirate Filter Bank Theory and Related Topics42755Polyphase Representation 23010.0Introduction 4275.6Perfect Reconstruction(PR) Systems 23410.15.7Alias-Frce Filter Banks 245Block Filters, LPTV Systems and Multirate Filter Banks 427Unconventional Sampling Theorems 4365.8Tree structured Filter Bank254Pro blems 4545.9Transmultiplexer 2595.10Summary and Tables 26611 The Wavelet Transform and its Relation to MultIrate Flier Banks 457Problems 27211.0Introduction 45711.16 Paraunitary Perect Reconstruction (PR)Filter BanksBackground and Outline 458112The Short-Time Fourier Transform 460Introduction 286113The Wavelet Transform 4816.1Lossless Transfcr Matrices 288114Discrete-Time Orthonormal Wavelets 50062Filter Bank Properties Induced by Paraunitarincss 29411.5 Continuous- Time Orthonormal Wavelet Basis 51063Two Channel FIR Paraunitary QMF Banks 298Concluding Remarks 564The Two Channel Paraunitary QMF Lattice 302Pmblems 53965A-channel FIR Paraunitary Filter Banks 31166Thansform Coding and the"LOT12 Multidimensional Multirate Systems5456.7Summary, Comparisons, and Tables 326Problcms 33312.0Introduction 54512.1Multidimensional Signals 5467 Linear Phase Perfect Reconstruction QMF Banks 337122Sampling a Multidimensional Signal 55512.3Minimum Sampling Density 56870Introduction 33712.4te fundamentals 572Some Necessary Conditions 33712.5Alias-Free Decimation 597Lattice Structures for Linear Phase FIR PR QMF Banks 339Cascade Connections 603Formal Synthesis of Linear Phase FIR PR Q\F I, attice 34712.612.7Multirate Filter Desi608Proble35】128Special Filters and Filter Banks 6238 Cosine Modulated Filter Banks129Maximally Decimated Filter Banks 62712.10Concluding Remarks 64180Introduction 353Pmblems 6508.1 The Pseudo QMF Bank 3548.2Design of the Pseudo QniF Bank 36383Efficient Poly phase Structures 370PART 4 MULTIVARIABLE AND LOSSLESS SYSTEMS84Deeper Properties of Cosine Matrices 37385osine Modulated Perfect Reconstruction Sy stems 37713 Review of Discrete-Time Mu/tH-nput Multl-Output LTI Systems660Problems 39213.0Introduction 660l3.1Input Multi-Output SysterPART 3 SPECIAL TOPICS13.2Matrix Polynomials 66113.3Matrix fractiOptions6659 Quantization Effects13State Space Descriptions 66913.5The Smith-MlcMfillan Form 6879.0 lntroduction 394136Poles of transfer matrices 9991Ty pes of quantization Elects 3949.2 Review of Standard Techniques 39713.7Zeros uf Transfer Matrices 703L38Degree of a TRansfer Matrix 707i139FIR Transfer Matrices 708C 5 Relation to Other Methods 83913.I0CauSal Inverses of Causal System 711ProblemsProblems 715D Spectral Factorization Technlque.8494 Paraunitary and Lossless SyslemsDOIntroduction 849140Introduction 722The Complex Cepstrum 84914.1A Brief History 723D2A Cepstral Inversion Algorithm 853142Fundamentals of Lossless SystemB 724D3A Spectral Factorization Algorithm 854143LosslesS Systems with Two Outputs 727Problems 85814.4Structures for M x M and M x 1 FIR Lossless Systems 731145State Space Manifestation of Lossless Property 740E Masons GaIn Formula 859146Factorization of Unitary Matrice] 745147Smith-McMillan Form and Pole-Zero Pattern 754Glossary of Symbols14.8 The Modulus Property 758Structures for IIR Lossless Systems 759List of Importent Summaries(ables) 86714.10Modified Lossleas Structures 763Preserving Lossless Property Under Quantization 768List of Importent Summaries(Flgures)6814.1114.12Summary and Tables 771Problems 775BIbliography659Alphabetical List of References Cited in the Book 869APPENDICESSome References by Topic 888A Review of Matrices 782A.0Introduction 782Index891A.1Definitione and Examples 782A.2Basic Operations 783A.3Determinants 786Linear Independence, Rank, and Related Issues 787A.5Eigenvalues and Eigenvectors 790A.6Special Types of matrices 793A7Unitary Triangularization 798A.8Maximization and Minimization 798A 9Properties Preserved in matrix products 799Problems 800B Revlew of Random Processes 803B.0Introduction 803B.1Real Random Variables 803B2Real Random Processes 806B 3 Passage Through LTI Syetems 810B 4The Complex Case8】1B. 5 The812c Quantization of Subband Slgnals816C0 Introduction 816Quantizer Noise Variance 816C.2The Ideal Subband Coder 818C. 3 The Orthogonal Transform Coder 826C 4Similarities and Differences 833PrefaceMultirate digital signal processing techniques have been practiced by engineers formore than a decade and a half. This discipline finds applications in speech andinage compression, the digital audio industry, statistical and adaptive signal pro-cessing, numerical solution of differential equations, and in many other fields. Italso fits naturally with certain special classes of time-frequcncy representations suchas the short-time Fourier transform and the wavelet transform, which are useful itanalyzing the time-varying nature of signal spectraOver the last decade there has been a tremendous growth of activity in thearca of multirate signal processing perhaps triggered by the first book in this fieldICrochiere and Rabiner, 1983]. Particularly impressive is the amount of new literature in digital fiter banks, multidimensional multirate systems, and wavelet repre-sentations. The theoretical work in multirate filter banks appears to have reached alevel of maturity which justifies a thorough, unified, and in-depth treatment of theseTopics. This book is intended lo serve that purpose, and it presents the above metCioned topics under one cover. Research in the areas of multidimensional systemsand wavelet transforms is still proceeding at a rapid rate. We have dedicatedchapter to each of these, in order to bring the reader up to a point where resecan be begI have always believed that it is important to appreciate the generality ofprinciples and to obtain a solid theoretical foundation, and my presentation herereflects this philosophy. Several applications are discussed throughout the book,but the general principles are presented without bias towards specific application-oricnted delail.haro The writing style here is very much in the form of a lert. whenever possible Ihave included examples lo demonstrate new principles. Many design exanmples andcomplete design rules for filter banks have been included. Fach chapter includes afairly extensive set of homework problens(totaling over 300). The solutions to theSearc available to instructors, from the publisher Tables and summaries are insertedal many places to enable the reader to locate important results conveniently. Ihave also tried to simplify the reader 's task by assigning separate chapters for moreadvanced material. For example, Chap. 1l is dedicated to waVelet transforms, andChap. I4 cont ains detailed developments of many results on paraunitary systemswhenever a result from an advanced chapter(for example. Chap. 1-4)is usd in ancarlicr chapter, this result is first stated clearly wit hin Che context of use, and thereader is referred to the appropriate chapter for proof.The text is sclf-cout ained for readers who have goe prior exposure to digi-tal signal processing. A one-term course which deals with saInpling,discrcte-timeFourier transforms, z-transforms, and digital filtering, is sulficient. In Chap. 2 anldXIlI3 a brief review of this material is provided. A thorough exposition can be foundcarefully supervising the production of the final book. karen Gettmdn, Prenticein a number of references, for example, [Oppenheim and Schafer, 1989 Chapter 3Hall, was very helpful during all st ages of the writing processalso contains some new material, for example, eigenfilters, and detailed discussionsSeveral professional colleagues and st udents have played a major role in the evcon allpass filters, which are very useful in multirate system design.lution and completion of (his project. Professor Maurice Bellanger (TRT, franceA detailed description of the text can be found in Chap. 1. Chapters 2 andand Drs. Ron Crochicre, N.S. Jayant, and Larry Rabiner of the aT& r Bell Lal3 provide a brief review of signals, systems, and digital fltering. Chapter 4, whichoratories, provided the valuable encouragement which I needed during the initialblockB and filter bankB, and describes many applications. Chapter 5 introdncesI am deeply thankful to Dr. Rabiner for his criticism of the first draft, and formultirate filter bankB, laying the theoretical foundation for alias cancelation, andproviding many valuable suggestions on the style of presentation. His feedback haselimination of other error8. The first two sections in Chap. 4 and 5 contain materialresulted in significant improvement of the presentation here. My heartfelt gratitudeoverlapping with crochiere and Rabiner, 1983. Most of the remaining material inalso goes to Prof. Martin Vetterli( Columbia University, New York)for his greatchese chapters, and in the majority of the chapters that follow have not appearedenthusism, interaction, friendship, and valuable feedback over the years, and toin this form in text booksProfessors Mark Smith and Tom Barnwell (Georgia Institude of Technology),forChapters 6 to 8 provide a deeper study of multirate filter banks, and present.their constant support. Prof. Smith had studied the first draft of the manuscriptseveral design techniques, including those based on the so-called paraunitary matrivery carefully, and provided valuable suggestions. I am indebted to Dr. Ajay i uthraces.(These matrices play a role in the design of many multirate systems, and areand his colleagues(Tektronix laboratories), for their enthusiasm and interest in thetreated in full depth in Chap. 14 )Chapters 9 to 12 cover apecial topics in multirateproject. Sone of the research work related to this book has been done with thesignal processing. These include roundoff noise effects(Chap. 9), block filteringsupport from Tektronixperiodically time varying systems and sampling theorems(Chap. 10), wavelet trans.Dr. Rashid Ansari (Bellcore), Prof. Roberto Bamberger(Washington Stateforms(Chap. 11)and multidimensional multirate systems( Chap. 12). ChaptersUniversity) and Dr. Jelena Kovacevic (at& T Bell laboratories provided val13 and 14 give an in-depth coverage of multivariable linear systems and lossless(orable comments on the chapter on multidimensional multirate systems. Dr. Ingridparaunitary systems, whiich are required for a deeper understanding of multirateflter banks and wavelet transformaproved parts of Chap. 11(wavelets)substantially. Ramesh Gopinath(Rice Univer-There are five appendices which serve as references as well as supplementarysity)also provided important comments on this chapter. I also wish to thank Prof.reading. Three of these are review-material(matrix theory, random processes, andTom Parks(Cornell University) for his valuable feedback on Chap. I to 6 and 11Masons gain formula). Two of the appendices contain results directly related toProf. P.K. Rajan(Tennesse 'Technological University)for his comments on Chapflter bank systems, One of these is a technique for spectral factorization; the other12, and Prof. A Sideris( Caltech) for comments on Chap. 13.Many of these chapters have been taught at Caltech over the last three years.Prof. George Moschytz(Swiss Federal Institute of Technology),and Prof. TorThis text can be used for teaching a one, two, or three term(quarter or semesterRamstad(Norwegian Institute of Technology). I also sincerely acknowledge thecourse on one of many possible topics, for example, multirate fundamentals, nulconstant moral support and encouragement I received from Prof. Sanjit alitratirate filter bankB, wavelet representation, and so on. There are many homework(University of California, Santa Barbara) during various st agesproblcms. The instructor has a great deal of flexibility in choosing the topics, butSeveral graduate students at Caltech have participated in the research thatI prefer not to bias him or her by providing specific course outlines hereeventually gave rise to this book. In this regard, my interactions with Isuhan ChenIn summary, I have endeavored to produce a text which is useful for the classroom, as well as for self-study. It is also hoped that it will bring the reader to a pointNguyen, Vinay Sathe, and anand Soman have been most enjoy able. Davids re-where he/she can start pursuing research in a vasst range of multirate areas. Finalli believe that the text can be comfortably used by the practicing engineer becauseIn addition to providing intellect ual interactions at the deepest level, Tsuhan Chenof the inclusion of several design procedures, examples, tables, and summariesDavid Koilpillai, Truong Nguyen, and Anand Soman have also generated many ofthe multirate design examples in this text. They have also read various chapters ofACKNOWLEDGMENTSthe manuscript and provided useful feedback. In this connection my special thanksgo to Tsuhan Chen, Zinnur Doganata, lan Galton, David Koilpillai, Ramesh RaThe generous support and pleasant environment offered by the Californi Iustitutejaram, Ken Rosc and Anand Soman for reading many of the chapters. Tsuhanof Technology has been tmost crucial in the successful completion of this project. Thewas a very carcful reader, and provided many valuable suggestions for Chapfunding provided by the National Science Foundation for our research in multiratelan Galton provided several comments on writing style as well as technical contentsu processing has been very helpful in developing many of the results which arehich I found to be extremely useful. lan's enthusiasm and friendship are gratefullyincluded in this text. I also take this opportunity to thank Prof. Alan Oppenheimacknowledgedfor his enthusiasm about this project, and for including this text in his distinguisDebbie McGougan and Cynt hia Stewart at Caltech were very helpful duringBignal processing serics. I an indebted to Brendan Stewart, Prentice Hallvarious phang of the manuscript preparation. Solutions to all the holme work prob.Preface xvlems have been prepared by Tsuhan Chen, igor Djokovic, See-afay Phoong, andAnand Soman. I appreciate their interest and patiencePART 1 Introductory ChaptersMy parents have been responsible for teaching me many valuable theoremsof life which i could not find in text books and papers. These certainly were therinciples which sustained me during all phases of this projectMy deepest gratitude goes to my wife Usha who showed infinite patience andunderstanding during my absorption in thisption in this long project, and offered thmoral support and loving encouragement which only she can offer. Coountless werethe evenings, weekends, and holidays during which she provided me with the scclsion and peace of mind needed to pursue this ambitious goal. She is certainlymy best blessing, and this book would hive remained an idle dream without herP. VaidyanathIntroductionCalifornia Institute of TechnologyA traditional single rate digital signal processing system can be schematically represented as shown in Fig. 1.1-1, whichis an interconnection ofcomputational building blocks such as multipliers, adders, and 'delay ele-ments'(which store internal signals). Examples are digital filters, Fouriertransformers. modulators and so on. In a multirate signal processing sys-tem, there are two new building blocks, called the Mf-fold decimator andthe L-fold expander(Fig. 1. 1-2). These will be defined and illustrated inChapter 4. For the purposeent discussionthe decimatodevice that reduces the sampling rate by an integer factor of M, whereas theexpander is used to increase the rate by L. Such sampling rate alterationcan be introduced at thed/or output of the system or interthe system, depending on the application.MultiplierAdderInoutDelayMultiplicationelementof 2 signalsle rate)digital bignaGuire1.1-1 Sch