Signals and Communication Technology Uwe Meyer-Baese Digital Signal Processing with Field Programmable Gate Arrays Fourth Edition Signals and Communication Technology For furthervolumes: http://www.springer.com/series/4748 Uwe Meyer-Baese Digital Signal Processing with Field Programmable Gate Arrays Fourth Edition 123 Uwe Meyer-Baese Department of Electricaland Computer Engineering Florida StateUniversity Tallahassee, FL USA ISSN 1860-4862 ISSN 1860-4870 (electronic) ISBN 978-3-642-45308-3 ISBN 978-3-642-45309-0 (eBook) DOI 10.1007/978-3-642-45309-0 Springer Heidelberg NewYork Dordrecht London LibraryofCongressControlNumber:2014939295 (cid:2)Springer-VerlagBerlinHeidelberg2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To Anke, Lisa, and my Parents Preface to First Edition Field-programmable gate arrays (FPGAs) are on the verge of revolutioniz- ing digital signal processing in the manner that programmable digital signal processors (PDSPs) did nearly two decades ago. Many front-end digital sig- nal processing (DSP) algorithms, such as FFTs, FIR or IIR filters, to name just a few, previously built with ASICs or PDSPs, are now most often re- placed by FPGAs. Modern FPGA families provide DSP arithmetic support with fast-carry chains (Xilinx Virtex, Altera FLEX) that are used to imple- ment multiply-accumulates (MACs) at high speed, with low overhead and low costs [1]. Previous FPGA families have most often targeted TTL “glue logic” and did not have the high gate count needed for DSP functions. The efficientimplementationofthesefront-endalgorithmsisthemaingoalofthis 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- portrevenuesgreaterthanUS$1billion.FPGAshaveenjoyedsteadygrowth of more than 20% in the last decade, outperforming ASICs and PDSPs by 10%. 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 advantages over 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 with PDSPs,FPGAdesigntypicallyexploitsparallelism,e.g.,implementingmulti- plemultiply-accumulatecallsefficiency,e.g.,zeroproduct-termsareremoved, and pipelining, i.e., each LE has a register, therefore pipelining requires no additional resources. Another trend in the DSP hardware design world is the migration from graphical design entries to hardware description language (HDL). Although manyDSPalgorithmscanbedescribedwith“signalflowgraphs,”ithasbeen found that “code reuse” is much higher with HDL-based entries than with graphical design entries. There is a high demand for HDL design engineers and we already find undergraduate classes about logic design with HDLs [2]. UnfortunatelytwoHDLlanguagesarepopulartoday.TheUSwestcoastand VIII Preface Asia area prefer Verilog, while US east coast and Europe more frequently use VHDL. For DSP with FPGAs both languages seem to be well suited, althoughsomeVHDLexamplesarealittleeasiertoreadbecauseofthesup- ported signed arithmetic and multiply/divide operations in the IEEE VHDL 1076-1987 and 1076-1993 standards. The gap is expected to disappear after approval of the Verilog IEEE standard 1364-1999, as it also includes signed arithmetic.Otherconstraintsmayincludepersonalpreferences, EDAlibrary and tool availability, data types, readability, capability, and language exten- sions using PLIs, as well as commercial, business, and marketing issues, to name just a few [3]. Tool providers acknowledge today that both languages havetobesupportedandthisbookcoversexamplesinbothdesignlanguages. Wearenowalsointhefortunatesituationthat“baseline”HDLcompilers are 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 with Altera’s newest MaxPlusII software, which provides a complete set of design tools,fromacontent-sensitiveeditor,compiler,andsimulator,toabitstream generator. All examples presented are written in VHDL and Verilog and should be easily adapted to other propriety design-entry systems. Xilinx’s “FoundationSeries,”ModelTech’sModelSimcompiler,andSynopsysFC2or FPGA Compiler should work without any changes in the VHDL or Verilog code. Thebookisstructuredasfollows.Thefirstchapterstartswithasnapshot of today’s 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 frequency synthesizer,includingcompilationsteps,simulation,performanceevaluation, power estimation, and floor planning. This case study is the basis for more than 30 other design examples in subsequent chapters. The second chapter focuses on the computer arithmetic aspects, which include possible number representationsforDSPFPGAalgorithmsaswellasimplementationofbasic buildingblocks,suchasadders,multipliers,orsum-of-productcomputations. Attheendofthechapterwediscusstwoveryusefulcomputerarithmeticcon- 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 possible implementationsoptimizedforsizeorspeed.Chapter5coversmanyconcepts usedinmultiratedigitalsignalprocessingsystems,suchasdecimation,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. InChap.6,implementationofthemostimportantDFTandFFTalgorithms is discussed. These include Rader, chirp-z, and Goertzel DFT algorithms, as well as Cooley–Tuckey, Good–Thomas, and Winograd FFT algorithms. In Chap. 7 we discuss more specialized algorithms, which seem to have great potential for improved FPGA implementation when compared with PDSPs. These algorithms include number theoretic transforms, algorithms for cryp- Preface IX tography and errorcorrection, and communication system implementations. The appendix includes an overview of the VHDL and Verilog languages, the examples in Verilog HDL, and a short introduction to the utility programs included on the CD-ROM. Acknowledgements. ThisbookisbasedonanFPGAcommunicationssystemdesign classItaughtforfouryearsattheDarmstadtUniversityofTechnology;myprevious (German)books[4,5];andmorethan60MastersthesisprojectsIhavesupervised in the last 10 years at Darmstadt University of Technology and the University of Florida at Gainesville. I wish to thank all my colleagues who helped me with critical 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,andJ.Wiet- zke. Iwouldliketothankmystudentsfortheinnumerablehourstheyhavespentim- plementingmyFPGAdesignideas.Specialthanksto: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. Kru¨ger, 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 Paul DeGroot from Springer. For financial support I would like to thank the DAAD, DFG, the European Space Agency, and the Max Kade Foundation. Ifyoufindanyerrataorhaveanysuggestionstoimprovethisbook,please contact me at [email protected] or through my publisher. Tallahassee, May 2001 Uwe Meyer-B¨ase Preface to Second Edition Aneweditionofabookisalwaysagoodopportunitytokeepupwiththelat- 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: www.eng.fsu.edu/∼umb The site has additional information on DSP with FPGAs, useful links, andadditionalsupportforyourdesigns,suchascodegeneratorsandextra documentation. • Correctedthemistakesfromthefirstedition.Theerrataforthefirstedition can be downloaded from the book web page. • 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 • Altera’s current student version has been updated from 9.23 to 10.2 and all design examples, size and performance measurements, i.e., many ta- bles and plots have been compiled for the EPF10K70RC240-4 device that is on Altera’s university board UP2. Altera’s UP1 board with the EPF10K20RC240-4 has been discontinued. • Asolutionmanualforthefirstedition(withmorethan65exercisesandover 33 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,andA.Acevedo(nowwithXilinx)forsoftwareandhardwaresupport and the permission to include datasheets and MaxPlus II on the CD of this book. Frommypublisher(Springer-Verlag)IwouldliketothankP.Jantzen,F.Holz- warth, and Dr. Merkle for their continuous support and help over recent years. XII Preface Ifeelexcitedthatthefirsteditionwasabigsuccessandsoldoutquickly.I hopeyouwillfindthisneweditionevenmoreuseful.Iwouldalsobegrateful, ifyouhaveanysuggestionsforhowtoimprovethebook,ifyouwoulde-mail me at [email protected] or contact me through my publisher. Tallahassee, October 2003 Uwe Meyer-B¨ase