Digital Signal Processing with Field Programmable Gate Arrays（Third Edition）.pdf

Springer Series onSignals and Communication TechnologySignals and Communication TechnologyWireless Network SecurityY.Xiao,D.-Z.Du,X.ShenISBN 978-0-387-28040-0Terrestrial Trunked Radio TETRAA Global Security ToolP.StavroulakisISBN 978-3-540-71190-2Multirate Statistical Signal ProcessingO.S.JahromiISBN 978-1-4020-5316-0Wireless Ad Hoc and Sensor NetworksA Cross-Layer Design PerspectiveR.JurdakISBN 978-0-387-39022-2Positive Trigonometric Polynomialsand Signal Processing ApplicationsB.DumitrescuISBN 978-1-4020-5124-1FaceBiometrics for Personal IdentificationMulti-Sensory Multi-Modal SystemsR.I.Hammoud,B.R.Abidi,M.A.Abidi(Eds.)ISBN 978-3-540-49344-0Cryptographic Algorithmson ReconfigurableHardwareF.Rodrguez-HenrquezISBN 978-0-387-33883-5Ad-Hoc NetworkingTowards Seamless CommunicationsL.GavrilovskaISBN 978-1-4020-5065-7Multimedia DatabaseRetrievalA Human-Centered ApproachP.Muneesawang,L.GuanISBN 978-0-387-25627-6Broadband Fixed Wireless AccessA System PerspectiveM.Engels;F.PetreISBN 978-0-387-33956-6Acoustic MIMO Signal ProcessingY.Huang,J.Benesty,J.ChenISBN 978-3-540-37630-9Algorithmic Information TheoryMathematics of Digital InformationProcessingP.SeibtISBN 978-3-540-33218-3Continuous-Time SignalsY.S.ShmaliyISBN 978-1-4020-4817-3Interactive VideoAlgorithms and TechnologiesR.I.Hammoud(Ed.)ISBN978-3-540-33214-5Distributed Cooperative LaboratoriesNetworking,Instrumentation,and MeasurementsF.Davoli,S.Palazzo,S.Zappatore(Eds.)ISBN 978-0-387-29811-5Topics in Acoustic Echo and Noise ControlSelected Methods for the Cancellationof Acoustical Echoes,the Reductionof Background Noise,and Speech ProcessingE.Hnsler,G.Schmidt(Eds.)ISBN 978-3-540-33212-1EM Modeling of Antennasand RF Components for WirelessCommunication SystemsF.Gustrau,D.ManteuffelISBN 978-3-540-28614-1Orthogonal Frequency Division Multiplexingfor Wireless CommunicationsY.Li,G.L.Stuber(Eds.)ISBN 978-0-387-29095-9Advanced Man-Machine InteractionFundamentals and ImplementationK.-F.KraissISBN 978-3-540-30618-4The Variational Bayes Methodin Signal ProcessingV.Smdl,A.QuinnISBN 978-3-540-28819-0Voice and Speech Quality PerceptionAssessment and EvaluationU.JekoschISBN 978-3-540-24095-2Circuits and Systems Basedon Delta ModulationLinear,Nonlinear andMixedModeProcessingD.G.ZrilicISBN 978-3-540-23751-8SpeechEnhancementJ.Benesty,S.Makino,J.Chen(Eds.)ISBN 978-3-540-24039-6Uwe Meyer-BaeseDigitalSignalProcessingwithFieldProgrammableGateArraysThird EditionWith 359 Figures and 98 TablesBook with CD-ROM123Dr.Uwe Meyer-BaeseFlorida State UniversityCollege of EngineeringDepartment Electrical&Computer EngineeringPottsdamer St.2525Tallahassee,Florida 32310USAE-Mail:Uwe.Meyer-Baeseieee.orgOriginally published as a monographLibrary of Congress Control Number:2007933846ISBN 978-3-540-72612-8 Springer Berlin Heidelberg New YorkThis work is subject to copyright.All rights are reserved,whether the whole or part of the materialis concerned,specifically the rights of translation,reprinting,reuse of illustrations,recitation,broadcasting,reproduction on microfilm or in any other way,and storage in data banks.Duplicationof this publication or parts thereof is permitted only under the provisions of the German CopyrightLaw of September 9,1965,in its current version,and permission for use must always be obtained fromSpringer.Violations are liable for prosecution under the German Copyright Law.Springer is a part of Springer Science+Business M Springer-Verlag Berlin Heidelberg 2007The use of general descriptive names,registered names,trademarks,etc.in this publication does notimply,even in the absence of a specific statement,that such names are exempt from the relevantprotective laws and regulations and therefore free for general use.Typesetting:Data conversion by the authorProduction:LE-TEX Jelonek,Schmidt&Vckler GbR,LeipzigCover Design:WMXDesign GmbH,HeidelbergPrinted on acid-free paper60/3180/YL5 4 3 2 1 0To my Parents,Anke and LisaPrefaceField-programmable gate arrays(FPGAs)are on the verge of revolutionizingdigital signal processing in the manner that programmable digital signal pro-cessors(PDSPs)did nearly two decades ago.Many front-end digital signalprocessing(DSP)algorithms,such as FFTs,FIR or IIR filters,to name justa few,previously built with ASICs or PDSPs,are now most often replacedby FPGAs.Modern FPGA families provide DSP arithmetic support withfast-carry chains(Xilinx Virtex,Altera FLEX)that are used to implementmultiply-accumulates(MACs)at high speed,with low overhead and low costs1.Previous FPGA families have most often targeted TTL“glue logic”anddid not have the high gate count needed for DSP functions.The efficientimplementation of these front-end algorithms is the main goal of this book.At the beginning of the twenty-first century we find that the two pro-grammable logic device(PLD)market leaders(Altera and Xilinx)both re-port revenues greater than US$1 billion.FPGAs have enjoyed steady growthof more than 20%in the last decade,outperforming ASICs and PDSPs by10%.This comes from the fact that FPGAs have many features in com-mon with ASICs,such as reduction in size,weight,and power dissipation,higher throughput,better security against unauthorized copies,reduced de-vice and inventory cost,and reduced board test costs,and claim advantagesover ASICs,such as a reduction in development time(rapid prototyping),in-circuit reprogrammability,lower NRE costs,resulting in more econom-ical designs for solutions requiring less than 1000 units.Compared withPDSPs,FPGA design typically exploits parallelism,e.g.,implementing multi-ple multiply-accumulate calls efficiency,e.g.,zero product-terms are removed,and pipelining,i.e.,each LE has a register,therefore pipelining requires noadditional resources.Another trend in the DSP hardware design world is the migration fromgraphical design entries to hardware description language(HDL).Althoughmany DSP algorithms can be described with“signal flow graphs,”it has beenfound that“code reuse”is much higher with HDL-based entries than withgraphical design entries.There is a high demand for HDL design engineersand we already find undergraduate classes about logic design with HDLs 2.Unfortunately two HDL languages are popular today.The US west coast andAsia area prefer Verilog,while US east coast and Europe more frequentlyVIIIPrefaceuse VHDL.For DSP with FPGAs both languages seem to be well suited,although some VHDL examples are a little easier to read because of the sup-ported signed arithmetic and multiply/divide operations in the IEEE VHDL1076-1987 and 1076-1993 standards.The gap is expected to disappear afterapproval of the Verilog IEEE standard 1364-1999,as it also includes signedarithmetic.Other constraints may include personal preferences,EDA libraryand tool availability,data types,readability,capability,and language exten-sions using PLIs,as well as commercial,business,and marketing issues,toname just a few 3.Tool providers acknowledge today that both languageshave to be supported and this book covers examples in both design languages.We are now also in the fortunate situation that“baseline”HDL compilersare available from different sources at essentially no cost for educational use.We take advantage of this fact in this book.It includes a CD-ROM withAlteras newest MaxPlusII software,which provides a complete set of designtools,from a content-sensitive editor,compiler,and simulator,to a bitstreamgenerator.All examples presented are written in VHDL and Verilog andshould be easily adapted to other propriety design-entry systems.Xilinxs“Foundation Series,”ModelTechs ModelSim compiler,and Synopsys FC2 orFPGA Compiler should work without any changes in the VHDL or Verilogcode.The book is structured as follows.The first chapter starts with a snapshotof todays FPGA technology,and the devices and tools used to design state-of-the-art DSP systems.It also includes a detailed case study of a frequencysynthesizer,including compilation steps,simulation,performance evaluation,power estimation,and floor planning.This case study is the basis for morethan 30 other design examples in subsequent chapters.The second chapterfocuses on the computer arithmetic aspects,which include possible numberrepresentations for DSP FPGA algorithms as well as implementation of basicbuilding blocks,such as adders,multipliers,or sum-of-product computations.At the end of the chapter we discuss two very useful computer arithmetic con-cepts for FPGAs:distributed arithmetic(DA)and the CORDIC algorithm.Chapters 3 and 4 deal with theory and implementation of FIR and IIR fil-ters.We will review how to determine filter coefficients and discuss possibleimplementations optimized for size or speed.Chapter 5 covers many conceptsused in multirate digital signal processing systems,such as decimation,inter-polation,and filter banks.At the end of Chap.5 we discuss the various pos-sibilities for implementing wavelet processors with two-channel filter banks.In Chap.6,implementation of the most important DFT and FFT algorithmsis discussed.These include Rader,chirp-z,and Goertzel DFT algorithms,aswell as CooleyTuckey,GoodThomas,and Winograd FFT algorithms.InChap.7 we discuss more specialized algorithms,which seem to have greatpotential for improved FPGA implementation when compared with PDSPs.These algorithms include number theoretic transforms,algorithms for cryp-tography and errorcorrection,and communication system implementations.PrefaceIXThe appendix includes an overview of the VHDL and Verilog languages,theexamples in Verilog HDL,and a short introduction to the utility programsincluded on the CD-ROM.Acknowledgements.This book is based on an FPGA communications system designclass I taught for four years at the Darmstadt University of Technology;my previous(German)books 4,5;and more than 60 Masters thesis projects I have supervisedin the last 10 years at Darmstadt University of Technology and the Universityof Florida at Gainesville.I wish to thank all my colleagues who helped me withcritical discussions in the lab and at conferences.Special thanks to:M.Acheroy,D.Achilles,F.Bock,C.Burrus,D.Chester,D.Childers,J.Conway,R.Crochiere,K.Damm,B.Delguette,A.Dempster,C.Dick,P.Duhamel,A.Drolshagen,W.En-dres,H.Eveking,S.Foo,R.Games,A.Garcia,O.Ghitza,B.Harvey,W.Hilberg,W.Jenkins,A.Laine,R.Laur,J.Mangen,J.Massey,J.McClellan,F.Ohl,S.Orr,R.Perry,J.Ramirez,H.Scheich,H.Scheid,M.Schroeder,D.Schulz,F.Simons,M.Soderstrand,S.Stearns,P.Vaidyanathan,M.Vetterli,H.Walter,and J.Wiet-zke.I would like to thank my students for the innumerable hours they have spent im-plementing my FPGA design ideas.Special thanks to:D.Abdolrahimi,E.Allmann,B.Annamaier,R.Bach,C.Brandt,M.Brauner,R.Bug,J.Burros,M.Burschel,H.Diehl,V.Dierkes,A.Dietrich,S.Dworak,W.Fieber,J.Guyot,T.Hatter-mann,T.H auser,H.Hausmann,D.Herold,T.Heute,J.Hill,A.Hundt,R.Huth-mann,T.Irmler,M.Katzenberger,S.Kenne,S.Kerkmann,V.Kleipa,M.Koch,T.Kr uger,H.Leitel,J.Maier,A.Noll,T.Podzimek,W.Praefcke,R.Resch,M.R osch,C.Scheerer,R.Schimpf,B.Schlanske,J.Schleichert,H.Schmitt,P.Schreiner,T.Schubert,D.Schulz,A.Schuppert,O.Six,O.Spiess,O.Tamm,W.Trautmann,S.Ullrich,R.Watzel,H.Wech,S.Wolf,T.Wolf,and F.Zahn.For the English revision I wish to thank my wife Dr.Anke Meyer-B ase,Dr.J.Harris,Dr.Fred Taylor from the University of Florida at Gainesville,and PaulDeGroot from Springer.For financial support I would like to thank the DAAD,DFG,the EuropeanSpace Agency,and the Max Kade Foundation.If you find any errata or have any suggestions to improve this book,pleasecontact me at Uwe.Meyer-Baeseieee.org or through my publisher.Tallahassee,May 2001Uwe Meyer-B asePreface to Second EditionA new edition of a book is always a good opportunity to keep up with the lat-est developments in the field and to correct some errors in previous editions.To do so,I have done the following for this second edition:Set up a web page for the book at the following URL:http:/hometown.aol.de/uwemeyerbaeseThe site has additional information on DSP with FPGAs,useful links,and additional support for your designs,such as code generators and extradocumentation.Corrected the mistakes from the first edition.The errata for the first editioncan be downloaded from the book web page or from the Springer web pageat www.springer.de,by searching for Meyer-Baese.A total of approximately 100 pages have been added to the new edition.The major new topics are:The design of serial and array dividers The description of a complete floating-point library A new Chap.8 on adaptive filter design Alteras current student version has been updated from 9.23 to 10.2 andall design examples,size and performance measurements,i.e.,many ta-bles and plots have been compiled for the EPF10K70RC240-4 devicethat is on Alteras university board UP2.Alteras UP1 board with theEPF10K20RC240-4 has been discontinued.A solution manual for the first edition(with more than 65 exercises and over33 additional design examples)is available from Amazon.Some additional(over 25)new homework exercises are included in the second edition.Acknowledgements.I would like to thank my colleagues and students for the feed-back to the first edition.It helped me to improve the book.Special thanks to:P.Ashenden,P.Athanas,D.Belc,H.Butterweck,S.Conners,G.Coutu,P.Costa,J.Hamblen,M.Horne,D.Hyde,W.Li,S.Lowe,H.Natarajan,S.Rao,M.Rupp,T.Sexton,D.Sunkara,P.Tomaszewicz,F.Verahrami,and Y.Yunhua.From Altera,I would like to thank B.Esposito,J.Hanson,R.Maroccia,T.Mossadak,and A.Acevedo(now with Xilinx)for software and hardware supportand the permission to include datasheets and MaxPlus II on the CD of this book.From my publisher(Springer-Verlag)I would like to thank P.Jantzen,F.Holz-warth,and Dr.Merkle for their continuous support and help over recent years.XIIPrefaceI feel excited that the first edition was a big success and sold out quickly.Ihope you will find this new edition even more useful.I would also be grateful,if you have any suggestions for how to improve the book,if you would e-mailme at Uwe.Meyer-Baeseieee.org or contact me through my publisher.Tallahassee,October 2003Uwe Meyer-B asePreface to Third EditionSince FPGAs are still a rapidly evolving field,I am very pleased that mypublisher Springer Verlag gave me the opportunity to include new develop-ments in the FPGA field in this third edition.A total of over 150 pages ofnew ideas and current design methods have been added.You should find thefollowing innovations in this third edition:1)Many FPGAs now include embedded 18 18-bit multipliers and it istherefore recommended to use these devices for DSP-centered applica-tions since an embedded multiplier will save many LEs.The CycloneII EP2C35F672C6 device for instance,used in all the examples in thisedition,has 35 18 18-bit multipliers.2)MaxPlus II software is no longer updated and new devices such as theStratix or Cyclone are only supported in Quartus II.All old and newexamples in the book are now compiled with Quartus 6.0 for the CycloneII EP2C35F672C6 device.Starting with Quartus II 6.0 integers are bydefau