Ata Elahi Computer Systems Digital Design, Fundamentals of Computer Architecture and Assembly Language Computer Systems Ata Elahi Computer Systems Digital Design, Fundamentals of Computer Architecture and Assembly Language AtaElahi SouthernConnecticutStateUniversity NewHaven,CT,USA ISBN978-3-319-66774-4 ISBN978-3-319-66775-1 (eBook) https://doi.org/10.1007/978-3-319-66775-1 LibraryofCongressControlNumber:2017952347 ©SpringerInternationalPublishingAG2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilarmethodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthis book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained hereinor for anyerrors oromissionsthat may havebeenmade. Thepublisher remainsneutralwith regardtojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland This book is dedicated to Sara, Shabnam and Aria Preface This textbook is the result of my experiences teaching computer systems at the Computer Science Department at Southern Connecticut State University since 1986. The book is divided into three sections: Digital Design, Introduction to Computer Architecture and Memory, and ARM Architecture and Assembly Lan- guage. The Digital Design section includes a laboratory manual with 12 experi- ments using Logisim software to enforce important concepts. The ARM ArchitectureandAssemblyLanguagesectionincludesseveralexamplesofassem- blylangaugeprogramsusingKeilμVision5developmenttools. Intended Audience This book is written primarily for a one semester course as an introduction to computer hardware and assembly language for students majoring in Computer Science,InformationSystemsandEngineeringTechnology. Organization Thematerialofthisbookispresentedinsuchawaythatnospecialbackgroundis requiredtounderstandthetopics. Chapter1–SignalsandNumberSystems:AnalogSignal,DigitalSignal,Binary Numbers, Addition and Subtraction of binary numbers, IEEE 754 Floating Point representations,ASCII,Unicode,SerialTransmission,andParallelTransmission. Chapter2–BooleanLogicsandLogicGates:BooleanLogics,BooleanAlgebra Theorems,LogicGates,IntegrateCircuit(IC),BooleanFunction,TruthTableofa functionandusingBooleanTheoremstosimplifyBooleanFunctions. vii viii Preface Chapter 3 – Minterms, Maxterms, Karnaugh Map (K-Map) and Universal Gates: Minterms, Maxterms, Karnaugh Map (K-Map) to simplify Boolean Func- tions,Don’tCareConditionsandUniversalGates. Chapter 4 – Combinational Logic: Analysis of Combination Logic, Design of Combinational Logic, Decoder, Encoder, Multiplexer, Half Adder, Full Adder, Binary Adder, Binary Subtractor, Designing Arithmetic Logic Unit (ALU) and BCDtoSevenSegmentDecoder. Chapter5–SynchronousSequentialLogic:SequentialLogicsuchasS-RLatch, D-Flip Flop, J-K Flip Flop, T-Flip Flop, Register, Shift Register, Analysis of Sequential Logic, State Diagram, State Table, Flip Flop Excitation Table and DesigningCounter. Chapter 6 – Introduction to Computer Architecture: Components of a Micro- computer,CPUTechnology,CPUArchitecture,InstructionExecution,Pipelining, PCI,PCIExpress,USB,andHDMI. Chapter 7 – Memory: Memory including RAM, SRAM, DISK, SSD, Memory Hierarchy, Cache Memory, Cache Memory Mapping Methods, Virtual Memory, PageTableandthememoryorganizationofacomputer. Chapter8–ARMArchitectureandInstructionsPartI:ARMProcessorArchi- tecture,andARMInstructionSetsuchasDataProcessing,Shift,Rotate,Uncondi- tionalInstructionsandConditionalInstructions,StackOperation,Branch,Multiply InstructionsandseveralexamplesofconvertingHLLtoAssemblylanguage. Chapter 9 – ARM Instructions Part II: This chapter is the continuation of Chapter 8 which covers Load and Store Instructions, Pseudo Instructions, ARM AddressingModeanddatarepresentationinmemory. Chapter10–ARMAssemblyLanguageProgrammingUsingKeilDevelopment Tools:CovershowtouseKeildevelopmentsoftwareforwritingassemblylanguage usingARMInstructions,CompilingAssemblyLanguageandDebugging. InstructionResources:Theinstructionresourcescontains • LaboratoryexperimentsusingLogisim. • Solutionstotheproblemsofeachchapter. NewHaven,CT,USA AtaElahi Acknowledgments I would like to express my special thanks to Professor Lancor Chairman of Computer Science Department at Southern Connecticut State University for her supportaswellasProfessorHervPodnarforhisguidance. IwishtoacknowledgeandthankMs.MaryE.James,SeniorEditorinApplied Sciencesandherassistant,Ms.ZoeKennedy,fortheirsupport. My special thanks to Marc Gajdosik, Nickolas Santini, Nicholas Bittar, Eric Basini,OmarAbidandAlirezaGhodsfortheirhelpindevelopingthemanuscript. Finally, I would like to thank the students of CSC 207 Computer Systems of Spring2017. ix Contents 1 SignalsandNumberSystems. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 AnalogSignals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 CharacteristicsofanAnalogSignal. . . . . . . . . . . . . . 3 1.3 DigitalSignals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 NumberSystem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.1 ConvertingfromBinarytoDecimal. . . . . . . . . . . . . 6 1.4.2 ConvertingfromDecimalIntegertoBinary. . . . . . . . 7 1.4.3 ConvertingDecimalFractiontoBinary. . . . . . . . . . . 8 1.4.4 ConvertingfromHextoBinary. . . . . . . . . . . . . . . . . 9 1.4.5 BinaryAddition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 ComplementandTwo’sComplement. . . . . . . . . . . . . . . . . . 11 1.5.1 SubtractionofUnsignedNumberUsingTwo’s Complement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Unsigned,SignedMagnitude,andSignedTwo’s ComplementBinaryNumber. . . . . . . . . . . . . . . . . . . . . . . . . 12 1.7 BinaryAdditionUsingSignedTwo’sComplement. . . . . . . . . 13 1.8 FloatingPointRepresentation. . . . . . . . . . . . . . . . . . . . . . . . 14 1.8.1 SinglePrecisionRepresentation. . . . . . . . . . . . . . . . 15 1.9 Binary-CodedDecimal(BCD). . . . . . . . . . . . . . . . . . . . . . . . 16 1.10 CodingSchemes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.10.1 ASCIICode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.10.2 UniversalCodeorUnicode. . . . . . . . . . . . . . . . . . . . 17 1.11 ParityBit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.12 Clock. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.13 TransmissionModes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.13.1 AsynchronousTransmission. . . . . . . . . . . . . . . . . . . 22 1.13.2 SynchronousTransmission. . . . . . . . . . . . . . . . . . . . 23 xi xii Contents 1.14 TransmissionMethods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.14.1 SerialTransmission. . . . . . . . . . . . . . . . . . . . . . . . . 24 1.14.2 ParallelTransmission. . . . . . . . . . . . . . . . . . . . . . . . 24 1.15 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2 BooleanLogicsandLogicGates. . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 BooleanLogicsandLogicGates. . . . . . . . . . . . . . . . . . . . . . 30 2.3 IntegratedCircuit(IC)Classifications. . . . . . . . . . . . . . . . . . 33 2.4 BooleanAlgebraTheorems. . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5 BooleanFunction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.6 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Minterms,Maxterms,KarnaughMap(K-Map), andUniversalGates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Minterms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3 Maxterms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.4 KarnaughMap(K-Map). . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.4.1 Three-VariableMap. . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.2 Four-VariableK-Map. . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 SumofProducts(SOP)andProductofSums(POS). . . . . . . . 58 3.6 Don’tCareConditions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7 UniversalGates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.7.1 UsingNANDGates. . . . . . . . . . . . . . . . . . . . . . . . . 62 3.7.2 UsingNORGates. . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.7.3 ImplementationofLogicFunctionsUsingNAND GatesorNORGatesOnly. . . . . . . . . . . . . . . . . . . . 64 3.7.4 UsingNANDGates. . . . . . . . . . . . . . . . . . . . . . . . . 64 3.7.5 UsingNORGates. . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.8 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4 CombinationalLogic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.2 AnalysisofCombinationalLogic. . . . . . . . . . . . . . . . . . . . . . 72 4.3 DesignofCombinationalLogic. . . . . . . . . . . . . . . . . . . . . . . 72 4.4 Decoder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.4.1 ImplementingaFunctionUsingaDecoder. . . . . . . . 76 4.5 Encoder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.6 Multiplexer(MUX). . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 77 4.6.1 DesigningLargeMultiplexerUsingSmaller Multiplexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.6.2 ImplementingFunctionsUsingMultiplexer. . . . . . . . 83 4.7 HalfAdder,FullAdder,BinaryAdder,andSubtractor. . . . . . 84 4.7.1 4-BitBinaryAdder. . . . . . . . . . . . . . . . . . . . . . . . . 87 4.7.2 Subtractor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88