SYNTHESIS OF ARITHMETIC CIRCUITS FPGA, ASIC, and Embedded Systems JEAN-PIERRE DESCHAMPS University Rovira iVirgili GE´RY JEAN ANTOINE BIOUL National Universityof the Centerof the Province ofBuenos Aires GUSTAVO D. SUTTER University Autonomaof Madrid A JOHN WILEY& SONS, INC., PUBLICATION SYNTHESIS OF ARITHMETIC CIRCUITS SYNTHESIS OF ARITHMETIC CIRCUITS FPGA, ASIC, and Embedded Systems JEAN-PIERRE DESCHAMPS University Rovira iVirgili GE´RY JEAN ANTOINE BIOUL National Universityof the Centerof the Province ofBuenos Aires GUSTAVO D. SUTTER University Autonomaof Madrid A JOHN WILEY& SONS, INC., PUBLICATION Copyright#2006byJohnWiley&Sons,Inc.Allrightsreserved. PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey.PublishedsimultaneouslyinCanada. Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinany formorbyanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise, exceptaspermittedunderSection107or108ofthe1976UnitedStatesCopyrightAct,without eitherthepriorwrittenpermissionofthePublisher,orauthorizationthroughpaymentofthe appropriateper-copyfeetotheCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers, MA01923,978-750-8400,fax978-646-8600,oronthewebatwww.copyright.com.Requeststo thePublisherforpermissionshouldbeaddressedtothePermissionsDepartment,JohnWiley&Sons,Inc., 111RiverStreet,Hoboken,NJ07030,(201)748-6011,fax(201)748-6008 oronlineathttp://www.wiley.com/go/permission. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbest effortsinpreparingthisbook,theymakenorepresentationsorwarrantieswithrespecttothe accuracyorcompletenessofthecontentsofthisbookandspecificallydisclaimanyimplied warrantiesofmerchantabilityorfitnessforaparticularpurpose.Nowarrantymaybecreatedor extendedbysalesrepresentativesorwrittensalesmaterials.Theadviceandstrategiescontained hereinmaynotbesuitableforyoursituation.Youshouldconsultwithaprofessionalwhere appropriate.Neitherthepublishernorauthorshallbeliableforanylossofprofitoranyother commercialdamages,includingbutnotlimitedtospecial,incidental,consequential,orotherdamages. ForgeneralinformationonourotherproductsandservicespleasecontactourCustomerCareDepartment withintheU.S.at877-762-2974,outsidetheU.S.at317-572-3993orfax317-572-4002. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprint, however,maynotbeavailableinelectronicformat. LibraryofCongressCataloging-in-PublicationData: Deschamps,Jean-Pierre,1945- Synthesisofarithmeticcircuits:FPGA,ASICandembeddedsystems/Jean-PierreDeschamps,Gery JeanAntoineBioul,GustavoD.Sutter. p.cm. ISBN-13 978-0471-68783-2(cloth) ISBN-10 0-471-68783-9(cloth) 1. Computerarithmeticandlogicunits. 2.Digitalelectronics. 3.Embeddedcomputersystems. I.Bioul,GeryJeanAntoine. II.Sutter,GustavoD. III.Title. TK7895.A65D472006 621.39’5--dc22 2005003237 PrintedintheUnitedStatesofAmerica 10 9 8 7 6 5 4 3 2 1 To Marc CONTENTS Preface xvii About theAuthors xix 1 Introduction 1 1.1 Number Representation, 1 1.2 Algorithms, 2 1.3 Hardware Platforms, 2 1.4 Hardware–Software Partitioning, 3 1.5 Software Generation, 3 1.6 Synthesis, 3 1.7 A First Example, 3 1.7.1 Specification, 3 1.7.2 Number Representation, 6 1.7.3 Algorithms, 6 1.7.4 Hardware Platform, 8 1.7.5 Hardware–SoftwarePartitioning, 8 1.7.6 Program Generation, 9 1.7.7 Synthesis, 10 1.7.8 Prototype, 12 1.8 Bibliography, 14 vii viii CONTENTS 2 MathematicalBackground 15 2.1 Number Theory, 15 2.1.1 Basic Definitions, 15 2.1.2 Euclidean Algorithms, 17 2.1.3 Congruences, 19 2.2 Algebra, 25 2.2.1 Groups, 25 2.2.2 Rings, 27 2.2.3 Fields, 27 2.2.4 Polynomial Rings, 27 2.2.5 Congruences ofPolynomial, 32 2.3 FunctionApproximation, 35 2.4 Bibliography, 36 3 Number Representation 39 3.1 Natural Numbers, 39 3.1.1 Weighted Systems, 39 3.1.2 Residue Number System, 42 3.2 Integers, 42 3.2.1 Sign-Magnitude Representation, 42 3.2.2 Excess-E Representation, 43 3.2.3 B’sComplement Representation, 44 3.2.4 Booth’s Encoding, 47 3.3 Real Numbers, 51 3.4 Bibliography, 54 4 Arithmetic Operations:Addition and Subtraction 55 4.1 Additionof Natural Numbers, 55 4.1.1 Basic Algorithm, 55 4.1.2 Faster Algorithms, 57 4.1.3 Long-OperandAddition, 66 4.1.4 MultioperandAddition, 67 4.1.5 Long-MultioperandAddition, 70 4.2 Subtraction of Natural Numbers, 71 4.3 Integers, 71 4.3.1 B’sComplement Addition, 71 4.3.2 B’sComplement Sign Change, 72 4.3.3 B’sComplement Subtraction, 74