December31,2012 09:16 vra80547_title Sheetnumber1 Pagenumberi magentablack Fundamentals of Digital Logic with Verilog Design THIRD EDITION Stephen Brown and Zvonko Vranesic DepartmentofElectricalandComputerEngineering UniversityofToronto January31,2013 11:41 vra80547_copy Sheetnumber1 Pagenumberii magentablack FUNDAMENTALSOFDIGITALLOGICWITHVERILOGDESIGN,THIRDEDITION PublishedbyMcGraw-Hill,abusinessunitofTheMcGraw-HillCompanies,Inc.,1221AvenueoftheAmericas, NewYork,NY10020.Copyright©2014byTheMcGraw-HillCompanies,Inc.Allrightsreserved.Nopartof thispublicationmaybereproducedordistributedinanyformorbyanymeans,orstoredinadatabaseor retrievalsystem,withoutthepriorwrittenconsentofTheMcGraw-HillCompanies,Inc.,including,butnot limitedto,inanynetworkorotherelectronicstorageortransmission,orbroadcastfordistancelearning. Someancillaries,includingelectronicandprintcomponents,maynotbeavailabletocustomersoutsidethe UnitedStates. Thisbookisprintedonacid-freepaper. 1234567890DOC/DOC109876543 ISBN978–0–07–338054–4 MHID0–07–338054–7 ManagingDirector:ThomasTimp Director:MichaelLange GlobalPublisher:RaghothamanSrinivasan DevelopmentalEditor:VincentBradshaw MarketingManager:CurtReynolds Director,ContentProduction:TerriSchiesl SeniorProjectManager:MelissaM.Leick Buyer:SusanK.Culbertson MediaProjectManager:PrashanthiNadipalli CoverDesign:StudioMontage,St.Louis,Missouri (USE)CoverImage:StevenBrownandZvonkoVranesic Compositor:Techsetters,Inc. Typeface:10/12TimesRoman Printer:R.R.Donnelley,Crawfordsville,IN LibraryofCongressCataloging-in-PublicationData Brown,Stephen. FundamentalsofdigitallogicwithVerilogdesign/StephenBrownandZvonkoVranesic.—Thirdedition. pagescm ISBN978–0–07–338054–4(alk.paper) 1.Logiccircuits—Designandconstruction—Dataprocessing. 2.Verilog(Computerhardware descriptionlanguage).3.Computer-aideddesign. I.Vranesic,ZvonkoG. II.Title. TK7868.L6B76 2014 621.39(cid:2)2–dc23 2012042163 www.mhhe.com December31,2012 09:15 vra80547_ded Sheetnumber1 Pagenumberiii magentablack ToSusanandAnne This page intentionally left blank December31,2012 09:08 vra80547_ata Sheetnumber1 Pagenumberv magentablack About the Authors StephenBrownreceivedhisB.A.Sc.degreeinElectricalEngineeringfromtheUniversity ofNewBrunswick,Canada,andtheM.A.Sc.andPh.D.degreesinElectricalEngineering fromtheUniversityofToronto. HejoinedtheUniversityofTorontofacultyin1992,where heisnowaProfessorintheDepartmentofElectrical&ComputerEngineering. Heisalso theDirectoroftheworldwideUniversityProgramatAlteraCorporation. Hisresearchinterestsincludefield-programmableVLSItechnologyandcomputerar- chitecture. He won the Canadian Natural Sciences and Engineering Research Council’s 1992DoctoralPrizeforthebestPh.D.thesisinCanadaandhaspublishedmorethan100 scientificresearchpapers. He has won five awards for excellence in teaching electrical engineering, computer engineering,andcomputersciencecourses. Heisacoauthoroftwootherbooks: Funda- mentalsofDigitalLogicwithVHDLDesign,3rded.andField-ProgrammableGateArrays. ZvonkoVranesicreceivedhisB.A.Sc.,M.A.Sc.,andPh.D.degrees,allinElectricalEngi- neering,fromtheUniversityofToronto. From1963–1965heworkedasadesignengineer with the Northern Electric Co. Ltd. in Bramalea, Ontario. In 1968 he joined the Univer- sityofToronto,whereheisnowaProfessorEmeritusintheDepartmentsofElectrical& ComputerEngineeringandComputerScience. Duringthe1978–1979academicyear,he wasaSeniorVisitorattheUniversityofCambridge, England, andduring1984–1985he was at the University of Paris, 6. From 1995 to 2000 he served as Chair of the Division ofEngineeringScienceattheUniversityofToronto. Heisalsoinvolvedinresearchand developmentattheAlteraTorontoTechnologyCenter. His current research interests include computer architecture and field-programmable VLSItechnology. Heisacoauthoroffourotherbooks: ComputerOrganizationandEmbeddedSystems, 6thed.;FundamentalsofDigitalLogicwithVHDLDesign,3rded.;MicrocomputerStruc- tures;andField-ProgrammableGateArrays. In1990,hereceivedtheWightonFellowship for“innovativeanddistinctivecontributionstoundergraduatelaboratoryinstruction.” In 2004, he received the Faculty TeachingAward from the Faculty ofApplied Science and EngineeringattheUniversityofToronto. He has represented Canada in numerous chess competitions. He holds the title of InternationalMaster. v December31,2012 09:15 vra80547_preface Sheetnumber1 Pagenumbervi magentablack Preface This book is intended for an introductory course in digital logic design, which is a basic course in most electrical and computer engineering programs. Asuccessful designer of digitallogiccircuitsneedsagoodunderstandingofbasicconceptsandafirmgraspofthe moderndesignapproachthatreliesoncomputer-aideddesign(CAD)tools. The main goals of the book are (1) to teach students the fundamental concepts in classical manual digital design and (2) illustrate clearly the way in which digital circuits aredesignedtoday,usingCADtools. Eventhoughmoderndesignersnolongerusemanual techniques, except in rare circumstances, our motivation for teaching such techniques is to give students an intuitive feeling for how digital circuits operate. Also, the manual techniquesprovideanillustrationofthetypesofmanipulationsperformedbyCADtools, givingstudentsanappreciationofthebenefitsprovidedbydesignautomation. Throughout the book, basic concepts are introduced by way of examples that involve simple circuit designs, which we perform using both manual techniques and modern CAD-tool-based methods. Havingestablishedthebasicconcepts,morecomplexexamplesarethenprovided, using the CAD tools. Thus our emphasis is on modern design methodology to illustrate howdigitaldesigniscarriedoutinpracticetoday. Technology Thebookdiscussesmoderndigitalcircuitimplementationtechnologies. Theemphasisison programmablelogicdevices(PLDs),whichisthemostappropriatetechnologyforuseina textbookfortworeasons. First,PLDsarewidelyusedinpracticeandaresuitableforalmost alltypesofdigitalcircuitdesigns. Infact,studentsaremorelikelytobeinvolvedinPLD- baseddesignsatsomepointintheircareersthaninanyothertechnology. Second,circuits areimplementedinPLDsbyend-userprogramming. Therefore,studentscanbeprovided with an opportunity, in a laboratory setting, to implement the book’s design examples in actualchips. Studentscanalsosimulatethebehavioroftheirdesignedcircuitsontheirown computers. WeusethetwomostpopulartypesofPLDsfortargetingofdesigns: complex programmablelogicdevices(CPLDs)andfield-programmablegatearrays(FPGAs). Weemphasizetheuseofahardwaredescriptionlanguageinspecifyingthelogiccir- cuits,becausetheHDL-basedapproachisthemostefficientdesignmethodtouseinpractice. We describe in detail the IEEE StandardVerilog HDLlanguage and use it extensively in examples. vi December31,2012 09:15 vra80547_preface Sheetnumber2 Pagenumbervii magentablack Preface vii ScopeoftheBook Thiseditionofthebookhasbeenextensivelyrestructured. Allofthematerialthatshould becoveredinaone-semestercourseisnowincludedinChapters1to6. Moreadvanced materialispresentedinChapters7to11. Chapter1providesageneralintroductiontotheprocessofdesigningdigitalsystems. ItdiscussesthekeystepsinthedesignprocessandexplainshowCADtoolscanbeused to automate many of the required tasks. It also introduces the representation of digital information. Chapter 2 introduces the logic circuits. It shows how Boolean algebra is used to representsuchcircuits. Itintroducestheconceptsoflogiccircuitsynthesisandoptimization, andshowshowlogicgatesareusedtoimplementsimplecircuits. Italsogivesthereader a first glimpse atVerilog, as an example of a hardware description language that may be usedtospecifythelogiccircuits. Chapter3concentratesoncircuitsthatperformarithmeticoperations. Itdiscussesnum- bersandshowshowtheycanbemanipulatedusinglogiccircuits. Thischapterillustrates howVerilogcanbeusedtospecifythedesiredfunctionalityandhowCADtoolsprovidea mechanismfordevelopingtherequiredcircuits. Chapter4presentscombinationalcircuitsthatareusedasbuildingblocks. Itincludes the encoder, decoder, and multiplexer circuits. These circuits are very convenient for illustratingtheapplicationofmanyVerilogconstructs,givingthereaderanopportunityto discovermoreadvancedfeaturesofVerilog. StorageelementsareintroducedinChapter5. Theuseofflip-flopstorealizeregular structures, suchasshiftregistersandcounters, isdiscussed. Verilog-specifieddesignsof thesestructuresareincluded. Chapter6givesadetailedpresentationofsynchronoussequentialcircuits(finitestate machines). It explains the behavior of these circuits and develops practical design tech- niquesforbothmanualandautomateddesign. Chapter7isadiscussionofanumberofpracticalissuesthatariseinthedesignofreal systems. Ithighlightsproblemsoftenencounteredinpracticeandindicateshowtheycan be overcome. Examples of larger circuits illustrate a hierarchical approach in designing digitalsystems. CompleteVerilogcodeforthesecircuitsispresented. Chapter8dealswithmoreadvancedtechniquesforoptimizedimplementationoflogic functions. Itpresentsalgorithmictechniquesforoptimization. Italsoexplainshowlogic functionscanbespecifiedusingacubicalrepresentationaswellasusingbinarydecision diagrams. AsynchronoussequentialcircuitsarediscussedinChapter9. Whilethistreatmentis not exhaustive, it provides a good indication of the main characteristics of such circuits. Even though the asynchronous circuits are not used extensively in practice, they provide anexcellentvehicleforgainingadeeperunderstandingoftheoperationofdigitalcircuits ingeneral. Theyillustratetheconsequencesofpropagationdelaysandraceconditionsthat maybeinherentinthestructureofacircuit. Chapter10presentsacompleteCADflowthatthedesignerexperienceswhendesign- ing,implementing,andtestingadigitalcircuit. December31,2012 09:15 vra80547_preface Sheetnumber3 Pagenumberviii magentablack viii Preface Chapter11introducesthetopicoftesting. Adesigneroflogiccircuitshastobeaware oftheneedtotestcircuitsandshouldbeconversantwithatleastthemostbasicaspectsof testing. AppendixAprovidesacompletesummaryofVerilogfeatures.AlthoughuseofVerilog is integrated throughout the book, this appendix provides a convenient reference that the readercanconsultfromtimetotimewhenwritingVerilogcode. TheelectronicaspectsofdigitalcircuitsarepresentedinAppendixB.Thisappendix showshowthebasicgatesarebuiltusingtransistorsandpresentsvariousfactorsthataffect circuitperformance. Theemphasisisonthelatesttechnologies, withparticularfocuson CMOStechnologyandprogrammablelogicdevices. WhatCanBeCoveredinaCourse Muchofthematerialinthebookcanbecoveredin2one-quartercourses.Agoodcoverage of the most important material can be achieved in a single one-semester, or even a one- quartercourse. Thisispossibleonlyiftheinstructordoesnotspendtoomuchtimeteaching the intricacies ofVerilog and CAD tools. To make this approach possible, we organized theVerilogmaterialinamodularstylethatisconducivetoself-study. Ourexperiencein teachingdifferentclassesofstudentsattheUniversityofTorontoshowsthattheinstructor mayspendonlythreetofourlecturehoursonVerilog,describinghowthecodeshouldbe structured,includingtheuseofdesignhierarchy,usingscalarandvectorvariables,andon thestyleofcodeneededtospecifysequentialcircuits. TheVerilogexamplesgiveninthe bookarelargelyself-explanatory,andstudentscanunderstandthemeasily. Thebookisalsosuitableforacourseinlogicdesignthatdoesnotincludeexposureto Verilog. However, someknowledgeofVerilog, evenatarudimentarylevel, isbeneficial tothestudents,anditisagreatpreparationforajobasadesignengineer. One-SemesterCourse Thefollowingmaterialshouldbecoveredinlectures: • Chapter1—allsections. • Chapter2—allsections. • Chapter3—Sections3.1to3.5. • Chapter4—allsections. • Chapter5—allsections. • Chapter6—allsections. One-QuarterCourse Inaone-quartercoursethefollowingmaterialcanbecovered: • Chapter1—allsections. • Chapter2—allsections. December31,2012 09:15 vra80547_preface Sheetnumber4 Pagenumberix magentablack Preface ix • Chapter3—Sections3.1to3.3andSection3.5. • Chapter4—allsections. • Chapter5—allsections. • Chapter6—Sections6.1to6.4. Verilog Verilogisacomplexlanguage,whichsomeinstructorsfeelistoohardforbeginningstudents tograsp. Wefullyappreciatethisissueandhaveattemptedtosolveit. Itisnotnecessary to introduce the entire Verilog language. In the book we present the important Verilog constructsthatareusefulforthedesignandsynthesisoflogiccircuits. Manyotherlanguage constructs,suchasthosethathavemeaningonlywhenusingthelanguageforsimulation purposes,areomitted. TheVerilogmaterialisintroducedgradually,withmoreadvanced featuresbeingpresentedonlyatpointswheretheirusecanbedemonstratedinthedesign ofrelevantcircuits. Thebookincludesmorethan120examplesofVerilogcode. Theseexamplesillustrate howVerilogisusedtodescribeawiderangeoflogiccircuits,fromthosethatcontainonly afewgatestothosethatrepresentdigitalsystemssuchasasimpleprocessor. AlloftheexamplesofVerilogcodepresentedinthebookareprovidedontheAuthors’ websiteat www.eecg.toronto.edu/∼brown/Verilog_3e SolvedProblems The chapters include examples of solved problems. They show how typical homework problemsmaybesolved. HomeworkProblems Morethan400homeworkproblemsareprovidedinthebook.Answerstoselectedproblems aregivenatthebackofthebook. Solutionstoallproblemsareavailabletoinstructorsin theSolutionsManualthataccompaniesthebook. PowerPointSlidesandSolutionsManual PowerPointslidesthatcontainallofthefiguresinthebookareavailableontheAuthors’ website. Instructors can request access to these slides, as well as access to the Solutions Manualforthebook,at: www.mhhe.com/brownvranesic